Computer Chess Club Archives


Search

Terms

Messages

Subject: Re: Let's analyze move 36

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.01 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.