The 8-piece suicide checkers database

It's been a long time since my last post - but that doesn't mean I wasn't doing anything! It just took a long time to do it. But as of today, my suicide checkers 8-piece database is ready. It took about 1 month to compute on an Athlon64 3000+ with 1.5GB memory, and another 2 days to compress it. I decided to compute it after Ed Gilbert told me I was wasting my time computing a suicide checkers opening book with "only" the 7-piece database. I realized he was probably right, and so I stopped that opening book computation and went for endgame database computation. Adapting the database-building code from 7-piece to 8-piece should have been straightforward, but of course there were some little traps into which I promptly fell: In regular checkers, I didn't compute the lopsided databases (like 5-3, 6-2 and 7-1 pieces), and I didn't have any problems with my code. In suicide checkers these databases are important too, and my code to compute the binomial coefficient of n and k (I hope that's what it's called in English; it's = n!/(k!*(n-k)!) ) promptly overflowed past the size that a 32-bit integer can hold, and my database builder crashed when computing the 7-1-piece database. Next, Suicidal Cake crashed when I tried to use it with the 8-piece database - I noticed that I had a hard limit of 25 database files which I could open in my 8-piece database code. But with the new lopsided databases, I needed more, and that caused the crash. After fixing all these bugs, it now seems to be working.

The database takes 113GB uncompressed on my disk, and it is compressed to 18.4GB - that's just over a 6-fold compression. The regular checkers 8-piece database compresses over 4 times better, which shows that the suicide databases are more irregular. I'm surprised that I can even use the database with any efficiency at all, since it is so large, but Ed Gilbert already predicted that this would be the case. He has experience with even larger databases, having computed the 9- and 10-piece databases for regular checkers.

Enough for now, I am going to test my new toy!

Ed Gilbert finishes the 10-piece endgame database!

Over the past approximately 2 years, Ed Gilbert (the author of KingsRow) had this completely crazy project of building the 10-piece database on a couple of "normal" PCs. Crazy because building endgame databases is in principle something very simple and straightforward - if you have enough RAM. PCs with 32-bit operating systems are limited to about 2GB RAM, which is just fine for the 8-piece database, but very little for the 10-piece database. Ed devised lots of clever schemes to circumvent these limitations; you can read the whole story on his page on building the 10-piece database.
Congratulations, Ed!

The suicide checkers endgame database

When I computed the suicide checkers 6-piece endgame database, I was in for an unpleasent surprise: My compression program which worked fine for the regular checkers endgame database didn't do a good job at all compressing the suicide checkers database. While the regular 6-piece database is only about 40MB, the suicide 6-piece database is a full 150MB, nearly 4 times larger. Why is this? To understand why it doesn't compress well, you first need to know how the compressor works: it uses a scheme known as "run length encoding" or RLE for short. RLE replaces "runs" of the same value in the database with a pair of values: the length of the run, and the value of the run. If this sounds gibberish, an example might help. Let's say you have a way of enumerating all positions in your database from 1...N. You write down the value for every position and get something like

WWWWWWWWWWDDDDDDDDDDWWWWWWWWWWDDDDDDDDDD....

with W a win, D a draw and L a loss - none of them present in the above database. The compressor now works by storing (10,W), (10,D), (10,W), (10,D) instead. In many databases the runs reach amazing lengths, especially in lopsided databases where most positions are just a win for the stronger side. There are of course the positions where one side can capture something, and they usually have more or less random results. For this reason, positions with captures are just removed from the database; your program will have to look one ply deeper and look up the position after the capture. This results in nice compression ratios for regular checkers, the compressed database is approximately 10x smaller than the uncompressed database. Now you can probably guess why the suicide checkers database doesn't compress well: The results in those databases are much less monotonous, and therefore this compression scheme is no longer particularly efficient.
Again, an example might make things clearer: In regular checkers, all positions with 2 vs 1 king are wins for the 2 kings if you remove the positions with a capture, with only one rather pathological exception; red kings on 3 and 12 and a white king on 11, with red to move. Therefore, this database compresses exceptionally well. In suicide checkers, 2 vs 1 king is normally a win for the side with 2 kings, however, if you played through the game I posted yesterday, you can see that in the endgame red could get 2 kings vs 1, but he would lose all the same. Therefore, the 2 vs 1 king database in suicide checkers has wins as well as losses in it, and doesn't compress well. On another note, this also means that the database is more important in suicide checkers than in regular checkers: Obviously, it would be quite difficult to write a heuristic that can guess the likely outcome of the game with 2 vs 1 kings on the board, something which is very simple for regular checkers. And of course for more complicated endgames, it gets even more difficult.