View Single Post
  #7   Report Post  
Old December 7th 04, 06:41 PM
David Richerby
 
Posts: n/a
Default

Simon Krahnke wrote:
(14:02) schrieb:
Simon Krahnke wrote:
Repetition: That's the same position for the third time, right? So I
keep a history of hashes, and search it each node for 2 hits.


What is the probability of a hash collision?


I want to keep a list of hashes, not a hash table where different hash
values share a single position.


Yes but if you have a hash collision (in the sense of two positions having
the same hash code), your list will think that a position has been
repeated when, in reality, it hasn't. However, the Birthday Theorem says
that you need about sqrt(n) different positions in your list before the
probability of two of them have the same hash exceeds 1/2. Since you're
using 64-bit hashes (I hope!), this means you need about 2^32 entries in
your list before bad things are likely to happen. Since games of chess
are considerably shorter than this, the collision probability is
negligible.


Dave.

--
David Richerby Old-Fashioned Adult Spoon (TM): it's
www.chiark.greenend.org.uk/~davidr/ like a piece of cutlery that you
won't want the children to see but
it's perfect for your grandparents!