Checkers Is Strongly-Solved for 8-pieces

[Rein Halbersma]

I've done Distance To Win endgames for chess (The Sniper, 1987), Gothic Chess (my 80-square variant with Archbishop and Chancellor pieces, 2004), and checkers (2001, 2017). In my opinion, the checkers algorithm is the one requiring the most brain power. It's hard to prevent an "infinite loop" in checkers DTW for reasons I will not elaborate here. Suffice it to say the iteration on which a win or loss is first realized RARELY matches the final Distance To Win number.

I would be interested in learning why DTW computations for checkers are inherently more complicated than for say chess. Can you elaborate? I don't think the basic algorithm of e.g. Wu & Beal relies on any game-specific knowledge. I am aware of at least 2 efforts (one completed, one in progress) to compute DTW for 10x10 draughts.

Furthermore, since the 8-piece exceeds the DTW distance for a single byte, unless you use operator-overloading for making functional 9-bit or 10-bit bytes, then you need two bytes per position in RAM. When you include the promotion slices and jump sub-databases, even loading and unloading them to minimize the RAM, you still need a 128 GB system, unless you want to grind your hard drive into pulp and magnify the time taken to solve it by a few thousand.

So, yeah, 20 years ago? Yeah right.

The fact that you used 128Gb does not prove that this is the minimum amount of RAM required. Why wouldn't the slicing techniques (leading ranks, leading man configs, subleading ranks) used for the 10-piece WLD databases apply for the 8-piece DTW databases? IIRC, the 8-piece WLD databases can be build with less than 1Gb of RAM, and probably for somewhat less if one would use finegrained slicing. That should mean not more than 16Gb RAM for the 8-piece DTW dbs.

[Sven]

This is one opinion. There are several opinions about it. My point is: the literature mostly ignores that "perfect play" for a legal position that is not a game-theoretical draw should require to provide the shortest path to win resp. the longest path to lose.

The key problem of ignoring it is that this can lead to "infinite winning attempts". If you have two choices to play a winning move and you always take the one with the longer distance to win then playing the game based on that strategy will *fail* to actually deliver the win on the board - unless there are other limitations like 50-moves rule or threefold repetition.

The literature asks for a winning strategy. A strategy that fails to make progress towards a win is clearly not a winning strategy. But there is no need to require the winning strategy to be DTM-optimal.

Agreed: a winning strategy does not need to be DTM-optimal. But that does not tell us whether "perfect play" requires it.

So for chess, for instance, I could accept a DTZ50 endgame tablebase as a valid tool for "perfect play" for the subset of endgame positions it covers. But in case of checkers I doubt that the 50-moves rule (or 40-moves rule - seems to be unclear which one is used?) is currently considered in any existing EGT. In any case, not playing the shortest win can't be called "perfect play" if it involves the risk of never winning the game at all.

I also doubt that endgame databases for checkers take into account such 50-move rule-like drawing rules. So strictly speaking they are endgame databases for the game of checkers without that rule. And as long as they contain sufficient information to guarantee progress (which the MTC data seems to do), they give a winning strategy for that game.

Sounds plausible.

For these reasons I can't accept statements that pretend that "perfect play" has a consistent definition in literature. It simply hasn't. Even "strongly solved" is defined differently, sometimes the definition involves to always provide the "best move", without mentioning the "distance to win" aspect.

You will have to agree on the game: chess with 50-move rule or chess without 50-move rule. They are two different games. Same for checkers. Change the game and you change what strategies give "perfect play".

The concept of a game being "strongly solved" has a perfectly clear and commonly accepted definition. You just have to be aware of what exactly is the game that is solved.

Not clearly distinguishing the games "with or without 50-moves rule" as you have requested may have been a weakness of my post, right. But I disagree about the "perfectly clear and commonly accepted definition". Regardless whether a "50-moves rule" (or a similar rule in case of checkers or other games) is part of the game or not, I do not see where the literature clearly defines whether "perfect play" requires a DTM-optimal strategy or not. It is simply left undefined. You argue that "there is no need to require it", so your argument is based on something like "common sense" but only from your viewpoint, while others have a different interpretation about what "perfect play" means.

So I see two possible interpretations of the "strongly solved" definition, assuming we have agreed that "making progress" is at least a requirement for "perfect play" as well as for a "strong solution":

1) A strong solution requires "perfect play" and "Perfect play" requires to be DTM-optimal.
=> That would mean: A strong solution requires a DTM-optimal strategy.

2) A strong solution requires "perfect play" but "Perfect play" does not require to be DTM-optimal.
=> That would mean: A strong solution only requires a strategy that guarantees progress in a winning position.

[Sven]

The point was: using WDL only, instead of DTM, can lead to infinite winning attempts (in a won position), or to missing a 50-moves draw (in a lost position that needs more than 50 moves for the opponent to win).

Do you realise that using DTM will mess up perfectly fine wins in "chess including the 50-move rule"?

