TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Daniel Shawul

Joined: 14 Mar 2006
Posts: 2187
Location: Ethiopia

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

lucasart wrote:
 Daniel Shawul wrote: Is there a way to directly measure the number of hash collisions (not its effect). I was thinking of storing the fen along with the hash key in transposition table entry, so that if the signatures match but the fens don't it would be collision. Is there a better way ? Edit: Right after I write this I realized storing _two_ hash keys is better than this (one could be a string hash of the fen). If the primary keys match but the second one don't it is a collision.

Be careful with comparing FEN. The FEN also contains the 50 move counter, and the play count. Those must be discarded, or course.
Probably easier would be to have a benchmark method, uwing 64 bits of a known good PRNG (like the Mersenne Twister or Bob Jenkins' 64 bit KISS). These hould have no collisions, or collisions would be so rare that you probably wouldn't see one in all your testing time. Now you can compare other PRNG by reducing the number of bits.

I wonder for example, how often you get collisions with 32 bits of an MT or KISS. For example Stockfish uses 32 bits only of Bob Jenkins' KISS 64 bit generator, and I use 62 bits of the same generator. Probably 32 is enough, but I wanted to be on the safe side.

I tested both and it seems I get 240 collisions/million on average for 28-bit key length with any decent PRNG. So p = 0.24*10^-3 collision rate for 28 bit key and a hash table of 1<<16 entries with bucket size of 1. I am quoting this detail for anyone that wants to do some calculations to arrive at an approximate figure. Once the mean rate of collision is known poisson equation can be used for prediction.
_________________
https://github.com/dshawul
 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
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
Re: how to measure frequency of hash collisions. 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