Author: Robert Hyatt
Date: 20:26:18 01/16/02
Go up one level in this thread
On January 16, 2002 at 17:40:24, Steffan Westcott wrote: >On January 16, 2002 at 09:22:55, Robert Hyatt wrote: > >>On January 16, 2002 at 00:08:19, martin fierz wrote: >> >>>On January 15, 2002 at 23:38:54, Robert Hyatt wrote: >>> >>>>On January 15, 2002 at 21:50:52, martin fierz wrote: >>>> >>>>>aloha, >>>>> >>>>>i have a question about repetitions, and it's only about the search itself, not >>>>>about the game history: in my checkers program, to find repetition draws i keep >>>>>track of the hash keys of the current variation, and if i find that the key for >>>>>the current position has already ocurred before in the search, i return zero >>>>>without searching further. i think this is the standard implementation?! >>>>>anyway, i am wondering about the following problem: imagine you are searching a >>>>>variation, and in the end you make a repetition. the program will stop searching >>>>>there in the tree and assign the position a value of 0. now imagine that you >>>>>have a different path of moves without a repetition which ends up at that node, >>>>>probes the hashtable and returns 0. is this just my imagination, or can this >>>>>happen and can it be bad? >>>>> >>>>>cheers >>>>> martin >>>> >>>> >>>>It can happen. As can the inverse, where you retrieve a real score from the >>>>hash table but you can never reach the position because there is a three-fold >>>>repetition between where you are and where you are going... >>> >>>so... is there a solution to this problem? or is it just tacitly assumed that it >>>"never happens"? >>> >>>cheers >>> martin >> >> >>You can disable hashing. Or you can hash all path information which will >>effectively disable transpositions which will disable hashing. :) > >How about including the number of position repititions in the hash information? > That doesn't help a thing. The path is the largest part of the problem, by far. IE getting a wrong repetition draw score from the hash table is _far_ less likely than it is to get a winning evaluation that is wrong because of a forced draw by repetition that the hash table isn't aware of along the path to the "winning" score... >Granted, it doesn't solve all the problems as it doesn't include path >information (so in general we don't know the move sequence which led to the >repeated position when we retrieve it from the hash table later) but it helps >making _some_ otherwise identical positions distinct. That way, repeated >positions get distinct hash table entries, and could have different scores >stored in them. Unfortunately, they have to be individually searched - No >assumption is made between the scores for each repeated position. The repeated positions are really _not_ the problem that causes the trouble here. It is the positions that appear to have nothing to do with a draw, but which (in reality) can't be reached without passing through a draw by repetition. > >Steffan
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.