ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

how to measure frequency of hash collisions.
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 12911
Location: Amsterdam
PostPost subject: Re: how to measure frequency of hash collisions.    Posted: Sat Jun 16, 2012 10:12 pm Reply to topic Reply with quote
Daniel Shawul wrote:
Is there a way to directly measure the number of hash collisions (not its effect).

I was just asking myself the same question. I wrote a program to generate random positions (assign random squares and piece types to a number of piees, taking care of that no square is used twice), and compared the number of collisions I got with truly random Zobrist keys, and keys derived with your pieceKey+squareKey idea. I checked with a second key, but that wasn't really needed, because all primary key matches were indeed collisions, as the chances to randomly generate the same position twice are about zero. I could not detect significant difference in collision frequency between the random key and the composite key.

I don't think this is a decisive test, though. What is important is how many collisions you get when you have a set of very similar positions, as occur in a search tree.

A method I used in the past to test the quality of a set of Zobrist keys is is to count the number of 'dependency loops': subsets of N different keys that XOR to zero. For a given key length and a much larger total number of keys there is a certain N beyond which such cycles cannot be avoided. The quality of the set of keys is determined by whether you already have cycles of lower N (i.e. an unnecessary dependency between a small number of keys).

E.g. with 768 keys you have 768*767*766/6 = 75M different 'products' (XORs, actually) of 3 keys, which conceivably could all be different if the key length is 27 bit (75M < 2^27). This means that you can have key sets of 27 bit where no product of 6 keys can be zero. You have 14G different products of 4 keys. So with 32-bit keys there must be duplicats, meaning there must be products of 8 keys that are zero. Keys of realistic length (such as 64 bit) are hard to test, because collisions are extremely rare. So it is best to test model systems of short key length, where collisions are frequent, and you can efficiently detect them by storing the complete key space in a table (so you can easily detect how often a product of N keys is repeated). Cycles of odd length (say 7) can be detected by putting all products of 3 keys in a hash table, and then checking all products of 4 keys against that table, to see if they occur there.

Note that is not yet the full story: in practice a vary bad dependency (like 3 keys XORing to 0) could be completely hidden by putting the bad keys in the table for a piece type that only occurs once (like King).
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 4:45 pm
      Re: how to measure frequency of hash collisions. Marcel van Kervinck Sat Jun 16, 2012 5:25 pm
            Some tests: Attn Don Daniel Shawul Sat Jun 16, 2012 6:25 pm
                  Re: Some tests: Attn Don Daniel Shawul Sat Jun 16, 2012 7:15 pm
      Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 9:17 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:05 pm
                  Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 10:23 pm
                        Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 10:29 pm
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 11:06 pm
                              Re: how to measure frequency of hash collisions. Don Dailey Sat Jun 16, 2012 11:39 pm
                                    Re: how to measure frequency of hash collisions. Kevin Hearn Sat Jun 16, 2012 11:50 pm
                                          Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 12:08 am
                                          Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 12:40 am
                                    Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 11:54 pm
                                          Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 12:23 am
                                    Re: how to measure frequency of hash collisions. Marcel van Kervinck Sun Jun 17, 2012 7:55 am
                  Re: how to measure frequency of hash collisions. Don Dailey Sun Jun 17, 2012 1:26 am
      Re: how to measure frequency of hash collisions. Ed Schroder Sat Jun 16, 2012 9:36 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:01 pm
      Re: how to measure frequency of hash collisions. H.G.Muller Sat Jun 16, 2012 10:12 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sat Jun 16, 2012 10:31 pm
            Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 2:00 am
                  Re: how to measure frequency of hash collisions. Rémi Coulom Sun Jun 17, 2012 8:30 am
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 10:49 am
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 2:58 pm
                              Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 3:41 pm
                                    Re: how to measure frequency of hash collisions. 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
                                                Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 9:57 pm
      Re: how to measure frequency of hash collisions. Lucas Braesch Sun Jun 17, 2012 3:02 am
            Re: how to measure frequency of hash collisions. 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
                  Re: how to measure frequency of hash collisions. Ronald de Man Sun Jun 17, 2012 9:14 pm
                        Re: how to measure frequency of hash collisions. Daniel Shawul Sun Jun 17, 2012 10:01 pm
      Re: how to measure frequency of hash collisions. Joshua Shriver Wed Jun 20, 2012 8:45 pm
            Re: how to measure frequency of hash collisions. Ronald de Man Wed Jun 20, 2012 10:44 pm
                  Re: how to measure frequency of hash collisions. Joshua Shriver Thu Jun 21, 2012 1:51 am
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
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




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads