Author: Andrew Shapira
Date: 19:19:43 06/05/05
(This is about hash tables and the 50 move rule and draw by repetition, and to some extend endgame databases; it's not about the mechanics of detecting whether a given position has occurred before on the board.) Imagine that a search encounters some position P for the first time, say at time T0, determines some evaluation E0(P) using a depth 9 search, and stores E0(P) in the hash table. For simplicity let's say that E0(P) is computed without using hash tables in any way. Some time later, say at time T1, P is encountered again, and we want to know its evaluation E1(P) with regard to a depth 9 search. We look up P in the hash table and find E0(P). Suppose that E0(P) looks fine for us to use, e.g., we are about to take E1(P) to be the same as E0(P), except that there is one difficulty: the halfmove clock at time T1 differs from the halfmove clock at T0, e.g., at T0 the halfmove clock was 12 and at T1 it is 95. This means that many of the nodes that went into the determination of E0(P) have evaluations that are not correct at time T1. For example, suppose that some position Q occurs at depth 4 in P's search tree, and Q has a mate in 3; E0(P) will incorporate this information, but E1(P) should not, because at time T1 if we follow the path to Q and then to the mate in 3 from Q, the result will be a draw by the 50 move rule, not mate. Because of this we do not want to use set E1=E0. A similar issue comes up with draw by repetition. For example, in the above situation, imagine that Q has appeared on the board 0 times before T0, but Q has appeared twice before T1. The same thing happens with endgame database lookups. It's somewhat easier to deal with there, if one has distance-to-conversion or distance-to-zero information in the database. (See http://www.aarontay.per.sg/Winboard/fiftymove.htm and http://www.aarontay.per.sg/Winboard/weaktablebase.html .) The essential reason this happens with hash tables and endgame databases is that results are computed while ignoring part of the game state. What is known and done about this in regard to hash tables? I wonder - should distance-to-zero information about the principal variation be stored in hash table entries? This might at least make it possible to detect when a hash table entry could be incorrect because of the 50 move rule. What to do when this situation is detected is another question completely. Also, handling lower and upper bounding hash table entries might be tricky. It doesn't seem to help with draw by repetition.
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.