Author: Robert Hyatt
Date: 01:16:50 07/28/98
Go up one level in this thread
On July 27, 1998 at 19:14:11, Roberto Waldteufel wrote: > >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 Be careful that you don't overlook another important feature. A good test is "fine # 70" the endgame position with blocked pawns where white plays Kb1 to win. This "feature" is that not only does hashing give a speed boost, it also gives a "quality" boost. IE I generally solve fine70 at ply=18, yet this is actually *impossible* at it takes something like 26 plies to win a black pawn. This is done because not only does hashes cause cutoffs and prevent us from searching the same part of the tree repetitively, it also lets us graft information from one part of the tree to another. try your idea on this position and see if the depth at which you solve it goes up. Until you win the pawn, all moves are reversible (king moves only). It is possible that you won't successfully do the "grafting" and push the solution off for one (or several) iterations as a result...
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.