Look Ma, No Hands!
A thorough investigation of the Super Mario Bros. 3 random number generator for speedrun exploitation.
Analysis of the random number generation present in Super Mario Bros. 3 is desirable due to the amount of places in the game that change the course of a playthrough based on a number chosen from the random number array. The speedrunning community has done considerable work to avoid needless interactions with hammer brothers and other elements controlled by random numbers, but as of the time of this writing, a lot of interactions are still left up to chance and no in-depth research has been published on the random numbers used by Super Mario Bros. 3.
This research was performed using a disassembly of revision 2 of the USA release of the Super Mario Bros. 3 game cartridge (Super Mario Bros. 3 (U) (PRG1)).
Previous Research
Some articles and forum posts have touched on the pseudo-random number generation used by Super Mario Bros, but none have really done analysis on the algorithm itself or on its implementation within the game system to determine its effectiveness or to look for weaknesses. Additionally, it seems most analysis has been concerned with Super Mario Bros. (the original game) rather than with Super Mario Bros. 3, which is what this analsyis is focused on.
Algorithm
Using Captain Southbird’s disassembly, the random number generator function can be re-written in the following C:
uint8_t Random_Pool[9] = { 0x88, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00 };
void Randomize(void)
{
uint8_t Temp_Var1 = Random_Pool[0] & 0x2;
uint8_t carry = !!((Random_Pool[1] & 0x2) ^ Temp_Var1);
for (int i = 0; i < sizeof(Random_Pool); i++) {
/**
* Carry is shifted into the most-significant bit.
* Least-significant bit is saved off into carry.
*/
uint8_t b = Random_Pool[i] & 1;
Random_Pool[i] = (carry << 7) | (Random_Pool[i] >> 1);
carry = b;
}
}
Listing 1: The pseudorandom number generator used by SMB3
Electrical engineers might recognize the algorithm in Listing 1 as the implementation of a linear feedback shift register (LFSR). It is a 9-byte, or 72-bit, LFSR with taps at bits 6 and 14 (the second-least significant bits of byte 0 and byte 1). The bits are XORed together to get the next bit input to the array: if the bits are equal, the next input bit is a zero, otherwise the next input bit is a one. The 9-byte array is initialized upon reset to all zeroes, and the first byte is then seeded to 0x88. A linear feedback shift register generates a periodic sequence of output bits, and some combination of its output bits are fed back as the input. “Taps” are placed on the output bits and they are fed through some mathematical operation(s) in order to generate the next input. The placement of the taps used as feedback to the input is crucial in determining the period of the sequence of output bits. The maximum length of a non-repeating output sequence is 2^n-1 in an n-bit LFSR that is correctly seeded and which has optimal tap positions. A maximum-length sequence is pseudo-random, with the number of ones equal to the number of zeroes. However, if seeded incorrectly, the period of the output sequence will be less than 2^n-1, and the output sequence will not necessarily be pseudo-random. It is common to see LFSRs used in games and other programs for pseudo-random number generation.
Given that the LFSR uses 9 bytes, the max possible number of unique output sequences is 2^{72}-1. However, the taps are chosen from the “top” two bytes of the shift register, not taking any later stage output bits into account. This effectively throws away any but the first two bytes and creates a 2-byte, or 16-bit, LFSR. It becomes slightly worse, however, because the two bits fed back are bits 6 and 14, which throws away the least significant output bit from the second byte, making it a 15-bit LFSR. This makes the maximum possible number of output sequences before repeating 2^{15} - 1, or 32,767. This makes intuitive sense, too, because whenever the first 15 bits are again equal to the original seed value, after 57 more iterations the entire array will again be equal to what it was 57 iterations after the initial seed. The 57 additional iterations allows for the 57 bits not included in the feedback to shift out of the array.
Simulations using the C algorithm from Listing 1 have shown that the output sequence repeats after 32,767 iterations. Iteration 57 was found equal to iteration 32,824 when seeding with the initial array of [0x88, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00]. The difference between 32,824 and 57 is 32,767.
Re-Seeding
When the Nintendo is reset, the game code’s reset handler is run. The reset handler initializes much of the RAM to zeroes, sets up the graphics chip and all the graphics for the beginning of the game, and seeds the random number array’s first byte to 0x88. Seeding the first byte in the random number array to 0x88 occurrs at the beginning of the start sequence where the game plays the introduction script in which Mario and Luigi throw a koopa shell at each other and various other scripted actions occur. This beginning sequence replays every 3,475 frames, or after fewer frames if the start button is pressed and the game is left on the “Players Select” screen. When the opening scene repeats, the first byte in the random number array is re-seeded with 0x88 again, but none of the other bytes are touched. Due to this new “initial state” for the linear feedback shift register, the pseudo-random number sequence is completely changed. Analysis on the sequences produced by all possible variations for the initial state showed that the output sequence will always repeat after 32,767 frames. However, depending upon what random numbers are desired at which point in time during the game, this re-seeding can be utilized to modify the random number sequence.
All of the speedrun categories for Super Mario Bros. 3 start the timer when the player hits start on the player select screen. This means that the random number generator can be re-seeded as many times as desired by waiting for the introduction scene to replay without inducing any time penalty. If the start button is pressed on frame 65, the opening sequence will be restarted and the random number generator reseeded on frame 1,952. Hitting start on any frame after 65 will cause the random number generator to be reseeded 1,887 frames later, thus allowing for 128 different sequences of LFSR output bits (128 due to the first 8 bits being reseeded to 0x88 and the last 7 bits staying at whatever they were at the reseed frame; 2^7 = 128). Each sequence still repeats after 32,767 frames, but the reseed allows a well-timed start press (probably only viable for a tool-assisted speedrun) to choose the sequence of LFSR bits that works best for the desired run.
For example, although it is impractical, consider the following contrived scenario: if the initial seed value of [0x88 0x62] for the random number generator allowed for an output of 100 1-bits in a row (not possible, but just trying to illustrate the point) at the point where a player was about to cross the hand levels, the player could always skip those levels by selecting that random number sequence by pressing start on the right frame, waiting for the opening sequence to replay, and then starting the speedrun.
Iterations
The linear feedback shift register is “clocked”–that is, the Randomize function is called–within the game’s non-maskable interrupt (NMI) handler. The NES’s graphics chip can be set up to generate an NMI at the start of its “vertical blanking” period. Most games use this feature to run code at known intervals and to talk to the graphics chip while it is idle. The NMI is fired 60 times per second, once for each rendered frame on NTSC consoles. Within Super Mario Bros. 3’s NMI handler, controller input is sampled and the random number array is shifted. However, there are times during normal gameplay when an NMI does not occur and the random number array is not clocked. These “lag frames” occur when the NMI is turned off in order for the game to do special rendering, such as the level-entering screen-fade effect or when changing the game’s background graphics. Lag frames can also occur if too much processing is done outside of NMI and the input poll is missed. If this occurs, the RNG tick is not processed and the bitstream is not shifted.
Exploitation
“Hand” Analysis
The most desirable use of random number exploitation in Super Mario Bros. 3 speedrunning is probably to skip three levels in World 8 toward the end of the speedrun. In World 8, after the first two auto-scroller levels (Bowser’s Tank Force and Bowser’s Navy), the player is presented with a set of three short levels. These three levels have been dubbed the “hand” levels, because whether or not the player must play them is determined randomly by a hand that may appear and grab the player, dragging Mario down into the level. Sometimes, if the player is lucky, all three hand levels may be skipped if the hand does not grab the player. In analysis of the game code’s disassembly, when a player moves, the tile on which the player lands is checked for which type of tile it is. If it is a “hand” tile, a random number check is done to determine if the hand will pull the player into the level, forcing them to play it.
The random number check is performed by getting the 2nd byte in the random number array, Random_Pool[1]. If the least significant bit of this byte is a 1, the player is allowed to skip the level. If it is a zero, the player is pulled into the level. This means a player has a 50% chance of skipping each hand level, which works out to a 12.5% chance of skipping all three hand levels. However, perhaps the knowledge of the random number generator’s internals can be exploited to always get “zero hands.”
Because the hand levels are encountered toward the end of a speedrun, they are one of the most notoriously hated aspects of the random number generation affecting a speedrun’s time. They are so desirable to skip because each one played adds around 15 to 20 seconds to a run and, especially for the shorter categories, can effectively end the run.
Movement Mechanics
In order to give the best possible chance to exploit the random number generation, some background is needed first on how movement works on Super Mario Bros. 3’s overworld map. Assuming Mario is sitting stationary on the overworld map, as soon as a directional pad button (dpad) press is registered, the game sets a counter to 32 for the number of pixels Mario is to move in that direction. If the move is in a valid direction, Mario’s position is changed in that direction 2 pixels per frame, and the counter value is decremented by 2 on each frame. On the frame that the counter value hits zero, the game checks the tile type Mario is standing on. If it is a hand tile, the game will do the random number check at this point.
After the first directional pad button press, the game will not register another dpad input until one of two scenarios occurs:
- The DPAD button is let go and pressed again while Mario is not moving, or
- The DPAD button has been held down for 24 frames
Because it takes Mario only 16 frames to move one space on the overworld map, if the DPAD is held down, Mario must remain stationary for 8 more frames after coming to a stop after the first movement. After the DPAD has been held down for 24 frames, Mario will continue to move along the overworld map in whichever direction is being pressed on the DPAD without any additional delay on each tile. This is the most reliable way to keep Mario moving along a path as fast as possible without requiring frame-perfect input each time Mario lands on a tile.
Using this knowledge, the most reliable way to move across the three hand levels in a pre-determined number of frames every time is to press an invalid movement direction (e.g. down) while Mario is sitting on the pipe next to the hand levels and then immediately press and hold the correct direction (left). After 24 frames, Mario will begin to move left over the hand levels and will immediately continue moving past each tile upon landing on them as long as a hand does not pull Mario into the level. This allows us to calculate an exact optimal frame number on which to begin the “down then left” sequence. The ideal sequence of bits would start off with as many ones in a row as possible to allow for a slightly mistimed DPAD press. After 16 frames (after Mario has moved and is landing on the next tile), the sequence of bits should be right in the middle of another long sequence of ones. After another 16 frames, the sequence should contain another long sequence of ones. Having a sequence of bits with three long sequences of ones 16-frames apart at about the time the player is passing the hands is the ideal random number sequence.
An analysis can be done offline to find the which of the 128 different sequences provides the best possible sequence at about the time the hand-crossing is done.
Other Possibilities and Future Work
This manipulation could also be applied to many other RNG-dependent strategies during a Super Mario Bros. 3 speedrun. Early-Hammer is an example where the hammer brothers’ movements are manipulated in order to cause the hammer brother that has the hammer in World 2 to move closer to the player before Level 3 so that the hammer can be used to skip 3 levels. Which direction the hammer brothers move depends upon the random number at the end of a level. Mitchflowerpower recently began looking into this in order to allow for Early-Hammer manipulation in RTA runs.
Analysis and characterization of all the possible random number sequences still needs to be done in order to find the ideal sequence or sequences. The optimal sequence also depends upon which RNG-dependent task is looking to be done: a sequence that works well for skipping hands may not work well to allow a player to achieve Early-Hammer.
