Author: David Rasmussen
Date: 05:12:22 12/06/01
Go up one level in this thread
On December 06, 2001 at 07:34:13, Sune Fischer wrote: >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. > Perhaps it is. Talk about that to Hyatt. It's his program. >>>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. > Ask Hyatt. >> 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. Errorprone codes? What does that mean? Anyway, I think you need not worry about me understanding the math. After all, I study math. I know of the birthday problem. It's not necesarily relevant here. Sequences of chess positions following the chess rules are not random. They have redundancy. >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 don't. This is not hard evidence. This is theory based on false assumptions and a wrong model. Hard evidence is hundreds (or thousands or millions if you want) of pairs of positions that has the same pawn hash signature in Crafty. That is by definition a collision. Could there be a problem with Bob's random numbers? Sure, but I doubt it. Also, when we talked about a 32-bit hashing scheme we both meant a "simple" one. That is, one where you generate random numbers, not one where you handpick every number. Surely there is some linear og non-linear algebraic code of high dimension that will have fewer collisions than "good" random numbers, but, we were talking about random numbers, which is what "people" use. Hyatt admits it is not good enough. I would like to see Bruce do a similar experiment. >>>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! > Talk to Hyatt about that. As for me, I have tried many different PRNG's. All with similar results. >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. > I will try his PRNG then.
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.