Author: Janosch Zwerensky
Date: 05:34:29 09/23/01
Go up one level in this thread
>If you zobrist table is perfect, >eg. it will generate all 64 bit keys with equal probability, >then the chance of a collision happening is less than a billion to 1!! The probability of not getting two identical hash keys from N randomly chosen positions should be equal to product((2^64-i)/2^64,i=0..N-1) imho. Last time I checked, that meant that the probability of not getting two different positions that have the same hash key in a search tree of 10^7 nodes was roughly equal to 0.999997289498, given that your hashtable had significantly more than 10^7 entries (otherwise, the above formula breaks down and the probability of not getting a hash collision will be somewhat bigger, though the difference is certainly too small to show up empirically in any practically accessible way). Anyway, for a sixty move game the probability of not getting one hash collision should, given search tree sizes of around 10^7 positions per move, be somewhere near that number raised to the 60th power, which would yield an around one in six thousand chance of a hash collision happening in the course of one game. Thus, I'd conclude that a) with a 64 bit hash key the probability of getting hash collisions is pretty low with current search tree sizes and that b) the probability of getting hash collisions in long searches does grow with hash table size, but only by insignificant amounts. Regards, Janosch.
This page took 0 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.