Some advances on Milhouse…

April 22, 2009 | Checkers, My Projects | By: Mark VandeWettering

I finally got around to totally ripping out the old implementation of transposition tables, and installing a new one based upon hints I read about on various web pages, mostly originating with some of the ideas for cache management that Ken Thompson implemented for his chess program Belle. The idea is to implement two caches, one of which is used to store board positions near the root of the tree, the other which contains all other nodes. The idea is that if you cache near the leaves, then you are likely to need the same values again soon, but if you cache higher up in the tree, you are more likely to save yourself long searches.

Using this, I managed to get my “two king vs. one king” endgames working, searching out 33 ply in just a few seconds.

LOADED puzzle 173: Simple Tests (harder)..
Color is set to red.
           White  
        +--------+
        | R - - R|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - W |
        +--------+
           Red    

milhouse: depth 40
search depth is now 40
milhouse: playout
     1. 29-25 {10000}   1-5 {-10000}
     2. 25-21 {10000}   5-1 {-10000}
     3. 21-17 {10000}   1-5 {-10000}
     4. 17-13 {10000}   5-1 {-10000}
     5. 32-27 {10000}   1-5 {-10000}
     6. 27-23 {10000}   5-1 {-10000}
     7. 23-18 {10000}   1-5 {-10000}
     8. 18-14 {10000}   5-1 {-10000}
     9.  13-9 {10000}   1-5 {-10000}
    10.   9-6 {10000}   5-1 {-10000}
           White  
        +--------+
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - R -|
        |- - - W |
        +--------+
           Red    

milhouse: playout
     1. 14-10 {10000}   1-5 {-10000}
     2.   6-1 {10000}   5-9 {-10000}
     3.   1-5 {10000}  9-13 {-10000}
     4. 10-15 {10000} 13-17 {-10000}
     5. 15-18 {10000} 17-13 {-10000}
     6. 18-22 {10000}  13-9 {-10000}
     7.  5x14 {10000}
           White  
        +--------+
        | - - - -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - R -|
        |- - - - |
        | - - - -|
        |- - - - |
        +--------+
           Red    

milhouse:

I then tried to play a game against the novice level of Chinook. I ended up in this position, with Chinook playing white and Milhouse black. Chinook kept bragging that I was in “serious trouble”, but the reality is that the position is drawn, and once in a six piece drawn end game, Milhouse won’t stumble (barring bugs) so I called this a draw.

board3