Author: Rémi Coulom
Date: 02:11:34 11/14/01
Go up one level in this thread
On November 14, 2001 at 03:52:31, Uri Blass wrote: >On November 14, 2001 at 02:37:45, Dann Corbit wrote: > >>On November 14, 2001 at 02:03:47, Gian-Carlo Pascutto wrote: >> >>>On November 13, 2001 at 19:34:44, Dann Corbit wrote: >>> >>>>64 bits is generally recognized as a good size for a hash, and 32 bits is >>>>*definitely* too small. >>> >>>I am still eagerly waiting to see someone actually produce >>>valid proof for this claim. >> >>Some programs may have a much bigger problem (e.g. fast searchers). >>Imagine a program that searches 1M nodes/second. There are plenty that can >>manage that, on steamy hardware. >>In 1000 seconds, there are 1 billion nodes, and in 4000 seconds (a bit over an >>hour) a 32 bit integer has been exhausted. By this time, it is absolutely sure >>to have collisions. Now, imagine a correspondence player, letting the computer >>think overnight. Each position will have been randomly overwritten 20 times a >>day (roughly speaking). >> >>I saw a rough mathematical justification somewhere (but I can't remember where >>it was). > >It is not a proof. >A valid proof is to show that the same available program practically generate >worse moves with 32 bits for hash. > >Uri It happened to me. I had been using only 32 bit (or maybe even a bit more, I do not remember) for years and never noticed any problem. TCB once crashed very mysteriously and I managed to find that this was because of a hash collision. I now use more bits and have made my hash algorithm a bit more collision-proof. This led me to think a little bit about the probability of collision for a given number of bits. An important result is that if you have N distinct values to choose from, you start getting high collision probabilities as soon as you have picked sqrt(N) values. So you get a lot of collisions with 2^32 values. Remi
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.