Since looking at Olithink a few days ago, I’ve been re-bitten by the “write your own game” bug, and dusted off milhouse, my Checkers program that I started a couple of years ago, but which I abandoned because I felt that it hid some obscure bug. Today, I tried adding some additional code to determine where the bug is hiding (optimistically assuming that there is only one, which frankly, is overly optimistic). In trying to figure it out, I tried it in a simple 2 king versus 1 king endgame. Black here can force a win by driving white into the black corner at 4. If White is allowed to doddle around in the double corner, there is no way for Black to force the win. So, in this situation, with Black to move, the proper move is 14-9 14-18. This forces white to retreat closer to the black corner (2-7) and you can eventually (although, to me, novice that I am, it’s still a bit tricky to work it all the way out) trap him in the corner. White cannot movr back with 2-6 (which loses instantly, so response with 2-7, to which Black response 18-15. Now, White is well and truly screwed. If he returns to 2, then Black responds with 15-11 and wins, or if White retreats to 3, the 15-11 pins him against the wall and White loses again. But stupidly, my program seems to love the 1-5 move, which frees white to move back to the double corner, and while white gains no safety, it doesn’t make any headway to capturing him.
Some bug is hiding in here, to be sure.
Addendum: if I’ve botched the analysis of this, then I am confessing that it is just as likely that bugs remain in my own understanding of the game, and that is as likely to hinder progress as bugs in my program.
Addendum2: The problem appears to lie with my transposition tables. When I disable them, it finds the appropriate moves. I’ll have to think really hard to figure out the bugs.
Addendum3: Here’s another example. It takes way too long to complete without transposition tables, but it does seem to find the right answer.
milhouse: puzzle 80
Puzzle SIMPLE TEST BUG loaded.
Color is set to white.
+--------+
| - - - -|
|- - - - |
| - - - -|
|- - - - |
| - - R -|
|- - - - |
| - R - -|
|- - - W |
+--------+
milhouse: playout
1. ... 1-6
2. 7-2
2. ... 6-1
3. 14-10
3. ... 1-5
4. 2-6
4. ... 5-1
5. 6-9
5. ... 1-5
6. 10-14
6. ... 5-1
7. 9-5
7. ... 1-6
8. 5-1
8. ... 6-2
9. 14-18
9. ... 2-7
10. 18-15
10. ... 7-2
11. 15-11
11. ... 2-6
12. 1x10
+--------+
| - - - -|
|- - - - |
| - - - -|
|- - - - |
| - - - -|
|- R R - |
| - - - -|
|- - - - |
+--------+