Ed Trice, who with Gil Dodgen computed the Perfect Play databases, sent along the following excellent explanation. Many thanks!
Let's start with the Chinook databases, which contain only 'win-loss-draw' information for any position. There is no information about how far away the win actually is. The good news is, as your program searches, it can read this data in RAM, and send the information back "down the tree" to the program. So, if there are any losses within its search horizon, the program will avoid them. If the program is in trouble and it finds a miracle draw, it will likewise pitch half its army if the result is a barely draw ending. For the most part, the program will start to find wins in the database, and head for them, preventing the human players from achieving a draw.
These databases are highly compressed, but not in the sense of "pkzip". The databases might look like this:
draw, draw, draw, win, draw, loss, loss, loss, win, win, win, win win, win, win, win, win.
The "compression technique" essentially does this:
draw(3), win, draw, loss(3), win(9).
This is a much more compact representation.
You can imagine in the 4 kings vs. 4 kings datbase, with one king hanging that can be captured by the side to win, no matter where the other kings are placed in safe havens around the board, the side to move can usually win. How many positions might there be in a row? How about 31 x 30 x 29 for your remaining kings, which would amount to 26,970 in a row! You can imagine there are many clusters of jumps that occur in these databases, and all of these "consecutive runs" can be stored as one entry by mapping the starting and stopping point of these occurences.
You saw on the kingsrow website that Ed Gilbert is saving "Distance to Conversion" in his databases as well. This tells you how far away a checker promotion OR a capture is from the present position, but you don't know which one.
This has a huge benefit in king-heavy endings with 1 or 2 checkers, as programs cannot search far enough ahead to find a forced winning line. Just as an example, set up this position:
Black checkers: 3, 10, 8
White checker: 12
Black King: 4
White Kings: 9, 21
Black to move and win in 127 moves.
While the first few moves are easy, once it plays into 3 kings + 1 checker vs. 3 kings, it makes Strickland's Position look like a piece of cake! Now the Distance-To-Conversion (DTC) database is a big help.
The irony is that a DTC database plays like an idiot in simple positions! Why is this so? It will prefer to promote a checker to a king in 1 move over a win in 2 moves. Here is the prime example:
White king: 31
Black checker: 25
Black king: 18
Black to move wins easily with 18-23, but a DTC database will promote the checker instead! Remember, the DTC assumes a conversion in fewer moves is the best play, so converting in 1 is better than "winning in 2". The DTC database has no information regarding the distance to the win.
This is why the "perfect play" databases are the best. They will ALWAYS win the quickest, and avoid losses the longest.
In one of the papers I published, I gave Kingsrow the winning side of that first position shown above, and it could not win against the perfect play database that was defending the loss. Why? The perfect play databse did not have to search, it could play the move leading to the longest loss, which was far, far beyond the searching capabilities of Kingsow. I played it against Wyllie a well, and it could not win either.
The disadvantage of the perfect play databases is that they are huge. They must record every database entry without using the "consecutive run" technique. So, they reside on the disk.
If you have WCC Gold Plus, set up this position:
Black checkers: 5,9
Black king: 25
White checkers: 17,30
White king: 18
This is the longest win in the 6-piece database. You will see WCC announce the distance-to-win all along the way.
This is what the "perfect play" database is all about.
---Ed Trice 01/29/2005