The NES Tetris PRNG
Computers are good at many things such as counting to very large numbers in their head or making fools of us all when we’re trying to project slides at an important meeting. But one thing they’re bad at is coming up with random numbers out of nowhere.
Actually, we’re pretty bad at coming up with random numbers too. If I asked you to choose a random number between 1 and 20, there’s a decent chance you chose 17, or at least a prime number. And you probably didn’t choose 20. What we think are “random” thoughts are really biased decisions, the result of whatever is going on in our brains at the time, and for some reason prime numbers and odd numbers “feel” more random than even numbers.
To be honest I always think of the number 17 because of the Humbug from Norton Juster’s The Phantom Tollbooth.
“By all means,” [the Dodecahedron] replied happily. “There’s nothing to it. If a small car carrying three people at thirty miles an hour for ten minutes along a road five miles long at 11:35 in the morning starts at the same time as three people who have been traveling in a little automobile at twenty miles an hour for fifteen minutes on another road exactly twice as long as one half the distance of the other, while a dog, a bug, and a boy travel an equal distance in the same time or the same distance in an equal time along a third road in mid-October, then which one arrives first and which is the best way to go?”
“Seventeen!” shouted the Humbug, scribbling furiously on a piece of paper.
Computers also can’t come up with a random number from out of nowhere. Even if we were to program one to simulate rolling a die, the rules of that simulation would use the same math and you’d roll the same number every time.
There are dedicated pieces of hardware that generate random numbers by listening to ambient noise or observing electrical interference or other physical phenomena, but these aren’t common in consumer devices, especially those built in the 80s like the Nintendo Entertainment System.
This is a massive simplification. Random numbers and entropy is a specialized topic in computers all by itself.
The truth is most computers fake randomness, and they can do a reasonable job at it. They use math to generate long sequences of repeating numbers that appear to be random unless you spend enough time to figure out how the generator works. These algirthms are bootstrapped with a “seed” initial value so they create different sequences each time they’re used. Choosing seeds is an entire topic in itself, but computers use everything from the current time to mouse movements as seeds.
There are lots of these Pseudo Random Number Generator algorithms (PRNGs). They have cool names such as “linear congruential generator” and “Mersenne Twister.” Choosing which one to use is very important. Cryptography depends on high quality random data—if you can predict the random number generator you may be able to break a cryptographic system. This is not a theorteical concern. There are many examples of bad random number generators leading to security problems.
I’m not saying games should use bad RNG, since players shouldn’t be able to gain an unfair advantage in a multiplayer game. And the stakes are even higher if real money is involved, such as with a video poker machine.
Single player games like Tetris don’t really need random number generators that are as good as the kind you need for cryptography. They just need to be good enough so you can’t predict which piece will come next in order to keep things interesting, and the really good PRNGs can be too slow to use in a game.
NES Tetris implements a 16-bit Fibonacci Linear Feedback Shift Register seeded with
0x8988 and taps at bits 1 and 9. This probably doesn’t make sense unless you’ve also recently read the related wiki pages, so let’s break this down.
I did none of the work to figure any of this out. All of the technical details for NES Tetris come from Michael Birken’s phenomenal “Applying Artificial Intelligence to Nintendo Tetris”.
The game uses 16 bits of storage for its PRNG. When the game starts up, the number is set to
0x8988, or 35,208 in decimal, or the bit pattern
b1000 1001 1000 1000. Each time the game wants a new random number it takes bits 1 and 9, counting from the right and starting at 0 because programmers are weird, and XORs them together. XOR, pronounced “ex or” or “exclusive or,” takes two numbers and gives back 1 only if exactly one of the inputs was 1. We could make a chart of how that works:
|First Input||Second Input||XOR Result|
The result of XOR’ing bits 1 and 9 is stuck on the left side of the number, and then the rightmost bit is chopped off. It looks something like this. Click the buttons to see how the system behaves.
That weird orange symbol that looks like a fat spaceship with a trailing shockwave means “XOR.” The reputation that engineers have a hard time communicating with non-engineers is wholly undeserved.
This process may seem kind of weird, but it does the job. The NES Tetris PRNG will generate 32,767 unique numbers before repeating the sequence.
But if this PRNG generates the same sequence of numbers every time, then why doesn’t every game of NES Tetris play exactly the same? And how does Tetris translate these random numbers into the next piece it gives you? We’ll keep exploring tomorrow.