9-Piece Perfect Play Databases

[Ed Trice]

This is the longest win for white to move in the 5 kings vs. 4 kings database.

It requires 151 ply from start to finish.

Code: Select all

XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X   W   X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X       X#######X   R   X#######X   R   X#######X       X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   W   X#######X   R   X#######X       X#######X   W   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X#######X       X#######X       X#######X       X#######X       X
X#######X       X#######X   R   X#######X       X#######X       X
X#######X       X#######X       X#######X       X#######X       X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
X       X#######X       X#######X       X#######X       X#######X
X   W   X#######X       X#######X       X#######X   W   X#######X
X       X#######X       X#######X       X#######X       X#######X
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX


White to move and win in 076 moves.

001.  xx-xx  12-08
002.  19-15  09-13
003.  18-14  01-06
004.  07-03  08-12
005.  03-07  06-02
006.  07-10  12-08
007.  14-18  13-17
008.  18-23  17-21
009.  10-14  02-06
010.  11-16  08-03
011.  16-11  21-25
012.  14-18  06-09
013.  15-19  09-13
014.  18-14  25-21
015.  19-15  13-17
016.  15-10  17-22
017.  10-15  03-08
018.  14-09  22-17
019.  11-16  08-03
020.  15-11  21-25
021.  16-19  25-30
022.  19-24  31-26
023.  24-19  26-22
024.  19-15  30-25
025.  23-27  22-26
026.  15-19  25-21
027.  09-06  03-08
028.  11-07  17-14
029.  27-32  14-18
030.  32-27  26-30
031.  19-24  21-17
032.  27-31  17-14
033.  24-28  18-15
034.  07-11  14-18
035.  11-07  30-26
036.  31-22  18-25
037.  28-24  08-03
038.  07-10  15-11
039.  24-27  04-08
040.  27-24  08-12
041.  24-27  12-16
042.  27-31  11-07
043.  10-14  07-02
044.  14-09  03-07
045.  31-27  16-11
046.  27-31  11-15
047.  31-27  07-10
048.  06-01  25-22
049.  27-31  15-18
050.  31-27  22-17
051.  09-13  10-15
052.  13-22  18-25
053.  27-31  25-22
054.  01-05  22-18
055.  31-27  15-10
056.  27-32  02-06
057.  32-27  06-01
058.  27-32  18-23
059.  32-28  01-06
060.  28-32  10-15
061.  32-28  23-19
062.  28-32  19-24
063.  32-28  06-10
064.  28-19  15-24
065.  05-09  24-19
066.  09-05  19-15
067.  05-01  10-14
068.  01-05  15-10
069.  05-01  14-09
070.  01-05  10-14
071.  05-01  09-05
072.  01-06  05-01
073.  06-02  14-18
074.  02-07  18-15
075.  07-03  15-11
076.  03-07  11-02

[Ed Trice]

I played through this 9-piece ending with WCC Platinum III. It had the 8- and 7-piece databases loaded into its maximum buffer size of 2 GB. This is an unfortunate relic of older, crappy versions of the Windows operating system that were not fully 32-bit compatible. Sadly, WCC cannot ever use more than 2 GB of RAM.

Anyway, I was curious to see how soon WCC could identify a "database win" from the longest win for 5 kings vs. 4 kings. As you can see from the diagram above, the program had to play 32 moves into the position and still search 25 ply ahead to determine it was impossible for the losing side to escape the databases.

This demonstrates an interesting point: WCC tries to find ways to avoid swaps into the database on the losing side, while the winning side tries to force the issue as early as possible. Even so, the Perfect Play database still vastly outperforms it on several fronts.

1. The perfect play database never needs to search, and it knows the distance to the final jump, instantaneously.
2. When probed in RAM, the perfect play databases will find definitive solutions from a much smaller tree, and thereby generate much quicker solutions to the optimal path, both in nodes explored, and in time.
3. Because the perfect play database does not remove jumps from its databases, probing them in RAM is many times faster than probing win-loss-draw databases.

I am in the process of hooking up the perfect play databases to my new program, to be named Only Perfect Checkers. Because OPC will have such incredibly expensive hardware requirements, the only way I can make it available is through a web interface like Chinook. The program requires 128 GB of RAM and at least 8 CPU processors, not to mention about 20 terabytes of disk space.

[Ed Trice]

There is a new ending that has been solved: 4 kings + 1 checker vs. 4 kings.

Amazingly, the longest win is 291-ply, the same length as the longest known win so far for 8 pieces. Here is the position.



White to move wins in 291.