Author: Robert Hyatt
Date: 08:59:14 04/07/04
Go up one level in this thread
On April 07, 2004 at 11:10:41, Sune Fischer wrote: > >>>If you have 2^64 different keys and 2^20 of these are already used in the table, >>>the probability for the next one (assuming it is different) is going to be 2^46, >>>ie. a frequency of 2^-46. > >44 of course. :) > >>>While you are still filling the table the probabilities are lower of course due >>>to "fewer kids in the class". >>> >>>Only new keys not already stored in the table can collide. >>>So to get the real frequency one should not count the true hash hits, and there >>>will be lots of those too so collision rate is a bit lower. >>> >>>Another reducing factor is present if you don't probe/store qsearch, since >>>collisions on these nodes aren't possible either. >>> >> >>Another issus is how the signatures are created. They are not completely >>random, they are related, in that sig(plyx) is based on sig(plyx-1) with some >>bits changed. That is a different assumption than in the birthday paradox... > >Paradox? :) > >But yes, there are some factors which pull the collision rate up and some which >pull it down so it's not easy to estimate the exact theoretical value. The ball >park estimates should work okay though, and 1 coll/7 mill nodes sounds like a >very high frequency. > >-S. Yes it is, but he is calling "illegal best move" a collision. There are plenty of ways to store a bad best move without having a real collision. I gave him a suggestion to test moves for legality when storing them, as errors there will point him to what is going wrong...
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.