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!