Author: Chris Whittington
Date: 10:49:14 10/08/97
Go up one level in this thread
On October 08, 1997 at 12:51:44, Robert Hyatt wrote: >On October 08, 1997 at 07:08:01, Amir Ban wrote: > > > >>Don't believe it. The fact that hash collisions occur does not mean that >>it affects the PV, and if it does, it is a really freak accident. I do >>48-bit hashing with almost no validation. If you wait for my program to >>fail because of that you will get old in waiting. >> > >this is not necessarily true. Several of us, in a long thread in >r.g.c.c a couple of years ago, very carefully measured the number of >hash collisions produced using a 32 bit, 48 bit, and 64 bit hash key. >32 bits is totally hopeless. 48 bits was better, but still produced a >large number of collisions at high node rates. 64 bits produced a >*significant* number of hash collisions as well. These were all run on >machines that were then searching 20-30K nodes per second, except for me >(and the 64 bit numbers) where I ran the test on a C90 at 500K nodes per >second or so.) > >We are getting far more collisions than you imagine I suspect, based on >the numbers from Crafty, ZarkovX, I believe Ed contributed some results, >and I don't know who else was involved. To think that multiplying by >2000 is really like removing 11 bits from the hash signature is a >sobering thought. It is likely that they are on the fringe of seeing >bad things happen, particularly when they search for 20 minutes at a >pop. Ok let's try my maths model. tell me if it predicts the results. Node rate N nodes per sec Hash lookups N/4 hits per sec Chance of hash collision is related to number of bits in hash signature, suppose we have n bits. Collision chance per pair of hash hash lookups = 1 / 2^n The hash collision rate is unfortunateyl going to be proportional to (roughly) the SQUARE of the hash lookup rate. Total collisions per second = 1 / 2^n x N/4 x N/4 = N^2 / 2^n / 16 ideally we could go for, say, only one hash collision per week, Someone with a calculator and some spare time .... How big a hash bit count would we need for a 10,000, a 100,000 and a 2,000,000 nps program ? Alternatively and additionally, for a 64 bit sized hash index, what collision rate will a 10,000, a 100,000 and a 2,000,000 nps program give ? Does this agree with Bob's empirical results ? Chris
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.