Author: Sune Fischer
Date: 10:50:09 07/29/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. If you use 64 bit keys sqrt(2^64) is too low an estimate, it gives you only 2^32 which means you must be driving a 2^32 entry table ~= 48 GB full hashtable! :) I think Uri's number is closer, perhaps we are even talking weeks here, but obviously depending on speed of computer and size of the table. Also remember that not all nodes are probed, in most program it's probably only about 1/3 of the nodes, add to that that many of these are not different but in fact genuine hits (this ratio will also increase with hash size). It's going to be messy to factor all that in, but 1 collision a week on a fast machine with a resonably sized hash should not be an overly optimistic estimate. -S.
This page took 0.02 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.