Author: Robert Hyatt
Date: 09:30:35 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. > this is not correct. There are *two* problems that are both unsolvable: (1) draw scores are path dependent, and the hash signature has *nothing* about the path in it. So just because you get a hit that says "draw" there is no guarantee that it is. (2) Now, forget draw scores for a minute. Becuase even if you don't store draw scores, you are going to get bad scores, because a hash probe gives you a score at the *end* of a path from this position. But it is certainly possible that before you reach that end position, you hit a draw by repetition or by 50 moves, and you will *never* catch that. So it's hopeless. Not storing draw scores doesn't solve the problem. Storing them ignores the problem, and hashing in general has problems no matter what is done. >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. this may not be true. It may be that setting *one* eval to zero drops the whole thing to zero... > >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? I'm not sure how it would solve the problem, because the "path" problem is hidden and undetectable totally... > >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 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.