“Some of these tricks we use make the games look broken. But we are not breaking the games, we are just breaking your notion of them.” ~From the TASVideos introduction page [1]. Somewhere in the list of dozens of papers I want to write someday when I’m finished with my dissertation, I’d like to try and write a paper addressing video game glitches. In the meantime, I’m writing this short non-peer-reviewed technical note and publishing it on the blog, because a recent paper posted on the arXiv by Greg Aloupis, Erik Demaine, and Alan Guo [2] suddenly brings the issues out of nerdy obscurity and into cutting edge computer science.

Introduction

In their paper (which is very interesting and which I highly recommend), Aloupis, Demaine, and Guo claim that the old Nintendo game Super Mario Brothers is NP-Complete. I immediately saw a (very minor) flaw in their proof, and noted it on Scott Aaronson’s blog [3]. A few hours later Ryan Landay confirmed [4] that he had independently noticed the same flaw. Without going into the specific details (see my comment on Scott’s blog for those), the authors assumed (and we can hardly blame them) that a solid wall is enough to stop a small Mario. But this assumption is false: Mario can actually jump through certain walls by exploiting glitches in the video game’s code.

To be clear, I am not claiming that (generalized) Super Mario is easier than NP-Complete. For all I know, Aloupis et al. are correct (indeed I’d be shocked if they aren’t). It’s just that the proof in their paper is a tiny bit flawed. I conjecture that the proof (at least for Super Mario Bros) could be patched up easily… maybe by placing a “checkerboard” of alternating solid blocks and spiky-shelled enemies behind the wall which is meant to be impassable– so that if Mario attempts to glitch his way through, the spiky-shelled enemies will skewer him. The point is that the episode places video game glitches in the spotlight.

Console games are extremely complicated, and very difficult to model game theoretically. Some would say chess is complicated, game theoretically. But the rules of chess are fairly simple, you can write them down on one page. You cannot do that for SMB, not if you want to accurately capture the real engine which the game uses. The true rules of SMB are coded in (I think) 6502 Assembly Code, and are about (I think) 40 kilobytes in their compiled form (so that in disassembled form they’d be considerably larger). That utterly dwarfs the rules of chess!

It would be completely impractical to prove things about SMB using its actual machine code. Instead, we simplify the game and try to intuitively explain it based on our experience playing it. This yields a model of the game which is enormously simpler. One such model is what Aloupis et al. study. In their simplified model of the game, Mario can’t jump through walls. But this does not accurately capture the actual rules of the actual console game, as measured by its assembly code (that is, as measured by what the game is capable of being twisted into doing, given a sufficiently superhuman player).

I find it kind of amusing and appropriate that this paper was brought up on Scott Aaronson’s blog, where issues of quantum complexity theory are so very expertly discussed. In the universe of Super Mario Bro’s, the model of physics which says “Mario can’t jump through solid walls” is kind of like Newtonian physics, and the (more accurate) model which says “Actually, sometimes he can” is kind of like quantum physics. Ryan Landay’s and my instructions for how Mario can quickly solve the Hard puzzles of Aloupis et al. might be viewed as some kind of strange analogy for hypothetical quantum computers which are sometimes hyped up as being capable of performing similar feats in our own world.

The Substantive Math, part 1: Game Theoretically Defining Glitches

I wouldn’t say I’ve exhausted the literature, but what searching I have done has unearthed very little about glitches through the game theoretical perspective. In fact, I’d go so far as to say that there is almost no literature about glitches in any of the current scientific literature. I could be mistaken here, it could just be that I’m no good at literature review. Of course, whole libraries have been written about software exploits, but I think there is something different about video game glitches.

I’ll focus on glitches which the player can exploit to win the game faster than intended. Call these speedrun glitches. These differ from the software exploits most studied in computer science because the end result of a software exploit is usually a state which was never meant to be reached: the programmers of Internet Explorer never intended for attackers to be able to execute arbitrary code, no matter what route they took. By contrast, a speedrun glitch aims for a state which is a perfectly normal part of the game– e.g., the “You Win” screen– but via a route which is unexpected.

It is very difficult to formally define what a speedrun glitch is. Objectively speaking– and this philosophy underlies the entire tool-assisted speedrun community– if it’s programmed in the game’s code, it’s part of the game. Thus, Mario being able to leap through solid walls is just simply a part of the Super Mario Brothers game.

