TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Ronald de Man

Joined: 28 Feb 2012
Posts: 841

Post subject: Re: how to measure frequency of hash collisions.    Posted: Sun Jun 17, 2012 9:06 pm

 Daniel Shawul wrote: Ok that will be 2^64 with a bucket size of 1 for a 64 bits hashkey (no change).

Only the bits that are not part of the index into the hash table count. If the hash table has say 2^24 entries, only 40 bits of the hash key are available to distinguish between nodes mapped to the same entry. Collission rate is 1 in every 2^40 nodes. If the hash table has 2^28 entries, collission rate will be 1 in every 2^36 nodes. (Of course if the index comes from a different hash key, the full 64 bits count.)

 Quote: My doubt is with the replacement scheme.

The replacement scheme has no effect on the collision rate (if we ignore the rate of hash hits). With a full table and a bucket size of 1, for each node searched there is only a collision if the node currently stored in its bucket happens to have the same hashkey, which is determined by the distinguishing bits (40 bits or 36 bits in the examples above).

 Quote: In the previous birthday formula, we assume that each key is compared against all available keys which is what brings up the probablity higher. But for this case I don't know how to quantitiy how many useful comparisons that lead to collision will be done. With a hashtable many positions map to the same entry (assume butcket_size=1). The entry is home to many hash signatures that may actually be real collisions or not in most cases. To detect collision the stored key should happen to be exactly same as the one we are going to store. Say A,B,C map to the same entry but only A == C. First we store C, then B, then A. Thus we will not detect collision. So don't you think the replacement scheme will have an effect ?

Of course the replacement scheme will affect individual collisions (if B does not overwrite C, there will be a collision between A and C, if B does overwrite C, there is no collision), but it will not affect the overall collision rate. The probability that A == C is the same as the probability that B == C. The point is that each time you compare to only one key. With a very small hash table (and the full 64 bits stored, so that the number of bits that "count" is high), collisions will be extremely rare even if the total tree searched has many nodes with identical hash keys.

Of course everything under the assumption that the Zobrist keys are independently and uniformly distributed.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First
Subject Author Date/Time
Daniel Shawul Sat Jun 16, 2012 4:45 pm
Marcel van Kervinck Sat Jun 16, 2012 5:25 pm
Daniel Shawul Sat Jun 16, 2012 6:25 pm
Daniel Shawul Sat Jun 16, 2012 7:15 pm
Don Dailey Sat Jun 16, 2012 9:17 pm
Daniel Shawul Sat Jun 16, 2012 10:05 pm
Don Dailey Sat Jun 16, 2012 10:23 pm
Don Dailey Sat Jun 16, 2012 10:29 pm
Daniel Shawul Sat Jun 16, 2012 11:06 pm
Don Dailey Sat Jun 16, 2012 11:39 pm
Kevin Hearn Sat Jun 16, 2012 11:50 pm
Don Dailey Sun Jun 17, 2012 12:08 am
Daniel Shawul Sun Jun 17, 2012 12:40 am
Daniel Shawul Sat Jun 16, 2012 11:54 pm
Don Dailey Sun Jun 17, 2012 12:23 am
Marcel van Kervinck Sun Jun 17, 2012 7:55 am
Don Dailey Sun Jun 17, 2012 1:26 am
Ed Schroder Sat Jun 16, 2012 9:36 pm
Daniel Shawul Sat Jun 16, 2012 10:01 pm
H.G.Muller Sat Jun 16, 2012 10:12 pm
Daniel Shawul Sat Jun 16, 2012 10:31 pm
Daniel Shawul Sun Jun 17, 2012 2:00 am
Rémi Coulom Sun Jun 17, 2012 8:30 am
Daniel Shawul Sun Jun 17, 2012 10:49 am
Daniel Shawul Sun Jun 17, 2012 2:58 pm
Ronald de Man Sun Jun 17, 2012 3:41 pm
Daniel Shawul Sun Jun 17, 2012 5:58 pm
Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 9:06 pm
Daniel Shawul Sun Jun 17, 2012 9:57 pm
Lucas Braesch Sun Jun 17, 2012 3:02 am
Ronald de Man Sun Jun 17, 2012 3:08 pm
Daniel Shawul Sun Jun 17, 2012 6:12 pm
Ronald de Man Sun Jun 17, 2012 9:14 pm
Daniel Shawul Sun Jun 17, 2012 10:01 pm
Joshua Shriver Wed Jun 20, 2012 8:45 pm
Ronald de Man Wed Jun 20, 2012 10:44 pm
Joshua Shriver Thu Jun 21, 2012 1:51 am

 Jump to: Select a forum Computer Chess Club Forums----------------Computer Chess Club: General TopicsComputer Chess Club: Tournaments and MatchesComputer Chess Club: Programming and Technical DiscussionsComputer Chess Club: Engine Origins Other Forums----------------Chess Thinkers ForumForum Help and Suggestions
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum