Author: Roberto Waldteufel
Date: 12:29:01 07/27/98
Go up one level in this thread
On July 26, 1998 at 16:08:19, Robert Hyatt wrote: >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... :( Hi Bob, Here is an isea that avoids thje problem without sacrificing all the backed up scores. I haven't had a chance to test it, but see what you think in principle. In the sequence you give, it has to be possible to reach Y from X and also to reach X from Y. That means that all the moves that lead between the two positions must be reversible moves. When the score of X is put into the hash table, the move that lead to that score is stored with it, but no further moves beyond that. Now if the stored move is a non-reversible move, then we are safe to use the score from the table. Since most of the refutation moves that cause beta cutoffs are captures, which are non-reversible, this allows safe usage of *most* but not *all* the hashed scores. If we hit on a hash score with an attached *reversible* best move, we have a decision: either accept the score and keep our fingers crossed, which is what normally happens, or search the hashed move (but no others) to see what happens. There is a good chance that this will lead to another position that matches in the hash table, and the proces repeats until we either find a safe hash score or we fail to find a hash match. Do you think the logic is sound? Do you think the cost in efficiency would be too great? I hope to test the idea soon and will post my findings here the method seems any good. Best wishes, Roberto
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.