Author: Angrim
Date: 12:40:03 07/30/03
Go up one level in this thread
On July 29, 2003 at 13:35:55, Dann Corbit wrote: >On July 29, 2003 at 13:09:35, Uri Blass wrote: > >>On July 29, 2003 at 12:25:39, Rick Bischoff wrote: >> >>>Hi, >>> >>>While my rate of 118/88570 was indeed high (I had a bug in the zobrist key >>>generation...), the rate you quote (one false match every few days) is way too >>>low!! Hash size is really irrelevant here assuming you store the full 64 bit >>>key in the hash table and only return a move if the keys match (which is what I >>>am doing); Anyway, it is the birthday paradox.. the more keys you have, the >>>better chance there is that at least two of them will share a key. >> >>Let assume that you have 2^24 keys. >>It means that the probability for collision is 1/2^40 so you may get less than >>one collision for 2^40 nodes or one collision in few days. > >Due to the birthday paradox, with a 64 bit keysize, you will start having to >worry about collisions around sqrt(2^64) = 4 billion key stores. If you can do >one million NPS (on a fast machine), then about 1000 seconds of search. On an >average machine, perhaps one hour of compute time. On an average machine, you don't have 20*2^32 bytes of ram to store all of those positions. My actual hash size that I used to calculate my collision rate is 2^23 entries, for a collision rate of 1 in 2^41 positions searched. Angrim
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.