Classic Nintendo Games are (NP-)Hard

March 13, 2012 11:01 AM

Some (slightly generalized) classic Nintendo games are NP-Hard. [pdf]

From the paper:

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to Super Mario Bros. 1, 3, Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games except Zelda II: The Adventure of Link; all Metroid games; and all Pokemon role-playing games. For Mario and Donkey Kong, we show NP-completeness. In addition, we observe that several games in the Zelda series are PSPACE-complete...

For these games, we consider the decision problem of reachability: given a stage or dungeon, is it possible to reach the goal point t from the start point s? If it is hard to decide even this question, then it is certainly hard to find an optimal path. Our results apply to generalizations of the games where we only generalize the map size and leave all other mechanics of the games as they are in their original settings. All of our NP-hardness proofs are by reduction from 3-SAT, and the proofs for Mario, Donkey Kong, Legend of Zelda, and Metroid rely on a common construction, while the proof for Pokemon is based on a reduction to Push-1. We show that certain Zelda games are in fact PSPACE-complete, by reducing from PushPush-1.

Wikipedia on NP-Hard problems and the 3-SAT problem.

posted by albrecht (59 comments total)

wooo woo woo doo doo dooo!!!

[Game Over Sound]
posted by Fizz at 11:04 AM on March 13, 2012

Further research is required to determine whether Battletoads is NP-Fucking Impossible
posted by theodolite at 11:06 AM on March 13, 2012 [37 favorites]

Further research is required to determine whether Battletoads is NP-Fucking Impossible

Not beyond that surfing on a board level. Fuck.
posted by Fizz at 11:08 AM on March 13, 2012

Further research is required to determine whether Battletoads is NP-Fucking Impossible

What further research could possibly be required? Did you play the jetski level?
posted by Holy Zarquon's Singing Fish at 11:10 AM on March 13, 2012 [2 favorites]

Or the giant red orb boss?

(Actually, no you didn't fight that boss, because you couldn't beat the jetski level without cheating and if you say you did you are a filthy liar.)
posted by Holy Zarquon's Singing Fish at 11:11 AM on March 13, 2012 [2 favorites]

Thanks HZSF, I was trying to remember what the hell they were riding on. Jetski seems to be the most accurate description for the fuckstorm that is that level.
posted by Fizz at 11:11 AM on March 13, 2012

Further research is required to determine whether Battletoads is NP-Fucking Impossible

I could never reach the final boss at the end of level 3's jetbike race.

What, you mean there's TEN MORE LEVELS after that? Fuuuuuuuuck.
posted by FatherDagon at 11:13 AM on March 13, 2012

Wow, evidently there's a LOT of generational rage and bitterness over being unable to have a sound victory in the Battletoads field.

Is Battletoads our Vietnam?
posted by FatherDagon at 11:15 AM on March 13, 2012 [9 favorites]

Is Battletoads our Vietnam?

You've never played Ninja Gaiden have you?
posted by Fizz at 11:17 AM on March 13, 2012 [1 favorite]

We do not hate the game because we could not win. We hate the game because the game hated us.
posted by griphus at 11:18 AM on March 13, 2012 [2 favorites]

"How do you ask a Battletoad to be the last Battletoad to die for a programming mistake?"
posted by The Card Cheat at 11:18 AM on March 13, 2012 [4 favorites]

Tetris is NP-complete.
posted by BungaDunga at 11:19 AM on March 13, 2012 [1 favorite]

You've never played Ninja Gaiden have you?

Ninja Gaiden is nowhere near as hard as Battletoads. I still have nightmares about that race level ...
posted by tocts at 11:27 AM on March 13, 2012 [1 favorite]

You've never played Ninja Gaiden have you?

You've never played Silver Surfer have you?

Tip: don't.
posted by ShutterBun at 11:27 AM on March 13, 2012 [1 favorite]

Or that shitty NES X-Men.
posted by symbioid at 11:31 AM on March 13, 2012 [1 favorite]

