I dusted off my copy of Schaeffer’s book One Jump Ahead: Challenging Human Supremacy in Checkers and reread the description of the match between Arthur Samuel’s checker playing program and Robert Nealy. Samuel’s program managed to beat Nealy, who advertised himself as a master, but in fact he makes a number of rather questionable (I’m being kind) moves that suggest he wasn’t really all that he said he was.
As part of my testing, I dusted off this particular position from the game as a challenge for milhouse to work through. Nealy is playing white, and moved 32-27. This is widely considered to be a terrible move: Schaeffer claims that the game was a virtual draw to this point, after this move, Chinook was capable of doing an 11 ply search that put it into its end game database and assured a win for Black. Interestingly enough, when confronted with the same position, milhouse made the same choice! It views the scores for all the possible alternatives after an 18 ply search as:
Puzzle Samuel Checkers v. Nealey loaded. Color is set to white. +--------+ | w - - -| |- - w - | | - - w w| |w r - - | | - - r -| |- - - - | | - r - -| |- r r - | +--------+ milhouse: annotate 20-16 : -43 21-17 : -201 22-17 : -73 22-18 : -9985 26-23 : -193 32-27 : -5 32-28 : -116
The move 20-16 is the preferred line. I don’t find this too surprising that milhouse gets this wrong: I don’t have a very strong evaluation function here, and in particular I don’t give any special bonus to protecting the rear ranks. I obviously need some additional work. Playing the game out at 18 ply doesn’t follow the historical line: we end up with a pretty standard draw type situation.
Addendum: Martin Fierz has the entire game online. On move 25, Samuel’s program moves 2-6, and it appears that with an 18 ply search, milhouse greedily takes the same move, which Fierz labels as “awful”. Lots left to do.
Addendum2: In the same position above but with a 22 ply search, milhouse returns the correct 23-18 move, although it still doesn’t see it as a win.