Author: Robert Hyatt
Date: 13:08:19 07/26/98
Go up one level in this thread
On July 26, 1998 at 03:54:36, Pat King wrote: > >On July 24, 1998 at 06:14:04, Robert Hyatt wrote: > > >> >> >>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. > >I have a solution to this problem, which may only work for my implementation, >but here goes... I implement undo by storing a stack of positions for the entire >game. It wouldn't be hard for me to modify this to include the current variation >being considered. Then, when the terminal position is reached, you... > a) Examine the game history for draws by repetition or 50 moves. If found, > return 0, else... > b) Consult hash. If found, return result, else... > c) Call static evaluator (or qsearch) store result in hash, and return result. > this doesn't address the problem. The problem is "what happens between the position where you get the hash *hit* and the endpoint position that produced that hash *value*. The hash entry has none of this information. So it is possible that you get a score of +5 from the hash table entry, but, in reality, in trying to play down the game and reach that position, you draw by repetition or 50 move rule. It's not what happens *before* the hash hit position, it is what you don't know about what happens *below* the position. Note that you are trusting that you can produce this score in the game, but you don't know because of potential draws.. >Thus stalemates and mates would get stored in the hash, but other draws >wouldn't. You only need to examine the history back to the last capture or pawn >move, so adding the history search isn't terribly expensive, although whether >it's worth the effort in terms of rating points is another matter. the problem above happens even if you don't store draws in the hash table. The score in question isn't a draw, it's a real score... try this: .....................X............Y..............Z at position X you continue searching, past position Y, to reach endpoint Z. You back up, and when you back up to X you store the score (say +5). now you search this path: ..............Y............X when you reach X, you get a hash match, and say +5. But that is wrong, because note in your path before X you searched position Y, which means halfway between X and the endpoint Z you will encounter a repetition. And get 0 rather than +5. But you have no way of knowing this, and no way of preventing it from happening, unless you store all the path information from the 50-move-rule counter position to the endpoint... then you could detect the repetition Y in the hash entry and realize it is not an accurate score. But it would make the hash table basically useless... > >> >>(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... > >I think this scheme addresses (1) nicely, but I haven't tried it yet. I'll have >to see how expensive the draw search really is. > >Pat King Remember, you are focusing on storing draw scores correctly. But non-draw-score positions inherit the same problem... :(
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.