Author: Robert Hyatt
Date: 19:43:47 09/24/01
Go up one level in this thread
On September 24, 2001 at 18:22:45, Sune Fischer wrote: >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. I don't think that is the issue. There are roughly 2^160 chess positions. We are hashing that into a 2^64 address space. That gives 2^96 different chess positions for every hash position. _that_ is the collision problem. I simply answered the question in an expermental way as I explained to Uri in a post right above this one. The answer suggested that 64 hours is not going to cause a problem. The question is "how many false matches does it take to screw up a tree of size (say) 100M nodes?" I experimentally answered that one is not enough. And I also experimentally found that at 1M nodes per second, I was getting less than one false match per hour, which is about 4B nodes. So I got less than 1 collision every 4B nodes, and I ran a test that proved that one false match ever 100M nodes won't kill the search. I conclude that things are safe for a long time. > >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. That would be great. One collision every 64 hours is _not_ going to influence anything at all... But even one ever 100M nodes is not harmful.. > >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. I ran a test with an error every 100M nodes, across about 100 test positions, and found zero changes at the root. No score changes, and absolutely no move/PV changes. We could run that kind of test again, but be prepared to burn months of computer time. I did. :) At one time I had 4 Crays smoking along until someone asked me "what in the hell is this stuff you are running up here?" :) >"
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.