Author: Vincent Diepeveen
Date: 07:16:43 04/07/04
Go up one level in this thread
On April 07, 2004 at 10:14:27, martin fierz wrote: >On April 07, 2004 at 10:03:33, Vincent Diepeveen wrote: > >>On April 07, 2004 at 09:19:13, martin fierz wrote: >> >>>On April 07, 2004 at 09:14:42, Vincent Diepeveen wrote: >>> >>>>On April 07, 2004 at 08:27:59, martin fierz wrote: >>>> >>>>>On April 07, 2004 at 06:49:59, Renze Steenhuisen wrote: >>>>> >>>>>> >>>>>>Hi all, >>>>>> >>>>>>could someone give me some numbers that are common with hashkey collisions? >>>>>>Because I guess my % is little too high... >>>>>> >>>>>>I'm getting like 0.03% [which is 1 every 3000, if I'm not mistaken] >>>>>> >>>>>>This is when using TT=32MB (haven't got the exact number of entries) >>>>>> >>>>>>If you think it is an error, any suggestions on where to start looking? >>>>>> >>>>>>Thanks! >>>>>> >>>>>> Renze >>>>> >>>>>hi renze, >>>>> >>>>>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 ;-) >> >>You do not store 64 bits i bet but just like 32 bits or so and use the rest for >>index. So effectively having like 60 bits at most. > >that's not a big difference. 2^-30 is still a very small number :-) > >cheers > martin I realized very soon that not a single statistical model is correct for predicting collissions/errors when using a large number of bits for hashing. All models are assuming IMHO incorrectly that the domain which gets hashed is having more positions than the hashkeys range. >>Note that i also store the color in a special bit. >> >>So i had a garantueed 65 bits in DIEP. >> >>Note that i write i 'had'. >> >>>cheers >>> martin >>> >>>>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.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.