Frisian draughts endgame

Discussion about development of draughts in the time of computer and Internet.
Post Reply
Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Frisian draughts endgame

Post by Rein Halbersma » Sun Aug 01, 2010 22:25

Image
White to move.

This is a famous Frisian draughts endgame. In 1976, H. Walinga even wrote a little book about this endgame, with the tentative conclusion that it was a draw. Now you might wonder how such a ridiculously simple looking endgame might be worth more than a few lines of analysis, let alone a whole book. Isn't this a simple draw?

Not so fast! In Frisian draughts, 2 kings win against 1 king since the majority side can always trap the lone king owing to the orthogonal and diagonal captures. So it must be a simple win then?

Not so fast again! There are 2 little rules that make it a lot harder for the majority side to actually win this endgame. The first rule is that a side with both kings and men cannot move the same king more than 3 consecutive moves. After that, a capture with that king or a move by any other piece is mandatory. This allows for some subtle delaying tactics by the minority side. E.g. if the majority side has just played 3 consecutive moves with the same king, then an attack on that temporarily immobile king can often not be answered. The second rule is that as soon as a 2 kings against 1 king endgame appears, the majority side has exactly 13 plies to win. In rare cases this can not be enough to win.

My universal engine <Mistral> (still experimental but supporting every legal draughts variant) does not know these 2 little rules yet, but it does know the orthogonal capture rule. So it should analyze this position to be a simple white win. Right?

Not so right after all. Even without the 3 consecutive move rule and the 13 plies rule, black has a lot of subtle delaying tactics that it took <Mistral> 10 minutes and a nominal search depth of 39 plies to resolve the above diagram to a win! Here's the longest line of defense:

[FEN "W:W28,K46:BK43"]
1. 28-22 43-38 2. 46-41 38-16 3. 41-10 16-2 4. 22-18 2-35 5. 10-14 35-8 6. 14-28 8-30 7. 28-37 30-35 8. 37-26 35-2 9. 26-31 2-30 10. 18-12 30-48 11. 31-13 48-43 12. 13-19 43-25 13. 19-46 25-34 14. 12-8 34-1 15. 46-10 1-29 16. 8-3 29-15 17. 10-23 15-42 18. 23-1
Image
18... 42-26 19. 1-12 26x8 20. 3x12 *

You might wonder why 18... 42-26 if forced in the second diagram. Just look at it carefully and see what all the orthogonal captures can do! E.g. 18... 42-15 19. 3-12! 15x11 20. 1x21.

Note that it took white 11 king moves to actually promote his man when it was only 4 moves away from the promotion line. In particular, the 5 consecutive white king moves (moves 5-9) are not allowed under the 3 consecutive king moves rule. If we write Frisian(K) as the Frisian rules with K allowed consecutive king moves, then we know that the above endgame is a win for Frisian(5) and higher K. It's an open question whether the endgame is won for the official K=3 rules.

Given the hardness of the partial analysis of this deceptively simple looking endgame, the full analysis (with the 3 consec. and 13 plies rules) might take far too long for a normal forward search. So I would have to build an endgame database. In this case, one actually needs to build 4 endgame databases, with the white king having 3, 2, 1 or 0 moves left. Still very doable and it should take only a few minutes to generate them once I have that programmed. But larger databases need 16 different versions if both colors have both a man and a king. That would probably limit the Frisian draughts databases to 6 or 7 pieces with current technology.

MichelG
Posts: 244
Joined: Sun Dec 28, 2003 20:24
Contact:

Re: Frisian draughts endgame

Post by MichelG » Mon Aug 02, 2010 23:05

Nice find!

Since even this 2 vs 1 endgame already seems so complex, an endgame database might give some interesting and unexpected results as well.

They would be a bit more difficult to generate then 'normal' draughts, because of the last touch rule, and they are going to be a lot bigger than the equivalent normal draughts with the same number of pieces. I suspect some endgames would take hunderds of ply to solve. (normal draughts already has 255 ply deep positions at 7 pieces)

Michel

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Frisian draughts endgame

Post by Rein Halbersma » Tue Aug 03, 2010 08:48

