Checkers Is StronglySolved for 8pieces
Moderators: hgm, Harvey Williamson, bob
Re: Checkers Is StronglySolved for 8pieces
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
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
Re: Checkers Is StronglySolved for 8pieces
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.syzygy wrote:That's just fine for a strong solution.Ed Trice wrote: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.
Re: Checkers Is StronglySolved for 8pieces
Hello Alvaro,Cardoso wrote: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
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 253ply, I knew 8bits 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 0253 are win or loss lengths.
254 = draw
255 = "lookup the 16bit result."
I store the 8byte index and the 2byte Distance To Win in a separate file. There are at most 2000something in one file, luckily! With a binary search, I can find one in 2000 in 11 probes or less. This is done instantaneously.
Re: Checkers Is StronglySolved for 8pieces
According to Victor Allis:Sven Schüle wrote: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.syzygy wrote:That's just fine for a strong solution.Ed Trice wrote: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.
Nobody will dispute that the discovery of a proof that chess is a win for white from the starting position means chess becomes ultraweakly solved (and similar for other games). It is not necessary to know the exact DTM value of the starting position. So, "gametheoretic value" simply means win, draw or loss.ultraweakly solved
For the initial position(s), the gametheoretic value has been determined.
weakly solved
For the initial position(s), a strategy has been determined to obtain at least the gametheoretic value of the game, for both players, under reasonable resources.
strongly solved
For all legal positions, a strategy has been determined to obtain the gametheoretic value of the position, for both players, under reasonable resources.
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, "gametheoretic 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".
Re: Checkers Is StronglySolved for 8pieces
Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hardpressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 6080 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.syzygy wrote:Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.
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?syzygy wrote:That's just fine for a strong solution.
Sorry, I disagree.
If a solution cannot outperform a human amateur, it's not "strong" in any sense of the word.

 Posts: 8587
 Joined: Wed Mar 08, 2006 7:57 pm
 Location: Redmond, WA USA
 Contact:
Re: Checkers Is StronglySolved for 8pieces
IMO, any win is equal in value.Ed Trice wrote:Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hardpressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 6080 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.syzygy wrote:Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.
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?syzygy wrote:That's just fine for a strong solution.
Sorry, I disagree.
If a solution cannot outperform a human amateur, it's not "strong" in any sense of the word.
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.
Taking ideas is not a vice, it is a virtue. We have another word for this. It is called learning.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
But sharing ideas is an even greater virtue. We have another word for this. It is called teaching.
Re: Checkers Is StronglySolved for 8pieces
I hate correcting myselfEd Trice wrote:There are at most 2000something in one file, luckily! With a binary search, I can find one in 2000 in 11 probes or less. This is done instantaneously.
There are 5787 distancetowins > 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 16bit entries.
The file looks like:
000000000355349582, 255
000000003006173900, 275
Etc.
64bit index, 16bit 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.
Re: Checkers Is StronglySolved for 8pieces
OK, now I see.syzygy wrote: According to Victor Allis:ultraweakly solved
For the initial position(s), the gametheoretic value has been determined.
weakly solved
For the initial position(s), a strategy has been determined to obtain at least the gametheoretic value of the game, for both players, under reasonable resources.
strongly solved
For all legal positions, a strategy has been determined to obtain the gametheoretic value of the position, for both players, under reasonable resources.
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 8piece solutions I have.

 Posts: 880
 Joined: Tue Mar 09, 2010 2:46 pm
 Location: New York
Re: Checkers Is StronglySolved for 8pieces
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.Ed Trice wrote: 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 8piece solutions I have.

 Posts: 880
 Joined: Tue Mar 09, 2010 2:46 pm
 Location: New York
Re: Checkers Is StronglySolved for 8pieces
How long do you have to search before you find a winning pawn move? That's all that's needed here.Ed Trice wrote:Incorrect. A quick search cannot solve a 3 kings + 2 checkers bridge ending vs. a hardpressed defender with 2 kings + 3 checkers. Some of these endings require maneuvering for 6080 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.syzygy wrote:Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.