Author: Sune Fischer
Date: 04:34:13 12/06/01
Go up one level in this thread
On December 06, 2001 at 06:23:14, David Rasmussen wrote: > >Not with tests from Crafty, no. Or any other program that uses a similar hashing >scheme. Perhaps your hashing scheme _is_ the problem, maybe that is why my results are better. >>Yes I read that he he "confirmed" your results, but if you really had 300 >>collisions you would have a really poor pawn eval(). > >There _are_ 300 collisions. Do you want me to show you the 600 positions in >question that has the same pawn hashkey (that is the definition of a collision), >and which comes in the first 3 minutes of search, and therefore causes true >collisions? What PRNG are you using? Have you optimized the zobrist table with respect to hamming distance? Someone proved a few days ago, that this might not be a good idea, you lose some randomness and large hamming distances is no guarentee that x1^x2^x3...^xn != y1^y2^y3...^ym. > I have already posted one pair. I have verified the first 10-15 >pairs. They were all collisions. You theoreticize. You say "because I can't >understand it, and it doesn't work with my theory, it can't be true". Like the >clericals and scholars, when Galileio asked them to look in his newly invented >telescope, to see with their own eyes the imperfections of the moon, the moons >of jupiter, that they didn't believe could be true. They said "It doesn't fit >with out theory, so it can't be true. And we don't care for hard evidence." Galileio was a scientist, they were not, they were from "the old school". If you want a piece of hard evidence you need to understand some basic math (the birthday problem) instead of relying on some errorprone codes. Hard proof comming your way: If you have 10000 random numbers between 0 and 4000000000 what are the odds that these are _all_ different? The first you can pick in for free, the next you can "only" pick in 4000000000-1 different ways so there is 3999999999/4000000000 chance that it will be different, the next is 3999999998/4000000000 chance and so on. You multiply all these together and get ~0.99 which means there are 99.0% chance that they will all be different! Try and solve this fraction, it is an upper bound on the probability for not having _any_ collisions: ((4000000000. - 10000)/4000000000)^10000 I can tell you the number is 0.97531, so there is 97.531 percent chance of _not_ having a collision! Of cause in real life you do not have a perfect PRNG nor do you need to keep all 10000 at the same time, some will be overridden in the table. The estimate is pretty good I think. >>I think some things has >>changed in crafty since last Robert tested, perhaps a bad PRNG? >>32 bits is enough, I'm pretty sure of it (both theoretical and emirical), unless >>you have too many positions. >> >>>>Huh? >>>>Neither me or Hyatt can confirm your findings, and since Bruce is also using >>> >>>Yes, Hyatt has. >> >>Give him more time, perhaps he will find the bug :) > >I give up. You'll never believe that 32 bits cause collisions, will you? I will honestly :) But you need many more positions to get those numbers. You simply _can't_ get 300 collsions out of 10000 random 32 bit numbers, if this is what you get, then try a different PRNG! I think Bruce and I use the same PRNG (I got it from his website), this could be why we are not getting those collision rates. And I am not doing any Hamming tricks to my Zobrist table. -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.