Author: Roberto Waldteufel
Date: 16:14:11 07/27/98
Go up one level in this thread
On July 27, 1998 at 18:50:31, Robert Hyatt wrote: >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"??? Hi Bob, I have now tried a simple implementation of the idea, where I always search the hashed move first, and I accept the hash score for bounding purposes only if the hashed move is irreversible. The slow-down is noticeable, but it is much less than I thought it would be. No firm figures yet, but the number of iterations remains the same most of the time, and is one iteration less on some occasions. I think this because the sequence of draft moves leading from an unclear hashed position usually involves a capture in a small number of plies from the unclear position, and the moves to reach the clear end-position are usually also in the table. I think captures function as refutations in the majority of cases where beta-cutoffs occur, but sometimes the capture is a few plies down the road, eg a fork for example. My program recently lost a game by playing a horrendous blunder in an admittedly already lost position, and I have a very strong suspicion that the "hash history bug" was responsible. It occurred in a position where the opponent had the option of perpetual check, but was up on material. If this new hashing scheme avoids such pitfalls I think a small amount of speed may be worth it, as long as the cost remains reasonable. 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.