Search Algorithm
-
- Posts: 1704
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re: Search Algorithm
I think that the game result depend on the rules, in particular the king range. For what it's worth, about 6 years ago, I did some computations on the 6x6 board for all game variants. The results have not been published before, but I shared them with Ed in private communication (October 19, 2011).Fabien Letouzey wrote:No.BertTuyt wrote:And last but not least, do you already have a gut feel whether this is (with perfect play) a white or black win?
We already know that white wins in 8x8 (with checkers capture rules anyway), so that is a strong indication. On the other hand, I put Draughts into the "blocking game" category (with Othello) so it's also possible that white has to self-destruct first.
These results should be taken with some disclaimer because of the Graph-History Interaction. With current technology, these 6x6 games could also be strongly solved (i.e. the opening position fits within the endgame databases). Also, I didn't compute the breakthrough results.============
I have weakly solved all 6x6 draughts and checkers variants, both the regular game and the suicide (AKA giveaway, misere or qui-perd-gagne) variety. This was a neglected corner of the solving small games literature http://en.wikipedia.org/wiki/Solved_game
The method used was a simple alpha-beta search (pvs and iterative deepening enhancements). No endgame databases were used. The games are therefore not strongly solved because there could conceivably be endgames which take more than reasonable resources to be resolved by forward search only. Strongly solving all these games (i.e. building the complete 12-piece databases) is also well within current technology (somewhat less than the 7-piece databases for the 10x10 game).
Compared to the Chinook project of solving 8x8 checkers (2007), Martin Fierz's probable draw solution for 8x8 suicide checkers (2010), and the recent announcement of the white win in 8x8 Russian suicide by Osipov and Morozev (2011), this was a nano-step for mankind. The searches took less than 15 minutes each on a 3.2 Ghz P4 with 1Gb of hash tables. The number of nodes are less than 1e9 per solution, somewhat in between solving 5x5 Amazons and 6x6 Othello.
Below are the results (W59 means white wins in 59 plies, L28 means white loses in 28 plies etc.). For a detailed description of the different rules, see the perft thread on this forum or the excellent website http://www.mindsports.nl/index.php/on-t ... s-variants
Interestingly, the results for 6x6 Russian suicide (white win) and 6x6 checkers suicide (draw) match the results for the 8x8 board. Also notable is that only the games with short ranged kings have drawn suicide games.Code: Select all
Variant Regular Suicide ------------------------------- International DRAW W36 Killer W59 W36 Frisian L28 L27 Pool DRAW W34 Russian DRAW W34 Thai DRAW W38 Czech DRAW W32 Spanish DRAW W32 Italian DRAW DRAW Checkers DRAW DRAW
The drawn games in the table above are not 100% guaranteed because my search does not take care of Graph-History-Interaction. On the other hand, the search engine (a series of C++ templates) was extensively unit-tested on the 4-piece databases for International and Killer draughts, without encountering any discrepancies between the forward search and the database results (with forward searches of up to 77 plies). Nevertheless, any confirmation would be welcome!
In any case, assuming correctness, note that Killer and Frisian are the only decided games on a 6x6 board, and with give-away, only the short-ranged king games (Italian and Checkers) are a draw. The Russian give-away game has also been solved to be a white win on a 8x8 game board (can't find the link anymore), most likely with far less resources than was required to proof 8x8 checkers to be a draw.
-
- Posts: 1704
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re: Search Algorithm
The Russian version of Wikipedia on give-away draughts has a section on strategy (use Google Translate).Fabien Letouzey wrote: Ah, I see. Well in general, mobility is still important in "losing games", so blindly giving away material is not recommended. But it makes your point clear now: we don't know what to put in evaluation, but learning probably will; better than our guesses anyway.
Yes, I read about it, but haven't studied in detail. 200-300 core years sounds like serious resources, more than a single man effort could doMark Watkins solved losing chess last year; white wins with 1. e3. A few black responses took a long time to refute. PDF at http://magma.maths.usyd.edu.au/~watkins ... GA2016.pdf
It's relevant because captures are mandatory and the king loses its special status, making this variant "draughts-like".

Re: Search Algorithm
Herewith the results for the PST based search (without the 22 - 20 match).
The results of the 4 different eval tests are summarized in below graph.
The PST Match is represented with the yellow line.
Basically match results are as expected.
Also here the initial model doesn't seem to hold, as the exponent seems to be related to eval strength.
I will today not focus on the 22-20 PST match, but run some tests with PST against the full eval.
Bert
The results of the 4 different eval tests are summarized in below graph.
The PST Match is represented with the yellow line.
Basically match results are as expected.
Also here the initial model doesn't seem to hold, as the exponent seems to be related to eval strength.
I will today not focus on the 22-20 PST match, but run some tests with PST against the full eval.
Bert
Re: Search Algorithm
I have now some results for the Scan - Scan match, where 1 player has a FULL eval, and the other a PST and 2 ply search more.
As expected the FULL eval wins easily.
I did not complete the 22-20 match due to a restart during the night, but think 154 games would be sufficient.
Below results.
Bert
As expected the FULL eval wins easily.
I did not complete the 22-20 match due to a restart during the night, but think 154 games would be sufficient.
Below results.
Bert
Re: Search Algorithm
Started a match between 2 identical versions of Scan (24 ply search and 22 ply search).
This time on my faster computer (so 8 core 4 GHz).
The 24 ply games take around 20-25 minutes per game, so very much comparable with standard tournament settings.
Match still running, will be finalised tomorrow ( = Tuesday), but after 116 games, the first win for the deeper search (24 ply) version (and 115 draws).
This translates ( so far) in a 3 Elo rating difference.....
Guess this is the future of Computer Draughts (comparable with the checkers matches these days most likely).
Bert
This time on my faster computer (so 8 core 4 GHz).
The 24 ply games take around 20-25 minutes per game, so very much comparable with standard tournament settings.
Match still running, will be finalised tomorrow ( = Tuesday), but after 116 games, the first win for the deeper search (24 ply) version (and 115 draws).
This translates ( so far) in a 3 Elo rating difference.....
Guess this is the future of Computer Draughts (comparable with the checkers matches these days most likely).
Bert
Re: Search Algorithm
The match (24 ply Scan against 22 ply Scan) ended with 157 draws and 1 win for the 24 ply search.
See below the update table and graph. So it becomes clear that we need more knowlegde (as Fabien already predicted) to really further (significant) improve Draughts Engines.
Increasing the search depth will only further increase ELO rating in a limited way (as the matches indicate).
Also not sure if we can predict how far we are from perfect play.
If we can translate this trend towards perfect play (based upon these results), and assume that we maintain a constant increase of 2 - 5 ELO point till ply 64 (just an arbitrary number, and not in line with exponential decrease), than there are still (best case) (64-24)/2 = 20 times 2 - 5 points to gain, so resulting in 40 - 100 points.
Bert
See below the update table and graph. So it becomes clear that we need more knowlegde (as Fabien already predicted) to really further (significant) improve Draughts Engines.
Increasing the search depth will only further increase ELO rating in a limited way (as the matches indicate).
Also not sure if we can predict how far we are from perfect play.
If we can translate this trend towards perfect play (based upon these results), and assume that we maintain a constant increase of 2 - 5 ELO point till ply 64 (just an arbitrary number, and not in line with exponential decrease), than there are still (best case) (64-24)/2 = 20 times 2 - 5 points to gain, so resulting in 40 - 100 points.
Bert
Re: Search Algorithm
It all seems to go to draw and perfection pretty fast at this level.
Maybe it is time for everyone to switch to breakthrough-draughts
Surely there is room for competition there.
I'll do some independent test, but that needs to wait a couple of weeks for my computer is working out some new algorithmic ideas.
Michel
Maybe it is time for everyone to switch to breakthrough-draughts

I'll do some independent test, but that needs to wait a couple of weeks for my computer is working out some new algorithmic ideas.
Michel
-
- Posts: 299
- Joined: Tue Jul 07, 2015 07:48
- Real name: Fabien Letouzey
Re: Search Algorithm
Hi Michel,
There is one aspect in Bert's experiments that is worrying me, however: the better the eval, the worse the diminishing returns. This seems to suggest that if we improve evaluation, search won't matter anymore.
Better hurry before Bert solves it on his computing monster, though.
Speaking of breakthrough. I've just computed an evaluation for this variant, and it's better than the generic one. Presumably it focuses on emulating a breakthrough table. I have no idea whether midgame strategy is actually different; I hope not.
I was comparing two evaluations, and did this with two different time controls: game in 1s and game in 4s. Both tests gave the same result. So this reinforces your theory that wilo remains constant with increasing depth/time. Furthermore, without draws, wilo = Elo so the unit is meaningful (and hopefully additive).
I also expect Killer draughts to stay interesting for a few years, but there's little doubt that it's going to follow the same fate eventually ... In both variants, I feel that there is a better balance between search and evaluation. In that context, working on search still makes sense.
Fabien.
It looks scary, but that's self-play. There is also the remote possibility that I prune too much with increasing depth, making "late plies" weaker and weaker. I only test using fast games.MichelG wrote:It all seems to go to draw and perfection pretty fast at this level
There is one aspect in Bert's experiments that is worrying me, however: the better the eval, the worse the diminishing returns. This seems to suggest that if we improve evaluation, search won't matter anymore.
Exactly! Who needs kings anyway?Maybe it is time for everyone to switch to breakthrough-draughtsSurely there is room for competition there.

Speaking of breakthrough. I've just computed an evaluation for this variant, and it's better than the generic one. Presumably it focuses on emulating a breakthrough table. I have no idea whether midgame strategy is actually different; I hope not.
I was comparing two evaluations, and did this with two different time controls: game in 1s and game in 4s. Both tests gave the same result. So this reinforces your theory that wilo remains constant with increasing depth/time. Furthermore, without draws, wilo = Elo so the unit is meaningful (and hopefully additive).
I also expect Killer draughts to stay interesting for a few years, but there's little doubt that it's going to follow the same fate eventually ... In both variants, I feel that there is a better balance between search and evaluation. In that context, working on search still makes sense.
Fabien.
-
- Posts: 19
- Joined: Mon Oct 17, 2016 09:05
- Real name: Robin Messemer
Re: Search Algorithm
Hey,
Do you use aspiration windows in your draughts engine ? Is it worth implementing ? What I have read so far about aspiration windows is that it does help quite a bit when most evaluations only differ slightly (At least in chess engines it does help). I thought this might help in the endgame when my engine hits the endgame tablebase.
Would like to know what you guys think
Do you use aspiration windows in your draughts engine ? Is it worth implementing ? What I have read so far about aspiration windows is that it does help quite a bit when most evaluations only differ slightly (At least in chess engines it does help). I thought this might help in the endgame when my engine hits the endgame tablebase.
Would like to know what you guys think
Re: Search Algorithm
Yes several Draughts programs use an aspiration window.
Bert
Bert
-
- Posts: 19
- Joined: Mon Oct 17, 2016 09:05
- Real name: Robin Messemer
Re: Search Algorithm
Thats cool. May I ask how wide your window is ? I implemented aspiration Windows now and started with a very large window but I haven`t had the time to test it yet.BertTuyt wrote:Yes several Draughts programs use an aspiration window.
Bert
Robin
-
- Posts: 299
- Joined: Tue Jul 07, 2015 07:48
- Real name: Fabien Letouzey
Re: Search Algorithm
There is a discussion about Wilo on the chess forum: http://www.talkchess.com/forum/viewtopi ... _view=flat
It seems to have all the good properties that we hoped.
Fabien.
It seems to have all the good properties that we hoped.
Fabien.
-
- Posts: 19
- Joined: Mon Oct 17, 2016 09:05
- Real name: Robin Messemer
Re: Search Algorithm
Hey,
are most engines using some version of YBW (Young brothers waint concept) for parallel search ? I tried lazy smp which seems to be quite popular among the chess engine scene nowadays. However, the speedup wasn`t much at all which means that I either implemented it incorrectly or lazy smp might not work very well in Checkers/Draughts.
Would like to know what your parallel search is based on and where I could find a paper about YBW or PseudoCode.
are most engines using some version of YBW (Young brothers waint concept) for parallel search ? I tried lazy smp which seems to be quite popular among the chess engine scene nowadays. However, the speedup wasn`t much at all which means that I either implemented it incorrectly or lazy smp might not work very well in Checkers/Draughts.
Would like to know what your parallel search is based on and where I could find a paper about YBW or PseudoCode.
Re: Search Algorithm
Sorry i forgot to answer this question.
In my case the parallel search is based upon YBWC, and my inspiration was Stockfish.
I don't have a paper, but browsing through he Stockfish source code is quite self explaining.
Bert
In my case the parallel search is based upon YBWC, and my inspiration was Stockfish.
I don't have a paper, but browsing through he Stockfish source code is quite self explaining.
Bert