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.