Yes. So replace "DTM" by "DTM50" in that case. It is certainly not an unimportant detail but I left it out, which is not precise enough.

DTM gives a winning strategy / perfect play for chess without 50-move rule.
Idem for DTC and DTZ.

DTZ50 gives a winning strategy / perfect play for chess with 50-move rule.
DTM50 (which is a far more complicated metric than I want to explain in this thread and requires considerably more storage space than DTM) gives a winning strategy / perfect play for chess with 50-move rule.

DTZ50+ (implemented by my tablebases) gives a winning strategy / perfect play both for chess with 50-move rule and for chess without 50-move rule.

As I pointed out in my other reply, this would be true for a definition of "perfect play" that does not require the "DTM-optimal" property. For the other possible definition that requires it, obviously only DTM (without 50-moves rule) and DTM50 (with 50-moves rule) would give "perfect play".

[Sven]

Ed, I absolutely agree but I don't see where I wrote something different than you? Would you mind to read my post once again? I am *very* sure that you misunderstood my point, completely.

If so, then I apologize.

Accepted

I did read and re-read it, and it still sounds like you're indicating my databases could misplay a win and have the game go on forever, and also misplay a swindle attempt whereby the losing side tries hard for a draw.

This is not the case, of course.

Actually I did not intend to indicate anything related to that with my post, and I thought there were several hints helping to understand my intention, for instance the fact that I replied to Dann's post where he stated that all wins (and all draws, all losses) were equal in his view, or the phrase

The key problem of ignoring it is that this can lead to "infinite winning attempts".

where the word "it" was related to "require to provide the shortest path to win" from the previous sentence, so the meaning in fact was "not providing the shortest path to win can lead to infinite winning attempts".

But my wording was probably too complex and might have confused you. Next time I'll try to do better

[Ed Trice]

I would be interested in learning why DTW computations for checkers are inherently more complicated than for say chess. Can you elaborate?

The details emerge once you are actually writing the code and getting results. You soon find out that "chess logic" for DTW does not apply to checkers. Not only that, once you figure out the checkers logic, it's not apparent if your routine will ever terminate. Then, finally, the "light bulb moment" occurs, and everything falls into place.

In chess, for example, you place the pieces on every possible square, and look for checkmates for the side to move. Every such position is a "loss in 0." Next, every move possible by the side-not-to-move must create a "win in 1." I am oversimplifying, leaving out illegal "still in check" moves and the fact that the mated side might also have winning chances, etc. This process repeats for loss in 2, win in 3, loss in 4, etc.

In checkers, you have to look at every position with each iteration, and not just "increment" the win/loss ply counters.

Example from the 9-piece database:



Here the red checker starts at the bottom and crowns to a king on squares 29, 30, 31, or 32. It must travel up the board.

You can see if it were white to move, 16-12 threatens to win the checker on square 8 trivially. One might then think 8-12 is forced for red to move, keeping the red checker safe. Recall an iterator only sees 1-move ahead at a time, and the values written are a function of the number of times a position is visited.

The correct winning move for red is 21-25! which can ignore 16-12? since that in turn loses to 25-22! which is a killer shot. It seems to throw away material pointlessly, but red wins after either 12x3 1-6! 18x25 6-10 14x7 2x11x18 and white to move loses in 28-ply, or 18x25 1-6 12x3 6-10 14x7 2x11x18.

So all this turmoil must first be examined, iteration after iteration, and we still don't have the optimal response for white to move after 21-25!

In chess endgames you don't have to deal with this.[/img]

[Ed Trice]

I would be interested in learning why DTW computations for checkers are inherently more complicated than for say chess. Can you elaborate?

The details emerge once you are actually writing the code and getting results. You soon find out that "chess logic" for DTW does not apply to checkers. Not only that, once you figure out the checkers logic, it's not apparent if your routine will ever terminate. Then, finally, the "light bulb moment" occurs, and everything falls into place.

In chess, for example, you place the pieces on every possible square, and look for checkmates for the side to move. Every such position is a "loss in 0." Next, every move possible by the side-not-to-move must create a "win in 1." I am oversimplifying, leaving out illegal "still in check" moves and the fact that the mated side might also have winning chances, etc. This process repeats for loss in 2, win in 3, loss in 4, etc.

In checkers, you have to look at every position with each iteration, and not just "increment" the win/loss ply counters.

Example from the 9-piece database:



Here the red checker starts at the bottom and crowns to a king on squares 29, 30, 31, or 32. It must travel up the board.

You can see if it were white to move, 16-12 threatens to win the checker on square 8 trivially. One might then think 8-12 is forced for red to move, keeping the red checker safe. But 8-12 throws away the win and white draws with 14-10 12x19 15x24x31. Recall an iterator only sees 1-move ahead at a time, and the values written are a function of the number of times a position is visited.

The correct winning move for red is 21-25! which can ignore 16-12? since that in turn loses to 25-22! which is a killer shot. It seems to throw away material pointlessly, but red wins after either 12x3 1-6! 18x25 6-10 14x7 2x11x18 and white to move loses in 28-ply, or 18x25 1-6 12x3 6-10 14x7 2x11x18.

