Author: David Eppstein
Date: 07:20:40 07/25/98
Go up one level in this thread
On July 25, 1998 at 09:08:24, Don Dailey wrote: >In my program I just do not store draw scores. I make those >scores unique by multiplying every score times two and making >the draw score the only ODD score. This is NOT a perfect >solution but I do not know what else to do. There are some draw scores which it is safe to hash (endgame tablebase). Your approach seems likely to cause subtle bugs, since repetition draws can also change the evaluation of lines in which the overall score is not drawn. Here's a simple algorithm (I haven't actually tried this) for detecting whether an eval has been "tainted" by repetition scores. Note that artificially setting some values to zero in a minimax tree can only bring the overall eval closer to zero (easy proof by induction on number of zeros), so if an eval is tainted, the "true" eval (without repetition detection) should only be farther from zero. Maybe this would not quite be true in practice because the eval can affect the shape of the tree that is searched (due to pruning and extensions) but it seems safe enough to take this as a general principle. So, modify the evals you're using so that the low bit stores a flag for whether the eval is tainted. Then do the usual negamax alpha-beta, treating this flag specially. A normal eval returns a number with the tainted flag cleared. A repetition detection returns a zero with the tainted flag set. A fail high >0 or fail low <0 is always untainted. Otherwise, if the result of an alpha-beta search is >=0, it is tainted if any of its nonnegative children were tainted. And if the result is <0, it is tainted if the PV is tainted. Nonzero tainted evals can be stored in the hash table if you only use them as upper or lower bounds as appropriate. Has anyone tried a scheme like this? How badly did it degrade hashing compared to the usual hash-everything approach? My own program simply does not detect repetition. The last time I tried it, I neglected to change my hashing at all. This caused major problems with draw scores escaping into the hash table and causing my program to play horrible blunders in which it thought some completely losing move maintained a draw. So treating this problem carefully is certainly important.
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.