Author: Heiner Marxen
Date: 14:31:42 04/03/02
Go up one level in this thread
On April 03, 2002 at 16:11:36, Tim Foden wrote: >Hi Heiner, > >I just thought of something to ask you. In Chest you have hash tables... how do >you cope with the Graph History Interaction problem? In most normal chess >programs this is simply ignored, but I would have thought that you couldn't >ignore it in Chest, in case you gave invalid results. > >Cheers, Tim. I'm not sure I understand completely. Do you mean that the board contents is not enough, and we need to consider the history, how we come there? Then, no, I do not explicitly do much about it, i.e. I ignore that problem, since (for Chest) it is no problem. First, I ignore the 50-move rule. Then, Chest always does internal iterative deepening. Therefore, each subtree of a solution tree always is of shortest possible depth. And if you think further... no position can appear twice on any path that is part of such a solution tree. Chest detects repeated position in its path indirectly via the hash table (TT), since it does create (and lock) a hash table entry when starting a recursive search, and gradually updates the known value of the entry, until the search is finished, the last result is entered, and the entry is unlocked. Any nested search of the same position will find a result with a larger depth in it, as the recursive search needs. That will cut off there. Note that I do NOT return any "impossible" value upon detection of a cycle. _That_ would create anomalies and false results. I strictly stick to the dogma, that the function that is cached in the TT must depend _only_ on the key of the TT-entry, i.e. the board (inclusive ep status and castling rights and side to move). I hope to have answered your question. Cheers, Heiner
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.