So all this turmoil must first be examined, iteration after iteration, and we still don't have the optimal response for white to move after 21-25!

In chess endgames you don't have to deal with this.

[jwes]

The point was: using WDL only, instead of DTM, can lead to infinite winning attempts (in a won position), or to missing a 50-moves draw (in a lost position that needs more than 50 moves for the opponent to win).

Do you realise that using DTM will mess up perfectly fine wins in "chess including the 50-move rule"?

DTM gives a winning strategy / perfect play for chess without 50-move rule.
Idem for DTC and DTZ.

DTZ50 gives a winning strategy / perfect play for chess with 50-move rule.
DTM50 (which is a far more complicated metric than I want to explain in this thread and requires considerably more storage space than DTM) gives a winning strategy / perfect play for chess with 50-move rule.

DTZ50+ (implemented by my tablebases) gives a winning strategy / perfect play both for chess with 50-move rule and for chess without 50-move rule.

If one defines "perfect play" as including "not making moves humans recognize as obvious blunders", then DTZ50+ does not play perfectly, e.g. DTZ50+ plays Qb4+ in this position.
[d]8/8/8/8/8/k7/2RQ4/4K3 w - - 0 1

[Rein Halbersma]

I would be interested in learning why DTW computations for checkers are inherently more complicated than for say chess. Can you elaborate?

The details emerge once you are actually writing the code and getting results. You soon find out that "chess logic" for DTW does not apply to checkers. Not only that, once you figure out the checkers logic, it's not apparent if your routine will ever terminate. Then, finally, the "light bulb moment" occurs, and everything falls into place.

In chess, for example, you place the pieces on every possible square, and look for checkmates for the side to move. Every such position is a "loss in 0." Next, every move possible by the side-not-to-move must create a "win in 1." I am oversimplifying, leaving out illegal "still in check" moves and the fact that the mated side might also have winning chances, etc. This process repeats for loss in 2, win in 3, loss in 4, etc.

And why can't you do the reverse iterations for checkers? The WLD databases were generated this way by the Chinook project (apart from the first few iterations).

In checkers, you have to look at every position with each iteration, and not just "increment" the win/loss ply counters.

Example from the 9-piece database:

Here the red checker starts at the bottom and crowns to a king on squares 29, 30, 31, or 32. It must travel up the board.

You can see if it were white to move, 16-12 threatens to win the checker on square 8 trivially. One might then think 8-12 is forced for red to move, keeping the red checker safe. But 8-12 throws away the win and white draws with 14-10 12x19 15x24x31. Recall an iterator only sees 1-move ahead at a time, and the values written are a function of the number of times a position is visited.

The correct winning move for red is 21-25! which can ignore 16-12? since that in turn loses to 25-22! which is a killer shot. It seems to throw away material pointlessly, but red wins after either 12x3 1-6! 18x25 6-10 14x7 2x11x18 and white to move loses in 28-ply, or 18x25 1-6 12x3 6-10 14x7 2x11x18.

So all this turmoil must first be examined, iteration after iteration, and we still don't have the optimal response for white to move after 21-25!

In chess endgames you don't have to deal with this.

Maybe for forward iteration you have to repeat all this stuff. But for backward iteration, that is not necessary. You only have to try capture / promotion or other conversion moves once, as your initial pass. This gives a DTW from an 7 or fewer piece database. For capture positions, the earlier found DTW is an exact depth. For promotions and other conversion moves it is a lower bound that could be overturned by other moves. During the conversion pass, you store a small array indexed by DTW to collect the possible depth levels.

Then you start with DTW = 0. If there are any "mate" positions, you do backward iteration from there, but you have to "fold in" all previous capture conversions when you reach the appropriate depth level. If not, you go to the lowest depth that you found from your conversion pass and start from there. You iterate until done, and then as a final pass you also treat the remaining conversion depths you found earlier. There can be gaps in the final table of number of resolved positions per depth, but it's a single conversion pass algorithm.

[syzygy]

The fact that you used 128Gb does not prove that this is the minimum amount of RAM required. Why wouldn't the slicing techniques (leading ranks, leading man configs, subleading ranks) used for the 10-piece WLD databases apply for the 8-piece DTW databases? IIRC, the 8-piece WLD databases can be build with less than 1Gb of RAM, and probably for somewhat less if one would use finegrained slicing. That should mean not more than 16Gb RAM for the 8-piece DTW dbs.

And if the values get bigger than what fits in a byte, one can periodically write the intermediate results to disk and "reduce" all values to create space for further iterations. So 1 byte per position suffices.

[syzygy]

If one defines "perfect play" as including "not making moves humans recognize as obvious blunders", then

then Humpty Dumpty comes to mind.

Perfect play in the context of game theory and "strongly solved" games has a perfectly clear definition and I have made perfectly clear that that is the definition I used here.