Author: Antonio Dieguez
Date: 13:46:12 09/24/01
Go up one level in this thread
On September 24, 2001 at 16:32:35, Robert Hyatt wrote: >On September 24, 2001 at 16:24:13, Antonio Dieguez wrote: > >>On September 24, 2001 at 16:17:14, Robert Hyatt wrote: >> >>>On September 24, 2001 at 15:41:07, Antonio Dieguez wrote: >>> >>>>On September 24, 2001 at 15:27:35, Robert Hyatt wrote: >>>> >>>>>On September 24, 2001 at 13:53:58, Antonio Dieguez wrote: >>>>> >>>>>> >>>>>>>Several hash into 2 X 32 bit values. You store one value, you use the other >>>>>>>to generate the hash index. This is not quite as safe as a true 64 bit hash >>>>>>>signature where all 64 bits are used, but it is pretty good. If you have >>>>>>>one million entries in the table, your hash key is 52 bits long, effectively, >>>>>>>which is not horrible. Not as good as 64, but not horrible. >>>>>> >>>>>>hi. isn't one million of entries around 2^20, so just 44 bits are used for the >>>>>>key, (not 52) ? >>>>> >>>>>I am assuming that the hash signature is made up of two 32-bit words. One of >>>>>the 32 bit words is stored in the hash entry. The other is used to generate >>>>>the index. That gives 32 + 20 == 52 bits used if you have a 1M entry table. >>>> >>>>yep, sorry. >>>> >>>>>>what I see is that 48 bits with separate hashindex is already safer than 64 bits >>>>>>without separate index when using just 131072 entries (=47 bits), so I may be >>>>>>not understanding something. >>>>> >>>>>You aren't really using 48 bits. You are using more. You are using the number >>>>>of bits you store in an entry + the number of bits you use to produce the table >>>>>index. In your case 65 (48 + 17). >>>> >>>>I'm hashing just 48 bits so what do I lose? only a few cycles. And what do I >>>>win? that I don't make 100 times more possible a collision if I increase the >>>>hashtable 100 times. >>> >>>Increasing the hash table 100 times does not make the probability of a collision >>>100 times greater. >> >>well, see my other post to Heiner and tell me where I am wrong. >>> >>>64 bits has been proven to do pretty well in today's chess engines. John >>>Stanback, myself, and a couple of others tested this several years ago in a >>>thread on R.G.C.C, and with 64 bits we didn't have enough collisions to think >>>about, while with 32 bits the collisions were overwhelming. >> >>you said it, "several years ago" > >2-3-4 years ago. But doing searches with _billions_ of nodes to check for >collisions. We are nowhere near doing searches that big today, even on fast >SMP hardware. I let at least one test grind on a Cray for weeks, to see how >many collisions I found. It was so small as to be ignorable. I think it was >maybe 2-3 collisions for every 8 hours of 1M nps searching or some such thing... ok thanks for sharing the data. 64 bits is enough for a long time. but with more and more ram a colision is more and more possible too, just as it were speed (when using part of the bits for the index) don't negate that.
This page took 0.01 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.