Author: Robert Hyatt
Date: 05:29:51 05/21/98
Go up one level in this thread
On May 21, 1998 at 06:42:02, Ernst A. Heinz wrote: >On May 20, 1998 at 18:20:16, Robert Hyatt wrote: > >>On May 20, 1998 at 12:48:01, Roberto Waldteufel wrote: >>> >>>If your program uses hash tables, you can easily avoid this problem. In >>>the hash table, along with bounding values for the position, reserve one >>>bit to indicate if the position has occurred previously in either the >>>current variation, or earlier in the game. If so, score the position as >>>a draw and exit without any searching. You do not have to wait for the >>>third occurrence of the position for the purposes of tree searching - >>>the second occurrence is enough. >>> >>>Roberto >> >>This works, but introduces a few problems that must be solved. You must >>be sure that such "open" entries never get replaced, until they have >>been >>"closed" (when unmaking the move that led to them) which has a small >>cost >>associated with doing this. You also can't call Search() recursively >>from >>the same position, as is done in "internal iterative deepening" because >>the >>position would already be "open" and get scored as a repetition, even >>though >>it is just being searched to a shallower depth. And you have to be sure >>that >>there are no paths out of search that don't clear this bit, plus you >>probably >>are going to store the *real* game history positions in the table with a >>"don't use this score/move, but note that if you hit this entry we are >>at >>a repetition". > >All easy and fast to handle -- "DarkThought" employs open hashing in >its main transposition table for repetition detection. Internal >iterative deepening represents no problem whatsoever because you only >do it in case of a *hash miss*. > >=Ernst= I see two problems to solve. First you can get a hash hit, but no suggested move... but it doesn't matter because you have already entered the position in the hash table as "open"... and if you then recursively call search because this is a PV node and you have no PV (hash) move to follow, you have to take some evasive action to avoid calling LookUp() in the iterative- deepening call to Search()... or else you have to defer storing the "open" hash entry until you pass the IID part... I tried it both ways... and didn't like the complexity... Ken Thompson used this however, but didn't do IID at all. My experiments offered no speed improvement over the repetition_list approach (this can be fast if you implement 50-move draws because you don't have to check the entire repetition list and it stays very short as well).
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.