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
Checkers Is Strongly-Solved for 8-pieces
Moderators: hgm, Rebel, chrisw
-
- Posts: 362
- Joined: Thu Mar 16, 2006 7:39 pm
- Location: Portugal
- Full name: Alvaro Cardoso
-
- Posts: 4052
- Joined: Thu May 15, 2008 9:57 pm
- Location: Berlin, Germany
- Full name: Sven Schüle
Re: Checkers Is Strongly-Solved for 8-pieces
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.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
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 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.
-
- Posts: 5566
- Joined: Tue Feb 28, 2012 11:56 pm
Re: Checkers Is Strongly-Solved for 8-pieces
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 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.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.
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".
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
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.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: 12541
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: Checkers Is Strongly-Solved for 8-pieces
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 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.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.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
I hate correcting myselfEd Trice wrote: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.
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.
-
- Posts: 100
- Joined: Fri Sep 19, 2014 5:03 am
Re: Checkers Is Strongly-Solved for 8-pieces
OK, now I see.syzygy wrote: 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.
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.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Checkers Is Strongly-Solved for 8-pieces
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 8-piece solutions I have.
-
- Posts: 931
- Joined: Tue Mar 09, 2010 3:46 pm
- Location: New York
- Full name: Álvaro Begué (RuyDos)
Re: Checkers Is Strongly-Solved for 8-pieces
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 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.syzygy wrote:Because a quick search can solve the rest. Strongly solved does not forbid a bit of calculation.