A fast PRNG for generating hash codes

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

[smrf]

Well, may I show my simple generator here?

I use only special balanced generated random values (BalancedKey).

Code: Select all

// (C) 2011 R.Scharnagl, 80992 München, Deutschland

#include <ctime>
#include <climits>

#pragma hdrstop

#include "Tool.h"

// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// --- SPEICHER ---

// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// zuletzt erzeugten Zufallszahl, lokal
U32 Tool::seed = 0;
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// --- METHODEN (RANDOM) ---

// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// setzt positive Startzahl für Generator
U32 Tool::SetSeed(U32 newSeed)
{
  // den Seed neu festlegen
  seed = newSeed;

  // technisch geswapped ausgeben
  return (newSeed << 16) ^ (newSeed >> 16);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// setzt (Zeit-) zufällige Generator-Startzahl
U32 Tool::Randomize(void)
{
  using namespace std;

  // Zeitpuffer
  time_t thisMoment;

  // ermittle eine Startzahl aus der Systemzeit
  time(&thisMoment);

  return SetSeed(MAGIC * (U32)thisMoment);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// holt <unsigned> Zufallszahl
U32 Tool::Random(void)
{
  // neue interne Zufallszahl merken
  return SetSeed(seed * 87641 + 98731);
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// holt <unsigned> Zufallszahl aus [0, Limit)
U32 Tool::RangedRandom(U32 limit)
{
  // Ergebnis und anzupassende Obergrenze
  U32 answer, limValid;

  // bestimme ersten ungültigen Treffer,
  // um Ungleichverteilung zu unterbinden
  limValid = UINT_MAX - UINT_MAX % limit;

  // iterative gleichverteilte Erzeugung
  for (;;) {
    // solange neue Kandidaten testen
    answer = Random();
    // bis Gleichverteilung sichergestellt
    if (answer < limValid)
      return answer % limit;
  }
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

// liefert positive Zufallszahl, die als Binärzahl
// genau 50% Einsen hat (für XOR Overlay)
U32 Tool::BalancedKey(void)
{
  int bitDifference;
  U32 answer;

  // selektiere ideale Hash-Kandidaten
  do {
    // Prüfinstrumente
    U32 oneBit = (U32)INT_MIN;
    bitDifference = 0;

    // bilde Zufallszahlen
    answer = Random();

    // bis Gleichverteilung vorliegt
    do {
      if (answer & oneBit) {
        ++bitDifference;
      } else {
        --bitDifference;
      }
    } while ((oneBit >>= 1) != 0L);

  } while (bitDifference != 0);

  return answer;
}
// - - - - - - - - - - - - - - - - - - - - - - - - - - -

[hgm]

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.

To create a pseudo-random term in the evaluation, I derive it from the hash key itself. That can be done much cheaper than runing the presented PRNG, e.g. (hashKey ^ GAME_ID) * MAGIC >> 24 for an 8-bit random. Another advantage is that such a random term is actually consistent: if, in the same game, you reach the same position through two different paths, it will have the same evaluation.

[sje]

Well, may I show my simple generator here?

It looks like your function retains 32 bits of state information, therefore its period has to be less than or equal to 2^32.

Have you checked to see what the actual period is? Could the period be different for different seed values?

[sje]

To create a pseudo-random term in the evaluation, I derive it from the hash key itself. That can be done much cheaper than runing the presented PRNG, e.g. (hashKey ^ GAME_ID) * MAGIC >> 24 for an 8-bit random. Another advantage is that such a random term is actually consistent: if, in the same game, you reach the same position through two different paths, it will have the same evaluation.

Yes, but what if you don't want it to be consistent? It seems to me that this latter choice could be more useful for some applications.

[smrf]

It looks like your function retains 32 bits of state information, therefore its period has to be less than or equal to 2^32.

Have you checked to see what the actual period is? Could the period be different for different seed values?

The generator fully covers 32 Bit. Thus the seed value does not matter for the period. So it could be set to any value.

Following test routine has been used repeatedly:

Code: Select all

  // einen Startwert auslosen
  U32 val1 = Randomize();
  out << "Random Start Value:"
      << Hex(val1, 8) << endl << endl;

  // Wiederholungszahl bestimmen
  long long cnt = 0;
  do {
    ++cnt;
  } while (Random() != val1);
  out << "Full Cycle Count: "
      << ((U32)cnt == 0) << endl << endl;

[hgm]

Yes, but what if you don't want it to be consistent? It seems to me that this latter choice could be more useful for some applications.

I could not imagine any. The only reason I would want to have a random evaluation term is to act as a poor-man's mobility eval. And there it would be a severe mistake to count yourself rich because there happen to be many paths to the only node that offers an escape from total disaster, because that node gets an independent random eval every time, making it seem as though there were many escapes.

But if I would need an independent random, I would use something like Reinhard. The periodicity of 2^32 would not worry me very much, as by the time it would start to repeat the generated values would be used to take completely different decisions (in other nodes of the tree, for trees that search other positons). In practice, only the state of the entire system (chess game state + random seed + opponent) matters.

[sje]

Yes, but what if you don't want it to be consistent? It seems to me that this latter choice could be more useful for some applications.

I could not imagine any.

I can. Adjusting the bottom bit of a positional score independent of the position's hash could add variety to play. In fact, I'm fairly sure that this was done in some commercial dedicated units long ago; at least one unit with a Zilog z80 used the CPU's refresh register as the random source.

[hgm]

It will also add variety of play when it is done consistently. In fact this is how Joker gets its non-determinism.

Dedicated units long ago had no hash tables, so the consistecy was not that much of an issue. But with hash table I would not recommend it when there is no need for it. It just decreases search efficiency. The hash moves wik direct you to a node that had a high score the previous time, only to discover that this time that samenode is no good, because its random get recalculated.