Author: Álvaro Begué
Date: 10:28:53 06/06/05
Go up one level in this thread
On June 06, 2005 at 11:25:31, Robert Hyatt wrote: >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. > Well, all that needs to be hashed is the set of positions visited since the last irreversible move. This will catch transpositions as long as there is a capture or a pawn move after the moves that are different between the two lines. I still think this would seriously hurt performance, though. >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.