8-Piece Perfect Play Databases

[Ed Trice]

White to move and win in 291 ply.

The longest forced win so far in the 8-piece perfect play database.



[Event "Only Perfect Checkers 1.0.3 291 ply 8-piece win"]
[Date "2016-08-10"]
[Black "OPC"]
[White "OPC"]
[Result "0-1"]
[Setup "1"]
[FEN "W:WK20,K17,K31,K30:B2,1,K13,K23"]

17-14, 23-19, 31-27, 1-6, 14-9, 19-15, 27-23, 15-11, 9-5, 11-8, 30-26,
8-3, 23-19, 13-17, 19-15, 17-14, 20-16, 3-7, 15-11, 7-10, 16-19, 14-17,
19-24, 17-14, 24-27, 14-17, 27-31, 17-13, 5-9, 10-7, 11-15, 13-17,
9-5, 17-13, 31-27, 13-17, 15-19, 7-11, 27-23, 17-13, 26-22, 6-10,
23-27, 11-7, 5-1, 10-14, 19-15, 14-17, 22-25, 13-9, 27-23, 9-5, 23-18,
17-21, 25-30, 7-3, 15-19, 5-9, 19-24, 3-7, 18-15, 7-3, 15-11, 9-14,
24-20, 14-10, 20-16, 10-14, 11-15, 14-17, 16-20, 17-14, 1-5, 3-8,
20-24, 8-3, 24-19, 14-17, 15-10, 2-7, 10-6, 17-14, 19-24, 7-11, 6-9,
14-10, 9-13, 10-6, 5-9, 6-1, 24-20, 3-7, 13-17, 7-3, 17-22, 3-7, 9-14,
1-6, 30-26, 6-2, 26-23, 2-6, 23-18, 6-2, 20-24, 2-6, 24-19, 7-3, 14-17,
6-10, 19-24, 10-6, 17-13, 6-10, 24-20, 3-7, 13-17, 10-6, 18-14, 7-3,
17-13, 3-8, 14-9, 6-10, 22-26, 10-15, 26-30, 8-3, 9-14, 3-8, 13-9,
15-19, 9-6, 19-16, 6-10, 16-12, 14-17, 8-4, 17-22, 12-16, 10-6, 16-19,
6-2, 19-16, 30-26, 16-12, 20-24, 12-16, 26-23, 16-12, 24-19, 4-8,
23-18, 8-3, 18-14, 3-7, 22-18, 7-3, 14-10, 3-8, 2-7, 11-16, 19-24,
16-20, 24-27, 8-3, 7-11, 12-16, 11-15, 21-25, 18-22, 25-30, 27-23,
16-12, 15-19, 12-8, 22-18, 8-11, 19-16, 11-8, 23-27, 30-25, 27-32,
8-12, 16-19, 25-21, 18-15, 3-8, 10-14, 8-4, 32-27, 4-8, 27-23, 21-25,
14-18, 25-30, 18-22, 8-4, 23-27, 12-8, 15-10, 8-3, 22-18, 30-25, 27-32,
3-8, 10-7, 8-3, 7-11, 3-8, 11-16, 8-12, 32-28, 12-8, 16-12, 8-3, 19-15,
25-21, 15-11, 21-17, 28-32, 20-24, 11-15, 4-8, 15-19, 8-11, 19-28,
11-7, 28-24, 7-2, 12-16, 17-13, 18-14, 2-7, 16-19, 7-10, 14-7, 3-10,
19-23, 13-17, 23-18, 10-6, 18-15, 17-21, 24-19, 21-17, 32-27, 17-13,
27-23, 13-9, 23-18, 9-5, 18-14, 5-1, 14-10, 6-2, 19-24, 1-5, 15-11,
5-1, 11-16, 1-5, 24-20, 5-9, 10-7, 2-11, 16-7, 9-13, 20-16, 13-9,
7-2, 9-5, 16-11, 5-9, 11-7, 9-5, 2-6, 5-1, 7-10, 1-5, 6-1, 5-9, 1-5,
9-13, 10-15, 13-17, 15-18, 17-21, 18-22, 21-25, 22-29

The next generation of WCC will be named "Only Perfect Checkers," or OPC for short.

It will probe perfect play databases in RAM, meaning it will be able to announce win lengths before actually entering into the database positions. No other checker program has this feature.

[liam stephens]

That’s very impressive – a mini marathon.
However, the inescapable logic arising from this approach, begs the question:
When will the 24 piece database be achieved ?
Then, and not till then, let the words “completely solved” be written.

There is a famous dictum:
“If you can’t solve a problem, then there is an easier problem you can’t solve – find it! “
George Pólya

[Ed Trice]

That’s very impressive – a mini marathon.
However, the inescapable logic arising from this approach, begs the question:
When will the 24 piece database be achieved ?
Then, and not till then, let the words “completely solved” be written.

The Perfect Play Databases differ in one very important way than the win-loss-draw databases: Every position has a number stored with it, and this number is the number of moves from the last move in the game. The longest win for any 7-piece ending is 253 moves, which means you can store every entry at 1 byte per position. But, once you go over 255 moves, you need more bits. Technically, 9 bits should be good (511 moves maximum) for quite a few databases yet computed, but it is very difficult to manage "such a mess" since the bits and bytes don't match up so well. It becomes difficult to look up a value when you can store them in 8-bit chunks and you need to line them up 9-bits at a time. What you need to do is allocate 72-bits = 9 bytes at a time, and write 8 values in staggered formation into those 72-bit structures.

