How do pseudorandom number generators work

Poker RNG - How does randomness work on a computer?

How does random work on a computer, what are good random numbers, how do you generate them and what is an RNG? In this article we want to explain how to create randomness, or at least pseudo-randomness, on a computer.

When a computer shuffles cards for the game of poker, it is extremely important that they do too Well mixes. In other words: You shouldn't be able to predict which cards are where in the deck and in the long run every player should receive all cards with the same frequency. How not to do it was demonstrated by Planet Poker in the late 1990s.

Without a real physical random number generator, it is impossible to generate real random numbers on a computer. Fortunately, it is enough if you can generate numbers that look random and cannot be predetermined. With the help of numbers like this, one can shuffle decks in poker and ensure a fair deal for all players.

Methods that generate such random-looking numbers on a computer are called pseudo-random number generators and how these work will be explained here.

How does a random number generator work?

To understand how a random number generator (RNG for short) works on a computer, let's look at a very simple example.

The algorithm presented here (the mean square method) comes from John von Neumann and even if he has quite a few flaws, it is still very instructive.

The algorithm dates back to the 1940s and was primarily used to generate semi-random-looking numbers for tests on the ENIAC as quickly as possible.

This is how the algorithm works:

1. Take any four-digit number (such as 4567).
2. Square this number (it comes out 20857489).
3. Delete the two front and rear digits (8574).
4. You have a new four-digit number and use it to repeat the algorithm to generate new numbers.

If you let the algorithm run a little, it produces (based on 4567) the following numbers: 8574, 5134, 3579, 8092, 4804, 0784, 6146, 7733, 7992, 8720, 0384, 1474 - at first glance that looks pretty random and that's enough for a few tests where you need random four-digit numbers.

Seed and Period

The first number that you put into such an algorithm is called Seed. If you feed an RNG with the same seed, it will produce the same numbers again. That is why you try to select this seed as often as possible when you run the RNG again.

System time as a seed

Many RNGs choose the system time in milliseconds as the seed, because this changes sufficiently often.

If you take the above algorithm and let it run a little longer, the numbers spit out will repeat themselves at some point. If you start with 4567, you get 4100 in step 18. After 4 more steps (in the 22nd), 4100 comes out again and then the RNG only spits out numbers that it had already spit out before.

How many steps it takes for an RNG to repeat itself is called that period of the RNG. Typically, the larger the period of an RNG, the better it is.

The above center square algorithm has a very short period for almost all seeds. For almost every initially selected four-digit number, the algorithm is repeated after 100 steps at the latest and immediately for some seeds (if you start with 1000, the next steps only come with zeros).

Quality of a random number generator

The algorithms of random number generators can be of very different quality. The length of the period is a characteristic of the quality of RNGs. The rule here is pretty mundane: the longer, the better.

Modern algorithms have period lengths beyond 1030 Steps up. In other words, these can generate an incredible number of numbers without repeating themselves in loops.

There are also extensive tests that check whether the numbers that are spat out are actually statistically random. An RNG that produces numbers between 0 and 100 should spit out every number with the same frequency in the long run, and all frequencies (say 4, 6, 8 or 97, 17, 60 in a row) should appear with the same frequency.

In total, there are over 100 statistical tests that an RNG can undergo. These will Big crush tests and in the case of random number generators that pass all these tests, the numbers produced can no longer be statistically differentiated from real random numbers (e.g. generated via a physical RNG).

The choice of a suitable seed for the generator is also elementary. Even the most advanced RNG will produce the same numbers over and over again if you choose the same seed.

As you have seen in the example of Planet Poker, a range of values ​​for the seed that is too small can lead to the fact that you can correctly predict the shuffled decks.

Twisters, shifts and whirlpools

A very physical twister

A very common RNG algorithm is that Mersenne Twister. This extremely fast algorithm always generates 64 random numbers between 0 and 4.3 billion simultaneously and has a period length of over 106000.

The Mersenne Twister is initialized via 64 random numbers found in another way. Accordingly, the twister has an extremely high range of values ​​for the seed and, for practical purposes, a de facto infinite period. Once started, a Mersenne Twister can generate enough random numbers to shuffle all the poker cards in the world forever without having to be restarted.

Other algorithms are XOR shifts or the Whirlpoolwhich is used for hashing.

From a statistical point of view, however, physical random number generators are the safest, as they generate random numbers without any further input. Wherever random numbers and RNG play an important role (for example in all modern online casinos and poker sites), physical random number generators are always used. At least their area of ​​application is the provision of seeds for other algorithms so that they can shuffle the cards via algorithmic RNGs.

PokerStars not only uses a physical RNG, but also picks up user input in order to mix the decks for playing on a separate server. In the next article in this series, we'll explain exactly how shuffling the cards works at PokerStars.