Search found 130 matches

by jj
Sat Aug 11, 2018 11:52
Forum: Draughts, Computer, Internet
Topic: Complexity of Checkers and Draughts on board sizes 6x6/8x8/10x10/12x12/14x14
Replies: 11
Views: 6116

Re: Complexity of Checkers and Draughts on board sizes 6x6/8x8/10x10/12x12/14x14

I changed the table data type from 64-bit integer to BigInteger, and new results are: 12x12 5732895173614141678179591577998733384657257103359 = 5.7 x 10^48 14x14 7717880162220474034203925206374892518645244798128637950441522462719 = 7.7 x 10^66 My new Python program can now reproduce this on all dig...
by jj
Sun Jul 01, 2018 11:53
Forum: Draughts, Computer, Internet
Topic: Complexity of Checkers and Draughts on board sizes 6x6/8x8/10x10/12x12/14x14
Replies: 11
Views: 6116

Re: Complexity of Checkers and Draughts on board sizes 6x6/8x8/10x10/12x12/14x14

From the thread 'Breakthrough Draughts', http://laatste.info/bb3/viewtopic.php?f=53&t=7805. Game SSC % of all Max.Depth Time Nodes/sec 6x6 checkers 27,364,174,047 21.4% 407,888 14:07:29 538,146 6x6 draughts 10,075,772,480 7.9% 123,536 5:33:57 502,858 If you use breadth-first-search on this tree, you...
by jj
Mon May 14, 2018 15:27
Forum: Draughts, Computer, Internet
Topic: AlphaZero-style Breakthrough program
Replies: 10
Views: 2173

Re: AlphaZero-style Breakthrough program

Fabien, are you using CNNs for chess now? No, my experience comes from working With Rémi Coulom on Crazy Stone two years ago. Even if I wanted to use them in chess, it wouldn't be realistic because of the huge computing-power requirement. Leela-Chess Zero (LC0) needs hundreds of people donating com...
by jj
Thu May 10, 2018 13:18
Forum: Draughts, Computer, Internet
Topic: AlphaZero-style Breakthrough program
Replies: 10
Views: 2173

Re: AlphaZero-style Breakthrough program

Interesting. However, what sets draughts (& checkers) apart from the mentioned games are the two rules 1) capturing is compulsory and 2) capturing multiple pieces in one move. This facilitates deep combinations (shots) and forcings, which in my view poses a problem to the underlying MCTS-ish search...
by jj
Wed May 09, 2018 12:06
Forum: Draughts, Computer, Internet
Topic: AlphaZero-style Breakthrough program
Replies: 10
Views: 2173

Re: AlphaZero-style Breakthrough program

... In any case, the message for anybody interested in the A0 approach is that it should work in all games, and apart from the hardest ones (Go, chess, Shogi) you don't need to be a millionaire to run the training part. Interesting. However, what sets draughts (& checkers) apart from the mentioned ...
by jj
Wed Feb 28, 2018 17:38
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

Basically you continue running test until low == upp and the best move is a move which assures low value. I see, so that part is equivalent to my solution (never use a fail-low value to select a move). In textbook MTD(f) you can also have low > upp because of search inconsistencies. Does your imple...
by jj
Wed Feb 28, 2018 16:14
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

So how do you select the best move if the last pass fails low? Or do you re-search until you get a fail high again? In this scenario after having run rootMT(root, moves, g(k-2),d) I obtained low = g(k-2) and upp = +INF then after having run rootMT(root, moves, g(k-1), d) I obtained low = g(k-2) and...
by jj
Wed Feb 28, 2018 13:50
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

Yes, you can have variations on MTD(f) like bisection or increasing/decreasing the step size. I wanted to show what can happen in the basic case. Yes you can implement MTD(f) in various manner and my point was only to show it is quite easy to avoid any inconsistency. Let's take the basis case you e...
by jj
Wed Feb 28, 2018 11:08
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

Let me try to explain how I excluded any inconsistency for this problem. First of all I consider pruning, extension and TT are essential in order to have a powerful MTD(f) algorithm. In addition clearing TT is a non-sense because you lost very valuable information. The solution I found is the follo...
by jj
Tue Feb 27, 2018 20:26
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

Theoritically it is wasteful but only when kings are present in each side because with no kings on the board it is of course possible but very improbable to reach a position with two paths with different depths. Yes, but there is also the issue of the present TT content. Clearing the TT takes time ...
by jj
Tue Feb 27, 2018 18:21
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

I am not sure I fully understand your point but when you say: "The second time we encounter position p (via a different path) we may need depth d' < d. If the TT entry is present we use it (d >= d')" you clearly use a "hidden" extension because instead of using depth d' you use the result of depth ...
by jj
Tue Feb 27, 2018 16:42
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

Hi Jan, In the past I used MTD(f) for long years and seeing how I implemented the algorithm I cannot have inconsistencies. Anyway I tried to understand your point and my very first comment is the following: Why do you say that inconsistencies appear as a result of using a transposition table? In my...
by jj
Mon Feb 26, 2018 19:16
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Re: Handling search inconsistencies in MTD(f)

Can you send me a pm? We can always see what is worth sharing.
by jj
Mon Feb 26, 2018 17:10
Forum: Draughts, Computer, Internet
Topic: Handling search inconsistencies in MTD(f)
Replies: 16
Views: 2712

Handling search inconsistencies in MTD(f)

I was wondering if people using MTD(f) are aware of what happens when there are search inconsistencies (as a result of using a transposition table) and how to deal with these situations. I wrote a paper on the subject: http://www.maximusdraughts.org/research/Handling%20Search%20Inconsistencies%20in%...
by jj
Sat Sep 02, 2017 16:49
Forum: Draughts, Computer, Internet
Topic: Complexity of Checkers and Draughts on board sizes 6x6/8x8/10x10/12x12/14x14
Replies: 11
Views: 6116

Re: Complexity of Checkers and Draughts on board sizes 6x6/8x8/10x10/12x12/14x14

Applying this formula on the 5 board formats, we obtain (for 1 color to move): Board size SSC <= 6x6 63838220543 = 6.4 x 10^10 8x8 500995484682338672639 = 5.0 x 10^20 [1] 10x10 2301985676687843186738387267616767 = 2.3 x 10^33 12x12 5732895173337388545809530684864049716501476802559 = 5.7 x 10^48 14x...