Author: Sune Fischer
Date: 04:11:52 09/23/01
Go up one level in this thread
On September 23, 2001 at 02:50:59, Uri Blass wrote: >>Why do you think the size of the table has any bearing on the number >>of collisions? The number of collisions is a function of the >>"uniqueness" of your key, not how many entries are in your table. > >let take an extreme case: >suppose there is only one entry in your hash tables and you use 64 bit numbers. > >The probability for wrong hash collision is 1/2^64 for every new node after the >first node. True >If you have 1000000 entries in your hash tables and the hash tables are full >then the probability for hash collision is 1000000/2^64 for every new node. Not so, you don't check you key against all the keys in the hash. I don't see why hash collisions have anything to do with hash size either. No matter what the chance of a collision per lookup is 1/2^64 (assuming the zobrist table is perfectly generated with "true" random numbers). Now the more lookups the bigger the chance of cause, but still much less than a million to 1 in a typical game. And it doesn't matter either that your table is full of old keys, the chance of colliding with them is no greater than with newer generated keys. >>Maybe my definition of a collision is different than the norm: I >>define a collision as a match of the entire key between different >>positions, not a match of the portion of the key used as a probe into >>the table. That would be my definition too. >Uri -S.
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.