We cannot simply choose glitches case-by-case on an ad hoc basis: they are subjective. To illustrate this: Aloupis, Demaine, and Guo make the “crouching slide” an integral part of their NP-Complete proof for Super Mario Brothers. This is a phenomenon where a large Mario can duck after building up speed and thereby slide through corridors normally too small for him to fit through. The question is: if jumping through walls should be ignored because it is “an obviously unintended glitch”, why doesn’t the same go for crouch sliding? I imagine the crouch slide is not officially documented in the Super Mario Brothers game manual (though I could be mistaken). The only way to know whether crouch slide was “intentional” would be to read the programmers’ minds as they were programming the game. It seems less glitchy only because it’s well-known by almost all players of the game and can be easily performed, whereas jumping through walls is more obscure and is almost impossible for a mortal human to perform. But these are not considerations we can very well articulate game-theoretically!

For the sake of putting some actual substantive math into this article, I very tentatively propose the following as a possible definition of glitch (or as a step toward such a definition):

  • Tentative, sketchy, incomplete, possible definition of video game glitches. (This definition uses vague notions of largeness and therefore needs more work.) Let G be a formal one-player game (in the sense of game theory). Say that G is console-like if G contains a very large number of subgames which are nearly identical to each other, and each of those subgames contains a very large number of subsubgames which are nearly identical to each other, and so on for a large number of levels. A speedrun glitch is a winning strategy which avoids a large number of said subgames.

To understand the intuition here, imagine a winning play of Super Mario Brothers. Now imagine a play which is identical except that the player waits 1 second longer at the beginning before taking his first step forward. (This does not alter the winningness of the play, as long as the first play finished the first level with at least 1 second remaining on the clock.) In the formal game of Mario Brothers, both plays follow extremely similar-looking paths through extremely similar-looking subgames. Similarly, if two winning plays are identical except that one of them enters the coin-pipe in World 1 Level 2, and the other does not, again this gives two nearly identical paths through two subgames which are nearly identical except for a brief initial part.

Now, suppose I find a way to beat Super Mario through some obscure sequence of keymashings which takes me directly from World 1 Level 1 to the victory screen. This yields a path through the formal game which skips an extremely huge number of nearly-identical subgames and subsubgames and so on. (Note: this is not such a hypothetical situation! Masterjun did almost exactly this for Super Mario World, and MUGG and anymac did something similar in Super Mario Land 2. See [5],[6]

Of course, there is still a lot of thinking to be done to make this definition precise. As is, it merely pushes the vagueness bubble around under the carpet: instead of “what is a glitch?”, the question becomes “what is a large number of subgames and what does it mean for two subgames to be almost identical?” It might be necessary to bite the bullet and require that the formal games be extended to explicitly make precise which subgames are intended to be unavoidable. Especially considering that ideally the definition shouldn’t give a false positive for strategies which use the intentional so-called “warp zones”!

The Substantive Math, part 2: An Actual Theorem??

The following theorem sketch is so vague that I won’t even try to fully spell it out. I fully acknowledge that I am here committing horrendous crimes against mathematics. Please have patience with me. The theorem, vague as it is, attempts to identify the “trivial and silly” problem of speedrunning with the dead serious problem of software verification.

  • Theorem: The following problems are equivalent:

    1. Finding the fastest speedrun of a game.
    2. Checking that a game has no major game-breaking glitches (at least none which allow the game to be won in a super fast time)
  • Proof:
    • (2 is reducible to 1). To check that the game has no major game-breaking glitches, first find its fastest speedrun. Watch the speedrun. If it does anything that knocks your socks off, you’ve found your glitches.
    • (1 is reducible to 2). To find the fastest speedrun of the game, first disassemble the game into machine code. Using 2, check the code for game-breaking glitches. If you find any, pick the most egregious one and use it to make a speedrunning mockery of the game. If not, you may reduce the speedrunning problem to the much simpler problem of speedrunning the much simpler abstract model of the game which everyone actually thinks of when they play it. As Aloupis, Demaine, and Guo point out, this may still be NP-Hard, but the space of paths you have to check is extremely drastically reduced (to use [5] as an example, you may immediately rule out any paths which involve having your pet dinosaur repeatedly chew up and spit out P-switches for no apparent reason).

References

[1] TASVideos. Welcome To TAS Videos, 2010. Retrieved 15 Mar 2012.
[2] Greg Aloupis, Erik Demaine, and Alan Guo. Classic Nintendo Games are (NP-)Hard (PDF). Preprint.
[3] Scott Aaronson. Big News. Shtetl-Optimized, 2012.
[4] Ryan Landay. Comment on [3], 2012.
[5] Masterjun. SNES Super Mario World (USA) “glitched” in 02:36.4, 2012. Retrieved 15 Mar 2012.
[6] MUGG and andymac. GB Super Mario Land 2 “glitched” in 2:08.98
[7] Alexander the Great. Solution to the Gordian Knot.