A fast PRNG for generating hash codes

[sje]

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 PRNG in Common Lisp:

Code: Select all

;; ---------- Pseudorandom number generation

(defconstant prng-state-limit 25 "Period is 2,305,567,963,945,518,424,753,102,147,331,756,070")

(defconstant prng-prime-vec
  (make-array prng-state-limit
    :initial-contents
      (list 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97)))

(defvar prng-state-vec (make-array prng-state-limit :initial-element 0))

(defun prng-advance ()
  "Advance the PRNG by one step."
  (dotimes (index prng-state-limit)
    (incf (svref prng-state-vec index))
    (when (= (svref prng-state-vec index) (svref prng-prime-vec index))
      (setf (svref prng-state-vec index) 0))))

(defun is-prng-bit-set? ()
  "Determine if the current bit of the PRNG is set."
  (let ((result nil))
    (dotimes (index prng-state-limit)
      (when (oddp (svref prng-state-vec index))
        (setf result (not result))))
    result))

(defun prng-bit ()
  "Generate a pseudorandom bit and then advance the PRNG state."
  (let ((result (is-prng-bit-set?)))
    (prng-advance)
    result))

[sje]

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.

Code: Select all

;; ---------- Pseudorandom number generation

(defconstant prng-state-limit 31)

(defconstant prng-prime-vec
  (make-array prng-state-limit
    :initial-contents
      (vector
          2   3   5   7  11  13  17  19
         23  29  31  37  41  43  47  53
         59  61  67  71  73  79  83  89
         97 101 103 107 109 113 127)))

(defconstant prng-prime2-vec
  (make-array prng-state-limit
    :initial-contents
      (vector
          4   6  10  14  22  26  34  38
         46  58  62  74  82  86  94 106
        118 122 134 142 146 158 166 178
        194 202 206 214 218 226 254)))

(defvar prng-state-vec (make-array prng-state-limit :initial-element 0))

(defun reset-prng-state ()
  "Reset the PRNG state vector."
  (dotimes (index prng-state-limit)
    (setf (svref prng-state-vec index) 0)))

(defun prng-advance ()
  "Advance the PRNG by one step."
  (dotimes (index prng-state-limit)
    (incf (svref prng-state-vec index))
    (when (= (svref prng-state-vec index) (svref prng-prime2-vec index))
      (setf (svref prng-state-vec index) 0))))

(defun is-prng-parity-odd? ()
  "Determine if the current bit of the PRNG is set (i.e., odd parity calculaton)."
  (let ((result nil))
    (dotimes (index prng-state-limit)
      (when (>= (svref prng-state-vec index) (svref prng-prime-vec index))
        (setf result (not result))))
    result))

(defun prng-bit ()
  "Generate a pseudorandom bit and then advance the PRNG state."
  (let ((result (is-prng-parity-odd?)))
    (prng-advance)
    result))

[Dann Corbit]

Have you tested it with DIEHARD and/or the NIST validation suite sts-2.1.1?

Diehard (C version):
http://www.phy.duke.edu/~rgb/General/dieharder.php

NIST validation suite:
http://csrc.nist.gov/groups/ST/toolkit/ ... -2.1.1.zip

[sje]

Have you tested it with DIEHARD and/or the NIST validation suite sts-2.1.1?

Diehard (C version):
http://www.phy.duke.edu/~rgb/General/dieharder.php

NIST validation suite:
http://csrc.nist.gov/groups/ST/toolkit/ ... -2.1.1.zip

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.

[sje]

For a C++ implementation of the aforementioned Lisp PRNG along with a megabyte of sample output, see:

https://public.me.com/chessnotation

Directory: PRNG

Have fun.

[AlvaroBegue]

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).

[sje]

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.

Code: Select all

;; ---------- Pseudorandom number generation

(defconstant prng-state-limit 31)

(defconstant prng-prime1-vec
  (make-array prng-state-limit
    :initial-contents
      (vector
          2   3   5   7  11  13  17  19
         23  29  31  37  41  43  47  53
         59  61  67  71  73  79  83  89
         97 101 103 107 109 113 127)))

(defconstant prng-prime2-vec
  (make-array prng-state-limit
    :initial-contents
      (vector
          4   6  10  14  22  26  34  38
         46  58  62  74  82  86  94 106
        118 122 134 142 146 158 166 178
        194 202 206 214 218 226 254)))

(defun new-prng-state ()
  "Return a new PRNG state."
  (make-array prng-state-limit :initial-element 0))

(defun prng-state-advance (my-prng-state)
  "Advance the given PRNG by one step."
  (dotimes (index prng-state-limit)
    (incf (svref my-prng-state index))
    (when (= (svref my-prng-state index) (svref prng-prime2-vec index))
      (setf (svref my-prng-state index) 0)))
  (values))

(defun prng-state-parity-odd? (my-prng-state)
  "Determine if the current bit of the given PRNG is set (i.e., odd parity calculaton)."
  (let ((result nil))
    (dotimes (index prng-state-limit)
      (when (>= (svref my-prng-state index) (svref prng-prime1-vec index))
        (setf result (not result))))
    result))

(defun prng-next-bit (my-prng-state)
  "Generate a pseudorandom bit and then advance the given PRNG state."
  (let ((result (prng-state-parity-odd? my-prng-state)))
    (prng-state-advance my-prng-state)
    result))

[hgm]

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.

[CThinker]

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.

[sje]

Do PRNGs have to be fast?

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.