Author: Robert Hyatt
Date: 08:25:31 06/06/05
Go up one level in this thread
On June 05, 2005 at 22:19:43, Andrew Shapira wrote: >(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? You have only two choices, plus a 3rd kludge that helps a good bit. 1. You can hash the complete path, not just the position. This solves the problem but is just as effective as removing the hash table completely, since the entire point is catching transpositions. If you want to be clever, you could just hash the moves rather than the order of the moves, but that would cut the number of hash hits down to almost nothing, again killing performance. 2. ignore the problem, which is what most do. 3. You can clear the scores as you near the 50-move rule boundary, so that you at least recognize 50-move draws correctly (doesn't help for 3-fold repetitions unfortunately). > >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 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.