MichelG wrote:Nice find!

Since even this 2 vs 1 endgame already seems so complex, an endgame database might give some interesting and unexpected results as well.

They would be a bit more difficult to generate then 'normal' draughts, because of the last touch rule, and they are going to be a lot bigger than the equivalent normal draughts with the same number of pieces. I suspect some endgames would take hunderds of ply to solve. (normal draughts already has 255 ply deep positions at 7 pieces)

Michel
Yes, there might be extremely complex endgames, even more complex than the Killer draughts endgames that you generated! One reason that it took 10 minutes to solve this endgame is that all the lines remain closely contested until the end. In normal draughts, there are also 2 vs 1 positions that take 29 plies to resolve, but there only the main line is that long. Probably a better move ordering scheme (e.g. attacking the opponent king that last moved might be a good idea to try first) could improve this a little.

The Frisian databases are quite straightforward to generate... once you have generalized the state space! You need 2 extra indices for the number of consecutive king moves (one for each side), and you need to determine the transitions between the different levels of the database.

For Frisian(N), these indices run from 0...N, so you have already a multiplicity of N^2 when both sides have both men and kings. Even worse, you also lose part of the combinatorial symmetry between multiple kings of each color. E.g. a 6 pc endgame of 2K+1M vs 2K+1M does not have the roughly 2-fold symmetry within each pair of kings anymore. That gives another factor of 4. So for N=3, you already have a db that has 36 times more positions! Plus the probably worse compression rate that you predict will make 6 pc dbs and a few 7 dbs (4 vs 3) probably the limit for current technology.

I thought of the following algorithm to connect different levels of the extra indices.

First, my convention is to let i=0 denote the positions where the last move was not made by a king, i=1 where the last move was by a king, i=2 the ones where the last 2 moves were by the same king etc. You could also count down from i=N to i=0 (so i would represent the number of consecutive king moves left), but this complicates building databases with different values of N. I prefer to let the index just represent the state and have the maximum allowed rule only be known when it is necessary (e.g. when generating moves). The first index of the king-tuple denotes the king that moved last (so you lose part of the pair-wise symmetry between kings).

Second, the moves that you generate fall into 2 classes: a) moves with the same king as the last piece that moved, and b) other moves. The first class of moves is only allowed for level i < N, and it takes a position from level i to i+1. The other class of moves take a position from level i to level 0. With "takes to another level" I mean that only the consecutive move index for the side to move changes, whereas all other indices (the 2 tuples for the pieces and the consecutive move index of the other color) remain the same.

With these indices and transitions, you can simply do the usual forward iteration over all position until nothing changes.

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Frisian draughts endgame

Post by Rein Halbersma » Sun Aug 08, 2010 22:05

Rein Halbersma wrote:Image
White to move.

Even without the 3 consecutive move rule and the 13 plies rule, black has a lot of subtle delaying tactics that it took <Mistral> 10 minutes and a nominal search depth of 39 plies to resolve the above diagram to a win! If we write Frisian(K) as the Frisian rules with K allowed consecutive king moves, then we know that the above endgame is a win for Frisian(5) and higher K. It's an open question whether the endgame is won for the official K=3 rules.
I have now coded the K-consecutive king moves rule in my engine <Mistral>. It turns out that the above conclusions are not completely correct.

First, for K=infinity (i.e. unrestricted consecutive king moves), I found a PV with 5 consecutive king moves on the PV. However, this does not mean that the position is a win for K>=5. It turns out that the PV relies on the fact that some refutations of other black moves can take more than 5 consecutive king moves.

Second, it turns out that proving draws is much easier than proving wins. The reason is that a draw can only happen if black can force the exchange of the lone white man and this either happens very quickly or not at all. It turns out that the diagram is a draw for all K<6 (search of only a few seconds).

Third, you have to be really careful with the transposition table. The consecutive king moves work a bit like castling and en-passant rights in chess. They are irreversible bits on your position state. So you have to store the whole history of them in your position state, and also not forget to incorporate this information in your hash index. If you don't do that, then you get a very instable search because the number of legal moves depend on the path to the position and sometimes this will preclude a win being found.

