[Randomness, Pokemon, and PRNGs]

Randomness is an illusion. In the physical world, events feel random, but this property only truly exists on the quantum level*. Classical systems (most real life interactions) may appear chaotic and are unpredictable in practice but are not truly random. For example, if you could measure every value precisely enough, the roll of a dice would be entirely predictable. So would the shuffling of cards. The unpredictability we perceive is caused by chaos and incomplete information. It is not random.

Computers have the same problem. A machine running deterministic instructions can only simulate, but cannot produce, true randomness. To do this, computers use algorithms called Pseudorandom Number Generators (PRNGS). They take a starting value (known as a seed) and apply mathematical operations to produce numbers that are meant to appear and be used as random. In practice, these numbers are entirely reproducible, and given the same seed the algorithm will always produce the same output.

PRNGs are foundational to cryptography and game design. In security, they generate encryption keys, session tokens, and anything else that must be unpredictable (which, in security, is a lot). They also drive a lot of the behavior that makes a video game feel dynamic and “alive”. In both cases, the quality of the randomness determines how exploitable the system is. Both depend on a strong algorithm that should not be able to be easily manipulated.

The Pokémon games are a great case study in the evolution of pseudorandom number generation. Because so much of the game depends on random encounters and outcomes, communities of players spent a long time reverse engineering the exact algorithms powering those systems. Their goals were similar to an attacker’s, and by understanding the generator well enough, they could predict and manipulate the output. The history of PRNGs in Pokémon is essentially a compressed history of the field itself. Generation I of the game featured a trivially breakable algorithm, while later games starting with Generation VIII made any manipulation nearly impossible.

Each algorithm in this project is implemented in C. I have shown the results with live output showcasing the internal state and generated values at each step. Implementations for each generator are available on my Github but can also easily be found online <3

[Gens I and II]

Nintendo used a customized PRNG during this time that was specific to the Gameboy hardware. It was very low level and niche, so I won’t get into it for the sake of my sanity. The only important thing to note is that these algorithms were extremely quickly figured out by the community, and exploited. Just because it was complicated didn’t mean it was very secure.

[LCG]

The first algorithm adopted by Nintendo, a Linear Congruential Generator (LCG), was used in Generation III (Pokémon Ruby and Sapphire). It is one of the oldest PRNGs that is still in use, invented by D.H. Lehmer in 1948.

It produces seemingly random but deterministic outputs by following a strict mathematical formula. The algorithm uses 32 bit integers and therefore has a period of 2^32, meaning there is a period of about 4 billion states before the sequence repeats. While this number seems large, a computer would be able to try every single seed value in seconds. This is part of what makes this algorithm so weak.

The initial seed is determined using the current time on the device when the game starts and takes on a value between 0 and 4,294,967,295 (2^32). If the generator was already called, the seed becomes the result of the previous call. The state is the current point in the cycle, representing how the seed changes over time. Here, the state and seed are the same variable because LCG is a simple algorithm.

The parameters of a LCG are extremely important. The formula is very simple (just one line!) and is as follows:

state = (a * state + c) % m.

As you can see it is a recurrence relation where:

a = multiplier

c = increment

m = modulus

And they all must be chosen carefully. A and C are hardcoded constants chosen by the programmer. Anyone who has seen a single output and knows the modulus can solve for the next value using simple algebra.

Nintendo used specific values of a and c as described in the textbook Numerical Recipes. These were publicly known (because they are nice numbers) but did make it even easier to reverse engineer.

Seed State: 1780438791

Multiplier: 0x41C64E6D (1103515245)

Increment: 0x6073 (24691)

Modulus: 2^32 (implicit uint32_t overflow)

State size: 1 x 32-bit integer

[run]

Call | Raw Value | Float [0,1) | Int [1,100]

0 | 3527839854 | 0.821389 | 55

1 | 2871092041 | 0.668478 | 42

2 | 1559094408 | 0.363005 | 9

3 | 1444683355 | 0.336367 | 56

4 | 3499820850 | 0.814866 | 51

While visually, the outputs look very nice and random for any non-critical purpose, it is entirely predictable and deterministic. It is not at all secure.

