brainwagon

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.