How does randomness work on a computer, what are high-quality random numbers, how are they generated and what is an RNG? In this article we would like to explain how to generate randomness or at least pseudo-randomness on a computer.
When a computer shuffles cards for poker, it is of utmost importance that it does this well. That is: it should not be possible to predict which cards will be in which position in the deck, and each player should receive all cards with the same frequency over time. Towards the end of the nineties, Planet Poker was proof of how it shouldn’t work.
Generating real random numbers on a computer is impossible without a real physical random number generator. However, generating random-looking and non-predictable numbers is fortunately already sufficient. Numbers of this type make it possible to shuffle poker decks and guarantee a fair deal for all players.
The methods that generate such random-looking numbers on a computer are called pseudo-random number generators. How they work is described here.
How does a random number generator work?
To understand how a computer random number generator (RNG) works, let’s look at a very simple example.
The algorithm presented (the mean-square method) was developed by John von Neumann. Although it has some shortcomings, it is still very instructive.
The algorithm, which dates back to the 1940s, was mainly used to generate semi-random looking numbers on the ENIAC as quickly as possible.
This is how the algorithm works:
- 1. select any four-digit number (for example 4567).
- 2. multiply this number by itself (the result is 20857489)
- 3. remove the two leading and two trailing digits (8574).
- 4. a new four-digit number is generated and the algorithm is repeated to generate further numbers.
If you let the algorithm run for a while, it produces the following numbers (starting from 4567): 8574, 5134, 3579, 8092, 4804, 0784, 6146, 7733, 7992, 8720 and 0384 as well as 1474 look quite random at first glance. This is also sufficient for some tests with random four-digit numbers.
Seed and period The first number entered into such an algorithm is called the seed. If you feed an RNG with the same seed, it will generate the same numbers again.
For this reason, it is ideal to exchange the seed when you run the RNG again.
Many RNGs use the system time in milliseconds as the seed, as it changes often enough.
If you run the above algorithm a little longer, the numbers it outputs will eventually repeat. If you start with 4567, the 18th step will result in 4100. In the 22nd step, after 4 more steps, 4100 will come out again, and then the RNG will only output numbers that it had already output before.
The number of steps required until an RNG repeats itself is referred to as its period. As a rule, the longer the RNG period, the better it is.
The above-mentioned mean-square algorithm has a very short period for almost all seeds. The algorithm repeats itself for almost every initially selected four-digit number after 100 steps at the latest and immediately for some seeds (for example, if you start with 1000, the next steps will only contain zeros).
Quality of a random number generator The algorithms used by random number generators can vary greatly in quality. The period length is an indicator of the quality of RNGs. The rule of thumb here is quite profane: the longer, the better.
The period lengths of modern algorithms exceed 1030 steps. In other words, they can generate an enormous amount of numbers without repeating themselves in loops.
There are also comprehensive tests that examine whether the numbers generated are actually random from a statistical point of view. An RNG that generates values in the range from 0 to 100 should produce each number equally often in the long term. This also applies to the frequencies (such as 4, 6, 8 or 97, 17, 60), which should also occur equally often.
An RNG can undergo a total of over 100 statistical tests. These are known as big crush tests. Random number generators that pass all these tests produce numbers that are statistically indistinguishable from real random numbers (such as those from a physical RNG).
The selection of a suitable seed for the generator is also of fundamental importance. Even the most sophisticated RNG will repeatedly produce the same numbers with an identical seed.
As the Planet Poker example shows, too small a range of values for the seed can lead to the shuffled decks being predicted correctly.
Twisters, shifts and whirlpools The Mersenne Twister is a widely used RNG algorithm. This extremely fast algorithm simultaneously generates 64 random numbers between 0 and 4.3 billion with a period length of over 106000.
The Mersenne Twister is initialized using 64 random numbers generated by other means. Accordingly, the twister has a seed value range of extreme magnitude and a de facto infinite period for practical purposes. Once started, a Mersenne Twister can generate enough random numbers to shuffle all the poker cards in the world forever without the need for a restart.
Other algorithms are XOR shifts or the whirlpool, which is used for hashing.
However, physical random number generators are statistically the safest as they generate random numbers without any additional input. In places where random numbers and RNG have an important function (such as all modern online casinos and poker sites), physical random number generators are always used. Their scope includes at least providing seeds for other algorithms to shuffle the cards using algorithmic RNGs.
PokerStars does not only use a physical RNG: the company also collects user input to shuffle the game decks on a special server. In the following article in this series, we explain exactly how card shuffling works at PokerStars.
