Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash table efficiency

Author: Robert Hyatt

Date: 19:22:18 12/09/00

Go up one level in this thread


On December 09, 2000 at 18:36:58, David Rasmussen wrote:

>On December 09, 2000 at 15:08:55, Robert Hyatt wrote:
>
>>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...
>
>I see now. You are, of course, right.
>As you might have suspected... ;)


After debugging this kind of problem more than once, it becomes pretty
easy to remember.

:)



This page took 0.03 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.