Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash Collisions

Author: Don Dailey

Date: 16:57:33 02/21/99

Go up one level in this thread


On February 21, 1999 at 01:14:37, KarinsDad wrote:

>I posted this the other day, but it may have been obscured (or not if nobody has
>any information on it).
>
>I have been wondering if changing the Zobrist hash from a set of random number
>to a set of non-random and very specific numbers could result in a more even
>distribution in the hash table. Has anyone done any work in this area?
>
>KarinsDad

Several weeks (months?) ago I posted something on how to compute
hamming distance between EVERY number in your random table.  You
want to maximize the "hamming" distance between all the numbers.
The hamming distance is the number of bits in common between any
two numbers.

*Socrates had a table that one of our previous students generated
for us.  I don't think he did anything magic, he just started with
a goal hamming distance and generated the numbers one at a time,
testing each number against all the others, trying to achieve at
least the goal hamming distance in the worst case.   If he succeeded,
he tried a stricter goal.  I don't know for a fact whether it is
"best" to try for worst case behavior or use some other criteria,
but I would say this would be a good start.   If you go back far
enough you will see a bunch of posts on this, search for "hamming"
in the older archives,  I think it was a few months ago.

- Don



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.