Search Algorithm

[Fabien Letouzey]

Hi Rein,

There are 4 variants that I can think of:

1) Killer draughts
2) Frisian draughts (orthogonal captures, and a few extra details)
3) Give-away draughts
4) Breakthrough draughts (aka Kingscourt, named by Martin Fierz)

Martin Fierz's blog has a story how he solved 4) and found 3) already very difficult to program well. His give-away program lost against a Russian program (in Russia, give-away is an often played variant for humans as well). I would expects patterns to pay off really well in this game.

1) Killer draughts

I didn't intend to stray too far away from the spirit of the main variant. The line I'm looking at, normal -> Killer -> Breakthrough, has the advantage of progressively reducing the draw rate while hopefully keeping the strategy elements of the game.

For Killer draughts I now have data that confirms this. I can learn evaluation weights using Killer-draught games and use them in normal draughts; the level is the same as a more taylored eval, at least with logistic regression; this wasn't the case in 2015. I divide the score by 2 because they intuitively go up too quickly for the main variant: 2 for a man and 6-7 for a king, but positional scores are probably higher too. Technically this only affects ProbCut, though; the rest of search is mainly concerned with comparing scores.

These variants also required very few changes in my code: 2 lines for Killer draughts and about 10 for Breakthrough (not counting code for handling the presence of variants).


2) Frisian draughts

I had interest in Frisian draughts in 2015. During the man-machine match the same year, a proponent of the game even had leaflets in English; kudos to him! Unfortunately I was unable to understand the capturing rules on my way back (...); something about a king being worth "between one and two men" for captures. It looked ambiguous to me, and I couldn't translate it to maths (other than picking 1.5 at random). However I'm looking for information again and it looks much clearer in two stages:
- majority rule
- "king majority" as a secondary rule
If only I had seen that in 2015 ...

Other rules of Frisian draughts are a show stopper, though. I was only considering othogonal captures, with the smaller draw rate as a bonus. At most 3 moves by a wolf/king (as I recall) will destroy the best-designed endgame table builder in no time. Nonetheless apparently an old game with a lot of tradition; interesting that it's still played.

For evaluation, my only thought was that 4x4 patterns might not be enough for top-level performance: line of 3 squares don't fit anywere. So maybe 5x5 patterns (13 squares), which are difficult to learn => probably not worth the effort. Regardless of eval quality, I don't expect humans to resist the tactical precision of programs however.


3) Give-away draughts

I haven't considered that variant. Already the concept of material-only search breaks down (guess), so I would have to start with a manual eval that plays decently. Or fully-random games, pure-MC style. I doubt that the strategy would be relevant in any other variant, but am confident that the usual techniques would do well: endgame tables -> generating games -> learning patterns -> tuning pruning -> opening book. There is order in this chaos.

I'm not sure why you're expecting pattern evaluation to be especially adapted to this variant. Maybe you're referring to the fact that they (more or less) automate feature construction like neural networks. In my view, patterns should do well in all draughts variants. They might collapse on very large boards if long-distance strategy is important (as in Go).


4) Breakthrough draughts

I only knew about Martin's main page: http://www.fierz.ch/, so his blog is new to me: http://checker-board.blogspot.fr

He mentions months of computation before solving the variant on 8x8. This seems to confirm my intuition that the game is not solvable in 10x10, at least with our usual means.


Fabien.

[BertTuyt]

Fabien, just out of curiosity.
What in breakthrough Draughts, is the score for the Woldouby position?

Bert

[Fabien Letouzey]

Fabien, just out of curiosity.
What in breakthrough Draughts, is the score for the Woldouby position?

It's a loss in both Killer and Breakthrough.

[BertTuyt]

Fabien thanks, and this was with 6P or 7P DBs (in normal Draughts the 8P is required to find the draw result).

in general at which move do you already see the theoretical final scores in breakthrough Draughts?
And last but not least, do you already have a gut feel whether this is (with perfect play) a white or black win?

Bert

[Rein Halbersma]

For Killer draughts I now have data that confirms this. I can learn evaluation weights using Killer-draught games and use them in normal draughts; the level is the same as a more taylored eval, at least with logistic regression; this wasn't the case in 2015.

Wow, I remember formulating that as a hypothesis 2 years ago. Nice result! Do you have any idea why it works now but didn't then?

I had interest in Frisian draughts in 2015. During the man-machine match the same year, a proponent of the game even had leaflets in English; kudos to him! Unfortunately I was unable to understand the capturing rules on my way back (...); something about a king being worth "between one and two men" for captures. It looked ambiguous to me, and I couldn't translate it to maths (other than picking 1.5 at random). However I'm looking for information again and it looks much clearer in two stages:
- majority rule
- "king majority" as a secondary rule
If only I had seen that in 2015 ...

The capture rules of Frisian are a bit exotic, but they can be computed in a very straightforward matter. The value of N kings is more than 2N-1 men, but less than 2N men. Hypothetically, if you were using floating point eval weights, you would put the value of a king at 1.999... men. But for integer weights, just use 2 - 1/64 since you can't ever capture more than 64 pieces. The total value of capturing M men and K kings is then: V = M + (2 - 1/64) K or 64 V = 64 * (M + 2 K) - K = (P + K) << 6 - K where P = M + K is the total number of captured pieces. So when comparing two moves for precedence, you only have to compute (P+K)<<6 -K for each move. For equal values, there is also a tie-breaker rule: capturing with a king takes precedence.

