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.01 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.