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@computer-go.org > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
