Author: Robert Hyatt
Date: 06:40:32 02/04/99
I found a pretty neat bug (not really a bug, more like a design problem)
last night. Crafty had played zarkovx on ICC, and was in a reduced material
position. It was getting close to repeating a position for the third time
when it announced a mate in 70 (tablebase hit). The next move it announced a
mate in 73, and after the opponent's next move it realized this was a dead draw
by repetition.
Here's what was wrong, which might serve as a warning for those of you doing
this in your program.
I obviously don't do a repetition check at ply=1 in the search, because by the
time I get there, I _must_ choose a move. If it is drawn at the root, I don't
even call search. The first time I do a repetition check is at ply=2. In this
game, crafty could make 1 move and not repeat, but after any _other_ move, the
next move by the opponent would repeat. What happened was it tried each root
move (remember, move A is a mate in 72 that does not allow a repeat of a prior
position, while any other move leads to a mate in 70, but the next opponent move
is a draw by repetition for any of them)
Back to the idea (the previous sentence was too long to continue, IMHO) when it
tried move A, at ply=2 it did the rep check and found 'no rep' and then it
probed the database and found mate in 73. OK so far. But then it tried the
next choice (again no rep, but if it does this the opponent can choose a move
that is a 3rd rep) and found no rep, but a database hit with a mate in 70. 70
is better than 73, so it took this move. And played it, and found that the
opponent instantly repeated and drew.
The fix was to _not_ probe at ply=2 any more... which means that now, Crafty
has to make a move, _and_ the opponent has to make a move without repeating the
position, _before_ I probe the database at ply=3 after the rep check. Solved
this rather ugly (and uncommon) problem.
My search looks like this:
Search(alpha,beta,etc){
if (repcheck) return;
if (EGTBprobe) return;
do {
normal move selection/recursive search
}
return;
}
The problem was that I did the EGTB probe at ply=2, _before_ my opponent had a
chance to make a move. And EGTB has _no clue_ about what has already happened
in the game. This has been around a while, hope this explanation is clear
enough to help others avoid debugging it. :)
Let me know if there are questions...
Bob
(and yes, I said mate in 70. The record on ICC (for crafty, anyway) is now a
mate announcement of mate in 138. This in a fairly complex ending that Crafty
managed to turn into a ugly KPP vs K ending that was a mate in over 120. But it
had already searched _very_ deep before it found the TB hit, to give that huge
mate in 138 score.)
If anyone is interested, I now have a 'dynamic depth adjustment' algorithm in
crafty to prevent the database probes from taking my normal 600-800K nodes per
second down to 10K or so. I now usually never drop under 300K and it is working
very well...
Bob
This page took 0.05 seconds to execute
Last modified: Thu, 07 Jul 11 08:48:38 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.