Other rules of Frisian draughts are a show stopper, though. I was only considering othogonal captures, with the smaller draw rate as a bonus. At most 3 moves by a wolf/king (as I recall) will destroy the best-designed endgame table builder in no time. Nonetheless apparently an old game with a lot of tradition; interesting that it's still played.

The rule you quoted is: you can't move with the same king more than 3 moves in a row if and only if you have both at least one king and at least one man. After the 3rd consecutive move with the same king, you either have to make a man move, or a capture (possibly with that same king).

With this rule, databases for Frisian draughts are also exotic but not impossible. You just need to multiply the state space by a pair of indices (index of king in the number of kings, number of consecutive moves). So for the endgame of 2 kings + 1 man vs 1 king e.g., this multiplies the number of states by 8 (2 values for the king index, times 4 for the number of moves). So this is a database in a generalized state space with 2 virtual pieces which take on special values (not board squares). Move generation in this state space is then straightforward: just reset the number of consecutive moves after any move with another piece.

See also this thread: viewtopic.php?t=2911

For evaluation, my only thought was that 4x4 patterns might not be enough for top-level performance: line of 3 squares don't fit anywere. So maybe 5x5 patterns (13 squares), which are difficult to learn => probably not worth the effort. Regardless of eval quality, I don't expect humans to resist the tactical precision of programs however.

Frisian draughts is probably the easiest game to solve (for a given board size, I am not claiming that on a 10x10 it is feasible), since it converges much faster to the endgame than international or Killer draughts. The number of captures are just enormous. You can be in a 6 vs 6 piece endgame within 20 moves of the opening.

3) Give-away draughts

I haven't considered that variant. Already the concept of material-only search breaks down (guess), so I would have to start with a manual eval that plays decently. Or fully-random games, pure-MC style. I doubt that the strategy would be relevant in any other variant, but am confident that the usual techniques would do well: endgame tables -> generating games -> learning patterns -> tuning pruning -> opening book. There is order in this chaos.

I'm not sure why you're expecting pattern evaluation to be especially adapted to this variant. Maybe you're referring to the fact that they (more or less) automate feature construction like neural networks. In my view, patterns should do well in all draughts variants. They might collapse on very large boards if long-distance strategy is important (as in Go).

The point that Martin makes in his blog is that a regular material-only eval didn't do anything. So patterns are not just nice to have, but need to have. Maybe you can have a good PST as well. But it's an extremely non-intuitive game. E.g. this position:


White to move

is a win for white! Think about that

[Fabien Letouzey]

Fabien thanks, and this was with 6P or 7P DBs (in normal Draughts the 8P is required to find the draw result).

That's right. Even before DB scores, the material ones go down so much (-21 might be a record for me!) that the result was not in doubt. Indeed, Scan doesn't prove the draw in normal draughts with 6P tables.

in general at which move do you already see the theoretical final scores in breakthrough Draughts?

I've just played two blitz games. The first one seemed lopsided early, but not by much: 0.20 which would correspond to 0.10 in normal draughts. Large positional scores appeared after around 70 plies in both games. Material-gain scores at 85 and 80 respectively, and the proofs followed: 100 and 85 plies.

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 started generating fast games today for evaluation training, and so far the results are balanced. I can run statistics once I have an evaluation for this variant. Probably, the program being far from perfection, this will not help much.

[Fabien Letouzey]

Wow, I remember formulating that as a hypothesis 2 years ago. Nice result! Do you have any idea why it works now but didn't then?

Yes, you did! The advantage for me is that I don't need to generate games for both variants anymore, except to validate the hypothesis that it's not needed

It's a strange result that I cannot attribute to anything in particular. I think the Killer-draughts evaluation "improved more than the other" with time, whatever this means with different Elo scales. They both use the same technology.

Frisian draughts is probably the easiest game to solve (for a given board size, I am not claiming that on a 10x10 it is feasible), since it converges much faster to the endgame than international or Killer draughts. The number of captures are just enormous. You can be in a 6 vs 6 piece endgame within 20 moves of the opening.

I didn't think about that. Looks like a job for opening-book construction, then. Do the players think that the perfect game is a draw?

The point that Martin makes in his blog is that a regular material-only eval didn't do anything. So patterns are not just nice to have, but need to have. Maybe you can have a good PST as well. But it's an extremely non-intuitive game. E.g. this position:


White to move

is a win for white! Think about that

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.

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

[Rein Halbersma]

However a possibility remains: maybe there are many move sequences, but few intermediate positions, say 40 plies from the starting position, with reasonable play from both sides.

See this manual on Frisian draughts: http://frisiandraughts.com/onewebmedia/ ... manual.pdf
Chapter 6 opens with this quote

The number of playing possibilities declines during an
opening. The point in the game at which the possibilities for
both players increase again is the moment at which the
opening in question will no longer be discussed. The moves
in this manual end at the narrowest point of this ‘hourglass’
The moment at which this happens is strongly related to the
type of opening.

Of course, this is only a claim by the writers of the manual, not an empirical observation on the search tree of a computer program. Nevertheless, I think this is supporting evidence that the game of Frisisan is qualitatively different than any other draughts game. It might therefore be easier to solve.

[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 14438 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 14438 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 14249 times

Table Scan Deep Search FPST.png (11.38 KiB) Viewed 14249 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 14136 times

SDA Graph.png (29.19 KiB) Viewed 14136 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