I’ve been entering puzzles from various checkers books that I have lying around as test cases for my checkers program milhouse. Oddly enough, I found the following puzzle to be fairly interesting. White is to move and win. The answer to solving it (as obviously contrived as it is, it would be very, very hard to get this position in a real game) occurred even to me, as much of a complete novice at checkers as I am.

Of course, as easy as the answer is, it is pretty hard for normal alpha-beta search to find the appropriate winning path. It requires a 28 ply search (fully 14 moves) to find the rather obvious win. Milhouse scores the position as -1169 (nearly twelve men down) with its normal default 15 ply search), and takes 9.4 seconds. To search to the required 28 ply takes a long time. Minutes at least, I killed it.

But I have other search strategies programmed, including Aske Plaat’s MTD(f) algorithm.. I’m not certain exactly why it works to well in this case, but it finds the 28 ply solution in just 0.554 seconds.

A brief history and bibliography of checkers research.

As part of my ongoing checkers work, I downloaded the Open Checkers Archive and wrote a simple bison/flex parser to read in the data. I am not illiterate when it comes to bison and flex, but it’s usually long enough between uses that it takes me an hour or two to tinker these things together. But, an hour or so later, and I’ve got a simple parser that can read all the games. It doesn’t do much of anything with the games at the moments, but having a parser allowed me to gather some really simple statistics about the archive. There are 22621 games in the archive, and totalling 1158096 moves. There are 276921 single jumps, 25405 double jumps, 2406 triple jumps, and just 7 quadruple jumps. There are 3626 wins for Black, 4803 wins for White, and 14192 draws.

I don’t know exactly what I’ll use this for quite yet, but I’m sure something will come to me.