The first win appears for K=6. As you can see from the output below, the longest sequence along the PV is 5 consecutive king moves, but a lot of refutations really need the 6 consecutive kings moves. Note also the explosion in tree size from d=37 to d=39: this shows that there are many ways for black to postpone the loss until the very last moment, which all have to be proven a white win. Also note that white can force a second king already on move 12 (depth=23 search), but that in the PV the second king only appears on move 16. One final explanation: the ^x notation means that the king just made its x-th consecutive move.

Code: Select all

"W:BK43:W28,K46"

Searching to nominal depth=39

search[ 1/ 0.9/ 1; -INF, +INF] =  102,            8 nodes,   0.00s, 0.01 Mnps
search[ 3/ 2.6/ 3; -INF, +INF] =  112,          252 nodes,   0.00s, 0.25 Mnps
search[ 5/ 4.5/ 5; -INF, +INF] =  112,         1876 nodes,   0.00s, 1.88 Mnps
search[ 7/ 6.3/ 7; -INF, +INF] =  113,         6641 nodes,   0.02s, 0.39 Mnps
search[ 9/ 8.1/ 9; -INF, +INF] =  114,        49412 nodes,   0.05s, 1.03 Mnps
search[11/ 9.8/11; -INF, +INF] =  115,       123083 nodes,   0.11s, 1.12 Mnps
search[13/11.5/13; -INF, +INF] =  115,       610996 nodes,   0.50s, 1.22 Mnps
search[15/13.2/15; -INF, +INF] =  115,       423074 nodes,   0.33s, 1.29 Mnps
search[17/14.9/17; -INF, +INF] =  115,       554430 nodes,   0.44s, 1.26 Mnps
search[19/16.5/19; -INF, +INF] =  115,      1451269 nodes,   1.09s, 1.33 Mnps
search[21/17.8/21; -INF, +INF] =  117,      1113581 nodes,   0.78s, 1.42 Mnps
search[23/20.5/23; -INF, +INF] =  339,      4962167 nodes,   3.42s, 1.45 Mnps
search[25/21.4/25; -INF, +INF] =  343,      3785309 nodes,   2.49s, 1.52 Mnps
search[27/23.3/27; -INF, +INF] =  343,      1576008 nodes,   1.05s, 1.50 Mnps
search[29/25.0/29; -INF, +INF] =  343,      3158526 nodes,   2.03s, 1.55 Mnps
search[31/26.9/31; -INF, +INF] =  343,      7213418 nodes,   4.45s, 1.62 Mnps
search[33/28.5/33; -INF, +INF] =  343,     35138127 nodes,  20.33s, 1.73 Mnps
search[35/29.1/35; -INF, +INF] =  343,      9659900 nodes,   5.86s, 1.65 Mnps
search[37/30.9/37; -INF, +INF] =  343,      6523734 nodes,   4.28s, 1.52 Mnps
search[39/34.4/39; -INF, +INF] =  W39,   1013946854 nodes, 581.44s, 1.74 Mnps
28-22   (43-38)
46-41^1 (38-16)
41-10^2 (16-02)
22-18   (02-35)
10-05^1 (35-08)
05-28^2 (08-30)
28-37^3 (30-35)
37-26^4 (35-44)
26-31^5 (44-06)
18-12   (06-01)
31-18^1 (01-06)
18-29^2 (06-44)
12-07   (44-49)
29-33^1 (49-35)
33-50^2 (35-19)
07-01   (19-05)
01-34   (05-41)
34-25   (41-05)
50-45   (05x35)
45x25

Rein Halbersma
Posts: 1664
Joined: Wed Apr 14, 2004 16:04
Contact:

Re: Frisian draughts endgame

Post by Rein Halbersma » Mon Mar 09, 2020 08:39

Marten Walinga kindly asked me to rewrite the above posts into a column for the tournament book for the 2020 Fryslân Open tournament (which includes a World Championship event in the 5v5 piece Frysk! variant). I was happy to oblige of course! See p13-14 of https://docs.google.com/viewer?url=http ... 202020.pdf

Post Reply