The following code implements a fast PRNG (pseudorandom number generator) that can be used to provide hash codes for a Zobrist hash signature generator. This PRNG is based on the theory behind commercial white noise generators and provides a long period bit sequence that has excellent aperiodicity. This PRNG uses no floating point operations, no multiplication, division, or even subtraction; just addition and comparison of small integers along with array indexing.
The following code produces a somewhat better pseudorandom bit stream. It works by setting up 31 periodic bit streams, the nth one of each has a period of 2 * Pn where Pn is the nth prime number. For the first half of its period, a Pn bit stream outputs a 0 bit; during the second half a 1 bit is produced. The value of the nth pseudorandom bit is the exclusive-or of the outputs of the 31 prime bit streams.
The period is about 8.6 * 10^57.
Note that all the arithmetic can be done with unsigned eight bit integers.
Well, not yet. I have been testing the generated codes in a chess environment and all seems okay. In fact, the new CIL toolkit can set a hash code length at any number of bits from one on up, so it is possible to see at exactly what the minimal hash code length is for certain construction tasks.
It might take months for me to get around to testing my PRNG with a third party harness. But others are welcome to give it a try.
I don't read LISP, so I can't comment on your method. I want to point out that comparisons of small integers can result in hard-to-predict branches, which are way more expensive than multiplications on modern hardware. However, the performance of your PRNG is not particularly important for the generation of Zobrist-key tables: They are pretty small, so you can just hard-code them into your chess program.
My favorite method for generating these tables is this: take several methods (e.g., a Mersenne twister, the first bytes of your executable, The MD5 hash of {"1","2","3",...}, and whatever /dev/random spits out on some computer running Linux) and XOR their outputs together. XORing guarantees that the resulting tables are at least as random as the most random of the ingredients (this statement can be made precise).
I've improved the Lisp PRNG by having the PRNG state vector be a parameter instead of being a global variable. Timing experiments with the new routines running on a modest machine show a bit generation rate of about 500 Kbps. For a man/square hash code table with 768 entries and a 128 bit code per entry (98,304 bits total), the initialization time is about a fifth of a second. Of course, the C++ implementation would be relatively faster, but that makes little difference as the table needs to be generated only once per program invocation.
I have yet to encounter a random generator that is so poor that the Zobrist keys generated with it performs below average. If it produces all zeros, or too few bits, then it is no good, but that is about all.
I must admit I never tried to measure the performance of super-simple PRNG like (seed *= 0x10003)>>16 for a 16-bit random.
hgm wrote:I have yet to encounter a random generator that is so poor that the Zobrist keys generated with it performs below average. If it produces all zeros, or too few bits, then it is no good, but that is about all.
I must admit I never tried to measure the performance of super-simple PRNG like (seed *= 0x10003)>>16 for a 16-bit random.
I totally agree.
I myself use a simple linear congruential generator. I have tried all sorts of more sophisticated RNGs, but so far, none has yet to make any significant improvement over the LGC as far as zobrist keys are concerned. Mind you, we just need less than 1,000 64-bit numbers. Some engines simply hard-code the zobrist keys.
Plus, the RNGs don't need to be fast. The RNG is only used once (at program start-up) and only has to generate a few numbers.
It depends on the definition of "fast". When loading an interpreted toolkit, a start-up time of 200 milliseconds is fast, but a delay of 20 seconds is not. And that can be the time difference between the above PRNG and one that uses a lot of tricky calculation.
Also, a PRNG has more uses than just making Zobrist hash codes. Consider the case where some randomness is desired in positional evaluation scores, perhaps changing the bottom two bits of a score. This means that the PRNG would be called many, many times in a search, so it needs to be fast.