Fun Fact: This is also used in rand() in C ;)

[Mersenne Twister]

The Mersenne Twister was a significant upgrade from the LCG and is significantly more complex. It was developed in reaction to LCG’s weaknesses by Makoto Matsumoto and Takuji Nishimura in 1997. Nintendo used this algorithm from Generation IV (Pokémon Diamond and Pearl) through Generation VII (Pokémon Sun and Moon)*.

The name comes from the large period of the algorithm which must be a Mersenne prime. This is any prime that is one less than a power of two. The most common implementation uses 2^19937-1 (MT19337). For reference, the number of atoms in the universe is around 2^266. So this is pretty big.

Compared to the LCGs single value of state, the Mersenne twister uses an array of 624 (32-bit) integers. The way this array is manipulated generates unpredictable values, but once again they are not truly random. It will generate 624 numbers at a time, and once those are exhausted, the process will repeat.

This process has three phases, and goes as follows:

Seeding Phase: This prepares the 624 values in the array. One single value is fanned out across 624 state slots using a multiply and XOR formula. This is a recurrence relation in which each slot is derived from the previous one. The constant 1812433253 is chosen carefully to chaotically spread bits. This is to avoid any obvious patterns.

Twisting Phase: Once all 624 values have been exhausted, every single slot gets remixed simultaneously. Each value combines its own top bit, the bottom 31 bits of its neighbor, and the value of a slot 397 positions away. It is then XORed (a bitwise operation) with a magic constant if a certain condition is met. All values will therefore completely change according to some very complex and low level manipulation.

Tempering Phase: This is a final, polishing phase. Before returning the array, four XOR and shift operations ensure every bit in the output is equally distributed. The raw state will have a slightly uneven bit distribution because some positions are more predictable than others. This is a natural consequence of the math used to twist the values. As an important note, the internal state is not changed by tempering, only the values that are returned change. The output of mt_rand() is the tempered value.

The large period cannot be exhausted by any computer that has or will exist. The number is simply too large. This is a significant advancement from LCG’s easily computable period. The statistical quality is much better as well, meaning that these are indistinguishable from random numbers. There are many statistical randomness tests (ex. Diehard tests) that this algorithm passes, whereas LCG did not.

However, do not mistake these advancements for cryptographic strength. Still, the algorithm is public and although large, the state is finite. Given 624 consecutive outputs you can reconstruct the entire state. From there, you can predict every future value, as well as work backwards to discover every past value. The Pokémon community was able to use in-game mechanics to even easier reverse engineer this functionality. Quite simply they could deduce exactly which frame to click on to give a perfect result.

This algorithm as stated by its creators was never designed to be secure, only fast and statistically sound, which it accomplished excellently. It was easily exploited because Pokémon developers didn’t know they also needed a security guarantee to ensure unrepeatable randomness.

Fun Fact: A modified version of this one is used when you shuffle on Spotify :P

[run]

Seed: 1608637542

State array size: 624 integers

State after seeding (no twist yet) (index=624):

state[0]: 1608637542

state[1]: 769659812

state[2]: 3177612214

state[3]: 534333959

state[4]: 3548967879
...

--- Generating 5 numbers (triggers first twist) ---

mt_rand[0]: 1952926171 | float: 0.454701 | range[1-100]: 72

mt_rand[1]: 637209641 | float: 0.148362 | range[1-100]: 42

mt_rand[2]: 3576127354 | float: 0.832632 | range[1-100]: 55

mt_rand[3]: 2737339338 | float: 0.637336 | range[1-100]: 39

mt_rand[4]: 296573260 | float: 0.069051 | range[1-100]: 61

State after first twist (index=5):

state[0]: 1260810252

state[1]: 727460946

state[2]: 3845626944

state[3]: 2324758816

state[4]: 2856208494
...

[Xorshift and Xorshiro128+]

Ironically, Xorshift is more simple than the Mersenne twister although it succeeds it. Despite this, it is statistically stronger than LCG. This algorithm was used briefly in the remakes Pokémon Brilliant Diamond and Shining Pearl, but it was mostly just a predecessor to Xorshiro128+ worth mentioning. Conceptually, it is important to understand how it works first:

