Wednesday, August 30, 2006

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!

No comments: