Search Algorithm

[Rein Halbersma]

And last but not least, do you already have a gut feel whether this is (with perfect play) a white or black win?

No.

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.

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).

============

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

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

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.

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!

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.

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.

[Rein Halbersma]

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.

The Russian version of Wikipedia on give-away draughts has a section on strategy (use Google Translate).

Mark 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".

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 do

[BertTuyt]

Herewith the results for the PST based search (without the 22 - 20 match).

Table Scan Deep Search DE2.png (10.85 KiB) Viewed 6986 times

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.

Scan Deep Analysis DE2.png (57.52 KiB) Viewed 6986 times

I will today not focus on the 22-20 PST match, but run some tests with PST against the full eval.

Bert

[BertTuyt]

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.

Scan Deep Analysis FPST.png (27.61 KiB) Viewed 6797 times

Table Scan Deep Search FPST.png (11.38 KiB) Viewed 6797 times

Bert

[BertTuyt]

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

[BertTuyt]

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.

SDA Table.png (10.41 KiB) Viewed 6684 times

SDA Graph.png (29.19 KiB) Viewed 6684 times

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

[MichelG]

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

[Fabien Letouzey]

Hi Michel,

It all seems to go to draw and perfection pretty fast at this level

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.

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.

Maybe it is time for everyone to switch to breakthrough-draughts Surely there is room for competition there.

Exactly! Who needs kings anyway? 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.

[CheckersGuy]

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

[BertTuyt]

Yes several Draughts programs use an aspiration window.

Bert

[CheckersGuy]

Yes several Draughts programs use an aspiration window.

Bert

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.


Robin

[Fabien Letouzey]

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.

[CheckersGuy]

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.

[BertTuyt]

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