Author: Gian-Carlo Pascutto
Date: 01:06:13 11/14/01
Go up one level in this thread
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). As Uri stated, this is not a proof at all 32 bits is not enough. I also disagree with your reasoning. There is no guarantee that if you search 2^32 that you will have a guaranteed collision, unless your hash table has 2^32 entries. Another point is that it does not matter that you have collisions, as long as they do not happen at critical points. The structure of the search nearly assures this. I would like to see someone test this, rather than to keep reiterating unfounded hearsay. -- GCP
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.