Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Hash collisions in chess programs?

Author: Dann Corbit

Date: 14:04:14 02/18/99

Go up one level in this thread


On February 18, 1999 at 14:45:59, Inmann Werner wrote:
[snip]
>What does this mean in particular for chess programming?
>
>I use one hashingadress between 0 and 2000000 for the hash adress and one
>extra calculated long int for verification. Each of the both hashcodes result
>out of 2 different sets of 64 long int numbers.
>How high is the probability of a collision in this case, and do you use the
>same algorithm?
I think we have to know what hash we are using in order to talk about
collisions.  For instance, I could choose a hash for people's names which uses
the first six letters as base 26 numbers.  This would probably be a rather bad
hash, because people's names are not spelled at random, and because we are
likely to receive them already in order (unless, for some reason we *want*
collisions).
It seems that most chess programs use Zobrist hash.  I think it would be
interesting to count collisions for opening, early middle game,  mid-game,
endgame, and late-endgame and see if the proportion stays the same as the board
clears.  I am fairly sure that it will not be exactly as probability would
dictate if we had a perfectly random distribution of positions.  It might also
be interesting to investigate the properties of other hashing algorithms.




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.