My checkers playing program milhouse is currently advancing at a good clip. I’ve added iterative deepening and a transposition table, and probably will add a history heuristic for move reordering to improve the search further. I’ve also started typing in a bunch of problems from Pike’s Little Giant Encyclopedia of Checkers Puzzles, and used them as test cases. It’s able to solve lots of them, but also stumbles on a few. I’m not certain that the basic alphabeta framework is completely bugfree (in fact, I’m pretty sure it is not) but it is still somewhat gratifying to find it solve problems like the one below:

EXECUTING PUZZLE From D. Oldbury, WHITE TO MOVE FIRST
        +--------+
        | - - - -|
        |- w r R |
        | - w w -|
        |r w w - |
        | - w w R|
        |r - w - |
        | - r w -|
        |- r - r |
        +--------+

1.      ...     27-24 [10001]
2.      20x27 [-10001]
2.      ...     14-9 [10001]
3.      7x14 [-10001]
3.      ...     15-11 [10001]
4.      1x10 [-10001]
4.      ...     11-7 [10001]
5.      13x6 [-10001]
5.      ...     18x2 [10001]
6.      25x18 [-10001]
6.      ...     23x14 [10001]
7.      10x17 [-10001]
7.      ...     19-16 [10001]
8.      3x10 [-10001]
8.      ...     2-6 [10001]
9.      12x19 [-10002]
9.      ...     6x13 [10003]

        +--------+
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - W|
        |- - - - |
        | - - - -|
        |- - - - |
        +--------+

transposition: 61096470 lookups, 7241926 finds, 
    53839352 stores, 1048576 entries

[tags]Checkers,Programming[/tags]