Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table efficiency

Author: Robert Hyatt

Date: 12:08:55 12/09/00

Go up one level in this thread


On December 09, 2000 at 03:39:22, David Rasmussen wrote:

>On December 08, 2000 at 23:04:42, Robert Hyatt wrote:
>
>>On December 07, 2000 at 13:20:29, Miguel A. Ballicora wrote:
>>
>>>On December 06, 2000 at 16:17:22, Robert Hyatt wrote:
>>>
>>>>Repetition is a known hashing "issue".  But in fact, it is there even when
>>>>you aren't thinking about a repetition... because what says that you can search
>>>>from the node where you get the hash hit, to the terminal node that follows
>>>>that deeper in the tree, without repeating something?
>>>>
>>>>It is messy.  I simply ignore it.
>>>
>>>If I understand what you mean, you ignore the issue altogether right? you don't
>>>mean you ignore the repetition. In other words, you find a repetition, return
>>>DRAW from search() and also store the previous postion with score=DRAW in the
>>>hash table. Correct? If that is true, this is not the origin of my problem...
>>>
>>>Thanks,
>>>Miguel
>>
>>
>>This is what I do, yes.  Draw scores are a problem.  Some don't store them.
>>Dave Slate was a proponent of that approach.  I _always_ stored draw scores,
>>and still do.  Either way leads to errors.  My way leads to a faster search,
>>however.
>
>How can not storing the draws, lead to errors, and not only ineffeiciency? A
>node that isnt hashed but searched, is still "correct", I gather. Whereas, a
>node that was stored as a draw because of repetition, and later read in a node
>where it isnt a repetition because of different history, will be "incorrect".
>
>Wrong?


Wrong either way.  Imagine you search from position A down a path, to reach
position B which you store in the hash table as +.2...  Suppose you search down
a _different_ path from A with maybe more moves in it, and _still_ reach
position B.  If you use that +.2, you are in danger of using a wrong eval,
because that eval from position B was produced by searching beyond B to some
endpoint before you got a score.  How can you be sure that this different
path doesn't repeat before reaching that endpoint?  You can't.  IE it is
possible that a position between the current path connecting A to B repeats
a position between B and the actual endpoint.  That didn't happen in the
original search path from A to B to endpoint.


You get errors either way, because you are hashing a position, and _not_ a
path to that position.  The latter would solve the problem, but drastically
cut down the efficiency of the hash table due to fewer hits...



This page took 0.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.