The funny thing about that Battletoads level is that, now, it looks more like Guitar Hero than anything else. It's probably easier now than it was when you were a kid.

That said, I've looked it up and tried really hard, but I can't seem to understand what the hell NP-Hard means exactly. Can anyone be a Master Explainer™ and make sense of it in layman's terms?
posted by Navelgazer at 11:31 AM on March 13, 2012 [3 favorites]

So if I'm reading this correctly, the generalization of Super Mario Brothers includes the addition of vertical scrolling? (Which was not present in SMB1)
posted by jcreigh at 11:32 AM on March 13, 2012

Ninja Gaiden is nowhere near as hard as Battletoads. I still have nightmares about that race level ...

Consider the XBox version with the difficulty turned all the way up. Now, try not to assume the fetal position.
posted by Holy Zarquon's Singing Fish at 11:35 AM on March 13, 2012

That said, I've looked it up and tried really hard, but I can't seem to understand what the hell NP-Hard means exactly. Can anyone be a Master Explainer™ and make sense of it in layman's terms?

Yes, please. Also, how many video games in general are NP-hard? And why does it matter?
posted by mrgrimm at 11:36 AM on March 13, 2012

Consider the XBox version with the difficulty turned all the way up.

I think it's a little apple-orange-y to compare an NES game and an XBox game. Albeit the new-gen Ninja Gaiden games (along with Demon's Souls/Dark Souls) are the closest the current gen has gotten to the straight-up fuck you, buddy of NES game difficulty.
posted by griphus at 11:40 AM on March 13, 2012 [1 favorite]

NP-Hard means, in essence, that it's impossible to compute a provable complete solution to the problem of how to win the game. In other words, we can let a thousand monkeys loose on the machine and find any number of winning routes through the game, but we can't come up with a simple mathematical proof that this set of moves is the best solution to the game.
posted by yoink at 11:41 AM on March 13, 2012 [3 favorites]

Talk about pointless research. This guy has got his career cut out for him in academia.
posted by dobie at 11:42 AM on March 13, 2012 [1 favorite]

No, it doesn't mean that at all. Not even "in essence".
posted by Wolfdog at 11:42 AM on March 13, 2012 [13 favorites]

Caveat: I'm not a mathematician or a philosopher of logic, so I could be screwing that explanation up.
posted by yoink at 11:42 AM on March 13, 2012