Unless, you do what I did, and take the easy way out. I assign 2 bytes to every position, so I have 16 bits to store results with. It's very easy to program. The downside: 2 bytes per position times billions of entries means you need many gigabytes of RAM to compute the data, and quite a bit of space to store the result.

The good news: This data format should work for up to 24 pieces. I can store a win in 65,535 moves using 16 bits per entry.

The better news: Since I probe the Perfect Play Databases in RAM during the search, the program can forecast "perfect announcements" with 10, 12, 14, and even 16 pieces, as long as a forced capture sequence leading to 8 pieces is within the horizon of search. I won't need to solve the "24 piece database" to be able to "completely solve" positions where the capture leads to a pre-computed result.

And, unlike win-loss-draw databases, once you enter into a Perfect Play Database position, no searching is required. The program makes the move leading to the fastest win, or the move leading to the most drawn-out loss, with a single probe, in a microsecond.

[Ed Trice]

Over 10 years ago, Murray Cash published the position above as Red to move and win, with a "longest conversion" count in the 8-piece database wherein 153 moves were required.

I have an improvement to that published play, where the Perfect Play Database can win in 263 plies.

The conversion database and perfect play database agree at the start:

4-8, 3-7, 8-3, 7-10, 21-17, 5-9, 32-28, 31-26, 17-13, 9-14, 28-24, 14-18, 13-9, 10-15, 9-6, 15-11, 6-10, 18-23, 1-6, 11-7, 10-14, 7-11, 6-2, 11-16, 24-20, 16-19...

...but here Nemesis plays 2-6 while Only Perfect Checkers continues with 14-10!

If anyone has Nemesis 2.0 with its conversion databases, I would be interested in playing OPC versus it to see how Perfect Play and Conversion databases battle against one another.

[Event "Only Perfect Checkers 1.0.3 263 ply 8-piece win"]
[Date "2016-08-14"]
[Black "OPC"]
[White "OPC"]
[Result "1-0"]

4-8, 3-7, 8-3, 7-10, 21-17, 5-9, 32-28, 31-26, 17-13, 9-14,
28-24, 14-18, 13-9, 10-15, 9-6, 15-11, 6-10, 18-23, 1-6, 11-7,
10-14, 7-11, 6-2, 11-16, 24-20, 16-19, 14-10, 23-18, 2-6, 18-23,
6-9, 23-27, 9-13, 19-24, 10-14, 24-19, 20-16, 19-15, 13-9, 27-23,
9-5, 26-22, 5-9, 23-26, 9-6, 26-23, 14-10, 15-18, 6-9, 23-27,
16-20, 27-31, 9-13, 18-23, 20-24, 23-27, 24-19, 31-26, 10-15, 27-23, 19-16,
23-27, 15-19, 26-30, 16-11, 30-25, 3-7, 25-21, 19-16, 27-31, 13-9, 21-25,
16-19, 31-27, 7-10, 25-30, 10-15, 30-26, 9-14, 26-30, 19-16, 27-23, 14-9,
23-27, 16-20, 27-23, 9-13, 30-26, 20-16, 23-27, 15-19, 26-30, 16-20, 30-25,
19-24, 27-23, 11-7, 23-18, 7-3, 25-30, 24-19, 30-25, 20-24, 18-14, 24-27,
14-17, 27-23, 17-21, 19-16, 25-29, 16-11, 21-17, 23-27, 17-14, 27-31, 14-17,
3-7, 17-21, 13-9, 21-17, 7-10, 17-21, 9-14, 29-25, 10-15, 25-30,
15-19, 30-26, 11-15, 26-30, 19-23, 30-25, 31-26, 22-17, 14-9, 17-13, 9-6,
25-30, 26-22, 21-17, 22-18, 12-8, 15-11, 8-3, 6-10, 17-21, 18-14,
21-25, 11-15, 25-22, 14-17, 22-25, 10-6, 3-8, 6-1, 25-21, 17-14,
8-12, 15-18, 30-25, 23-19, 25-29, 1-6, 29-25, 6-10, 12-8, 19-15, 8-3,
15-11, 25-29, 10-6, 21-25, 18-23, 25-30, 11-15, 3-8, 6-1, 30-25, 23-26,
25-30, 26-22, 30-25, 22-17, 25-21, 1-5, 21-25, 17-21, 25-30, 14-18, 8-12,
18-22, 12-16, 5-1, 13-9, 22-18, 29-25, 18-14, 25-22, 14-5, 22-26,
5-9, 26-31, 21-17, 16-20, 15-19, 31-26, 17-14, 26-23, 19-26, 30-23, 14-10,
20-16, 9-14, 16-19, 1-6, 19-24, 10-15, 24-27, 15-18, 23-19, 6-10,
19-23, 10-15, 23-26, 15-19, 26-31, 19-23, 27-32, 14-9, 32-28, 18-22, 28-32,
22-17, 32-28, 9-13, 28-24, 23-26, 31-22, 17-26, 24-20, 13-17, 20-24, 26-31,
24-28, 17-22, 28-24, 22-26, 24-28, 31-27, 28-32, 26-23, 32-28, 27-32, 28-24, 32-28, 24-20,
23-18, 20-16, 18-15, 16-12, 15-11, 12-8, 11-4