backgammon RNG FAQ

Random Number Generator

Which RNG does GamesGrid use?

Mersenne Twister (MT) is a pseudorandom number generator developed by Makoto Matsumoto and Takuji Nishimura (alphabetical order) during 1996-1997. MT was designed specifically for Monte Carlo simulations, to overcome the flaws found in previous generators. It has far longer period and higher order of equidistribution than other generators: the period is 2¹⁹⁹³⁷-1 (approximately 4 followed by 6001 zeros), and 623-dimension equidistribution is assured. Period is the number of occurrences before the sequence repeats; the huge period of the MT generator means that for practical purposes, the sequence never repeats. Equidistribution means that every sequence of 623 (or fewer) dice is guaranteed to occur with the correct frequency over the period of the generator. More information may be found on the MT home page. A slightly more readable version may be found at wikipedia.org. MT is one of the few RNGs that passes the independent DIEHARD and ENT randomness tests. Some test results are available at the randomizer site.

How are the dice rolls generated?

The dice you receive as a GamesGrid player are generated by a two-step process. The process is designed to produce a sequence that is indistinguishable from a sequence that would be produced by high-quality precision dice.

Step 1: The core random backgammon number generator (RNG) in the GamesGrid server produces a single sequence of numbers (the core sequence). This sequence of numbers is initialized at a different starting point each time the game service is started. Think of the core sequence as a very, very long series of random numbers, which are returned in order as they are requested. The period of the RNG is described above it is very, very long.

Here is an example of a small portion of a core sequence produced by step 1:

core sequence

...

If only one game was being played, or if the same core sequence was given directly to all games, a clever and talented (and dishonest) person might be able to use sophisticated computer analysis to detect the nature of the sequence (even if it was encrypted). They could then predict future dice rolls (in the example: 16, 25, 44, 34, 65). In order to prevent that possibility, the GamesGrid uses the standard technique of distributing the output of the core sequence among all players, as described in step 2. (Most, but not all, game services use similar techniques.)

Step 2: In a multi-user environment like GamesGrid, many users request dice nearly simultaneously, as needed to play their games. Whenever any player requests a dice roll (or requests a random number for any other purpose), the next numbers in the core sequence are sent to that requester. But long before that player (or their opponent) can request another roll from the core sequence, many other players will have requested rolls. In fact, the amount of time that elapses before a player requests a roll has a direct effect on the dice that are rolled. This is equivalent to "shaking the dice in the cup" for a little longer: the outcome will be different, but still perfectly random.

So long as more than one game is being played, the numbers returned to an individual requester are an unknown distance along the core sequence from the numbers sent in response to their previous request. Consequently, the numbers that are returned to the requester cannot be predicted. And once the numbers are requested, they are stored on the game server, so they cannot be altered even if the game is interrupted before the dice roll is received by the clients.

Here is the same example from the core sequence, with games A, B, and C identified by different colors. Assuming that requests for dice arrived from the games in the order A, B, A, C, B; then the requests would be returned to the three games as shown:

core sequence	...	1	6	2	5	4	4	3	4	6	5	...
game A		1	6			4	4

game B				2	5					6	5
game C								3	4

Of course, the players in each game alternate turns, so the players in-game A received 61 and 44, respectively. Between those rolls, a player in-game B received 52. Later a player in-game C received 43, and then the other player in-game B received 65.

Using this two-stage technique, the sequence of rolls received by any player is completely random, and cannot be predicted.

last modified: 2005-04-27