Author: Sune Fischer
Date: 05:02:15 09/23/01
Go up one level in this thread
On September 23, 2001 at 07:32:45, Uri Blass wrote: >On September 23, 2001 at 07:11:52, Sune Fischer wrote: > >>On September 23, 2001 at 02:50:59, Uri Blass wrote: >> >>>>Why do you think the size of the table has any bearing on the number >>>>of collisions? The number of collisions is a function of the >>>>"uniqueness" of your key, not how many entries are in your table. >>> >>>let take an extreme case: >>>suppose there is only one entry in your hash tables and you use 64 bit numbers. >>> >>>The probability for wrong hash collision is 1/2^64 for every new node after the >>>first node. >> >>True >> >>>If you have 1000000 entries in your hash tables and the hash tables are full >>>then the probability for hash collision is 1000000/2^64 for every new node. >> >>Not so, you don't check you key against all the keys in the hash. > >I do not understand. >I know that basically chess programs compress chess positions to 64 bit numbers > >The hash tables are basically an array of 64 bit numbers. >hash[1048576] > >Let suppose that the size of the array is 2^20 and you decide which entry to use >based on the last 20 bits of the number. >if the last 20 bits are 0 then the number is stored in hash[0] if there is >nothing in hash[0] > >if you find a new position that is also a candidate to be stored in hash[0] then >it means >that you need to check if the position is a new position based on the 64 bit >number. > >The only case when there may be hash collision is case when the position is a >new position but you have the same 64 bit number. Well we agree so far ;) >If the position is a new position then the probability that you have > the same 64 bit number is 1/2^44 and not 1/2^64 because you already know the last 20 bits. yes, that would be correct, but aren't we talking about the chances of two 64 bit keys colliding? I say here collide as in 2 different positions corresponding to the same 64 bit key. Your example doesn't compare two 64 bit keys, it compares the chance of finding a different key at a certain hash entry. To simplify lets say we have a 2^63 size hash table, now you would have a 50% chance of a "collision", but what you have been asking is: the key that is here, is that the same as my key? You are not asking if the key corresponds to the same position, how would you even ask such a question without more detailed information about the position? You would need e.g. a 128 bit position key to check that the 64 bit key was valid and so on and so on. I believed you had the same perseption of what a collision was as I. Of cause some might consider it a collision if you go to the hash entry and don't find the 64 bit key you hoped for. However that is just "too bad", it is not dangerous in the same way as when one 64 bit key gets to represent to different positions. If you zobrist table is perfect, eg. it will generate all 64 bit keys with equal probability, then the chance of a collision happening is less than a billion to 1!! Most likely though the zobrist table with not be perfect. >Uri -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.