Author: Sune Fischer
Date: 17:18:36 12/03/01
Go up one level in this thread
On December 03, 2001 at 18:36:50, David Rasmussen wrote: >On December 03, 2001 at 18:05:43, Sune Fischer wrote: > >>On December 03, 2001 at 17:50:15, David Rasmussen wrote: >> >>>On December 02, 2001 at 23:58:43, Robert Hyatt wrote: >>> >>>>On December 02, 2001 at 22:38:30, David Rasmussen wrote: >>>> >>>>>Many people use 32-bit pawn hashkeys. But I've found that 32 bits is not enough >>>>>to avoid collisions. 64-bit seems to be enough, and maybe less could do the job. >>>>>Why do people use 32-bit keys, when it screws up evaluation this way? >>>>> >>>>>/David >>>> >>>> >>>>32 is ok for pawns. To see why, figure out how many _different_ positions >>>>there are with only pawns on the board. The number is not as large as you >>>>might think, which makes collisions unlikely so long as you _only_ hash pawn >>>>positions. >>> >>>Are you saying that if I'm seeing collisions, I have a bug, or are you saying >>>that 300 collisions out of 60.000.000 successful probes is not a problem? If the >>>latter, then why? How can you be sure? >>> >>>/David >> >>I would say so, 300 collisions is way too high, even if you used a 32^2 entry >>size table you shouldnt get more than 1 collision per 100 game or so. >>Using a smaller table will decrease the probability even further. >> >>-S. > >Mmm.. But I use a wellknown good PRNG, the avg. hamming distance of the keys is >good, the distribution of the keys is good, and I have no collisions at all >using this PRNG for generating my 64-bit keys for the trans/ref table. So how to >find my bug... I seriously doubt that there's a bug, but one always does... :) >Any ideas of how to find such a bug? heh, not really I have a bug myself, been looking for it for 2 months, I'm really stuck.. :( Using large hamming distances for the zobrist table sound very "okay", but when you say 60,000,000 probes have you testet how many of these are successful? My numbers are something like this: Average Node-Speed:....... 177.54 kNs Total Nodes Reached:...... 11364494 Total Evaluations:........ 7414407 Total Pawn Evaluations:... 5062 the pawn eval() is part of the standard eval(), but most of the time the pawn hash has the score, so the function was only called 5062 times in that game. I currently use 64 bit keys, but I think 32 bit is okay because... The probability of none of the 5062 will collide is: x = (2^32-1)*(2^32-2)*...(2^32-5062)/(2^32)^5062 ~= ((2^32-3000)/2^32)^5062 ~= 0.9965 so the probability of a collision is 1-x=0.004 ~= 1/200. So in ball park figures thats 1 in every 200th games. So I think the 300 sounds a little high. Maybe you can debug by putting more position knowledge into the hash, I have been debugging by storing the _full_ position info in the hash. I found that there where collisions if I didn't do en-passent flags, so I'm now doing that too. Mayby castle rights needs to be added too, but I haven't seen a collision there yet. -S.
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.