Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash collisions and a little maths

Author: Ed Schröder

Date: 10:06:33 02/24/99

Go up one level in this thread


>Posted by Vincent Diepeveen on February 24, 1999 at 11:53:39:

>>>I know however that i must have had wrong collisions, probably the fact
>>>that i don't store true values hides collision probs from me, as i
>>>cannot have true values in my program; if a score is true then alfa
>>>gets improved and then score is again <= alfa, so i use only 1 bit
>>>to see whether it's >= beta or <= alfa.
>>
>>I don't understand the above. You say,  "i cannot have true values in
>>my program" and then "if a score is true then..." which I interpret as
>>you use true score after all?
>>
>>My best guess is you only use alpha (and not beta) to mark the
>>score in the hash table. Correct view?
>>
>>Can you tell why Diep can't use "true scores" in the hash table?
>
>This is something theoretical Ed,
>ASSUME we have true scores in search.
>Now try to prove that to false.
>
>We assume that we have true scores.
>then alfa becomes the true score,
>however score <= alfa, so
>conclusion is falsum.
>
>so the score is <= alfa, which is a bound.
>therefore i only store using 1 bit in hashtable.
>a score is either <= alfa or >= beta, but never alfa < score < beta,
>that cannot happen in DIEP as i improve alfa with the result of the search.

Here is how I do things. As far as I know it should work for every program.

Store_in_Hash:
flag=REAL;
if (score >= beta) flag = UPPER;
if (score <= alpha) flag = LOWER;
Store flag in hash table

Search_in_Hash:
if (flag==REAL) return 1;		// transposition
if (flag==LOWER && score <= alpha) return 1;
if (flag==UPPER && score >= beta) return 1;
return 0;		                // no transposition

Ed



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.