Dusting off Dusting off Milhouse…

A year ago, I blogged that I had dusted off my old checkers program, named Milhouse, and had uncovered a bug in my transposition tables. Today, a year later, I still haven’t debugged it entirely. I tried adding routines to access the Chinook endgame database files to it, but it’s not quite there yet: it seems to go seriously astray in certain positions. I’ve got a few goals in this project which are as yet unrealized:

  • Make the endgame stuff work.
  • Tune the evaluation function.
  • Develop a program to generate a good opening book.
  • Make a nice interface for it, and release it to the universe.

Doubt I’ll get to any of this today.


Addendum: It can solve some pretty tricky checkers problems. This position seems unobvious to checkers novices like myself. White is to move and win:

LOADED puzzle 101: Rob Pike, Puzzle #28.
Color is set to white.
           White  
        +--------+
        | W - - R|
        |- - r r |
        | - - - w|
        |r r - - |
        | - - R -|
        |- - r r |
        | W - - W|
        |- - r - |
        +--------+
           Red

On the other hand, puzzles like this one remain elusive. The chinook database reports that this position is a win for red, but it’s pretty difficult. It takes milhouse a 22 ply search to identify the path which leads to a strong advantage. Ironically, I find this position fairly easy to guess the right answer. Red has both white men pinned, and it seems releasing those pins would probably not be a good idea. This leaves the red man at 15 as a possible mover. You could move to 19, and force the white king to give way, and then march down the side to get kinged, but what’s less obvious is that you can then drive the white king to the single corner where it too can be pinned. Of course, I’m a checkers idiot, so what do I know. The winning line appears to be to force an exchange of the checker originally at 15 for the white king, and then capture the white checker originally at 12 which gets pinned in the corner. Then you have a classic 2:1 king endgame.

LOADED puzzle 85: 2nd position, easy, from The Checker Maven.
Color is set to red.
           White  
        +--------+
        | - - - -|
        |W - - - |
        | - - - -|
        |- - - - |
        | - r - w|
        |w R - - |
        | - - R -|
        |- - - - |
        +--------+
           Red