Daily Archives: 4/22/2009

Milhouse still hides some mysteries…

So, I was doing some more testing this morning, and noticed an anomaly in my checkers program, Milhouse. Consider the following position:

LOADED puzzle 177: Testing move ordering..
Color is set to red.
           White
        +--------+
        | R - - R|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - W |
        +--------+
           Red

This has a 33 ply solution, which milhouse finds pretty easily, yielding the following statistics:

final score = 10000
transposition tables
... 1049502 gets (1015774 tier0 / 0 tier1 / 33728 failed)
... 757147 puts (33728 tier0 / 723419 tier1) (298250 L/365516 X/93381 U)
... 349949 chinook database accesses.
        1. 29-25
1.173 seconds elapsed.

Not bad. The caching works reasonably well, and I only need to access about 349K positions from the Chinook endgame database (which is basically the entire thing a couple of times over, which isn’t good, but not fatal). But let’s try the same position, but with the board rotated 180 degrees:

LOADED puzzle 178: Testing move ordering..
Color is set to red.
           White
        +--------+
        | W - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |- - - - |
        | - - - -|
        |R - - R |
        +--------+
           Red

Much to my chagrin, this took a lot longer, but also found a shorter solution (29 ply). Grumble!

... 78459032 gets (78280388 tier0 / 14207 tier1 / 164437 failed)
... 65025084 puts (164623 tier0 / 64860461 tier1) (19696902 L/36414475 X/8913707 U)
... 34724781 chinook database accesses.
        1. 1-5
55.834 seconds elapsed.

I’m guessing that move ordering plays a huge role in this (I haven’t implemented even the most rudimentary version). My move generator basically generates moves in a fixed order, which means that the entire search tree is searched in a consistent order. It’s not surprising particularly that this order doesn’t cause optimal pruning of the search tree. My guess is that implementing some form of move ordering is a good idea. I suspect I can do it by just searching the “best move” previously recorded in the hash table before all others. That should be pretty straightforward to implement.

I’m still a little concerned about the discrepency in the depth of searches.

I’ll ponder that some more later.

Some advances on Milhouse…

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