Author: Mike Siler
Date: 22:58:13 12/18/03
Go up one level in this thread
On December 19, 2003 at 01:24:27, Russell Reagan wrote: >On December 19, 2003 at 01:00:31, Steffen Jakob wrote: > >>I repeat my posting from below because the ruffian thread pushed it very fast to >>the bottom of the message list. :) >> >>What are you using for the hash key in your distributed perft implementation? >>How do you make sure that there are no hash key collisions which are possible in >>the usual zobrist key approach? Those collisions are too rare to influence the >>playing strength of a chess engine but would make the result of your perft >>project invalid. > >I remember Albert saying that he uses 128-bit hash keys, which is not >theoretically sound, but should work in practice. Deiter also uses hash tables >for this I think. Maybe he can tell us what he does. One could theoretically calculate the odds of a collision, because this is simply the famous "birthday problem" (if you get 23 random people together, there's about a 50-50 chance that two of them will share a birthday). If you randomly store N positions in a 128-bit key, which will be capable of holding 2^128 unique values, then the probability that two of them will be stored in the same value is 1-(2^128)!/[(2^128-N)!*(2^128)^N] (according to http://mathworld.wolfram.com/BirthdayProblem.html ) It would be interesting to see what this would yield with the number of positions in perft(10). The perft(11) and perft(12) projects probably won't be affected since they actually consist of several separate perft(8)'s, for which there are far fewer positions. Unfortunately, 2^128 is about 3.4*10^38 and there were 69,352,859,712,417 positions in perft(10). I'm not sure how anyone would be able to perform the above calulation with numbers that large. That might require its own distributed computing project... Michael
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.