It is composed simply of three XOR and shift operations, which can be written in three lines of code.

XOR (a bitwise operation) compares two bits and returns 1 only if they are different:

0 XOR 1 = 1

1 XOR 1 = 0

0 XOR 0 = 0

These bits are then shifted, or moved left/right by a fixed amount. This is equivalent to multiplication or division by powers of two, but in binary. Bitwise operations are fast and some of the cheapest computationally that a CPU can perform. Unlike MT and similarly to LCG, the state is the output and is the value returned. Only one 32-bit integer is being manipulated.

[run - xorshift]

Seed: 1780438791

State size: 1 x 32-bit integer

Operations: XOR + shift only (no multiply, no modulo)

Period: 2^32 - 1

Call | Raw Value | Float [0,1) | Int [1,100]

------ | ------------ | ------------ | ------------

0 | 2667649144 | 0.621110 | 45

1 | 1036421535 | 0.241311 | 36

2 | 1918296901 | 0.446638 | 2

3 | 1778163482 | 0.414011 | 83

4 | 3119243445 | 0.726255 | 46

Xorshiro128+ was an improvement on Xorshift using two variables of state. It introduces two 64 bit integers, s0 and s1, working together to create a large state size of 128. Nintendo introduced this algorithm in Generation VIII (Sword and Shield), and it is still used in tandem with CSPRNGs.

It works by adding a rotation operation between the XOR and the shift. Rotations ensure that when the bits are shifted off the back, the numbers being pushed off rotate back around to the front to be reused. This ensures that no information is lost.

Manipulating this algorithm was only possible because the seeds feeding it were sometimes predictable. When the seed is truly random (made possible with CSPRNGs - coming next!), it is impossible to exploit this algorithm.

[run - xorshiro128+]

Seed s0: 1780438791

Seed s1: 11400714821103637276

State size: 2 x 64-bit integers (128 bits)

Output: s0 + s1 before state update (the '+' in the name)

Period: 2^128 - 1

Call | s0 (state) | s1 (state) | Float [0,1) | Int [1,100]

0 | 1780438791 | 11400714821103637276 | 0.618034 | 68

1 | 16709732958456349723 | 7985026672609933104 | 0.338706 | 12

2 | 8637849029961471950 | 15012297944538602872 | 0.282077 | 7

3 | 16319829028586607995 | 1752277202603676553 | 0.979691 | 49

4 | 863291169908866396 | 12018100106405288895 | 0.698302 | 92

[CSPRNGs]

This algorithm does not require implementing any math and can be used alongside any of the algorithms we have previously discussed. Nintendo realized that some level of security needed to be present to avoid players discovering ways to cheat the system. CSPRNG is a source of entropy from the real world. It harvests unpredictability from the way you interact with your computer.

Here, I have pulled unpredictable values from /dev/urandom, the Linux kernel’s entropy pool. This pool collects randomness from hardware events on your device. It is put through a cryptographic function before being served to the user. On each run, unlike the other algorithms, the numbers will be completely different.

In current Pokemon games, this is what feeds the Xorshiro128+ algorithm and has finally allowed them to reach enlightenment (randomness). Computationally these numbers are now indistinguishable from random. There is no math to reverse. The entropy does not come from an algorithm, it comes from the only place where true randomness can exist: the physical world.

[run]

Entropy source: /dev/urandom (OS kernel entropy pool)

Output width: 64 bits per call

Seed: N/A

Period: N/A

Call | Raw Value (64-bit) | Float [0,1) | Int [1,100]

------ | -------------------- | ------------ | ------------

0 | 335126954352569717 | 0.018167 | 18

1 | 9150489343205140267 | 0.496049 | 68

2 | 1196857022575942900 | 0.064882 | 1

3 | 8498734904592370568 | 0.460717 | 69

4 | 6838540434366888753 | 0.370718 | 54

I thought it was fun how a series of games from my childhood told this story of how algorithms had to improve over time as people exploited them

Thanks for reading <3