Author: Robert Hyatt
Date: 11:18:51 04/07/04
Go up one level in this thread
On April 07, 2004 at 12:09:01, Sune Fischer wrote: >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? Yes.. > >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. No. Think about storing a "PV" move. You can get the PV move from several places, either the current move you just searched or from the backed up PV. The latter is perfectly safe, bit not if the previous ply failed low, as it didn't back up _anything_ and the backed up PV array for the current ply could contain an old (and illegal) move from another search at this ply... It is not hard to store an illegal move... > >-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.