Perfect Play Database for 8-pieces

Discussion and analysis about certain positions.

Perfect Play Database for 8-pieces

Postby EdTrice on Sun Jan 07, 2007 11:49 pm

Image

After a long hiatus, I decided to re-write the code to solve the endgame databases that come with the free version of WCC. There are actually 4 different database compression/lookup schemes in that hodge-podge of code.

1. Gil's 4-piece perfect play database from 1992, where he fit all 7.5 million positions with the distance-to-win for each onto a single 800K floppy disk. This was an incredibly convoluted scheme where he saved distance-to-win only for the losses with white to move. A "win" was found by looking at a move and seeing that every reply was in the "lost" database, very time consuming, but an amazing compression technique.

2. The Schaeffer 5- and 6-piece databases. We never generated our own once his were made available. Later on, we "seeded" the perfect play databases with his "win-loss-draw" scores, then we iterated over that to determine the distance-to-win for perfect play. Again, messy, messy code.

3. My 7-piece database, which I generated without any subdivisions. It compressed extremely well with very long runs of jumps that could be removed.

4. The Trice-Dodgen 8-piece database with some of the Schaeffer 8-piece database indexing functions. Basically, we generated our own database, but used many of Schaeffer's indexing formulae to "map" where the positions were, again, a complete mess when you look at the two different approaches used by different teams. It is very much like hooking up a typewriter to a TV and trying to make a computer out of it.

Now, the new Only Perfect Checkers program will have one code module that generates, probes, and compresses the databases. Basically, less code than appears in this message can generate perfect play databases of any size, up to an including 10-pieces. How long it will run is a different story.

To test out the algorithm, I quickly generated "kings only" database slices, up to the 8-piece slice of 4 versus 4.

I just received an email from Ed Gilbert, and my new database win-loss-draw counts agree with his for this slice.

Sadly, the longest win with 4 kings versus 4 kings is only 2 plies longer than the longest win for 4 kings versus 3 kings. And, since all of the 4x4's convert into 4x3's rather quickly, they are ALL uninteresting!

This is one case where a longest "conversion win" would be more interesting than the longest "perfect play" win. If anyone has the longest conversion win for 4 kings versus 4 kings, I would be interested in seeing it.

Anyway, here are all 40 of the longest wins for 4 kings versus 4 kings. Most are reflections/rotations of the others with just a few different ways to win. Each requires 115 plies in order to win.

===========

4 white kings vs 4 red kings, white to move and win in 115 plies

white kings: 1, 7, 21, 29 red kings: 5, 11, 18, 26
white kings: 1, 21, 23, 29 red kings: 5, 17, 18, 19
white kings: 2, 3, 8, 26 red kings: 1, 6, 15, 16
white kings: 2, 3, 8, 27 red kings: 15, 19, 26, 31
white kings: 2, 9, 20, 29 red kings: 5, 10, 17, 26
white kings: 2, 20, 27, 29 red kings: 17, 19, 26, 32
white kings: 2, 21, 23, 29 red kings: 1, 10, 15, 22
white kings: 3, 4, 5, 17 red kings: 1, 15, 16, 22
white kings: 3, 4, 5, 19 red kings: 1, 7, 15, 23
white kings: 3, 4, 13, 19 red kings: 5, 11, 14, 18
white kings: 3, 4, 14, 26 red kings: 1, 9, 15, 16
white kings: 3, 8, 9, 17 red kings: 1, 7, 15, 22
white kings: 3, 8, 9, 17 red kings: 1, 15, 16, 22
white kings: 3, 8, 9, 19 red kings: 1, 7, 15, 23
white kings: 4, 6, 13, 31 red kings: 1, 7, 14, 16
white kings: 4, 10, 12, 31 red kings: 11, 18, 23, 32
white kings: 4, 10, 12, 32 red kings: 14, 15, 16, 28
white kings: 4, 12, 17, 23 red kings: 7, 15, 27, 28
white kings: 4, 12, 26, 32 red kings: 7, 15, 22, 28
white kings: 4, 13, 24, 31 red kings: 7, 16, 23, 28
white kings: 6, 7, 21, 25 red kings: 5, 11, 17, 18
white kings: 6, 7, 21, 25 red kings: 5, 11, 18, 26
white kings: 6, 21, 23, 25 red kings: 5, 17, 18, 19
white kings: 6, 25, 30, 31 red kings: 2, 7, 14, 18
white kings: 7, 19, 29, 30 red kings: 17, 18, 24, 32
white kings: 7, 25, 30, 31 red kings: 17, 18, 27, 32
white kings: 8, 9, 12, 20 red kings: 10, 13, 15, 17
white kings: 8, 10, 12, 27 red kings: 14, 15, 16, 28
white kings: 8, 12, 17, 20 red kings: 7, 15, 24, 28
white kings: 8, 12, 26, 27 red kings: 7, 15, 22, 28
white kings: 8, 12, 26, 27 red kings: 15, 16, 22, 28
white kings: 10, 16, 21, 29 red kings: 5, 6, 18, 26
white kings: 13, 16, 21, 25 red kings: 5, 9, 18, 26
white kings: 13, 21, 24, 25 red kings: 16, 18, 20, 23
white kings: 14, 20, 29, 30 red kings: 15, 19, 22, 28
white kings: 14, 24, 25, 30 red kings: 10, 18, 26, 32
white kings: 14, 28, 29, 30 red kings: 10, 18, 26, 32
white kings: 16, 24, 25, 30 red kings: 11, 17, 18, 32
white kings: 16, 24, 25, 30 red kings: 11, 18, 26, 32
white kings: 16, 28, 29, 30 red kings: 11, 17, 18, 32
--Ed
User avatar
EdTrice
 
Posts: 97
Joined: Fri Jul 14, 2006 2:39 am
Location: Philadelphia

Return to Positions

Who is online

Users browsing this forum: No registered users and 1 guest

cron
class=