Checkers Is Strongly-Solved for 8-pieces

[Cardoso]

I did the same around 2003 for the portuguese variant (with flying kings).
I did the 8 piece DTM wich is about 460GB uncompressed.
I had it uncompressed for many years, only recently I compressed it to 46GB, that's 1/10th of the original.
The longest win is 210 ply.
DTM was the first TBs I coded, later I computed also the WDL.
I noticed you have both 1byte and 2byte values.
Where do you put the 2byte values and index them?
Maybe you have a special 1byte value telling it's a 2byte value and append it after the end of the slice.
But how do you find/index the 2byte values?

best regards,
Alvaro

[Sven]

2. As I demonstrated in a paper published in 2003, with as few as 3 pieces on the board, the MTC database can miss a win in 2 moves and instead elect to promote a checker to a king (a "conversion in 1") which prolongs the game for 29 more moves.

That's just fine for a strong solution.

Not if "perfect play" (which is the subject of a strong solution) includes to always provide the shortest solution. It seems that different people have a different interpretation of it.

[Ed Trice]

I noticed you have both 1byte and 2byte values.
Where do you put the 2byte values and index them?
Maybe you have a special 1byte value telling it's a 2byte value and append it after the end of the slice.
But how do you find/index the 2byte values?

best regards,
Alvaro

Hello Alvaro,

The short answer: I use a binary search on a list sorted by the index.

Details: I solved the database using 2 bytes per position. Since DB7 had a max win of 253-ply, I knew 8-bits would not suffice for DB8 and up. After the data is saved to disk, I convert it to 1 byte per position, and I keep longer wins/losses in another file.

Values 0-253 are win or loss lengths.
254 = draw
255 = "lookup the 16-bit result."

I store the 8-byte index and the 2-byte Distance To Win in a separate file. There are at most 2000-something in one file, luckily! With a binary search, I can find one in 2000 in 11 probes or less. This is done instantaneously.

[syzygy]

2. As I demonstrated in a paper published in 2003, with as few as 3 pieces on the board, the MTC database can miss a win in 2 moves and instead elect to promote a checker to a king (a "conversion in 1") which prolongs the game for 29 more moves.

That's just fine for a strong solution.

Not if "perfect play" (which is the subject of a strong solution) includes to always provide the shortest solution. It seems that different people have a different interpretation of it.

According to Victor Allis:

ultra-weakly solved
For the initial position(s), the game-theoretic value has been determined.

weakly solved
For the initial position(s), a strategy has been determined to obtain at least the game-theoretic value of the game, for both players, under reasonable resources.

strongly solved
For all legal positions, a strategy has been determined to obtain the game-theoretic value of the position, for both players, under reasonable resources.

Nobody will dispute that the discovery of a proof that chess is a win for white from the starting position means chess becomes ultra-weakly solved (and similar for other games). It is not necessary to know the exact DTM value of the starting position. So, "game-theoretic value" simply means win, draw or loss.

Similarly, nobody will expect a "weak solution" for chess to give a strategy to win the opening position (assuming chess is a win for white) in the least number of moves. It is sufficient that a strategy is found that guarantees a win against any play by black. Again, "game-theoretic value" simply means win, draw or loss.

I don't see why the same words should have a different meaning in case of "strongly solved".

[Ed Trice]

Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.

Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hard-pressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 60-80 moves before making a single trade. Ed Gilbert stored conversion data while he had storage capacity. And, as I mentioned already, conversion databases work best with a plethora of kings.

That's just fine for a strong solution.

So in chess, if a program can't find a mate in 2 but instead promotes a pawn to a queen and spends 29 moves running down the enemy King, you would say that is a strong solution?

Sorry, I disagree.

If a solution cannot outperform a human amateur, it's not "strong" in any sense of the word.

[Dann Corbit]

Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.

Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hard-pressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 60-80 moves before making a single trade. Ed Gilbert stored conversion data while he had storage capacity. And, as I mentioned already, conversion databases work best with a plethora of kings.

That's just fine for a strong solution.

So in chess, if a program can't find a mate in 2 but instead promotes a pawn to a queen and spends 29 moves running down the enemy King, you would say that is a strong solution?

Sorry, I disagree.

If a solution cannot outperform a human amateur, it's not "strong" in any sense of the word.

IMO, any win is equal in value.
And any draw is equal in value.
And any loss is equal in value.

A shorter win is only prettier.

A proven win in 100 moves is a win.
A proven win in 1 move is a win.
Neither is superior from a game theoretic standpoint, as far as I can see.

[Ed Trice]

There are at most 2000-something in one file, luckily! With a binary search, I can find one in 2000 in 11 probes or less. This is done instantaneously.

I hate correcting myself

There are 5787 distance-to-wins > 253. I forgot with draws = 254 you also need to store a loss in 254 and win in 255 as well.

4 kings vs. 2 kings + 2 checkers has the 5787 16-bit entries.

The file looks like:

000000000355349582, 255
000000003006173900, 275

Etc.

64-bit index, 16-bit result.

I know the index, and I know the total number (5787 in this case) of entries, so I binary search the data until indices match, then I read (10 * found_index) into the file, and the next 2 bytes will be the associated distance to win.

[Ed Trice]

According to Victor Allis:

ultra-weakly solved
For the initial position(s), the game-theoretic value has been determined.

weakly solved
For the initial position(s), a strategy has been determined to obtain at least the game-theoretic value of the game, for both players, under reasonable resources.

strongly solved
For all legal positions, a strategy has been determined to obtain the game-theoretic value of the position, for both players, under reasonable resources.

OK, now I see.

So we need "ultra strongly solved" as a counterbalance to ultra weakly solved, but this is beginning to strain what people might consider "serious" terminology.

I suppose "Perfect Play" should be the correct prefix to the 8-piece solutions I have.

[AlvaroBegue]

OK, now I see.

So we need "ultra strongly solved" as a counterbalance to ultra weakly solved, but this is beginning to strain what people might consider "serious" terminology.

I suppose "Perfect Play" should be the correct prefix to the 8-piece solutions I have.

No, some people would disagree that a longer win is less perfect than a shorter one. In the game of go, some people would argue that a win by many points is better than a narrow win. My position is that all wins are equally good.

[AlvaroBegue]

Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.

Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hard-pressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 60-80 moves before making a single trade. Ed Gilbert stored conversion data while he had storage capacity. And, as I mentioned already, conversion databases work best with a plethora of kings.

How long do you have to search before you find a winning pawn move? That's all that's needed here.