Author: Robert Hyatt
Date: 15:50:31 07/27/98
Go up one level in this thread
On July 27, 1998 at 15:29:01, Roberto Waldteufel wrote: > >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 the logic sounds ok at first reading, but the problem I see is that this would most likely cut hash hits by 99%... because *most* moves are reversible moves in the search, and they would leave it "unclear"???
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.