Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: draw by repetition and hash tables

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 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.