The really short version is that an NP-Hard game is (by these folks' metric based on mostly just a glance at the paper so far) a game where it is computationally prohibitive to discover the optimal path through a game for the purposes of a speedrun. That is, these are games where it is unreasonably difficult to establish mathematically the fastest possible route through a game.

That doesn't mean the game is actually hard (most major Nintendo franchise games are actually pretty approachable to casual players), or that even a speedrun in that game is hard to accomplish (though speedruns tend to require a good bit of skill to really pull off well); it's not even saying that it's hard to figure out a really good speedrun route. It's just saying that being sure you've found the fastest route is hard in the same mathematical sense that, e.g., decrypting something well is hard.

The jetski level from Battletoads is, in fact, more plausible not NP-Hard than most of this stuff. I don't know that there's really any choices to be made in how to run it quickly; the difficulty of that level is all in memorization and twitching. If you get through it without dying you're probably doing a perfect speed run of it by default.
posted by cortex at 11:45 AM on March 13, 2012 [11 favorites]

No, it doesn't mean that at all. Not even "in essence".

O.K. then, your turn.
posted by yoink at 11:45 AM on March 13, 2012

Hmmm...Cortex's definition seems to be the same as mine. Maybe Wolfdog needs to correct us both?
posted by yoink at 11:46 AM on March 13, 2012

Someone else's lengthy semi-layman definition of P, NP-Complete, and NP-Hard.
posted by filthy light thief at 11:47 AM on March 13, 2012 [1 favorite]

O.K. then, your turn.
Previously.

Shorter: NP-Hard means that there is an algorithm for solving the problem (which is the exact opposite of how I interpret the phrase "it's impossible to compute a provable complete solution to the problem"), but the growth rate of time required by known algorithms is higher than polynomial in the size of the input. If you have a lot of monkeys, they will be able to solve it. But making the problem size one unit larger might, say, double the number of monkeys required.
posted by Wolfdog at 11:51 AM on March 13, 2012 [7 favorites]

Ninja Gaiden is nowhere near as hard as Battletoads. I still have nightmares about that race level ...

I'll let AVGN take over.
posted by Fizz at 11:54 AM on March 13, 2012 [1 favorite]

Hmmm...Cortex's definition seems to be the same as mine. Maybe Wolfdog needs to correct us both?

It wasn't.

An NP-Hard problem is by definition soluble, but in a very long period of time (relative to some other quantity). You stated that the problem was insoluble, which is completely wrong.
posted by TypographicalError at 11:57 AM on March 13, 2012 [4 favorites]

In this case, the authors show these games, meaning the problem of determining a path through the level, are NP-Hard by showing that in their generalized form they contain the 3-SAT problem, meaning the problem of determining whether it's possible to give truth value assignments to a collection of variables to make a given logical statement (of a particular form) about those variables true. So the statement might be something like:

"(x OR y OR not z) AND (x OR not w OR z) AND (not x OR not y OR not z)" and a possible solution, only one of many, would be

x = true
y = false
z = true
w = true

Verifying that it is a solution is easy, but checking through all possible arrangements to see that there was a solution in the first place is, in general, hard, i.e., (probably) not possible in polynomial time.

(All the allowable statements look like that example: a collection of triplets of variable OR not variable, all ANDed together.)

So the way they build that into each game is to create variable "gadgets", or rooms, where leaving the room through a certain exit counts as assigning a truth value to that variable. And then there are "clause" rooms where if you've entered through one of the three variables in the clause (presumably via whichever exit from the variable room corresponds to the one in the clause--i.e., you get to the clause from the (not X) exit if "not X" appears in the clause), and then "unlocking" the clause by breaking a brick or killing an enemy or something that would allow you to pass through the room later. They also built these "crossover" rooms that, as far as I can tell, are just there to make sure everything could fit in the same overworld map. I think you'd get the same result if you allowed pipes and/or warp zones.

(I was also bothered by the down and up travel between rooms in Mario, but I think you can replace that with pipes and vines, respectively, WLOG.)

The final step is running back through all the clauses to get to the exit, which you can only do if you've successfully unlocked them all, meaning the truth value assignments you picked resulted in all the triplet clauses being true at the same time. Ergo 3-SAT, ergo NP-Hard.
posted by albrecht at 12:01 PM on March 13, 2012 [3 favorites]

I suspect that Battletoads is NP-Hard due to the mechanics of the ice cavern level, which has walls that are only breakable by ice blocks. This is precisely the same mechanic that they use to show that SMB has a clause gadget. Variable gadgets are straightforward. The only thing that you'd have to figure out is how to make a crossover gadget, and if you were willing to mix ice levels with snake levels, you could probably modify a snake screen to work as a crossover gadget.
posted by TypographicalError at 12:03 PM on March 13, 2012

It should also be pointed out that NP-hardness and NP-completeness (and in fact most of the complexity hierarchy) are *worst case* measures.

There are plenty of NP-complete problems that are quite easily solvable in practice, even for large instance sizes (SAT, for example).
posted by homotopy at 12:03 PM on March 13, 2012

It's worth noting that they took the case of working out an optimal tool assisted speedrun, not of playing the game in a traditional sense. Playing the game ordinarily is much easier, but more difficult to reduce to an NP value.
posted by JHarris at 12:05 PM on March 13, 2012 [1 favorite]

NP-Hard means that there is an algorithm for solving the problem (which is the exact opposite of how I interpret the phrase "it's impossible to compute a provable complete solution to the problem"),

Yeah, I expressed myself poorly in trying for compression. Cortex's term "computationally prohibitive" was a far more elegant expression. Although I suppose if you want to nitpick that's only true for a sufficiently complex example of the NP-Hard problem.
posted by yoink at 12:06 PM on March 13, 2012

Also, I was playing Blaster Master the other night and I accidentally proved P=NP.
posted by albrecht at 12:10 PM on March 13, 2012 [1 favorite]

Old joke: P=NP iff P=0|N=1
posted by kmz at 12:18 PM on March 13, 2012 [3 favorites]

Slight (further) derail: Top 10 "NES-hard" games

No surprises for anyone participating in this thread, really.
posted by ShutterBun at 12:18 PM on March 13, 2012 [1 favorite]

Layman's explanation of NP-Hard:

We can break this up to understand it.

P: Say you have a problem of a particular size (Here are X items in a list; give me that list in sorted order). There is a solution to that problem that takes some Polynomial amount of time to solve. (A polynomial is the sum of some number of numbers and variables multiplied together- like X times X, which in the right units is more than enough time to sort a list that's X items long)

NP: Ok, now you have access to a super-guessing machine (often called an oracle) that can tell you a potential solution to your problem. We'll call it a Nondeterministic machine. Can you check that the solution is correct in a Polynomial amount of time? (I want a path that hits these ten cities, with a total path length less than 1000 miles. My oracle gives me a possible path. Regardless of how hard it was to generate that path, can I verify the solution in a polynomial amount of time? In this case, yes- just add up the distances of each leg of the path and check if it's less than 1000 miles).

NP-Hard: This problem is at least as hard as any problem whose solution can be verified in polynomial time. When I say that some problem P is "at least as hard" as another problem Q, I mean that if I can solve P, I can solve Q too. We prove this by a method called "reduction": I show a reasonably-fast algorithm that can turn a Q problem into a P problem (and a solution to a P problem into a solution for the Q problem). With such an algorithm, I can solve any Q problem by turning it into a P problem and solving that.

A (stupid) example of a reduction would be- sorting a list of numbers is at least as hard as finding the highest number in the list. I can reduce finding the highest number in a list to sorting the list, then just looking at the last number in the sorted list.

People mention things being "computationally prohibitive" because it is very widely believed that there are problems in NP that are not in P (which is to say, problems whose solutions can't be generated in polynomial time, even though those solutions can be verified in polynomial time). Whether these problems exist is an extremely important open problem in computer science. (When I say "can't be generated in polynomial time", I mean that for any polynomial you give me, if I give you a big enough example of the problem, the time taken to solve the problem will exceed the value of that polynomial.)

The path-finding problem I gave earlier is an example of a problem in which most people believe no polynomial-time method exists to find solutions (even though verifying solutions is easy).
posted by Jpfed at 12:27 PM on March 13, 2012 [5 favorites]

From what i could get skimming through, it looks like they're dealing with the rulesets of the games with arbitrary or random level design. So it's not that Metroid is NP hard, but designing a game with the movement restrictions and item gating of Metroid that can actually be completed is NP hard.
posted by Uncle Ira at 12:30 PM on March 13, 2012 [1 favorite]

Slight (further) derail: Top 10 "NES-hard" games

Not a bad list. I think I would basically agree with the content, though I have a few quibbles with the ordering. For some reason, pre-teen me was completely able spend hours upon hours re-playing Ghosts ' n Goblins till I beat it (the requisite two times, even!), but something about TMNT just killed me. I don't think I ever beat it.

And Fester's Quest ... god, I don't even know why we even had that game. No idea where it came from, but good lord was it bad.
posted by tocts at 12:41 PM on March 13, 2012

Here's my attempt at explaining the whole P versus NP thing in a simple but detailed manner. Let's take problems where we have a quick way of figuring out an answer and call that P. So, for example, take the problem of finding a given person's name in a phonebook, one very simple solution to that problem is to just start at the beginning and look at every name until you find the one you are looking for. That counts as fast because if you say, double the number of names in the phonebook, it only doubles the amount of work you have to do, which is pretty reasonable.

A problem that isn't in P would be something that we only know slow solutions for. So for example, guessing someone's password by checking every possible password one by one. For a 4 character password, your computer might be able to easily find the answer in under a second, but for a 16 character password it doesn't just take a few seconds, it takes years of computation on the same machine because there are exponentially more combinations to try.

NP on the other hand is problems where the result can be verified to be correct quickly. One such example is factorization, you can verify a given set of primes multiplied together equal a number, even if we don't know of a way to actually find those primes for a given number quickly.

An open question is whether every NP problem is really a P problem, i.e. that if there's a quick way to verify the answer of a problem, then there's a quick way to get the answer of the problem. Computer Science theorists guess that this isn't true, but no one has come up with a formal proof yet. No one has shown that a given NP problem is absolutely impossible to solve quickly rather than that there is a possible quick solution that we haven't figured out yet.

So let's take an NP problem that we don't think there is a quick solution to. Say figuring out the best route to take between GPS coordinates. Then let's say that we take another problem that's similar, like figuring out the best way to play Zelda. Both of those problems could have a quick solution for all we know, but we think neither of them do. If we can show that the game of Zelda can be easily represented as GPS coordinates, then that means that the two problems are at least as hard as each other, i.e. that if you can solve the GPS map problem quickly then the quick solution should also work for Zelda. The group of GPS, Zelda, and any other difficult problem that we've proven are equivalent to each other are called NP-Hard. So if any NP-Hard problem is solvable quickly, then all of them are. NP-Complete problems are problems that are NP-Hard and are also in NP (there is a quick way to verify the result). So if someday someone figures out a quick solution to any NP-Complete problem, that means a huge number of NP problems that we think can't be solved quickly are actually in P and can be solved quickly.
posted by burnmp3s at 12:44 PM on March 13, 2012 [3 favorites]

I think we probably have more people reading this thread who are down to explain complexity classes than we have people who want them explained.

From what i could get skimming through, it looks like they're dealing with the rulesets of the games with arbitrary or random level design. So it's not that Metroid is NP hard, but designing a game with the movement restrictions and item gating of Metroid that can actually be completed is NP hard.

They're pretending to be a level-designer for these games, with their given rule-sets, and showing that you can embed 3-SAT into a level design. It's pretty neat!
posted by kaibutsu at 12:52 PM on March 13, 2012 [2 favorites]

How in the world has there not been a Battletoads remake yet?
posted by Tomorrowful at 12:56 PM on March 13, 2012 [1 favorite]

How in the world has there not been a Battletoads remake yet?

In like 2007, on 4chan, someone made a lovely little Battletoads logo in the style of Yoshitaka Amano's Final Fantasy logos, and people would periodically post it to troll others into thinking a new Battletoads game was coming out. I'm really surprised I can't find that logo anywhere in Google Image Search. I bet I have it somewhere on my hard drive. It always caused a ruckus!

Whoa, I just realized the above paragraph is essentially what I'll sound liketo my grandkids when I'm 70. Huh.
posted by Greg Nog at 1:20 PM on March 13, 2012 [5 favorites]

The Battletoads jetski level was the one thing I was freakishly good at as a kid. Like not even needing to memorize, my eyeballs just processing at super light speed and my fingers twitching immediately in response. Friends were amazed and made me do it over and over again, insisted I was cheating somehow.

I found my calling in life early. I've been trying to parlay this skill into something productive ever since (sightreading music was the closest analog), but nah, my reflexes eventually dulled. It's all been downhill from there.
posted by naju at 1:25 PM on March 13, 2012 [1 favorite]

people would periodically post it to troll others into thinking a new Battletoads game was coming out

They also pranked a bunch of Gamestop stores around that time by calling up over and over again to ask to preorder Battletoads II.
posted by burnmp3s at 1:27 PM on March 13, 2012

Theoretical computer scientist here: came to give an explanation but see that there are some excellent ones here already: Jpfed's is good, for example. There are some gaps to fill and clarifications to be made:

1) NP-completeness is mentioned in the paper: A problem is NP-complete if it is NP-hard and *also* in NP. This is important because, as has been said above, solve one NP-complete problem in polynomial time, and you solve them all!

2) There are problems which are strictly harder than those in NP, and of course all of them are NP hard (that's the definition of "strictly harder")

So, are NP-complete problems easiest "hard" problems? Not necessarily (i.e. we don't know)

3) We don't know if all NP-complete problems are in P or not. Even assuming they are different, there are some problems for which we don't know if they are in P, and we also don't know if theyre NP hard. That is, as far as we know they're in between (assuming there *is* some in between, which it has been proved there is if P =/= NP). An example of such a problem is integer factorization (given an integer n, and an integer m, does n have a factor less than or equal to m?)

Why did I just formulate integer factorization in such a frankly bizarre fashion (instead of "find the factors of n")?

4)(This one is really picky) All problems in P, NP etc are decision problems: that is, they ask if a particular solution exists. But, a lot of the time, people refer to there things in terms of calculations, or function problems: for example, "find the shortest path that links these 10 cities". The decision version of that problem is, as Jpfed says, "is there a path shorter than 100 miles between these 10 cities". Perversely, most research is done into decision problems, but most applications involve function problems. And, worse yet, the two are not necessarily the same: there is a proof (relying on some standard assumptions) that there are NP problems whose function version is not in FNP (the function version of NP).

