Skip to content

Instantly share code, notes, and snippets.

@0xabad1dea
Last active December 28, 2021 17:38
  • Star 25 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save 0xabad1dea/7740977 to your computer and use it in GitHub Desktop.
Weird Machines in Video Games

Abadidea's Index of Weird Machines in Video Games

A "weird machine" is when user-supplied input is able to create an arbitrary new program running within an existing program due to Turing-completeness being exposed. Sometimes such functionality was deliberately included but it is often the result of exploitation of memory corruption. You can learn more at the langsec site. There is a good argument for weird machines being inherently dangerous, but this index is just for fun.

It is broken into two categories: intentional gameplay features which may be used as weird machines, and exploit-based machines which can be triggered by ordinary player input (tool-assisted for speed and precision is acceptable). Games with the sole purpose of programming (such as Core Wars) are not eligible and plugin APIs don't count. If you know of more, feel free to add a comment to this gist.

Intentional Gameplay Mechanics

  • Minecraft is the leader in the voxel adventure genre. It contains a fictional ore called redstone which can be used to construct wires, power sources, and switches. The basic intention of redstone is to trigger a state transition in blocks which have more than one state, to facilitate things like automatically opening doors. However, extremely large, complex systems may be built to perform arbitrary computations and display the results – if not in a particularly time-efficient manner. A working example of a Turing machine with an actual tape may be seen here. Since the addition of piston blocks, it is also possible to use pistons and minecarts in computing primitives. Even a complete scientific/graphing calculator with a traditional-looking screen is possible.

  • Dwarf Fortress is a roguelike game about managing a colony of dwarves who are guided by their own quirky AI. (Some might say it's a game about engineering against the dwarves' own stupidity.) Like Minecraft, it contains the notion of a block which may have more than one state. One can use one of three means of conveying state: water flow and pressure plates, wind-powered mechanical linkages, or the movement of creatures across pressure plates, relying on predictable pathfinding goals of the AI. This creature logic is the only example I am aware of which uses the desires of a simulated person as a computing primitive. It raises disturbing possibilities if one buys into the hypothesis that our own world is a simulation. Water and wind based dwarven computing is certainly more ethical.

Figure 1: Look at those smiles! Dwarves love pulling levers.

  • While usually more of an analog game, Magic: The Gathering can be played online so I think it merits inclusion. Via some ridiculously specific scenarios, it is possible to set up a Turing machine in a Magic card game. The rules of this game are complex enough to begin with, so I don't pretend to understand what's going on here at all.

  • Little Big Planet (PS3) is another sandboxy game with mechanical widgets. This implementation of Game of Life is proof-by-construction of turing completeness. Here is a clearer video of a conventional calculator in LBP2 (but the first half is just the player messing around with their avatar's costume...). Unfortunately I don't know enough about how this game works as I never owned a PS3.

Player Exploits

  • In Pokemon Red and Blue (Gameboy), memory corruption bugs (of which there are several known ones) enable the player to redirect execution to strings of memory under their control, such as the nicknames given to Pokemon. Extremely specific steps can be followed by the player to achieve arbitrary code execution. While (probably) not Turing complete, another field under the player's control – their own name – can be used with the Missingno bug to program the arguments to the wild Pokemon encounter subsystem and give arbitrary results, as well as to write specific values to specific places in memory (enabling you to give yourself a large number of an item of your choosing).

  • In the essentially-the-same sequel to Red and Blue, Pokemon Yellow (Gameboy), another memory corruption bug may be triggered very early in the game. One use of this bug is to achieve the fastest possible run to the victory condition. This programmer also used it as the entry point to input large amounts of arbitrary code and data into the game. If you watch the whole video, a long time is spent in the game's shopping mall to fill the player's inventory with very specifically crafted values. Right down to buying one lemonade at a time over... and over...

  • Super Mario World (SNES) contains tables of data related to specific sprite-related actions. By putting these into an inconsistent state with a glitch, the video memory can be executed which makes the visual composition of the sprites on the screen a programming primitive. The fastest playthrough yet achieved uses this to jump to controller RAM and execute that. The maximum amount of controllers are plugged in and their buttons held down (virtually, in this case) to spell out a program to jump to the end credits. There's also this magnificent piece of stunt-hacking to actually implement new minigames on the fly.

  • Super Mario World 2: Yoshi's Island (SNES) contains essentially the same bug.

  • Something about the Super Nintendo just really encourages these kinds of bugs. Kirby Super Star manipulates registers with unexpected simultaneous up/down on the controller (normally prevented by the four-way rocker design) to achieve arbitrary code execution. Amusingly, the bug was originally written off as a useless curiosity, when in fact it unlocks direct control of the universe. Of course, the only thing these speedrunners ever want to do is program in a jump to the credits sequence :)

Honorable Mentions

  • Everyone loves the Game of Life but it's not really a game. Implementing it in a video game makes that game an excellent candidate for this list, however. (Again, please no examples where programming is the game.)

  • It is possible to use the rules of Minesweeper to construct a computer, but it doesn't sound particularly playable.

@Sanqui
Copy link

Sanqui commented Dec 1, 2013

An exploit similar to 8F in Pokémon Red is also possible in Pokémon Gold: the Coin Case exploit.

@ianh
Copy link

ianh commented May 13, 2014

To add to your list of SNES games, there's a total control TAS for Super Metroid: http://tasvideos.org/4224S.html

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment