Author: Don Dailey
Date: 06:21:18 07/25/98
Go up one level in this thread
On July 24, 1998 at 06:14:04, Robert Hyatt wrote: >On July 24, 1998 at 00:38:01, Inmann Werner wrote: > >>Hello all! >> >>can anybody help??? >> >>I have some problem to implement draw by repetition in my program. >>If a position is reached the third time, its a draw by repetition. Ok. >>But the position has an evaluation. But because of the draw I return zero >>(draw). Now all positions before in alpha beta get a Score of zero. OK. >>But this values also may come into the hashtables, and thats really bad and >>not correct! >>Does anybody have the same problem, and maybe solved it? >> >>Werner > > >There are two issues: > >(1) *all* hash table scores are technically wrong almost all the time. Because >*none* include path information in the key, yet most include path information in >the score. Examples include repetition and 50-move draws. > >If you store a position a long way away from a 50 move draw, then look it up >near a 50-move draw position, you get a wrong result. And there's nothing you >can do. If you look up a non-draw position and use that score, you can be >making a mistake, because the path in front of that position could be different >than the path when it was stored, so that there could be either a 50-move draw >or a repetition draw before you reach the endpoint that the position's score >belongs to. > >(2) does the error in (1) affect the program? Hard to say. But everyone uses >hashing, and everyone therefore ignores the errors that crop up, most of the >time with no ill effects. I always have, for example. Note that not storing >draw scores in the hash table only cures one class of error, but not the main >ones in (1) above... > >As to your question about "help" note that a position's score is *not* for that >position... it represents the minimax score obtained by searching "draft" plies >*below* that position, which is not the same thing at all... Yes. A similar situation exists with FEN position records. The half move clock deals with the 50 move rule but there is no notation (except a game record) to deal with positions that have occured prior to a fen position. So 2 identical FEN records COULD be describing different positions. In the very worst case, the difference actually could make a difference on whether the position is a win or draw. Think of a FEN record as equivalent to a hash table record and you see the difficulty. If you stored the half move clock in the hash table record you could probably fix the 50 move problem but would still have the move history problem. You could also fix this by keeping a signature of move history, but this would be horribly wasteful and inefficient. So I think the problem can be completely solved, but no one would want to do this since it would require throwing away useful information. In summary, the problem is completely solvable by storing the EXACT position where a position is defined completely by it's move history. It could be built into the hash key and need not be expensive. But this is not a practical solution and would significantly decrease the performance of you chess program. My feeling is that if you do not store positions with draw scores, you can ignore the other issues without losing too much sleep. I doubt the weaking effect of these things is enough to measure. - Don
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.