One way to provide instrumentation for collision detections is 
to either reserve a few bits for the purpose, or allocate a
few extra bits for this purpose.  

For instance,  if you have a 64 bit key, use 60 bits instead
and let 4 bits be for collision detection.  If the 60 bits match,
but the 4 bits do not match, then you can report a collision
in your log file.  You will never get a false collision reported
but about 1 out of 16 collisions would fail to get detected.

So if you are happy with the collision rate of 60 bits,  then
you can be about 16X happier with 64 bits!
You could of course extend this to 8 bits for instance,  and
then only 1/256 would fail to get reported.    

- Don

On Sun, 2007-02-11 at 19:35 +0100, Antoine de Maricourt wrote:
> > Please do.
> I will put it on a web page. But I need some time. My job keeps me very 
> busy right now.
> >> But I'm not sure I
> >> will post the statistical analysis (it was almost ten hand writen pages,
> >> and I'm not sure I still have them).
> > Have You performed an empirical test for collisions?
> No, analysis was analytic. I've used the scheme in different ways, and 
> since I knew were was the defect I put extra code to protect from the 
> defect. This proved to be usefull... I was able to catch collisions at 
> low rate in practice, but this rate would have been unacceptable if I 
> had not been able to detect them.
> The defect is as follow: if you have 2 different board configurations, 
> the probability that they have the same hash key can be as low as 1/256 
> (for a 64-bit key) if the difference between the 2 configurations has 
> self symmetries. Anti Huima's scheme had the same defect, except the 
> probability was 1. That's why I've been able to isolate it: I always had 
> collisions between the same positions, and it didn't depend on the way 
> random bits were generated.
> Antoine
> _______________________________________________
> computer-go mailing list

computer-go mailing list

Reply via email to