Checkers Is Strongly-Solved for 8-pieces

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

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

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.

The 4 kings vs 4 kings db requires less than 1.5 Gb of RAM, with 2 bytes per position. I guess my initial statement that the 8 piece DTW dbs could have been built 20 years ago was inaccurate. It could have been done 12 years ago, when Ed Gilbert built the 10 piece WLD dbs with 2 Gb of RAM.

Or are you going to do 10 piece DTW dbs? Even then, 5 vs 5 kings does require a little over 32 Gb, without using mirror symmetries, otherwise you could do it with 8Gb. So where does your 128 Gb come from? Seems a massive overkill.

[Rein Halbersma]

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.

Calling me trapped in a tunnel vision without addressing the perceived mistakes is bad form. Carries no weight whatsoever.

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.

And even so, that does not invalidate the summary of the Wu & Beal algorithm that I gave earlier. Backward iteration works, and if you remember all encountered DTW values from conversions, you only have to process each position once.

I am not questioning the accuracy or value of your computations, but I am questioning the efficiency and minimally required resources. You have only handwaved so far. Please explain why backward iteration cannot work (other than that you perhaps tried and chose the more straightforward but less efficient approach). IIRC, Nalimov also used the forward algorithm for the 6 piece chess DTM dbs, but others have improved on that.

Also please explain the 128 Gb requirement.

[Ed Trice]

The 4 kings vs 4 kings db requires less than 1.5 Gb of RAM, with 2 bytes per position.

Incorrect.

I guess my initial statement that the 8 piece DTW dbs could have been built 20 years ago was inaccurate. It could have been done 12 years ago, when Ed Gilbert built the 10 piece WLD dbs with 2 Gb of RAM.

Incorrect. Any statement starting with "could have" that never occurred is ridiculous.

Or are you going to do 10 piece DTW dbs?

5 kings vs. 5 kings has a max win of 175-ply. Solved in 2016.

Even then, 5 vs 5 kings does require a little over 32 Gb, without using mirror symmetries, otherwise you could do it with 8Gb.

Incorrect.

So where does your 128 Gb come from? Seems a massive overkill.

It comes from me actually doing the work and you just talking about it. If you can't even calculate the RAM size for an all-kings slice, you should stop embarrassing yourself when addressing the world's only computer scientist who ACTUALLY DID THE COMPUTATION.

[Rein Halbersma]

The 4 kings vs 4 kings db requires less than 1.5 Gb of RAM, with 2 bytes per position.

Incorrect.

NumberOf(4 kings vs 4 kings) = Binomial[32,4] * Binomial[28,4] = 736 281 000 (same number as listed on the Chinook project page https://webdocs.cs.ualberta.ca/~chinook ... piece.html), times 2 bytes per position is 1.5 Gb. Please tell me where I might be incorrect.

And yes, I am aware that you need some buffers to also probe into 7-piece and lower dbs for conversions. But you don't need everything in RAM.

Even then, 5 vs 5 kings does require a little over 32 Gb, without using mirror symmetries, otherwise you could do it with 8Gb.

Incorrect.

NumberOf(5 kings vs 5 kings) = Binomial[32,5] * Binomial[27,5] = 16 257 084 480 (same number as listed on the Chinook project page https://webdocs.cs.ualberta.ca/~chinook ... piece.html), times 2 bytes per position is 32 Gb. Please tell me where I might be incorrect.

[Sven]

The 4 kings vs 4 kings db requires less than 1.5 Gb of RAM, with 2 bytes per position.

Incorrect.

NumberOf(4 kings vs 4 kings) = Binomial[32,4] * Binomial[28,4] = 736 281 000 (same number as listed on the Chinook project page https://webdocs.cs.ualberta.ca/~chinook ... piece.html), times 2 bytes per position is 1.5 Gb. Please tell me where I might be incorrect.

And yes, I am aware that you need some buffers to also probe into 7-piece and lower dbs for conversions. But you don't need everything in RAM.

Even then, 5 vs 5 kings does require a little over 32 Gb, without using mirror symmetries, otherwise you could do it with 8Gb.

Incorrect.

NumberOf(5 kings vs 5 kings) = Binomial[32,5] * Binomial[27,5] = 16 257 084 480 (same number as listed on the Chinook project page https://webdocs.cs.ualberta.ca/~chinook ... piece.html), times 2 bytes per position is 32 Gb. Please tell me where I might be incorrect.

The RAM usage is determined by the indexing scheme, not by the number of valid positions. As an extreme example, the indexing scheme might imply a total size of 2 * 32^8 entries for 8 pieces. There are certainly more clever schemes. Whether you can actually apply them can only be seen during implementation. And since the generation software must be generic enough to avoid writing special code for each piece configuration, I can imagine that an indexing scheme was chosen that may waste some memory but guarantees efficient and reliable generation for all (or all relevant) piece configurations, not just for 4k-4k. Therefore I doubt that you can take the numbers from the Chinook page to directly calculate RAM usage.