Author: Ernst A. Heinz
Date: 03:42:02 05/21/98
Go up one level in this thread
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=
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.