Author: Robert Hyatt
Date: 09:33:00 07/25/98
Go up one level in this thread
On July 25, 1998 at 09:21:18, Don Dailey wrote: >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 I've always stored draws and mates, and still don't lose too much sleep. :) And I haven't seen it cause me to lose a game yet, either, although it might make me draw one that might be winnable. But two-fold repetition detection will do that too...
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.