Paul Kuliniewicz

I recently stumbled across (via Scott Aaronson’s blog) an academic computer science paper that proved that Super Mario Bros. is NP-complete, and so are Donkey Kong Country, The Legend of Zelda, Metroid, and Pokémon. Or, to be more precise, the decision problem of whether a level in any of those games is winnable is NP-complete.

Don’t get too excited about this result, however. It doesn’t mean you’re going to be able to pick up a NES controller and suddenly be able to solve intractable problems with ease.

Informally, an NP-complete problem is the hardest type of question where there is no known way to figure out the answer quickly, but it is possible to quickly verify that an alleged answer is true. The Boolean satisfiability problem is one well-known NP-complete problem: given an arbitrary Boolean formula, is there some way to assign values to each variable in it to make the formula true? If I say I know the answer for a particular formula, it’s easy to see if I’m right: plug in the values I give you for each variable, and see if the formula evaluates to true or false. However, there’s no known way to figure out in general what those values should be, if they even exist at all.

NP-complete problems are a subset of the NP problems, which are all problems where it’s possible to quickly check whether an alleged answer is true. NP-complete problems are the hardest NP problems.

What does that mean? NP-complete problems have the property that if you can find a fast way to solve one of them, you automatically know how to solve all NP-complete problems (and all NP problems in general) quickly too. This works because it’s possible to quickly transform any NP problem into any NP-complete problem, in such a way that if you can solve the NP-complete problem, you can quickly transform that answer back into an answer for the original NP problem.

Whether or not there’s a fast way to solve NP-complete problems is one of the big unsolved problems in computer science. Despite several decades’ worth of people working on it, no one has come up with a fast way to solve any of the thousands of known NP-complete problems in general, nor come up with a proof that it’s not possible.

So, what does this have to do with Super Mario Bros.? The authors of the paper found that the question of whether a stage in generalized Super Mario Bros. is winnable or not is an NP-complete problem. Here, “generalized” means that unlike in the original game, the stage can be more than one screen high, and there is no limit (in physical size or in time) on the size of the stage. Their proof of NP-completeness shows that given an instance of the 3-SAT problem (a special case of the Boolean satisfiability problem that is also NP-complete), it’s possible to construct a generalized Super Mario Bros. stage that is winnable only if a solution exists for the Boolean formula, and where the path Mario takes from the start to the finish directly corresponds to how to set the variables in the Boolean formula to make it true. If you can find a path from the beginning to the end of the stage, you can find a solution to the 3-SAT problem, and so the winnability problem is also NP-complete.

The construction effectively turns Super Mario Bros. into a puzzle game, where the challenge is to find a way to the flagpole that doesn’t result in getting Mario trapped in a dead-end. The idea behind the construction is that Mario has to kick the right Koopa shells to break bricks that block a corridor leading to the flagpole. Forks in the path correspond to each variable in the Boolean formula, and different paths lead to different Koopas positioned to break different blocks. Most of the rest of the construction is contrived to prevent Mario from backtracking through the stage, and contriving a way to have two paths cross without letting Mario change which path he’s on.

The authors use the same basic approach to show that the question of winnability of Donkey Kong Country and Metroid stages is also NP-complete. The details of the construction of course vary based on the game mechanics, but use the same basic idea. The authors also prove NP-completeness of the question of winnability of Legend of Zelda and Pokémon dungeons using a different style of construction. In all cases, each game’s mechanics are used to effectively turn it into a puzzle game.

It might be interesting to come up with something to let someone actually “play” a stage derived from an instance of 3-SAT, although playing through such a stage wouldn’t be very fun. The stage would clearly be composed of repetitive elements, and it’d often be difficult to figure out how to get through it successfully. That is the idea, after all. Such a game would just be a novelty to demonstrate the concept; it wouldn’t be an effective way to try to solve NP-complete problems, as amusing as it might be to see a compiler challenge a programmer with a Legend of Zelda dungeon when it needs to perform register allocation (which is equivalent to graph coloring, which is NP-complete).

One of the recurring issues with Wallace, in those rare times when I’m actually working on it, is the difficulty of interfacing Wallace with the NES emulation engine. Emulators generally aren’t written with the goal of being driven by another program; as a result my most recent effort at it involved a lot of ugly hacks to Mednafen to make it spew some useful data to stdout, and to cleverly disguise controller inputs generated by Wallace as a movie file.

However, I discovered by accident while wasting time I could’ve been spending on Panflute instead of browsing the epic time sink that is TV Tropes that some modern console emulators have built-in scripting support, and in FCEUX‘s case, the scripting support is also part of the often-relatively-neglected Linux version. Said scripting support offers a relatively straightforward way to write add-on code that mucks around with the game running inside the emulator, which would be orders of magnitude more elegant and maintainable than the approaches Wallace has taken up until now.

What do I mean by “muck around”? Well, you could add a way to drag-and-drop enemies in Super Mario Bros.:

Or give Mega Man kill-anything laser eyes (maybe he defeated Mr. Flibble Man?) in Mega Man 2:

Or replace the control scheme in Super Mario Bros. 3 with the one in Kirby: Canvas Curse, drawing platforms and obstacles on the screen using the mouse instead of having direct control over Mario:

Or add head-to-head network play to Nintendo’s Tetris game. You know, the one that doesn’t actually have a multiplayer mode to begin with:

Note that all that craziness is being implemented using Lua scripts in the emulator, without doing any hacking of the ROMs themselves. In FCEUX, loading a Lua script gives it control of the emulation loop and do pretty much whatever it wants, including poking around in game memory and messing with controller inputs but also doing anything else that can be done in Lua.

For the time being I’m not working on porting Wallace to FCEUX+Lua, but that’s mostly because I need to get Panflute in a releasable state and resurrecting Wallace right now would be too great a distraction.

If you’ve ever wondered what life would be like in the mirror universe where Shigeru Miyamoto is evil, try playing this fiendish knockoff of Super Mario Bros. (Hint: use Up to jump.)

Or, for the morbidly curious but not masochistic, take a look at this series of videos that show someone trying to play through it:

• Stage 1
• Stage 2
• Stage 3
• Stage 4