Checkers Is Strongly-Solved for 8-pieces

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

[syzygy]

I do not see where the literature clearly defines whether "perfect play" requires a DTM-optimal strategy or not. It is simply left undefined.

This started with the subject title: strongly solved. A concept that has a clear definition in the literature. If you call "perfect play" whatever is required for "strongly solved", then very certainly perfect play does not require fastest win. (And Wikipedia isn't very accurate on this.) See here.

[Rein Halbersma]

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.

Ow, that's a nice trick, you mean add 256 when writing the final results back to disk?

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

Ow, that's a nice trick, you mean add 256 when writing the final results back to disk?

If you have determined all positions with, say, DTM <= 120, then save the whole table to disk and subtract 120 from all values in RAM. Once you get to DTM = 240, do the same, etc. At the end you can build the final table from the saved intermediate tables in one go.

Here is some code. reduce_tables() saves the table and shifts all values by constructing a map v mapping byte values to byte values and applying this map to all table elements. (Since I distinguish between wins/losses and cursed wins/losses (drawn under the 50-move rule) and I also keep track of which positions can be won or drawn by a capture, things are a bit complicated.) reconstruct_table() reconstructs the table. The reconstructed values all happen to fit in a byte for 6-piece DTZ50+, because I do not need to preserve the sign and whether the position is a draw by the 50-move rule (so I subtract 100 ply if > 100) and I count in moves if DTZ > 100. (Sign and 50-move info are stored separately in the WDL50+ table, and the probing code combines everything again.)

One complication for DTM is that you will have to reseed the table with uncaptures after each reduction pass (since there might be captures to a position with DTM >= 120).

[Ed Trice]

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.

In the first case, the "all kings" slice must be solved first and foremost. There's no subdivisions possible by leading checker rank when you have no checkers. You'd need to write a buffering schema, which I did for db-9 and up. Once you optimize the buffer's performance there's no need for subdivisions anymore.

In the second case, for WLD you visit unsolved positions only once. For DTM, you visit them many times. The disk access in a rank subdivision scheme would tax even the most robust SSD, slowing down the solve time tremendously.

The object is not to minimize your RAM usage; it's to minimize your solve time.

[Ed Trice]

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

You're trapped in chess "tunnel vision," which is very difficult to break out of. First, let me say there were several mistakes in your post, and I don't have time to address them.

Secondly, this might help you understand a big difference between chess and checkers DTM computation:

IN CHECKERS, IT IS POSSIBLE TO GET YOUR MAXIMUM DTW ON THE FIRST PASS AFTER YOU SOLVE THE JUMPS.

I've seen a win in 211-ply for 3 kings + 1 checker vs. 4 kings show up on iteration 1, and on iteration 78, the last one, it was still the max win.

I'm pretty sure that never happens in chess.