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.