TalkChess.com
Hosted by Your Move Chess & Games

Author Message
Daniel Shawul

Joined: 14 Mar 2006
Posts: 2186
Location: Ethiopia

Post subject: Some tests: Attn Don    Posted: Sat Jun 16, 2012 6:25 pm

marcelk 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.

You can get a good estimate by measuring the number of near-collisions.
For example, each time you have a miss, count how many of the left-most bits match (xor and look for the highest bit set, call that index 'b'). Then do count[b]++. Then make a histogram with b on one axis, and log(count[b]) on the other. You should get a linear plot once you have enough measurements. The number of false hits would be approximately count[0]/2.

There are variants on this that are essentially the same (instead of xor use substraction, or count hamming distance, or count right-most match etc)

Thanks for the suggestion. I think that will be a good way to measure for PRNG generated hash keys when collisions are very rare. Because of that it may better to test for similarity of keys...

I did a quick test over the forumulas we have been examining and the collision rate is embarassing :(The keys differ in a subtle way and they look good visually but there are many collisions.
FNV-1 => 25000 collisions/sec
FNV-1a => 15 collisions/sec
The one I suggested with a rotate & multiply => 1600 collisions/sec !!
 Code: const U64 C1 = U64(0x109951162821a737);    U64 h = U64(0xeadf018b615d3be8);    h = (h << sq) ^ (h >> (64 - sq));    h *= C1;    h = (h << cp) ^ (h >> (64 - cp));    return h;

I changed the third line to
 Code: h += C1

and collions dropped to => 0 collions/second so far...
Visual inspection is definately misleading. And the power of additions is revealed again

More later
_________________
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
Some tests: Attn Don 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
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