Author: Sune Fischer
Date: 09:09:01 04/07/04
Go up one level in this thread
On April 07, 2004 at 11:59:14, Robert Hyatt wrote: >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... I don't understand this, store a bad best move? Bad as in illegal? The move you store is always a move that has been searched AFAIK, this in itself should guarantee legality I think. In my case an illegal hash move would indicate a genuine collision. -S.
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.