On the futility of expert checkers play through deep searches alone…

I really can’t put off creating an endgame database for my checkers program for much longer. I’ve been studying the so-called “First Position” for a while, and it’s basically hopeless to find the way through to the win for white from this position:

	   White  
	+--------+
	| - - - -|
	|- - - R |
	| - - - -|
	|- - - - |
	| - - - -|
	|- w - - |
	| - - w -|
	|- r - - |
	+--------+
	   Red

What’s so difficult about this? It’s a very, very tricky position. As Jim Loy says, “The procedure: Force the piece to advance by immobilizing the king. The king and piece cannot both fit in the double corner, so the king is forced out, where his situation is hopeless.” Easier said than done! Try following his analysis all the way through. Milhouse can’t even seem to find the right winning combination from Figure 8, falling into a draw by repetion where it can’t make any headway in self play.

Here’s a link to the “perfect play”. 93 moves. First Position with Optimizations

Addendum: During play against the novice level of Chinook, I ended up on the losing side of a 4 on 3 king endgame. But here’s the thing: Chinook seemed to take a very, very long time in converting the endgame into the more manageable 3 on 2 endgame. It does point out a problem though: the endgame databases contain only whether a given move is a win, loss or draw. In many cases, all possible moves are still wins, but you may not actually make any headway in reaching the endgame. For instance, check out the following position queried from the endgame database:


4 on 3… which way to go?

All available moves for white are wins (not too hard to believe, since white is up a king), but the question remains which move should I make? If you can’t see a “conversion” (an exchange or capture which simplifies the position) in your search depth, then you aren’t guaranteed to make any headway towards winning the game, and you kind of march around, hoping to stumble into the winning line.

You can build a database which stores the optimal move at any given position, but of course that takes more memory. Still, I think the 5 piece subset, and probably the 6 piece “perfect play” endgame databases are pretty reasonable given modern machines. That’s where I’m heading.