Author: martin fierz
Date: 07:37:28 04/07/04
Go up one level in this thread
On April 07, 2004 at 10:21:38, Sune Fischer wrote: >>>> >>>>your number is much too high. a good estimate for the hash collision probability >>>>is 1/sqrt(hashkey_range); which in your case comes out as 2^-32 or about >>>>somewhere around one in a billion... >>> >>>Not at all. It's way less than that with 64 bits Zobrist. >> >>i never took the trouble to measure it, but the math is rather straightforward. >>so i'd say you have an implementation bug too ;-) >> >>cheers >> martin > >Not necessarily. If he has a very large hash table with more than 2^32 entries >the probability of a collision increases rapidly with 64 bit keys. you are right of course that vincent should have given the size of his hashtable. but: 2^32 = 4 billion, with 12 bytes per entry (?) you are talking 48GB here. i hardly think his hashtable has that kind of size. then again, with his supercomputer stuff, who knows? i tacitly assumed that he didn't have that kind of table size. besides that, it doesn't really matter: you are probably interested in a collision frequency, e.g. 1 collision per X lookups. the birthday problem doesn't really apply to this: it gives you the probability that *any* two hashkeys in your table are identical. this probabiltiy has a different behavior than the actual collision rate... cheers martin > >It's the birthday problem, the more kids you have in the class the bigger the >chance of two birthsdays falling on the same date. > >If you have a only a single hash entry the chance will be 2^64 of a collision, >assuming perfect randomness. > >-S. >>>I measured it with 460 processors at a supercomputer with a shared hashtable and >>>had major problems to get at 7 million nodes a second stored, some >>>errors/collissions. >>> >>>>make sure you're not doing anything wrong with the hashkey updating like >>>>suggested by others - compare with a computed-from-scratch key. also make sure >>>>that your nullmove doesn't break your hashkey. and just to be sure, check that >>>>you haven't got 32-bit numbers instead of 64 bit numbers by accident... >>>>cheers >>>> martin >>> >>>I'm sure it was some implementation bug with Renze.
This page took 0.01 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.