Author: Don Dailey
Date: 08:13:15 07/25/98
Go up one level in this thread
On July 25, 1998 at 10:20:40, David Eppstein wrote: >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. I only have a unique draw score for repetition, I use -1 usually although it's adjustable. -1 from the computers point of view. Other kinds of draws get a different score, usually zero (like stalemates.) As Bob pointed out ALL programs have these subtle bugs you are now describing. >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. I'll have to give your scheme some thought. Something don't sound right, but let me consider. - Don
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.