On preview: I have nothing of any use to say about Battletoads...
posted by Omission at 1:31 PM on March 13, 2012 [4 favorites]

Omission (and everyone else) thanks for all of the explanations. I get it.... a little better now. Where I'm (most?) confused now is how the question of "most optimal" path is a decision problem instead of a function problem.
posted by Navelgazer at 1:44 PM on March 13, 2012

Navelgazer: they aren't. "Most optimal" problems are function problems. To turn an optimization problem into a function problem, just provide an upper bound on the size of your solution.
posted by Omission at 1:58 PM on March 13, 2012

On preview: I have nothing of any use to say about Battletoads...

In that case it is generally acceptable to just throw the controller across the room and go get a root beer.
posted by cortex at 2:09 PM on March 13, 2012 [1 favorite]

I was not allowed a video game system. The reaction of my NES-having friends to Battle Toads was one of the few pleasures of my youth.
posted by idiopath at 2:32 PM on March 13, 2012

Unfortunately, the paper missed some important prior art.

(The authors have been notified.)
posted by erniepan at 4:17 PM on March 13, 2012 [5 favorites]

Solving a rubix cube is NP-complete as well, I believe. (Which also makes it NP-hard, if I'm remembering right (which I may not be))
posted by delmoi at 5:55 PM on March 13, 2012

Battletoads? Hell, I couldn't even beat Frogger.
posted by IndigoRain at 12:46 AM on March 14, 2012

Perversely, most research is done into decision problems, but most applications involve function problems.

When dealing with lower bounds, I wouldn't call this perverse, but rather reasonable. Proving lower bounds for one decision problem gives you lower bounds on various related function problems for free, and it's often much more comfortable to work with the former than the latter.
posted by erdferkel at 1:30 AM on March 14, 2012

The Battletoads jetski level was the one thing I was freakishly good at as a kid. Like not even needing to memorize, my eyeballs just processing at super light speed and my fingers twitching immediately in response. Friends were amazed and made me do it over and over again, insisted I was cheating somehow.

This was my experience! I parlayed it into... also being really good at Guitar Hero.

Seriously though, it was something to do with the complete ability to zone out everything-- everything.
posted by stoneandstar at 8:46 PM on March 14, 2012

And Mickey-fucking-Mousecapade needs to be on that list of NES-hard games. I don't know why we owned it or where it came from or if I just tried to play it at too early an age, but every now and then in a moment of frustration I think of the ocean just puking up everything it nurses onto Mickey and Minnie, while beating them to death with tidal waves.

Either it wasn't that hard or nobody is really that interested in mousecapades? To YouTube!
posted by stoneandstar at 8:52 PM on March 14, 2012