Author: Sune Fischer
Date: 15:22:45 09/24/01
Go up one level in this thread
On September 24, 2001 at 17:55:57, Robert Hyatt wrote: >Note that I don't sign on to the theory that more ram increases the probability >of a collision. The probability of a collision is 1 / 2^64 for a normal >position. This means for a table that holds 2^64 entries in a 2^64 signature >space. Smaller RAM improves that by overwriting/replacing entires before they >can collide. But the base 1/2^64 is good enough for me. That is a very tiny >number... > >Since we will never see memories that large, the probabilities are going to be >good enough for a long time, assuming that 1 collision every few billion nodes >is acceptable... So far that seems to be ok... Well as I said in another post, your math is simply not correct. Probablility of collisions does increase linearly with table size if you search deep enough to fill the hash several times over. The argument is trivial, and I can repeat if you want. Whether or not it is something to worry about in reality is a completely different question. Uri Blass did some considerations about that, I would like to quote them here: "I believe that in 2010 it is going to happen at tournament time control. Today the size of the hash tables on the best hardware can be at least 512 Mbytes that mean 2^29 bytes and 2^26 64 bits numbers. 2^32 nodes per hour is also possible for Deep Fritz on good machine and it means that 2^38 nodes per 64 hours is possible. Here my estimate is even bigger amd I estimate almost 1 hash collision per move if you use a good hardware for 64 hours per move. I do not say that this almost 1 hash collision per move is important and it is possible that it causes problem only in 1/100000 of the cases but I do not know a good estimate for it. "
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.