Classic Nintendo Games Are NP-Hard (2012)
arxiv.orgI wondered how this could possibly work, then found this sentence. Basically their generalisations have to go far beyond what these games are (the NES mario games had everything be forgotten when you scrolled along).
> For example, recall that in Super Mario Bros. everything substantially off screen resets to its initial state. Thus, if we generalize the stage size in Super Mario Bros. but keep the screen size constant, then reachability of the goal can be decided in polynomial time:
Misleading article title and misleading paper title.
Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how "enjoyably challenging" a game is. There's a reason these games are such classics, and I dont think its entirely because of their timing, polish, and marketing. Miyamoto's games always had that special "something" (opinion, I know), maybe this has something to do with it?
Probably not formally, but I do tend to find that how much I enjoy a game correlates inversely with how easily I can imagine teaching a computer to play it. Most of the time, if I start thinking "I could write an algorithm for this game", I very quickly lose interest in playing it.
So, I enjoy games where I feel like I can recognize patterns that have some depth and complexity, that make me feel like I can develop some skill, that don't seem trivially teachable to a computer.
This is why I never enjoyed Sudoku. I finally just spent some time in between classes writing a solver that solved it in as optimal a fashion one can deterministically solve it in, and said "Okay. Done. I will never feel any guilt over dismissing these again".
(EDIT: Writing the solver was actually enjoyable though; far more than manually solving a Sudoku ever was)
Back when Sudoku was a big craze I noticed a relationship between people's approach to it and their chosen career path.
Quite a number of engineers I knew had written solvers of various sorts and rarely solved the puzzle by hand, the company accountant wrote little tally numbers in the box corners and worked by a process of elimination, and a lawyer whom I travelled with for many plane flights spent hours on them using some ad-hoc hunt and seek approach.
Oh man, please don't tell me I'm secretly an accountant!
> in as optimal a fashion one can deterministically solve it in
I'm curious what you mean by this? Sudoku is mechanically solvable, but not all sudoku puzzles feel that way, to me.
Uh, I haven't actually done sudoku in a long time, so let me talk about kakuro (https://en.wikipedia.org/wiki/Kakuro) instead. I think the feelings I have about them are similar.
So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column.
And getting a computer to implement that sort of algorithm would be challenging. (http://www.sudokuhints.com/ seems to do something like it for sudoku, to let it give you a number and tell you how you could have found that number yourself. But trying a fiendish puzzle, it's not explaining itself very well.)
(Obviously, if you don't enjoy sudoku, that's fine. I'm not trying to convince you that you should. It just feels to me like the skills I use for sudoku, aren't ones that I could trivially teach to a computer.)
My apologies, the terminology is imprecise; basically, in as optimal a way as you can brute force a solution, if one exists, relying on the simplest heuristic for branching. The same way, really, as you'd do it by hand, if you wanted to guarantee a solution (if one exists). So, yes, a backtracking solver, a la (this is basically what Norvig did in the link someone else mentions; I implemented mine around the same time as his article was written, it looks like, as a fun college time killer, probably when Sudoku was first in vogue) -
Figure out the possibility sets of all empty squares (that is, a set of all possible values given the current state of the table, i.e., for each square, initialize them with 1-9, then remove every value that is already contained in the same row, column, and 3x3, thus figuring out for each "this square could be 1 or 5, and nothing else"). Grab the square with the fewest possibilities; does it have only one? If so, go with it, update all related squares (by removing that value from their possibility set), recurse. Is it of possibilities > 1? Take one of the values out of the possibility set. Push a copy of the table as it stands (without that removed value) onto a stack; put in the taken value for the value of that square, update all related squares, and recurse. If you ever find a possibility space of zero (that is, a square has neither a value, nor any possible values), throw out your current table and pop off the stack, recursing upon that. If you find a possibility space of zero, and the stack is empty, the sudoku is unsolvable. Otherwise, once every square has a value, you're finished.
I feel like I had done a little pondering on ways, while coding it up, to find better heuristics for picking what number to start with, in the event the square with the minimal number of possibilities had more than one (i.e., "this square could be 1 or 5", rather than just picking one arbitrarily, would choose one based on some criteria), but I never really got around to playing with it, as nothing took more than a few tenths of a second, and that was enough to say "there, I need never care about Sudoku"
Solvers aside, many puzzles like Sudoko require another family of algorithms, to generate puzzles that a human can solve without brute force. Finding the right hints to offer seems rather orthogonal to writing a brute-force solver.
> So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column.
For Sudoku puzzles generated for humans, the simplest algorithm doesn't require any backtracking or brute force at all: note for every square which numbers can still potentially work there, and at each step, select one of the squares that has only one number, fill in that number, and update all other squares accordingly. Any puzzle that that algorithm can't solve qualifies as "hard".
One of the rules I use (in that and similar puzzles) for harder puzzles: if you've determined that a pair of squares can each only have X and Y, or a trio of squares can each only have X, Y, and Z, then you know those squares contain those numbers, just not which square contains which number. So you can (for instance) eliminate X and Y from the possibilities for other squares accordingly, which may then provide more steps. Puzzles where I can recognize and apply higher-level, complex rules like that have more staying power with me.
However, it may or may not make sense to teach a computer that special-case rule. A solver may find it easier, rather than recognizing that pattern, to instead just do a search, with transposition tables and similar to avoid duplication. Providing special-case reasoning rules for specific patterns may speed up or slow down such a search, depending on how often the pattern occurs, how much brute-force it eliminates, and how much computation recognizing it requires.
> For Sudoku puzzles generated for humans
I agree that there's a significant difficulty jump, when that algorithm fails to suffice, and I think it's fair to say that's the "hard" jump. But I think a lot of puzzles intended for humans are "hard", by this definition.
Teaching a computer that special-case rule might not make sense for speedy computer solving, but I think it would make sense for telling a human "here's how you could have found this number".
Agreed; the difference between "easy" and "hard" is whether a square always exists with one choice, but the difference between levels of "hard" is how complex a reasoning rule you have to apply. No human should be expected to apply a brute-force backtracking solver, but humans can be expected to apply highly complex pattern-matching rules, or even invent new methods and sets of puzzles solvable with those methods.
Do you count backtracking as 'mechanical'?
This could be relevant to you: http://norvig.com/sudoku.html
I count backtracking as mechanical; but I was also using it in a perhaps overly-broad sense, which includes that solver.
Interestingly, Sudoku is known to be NP-complete.
I had initially thought the same thing, and further that the computational complexity of a game as defined in this paper might be a metric of how challenging a game is.
The paper shows that Super Mario Bros. is NP-complete, whereas Zelda games are PSPACE-complete. So Zelda is more complex than Mario (unless P=PSPACE). Is there some subjective way in which Zelda is harder than Mario, that would correspond to the difference? I guess Zelda can feel more cerebral, maybe.
More crucially the proofs in this paper rely just on the availability of certain items and level configurations that allow them to build circuits to solve 3SAT or whatever. All the other items and possible configurations in a game are irrelevant. For example they show Zelda OoT is PSPACE-complete because it has puzzles where you push around ice blocks---it is possible to construct such as puzzle where solving the puzzle is PSPACE-complete. All the other puzzles in the game, and also the configuration of real ice block puzzles in the game, do not factor into the proof, all that matters is that ice blocks exist somewhere in the game.
So these proofs might point to a potential hard core of cerebral difficulty in games but they ignore many other factors which contribute to enjoyable challengingness. I remember the ice block puzzles in Zelda OoT being pretty tricky, but they certainly don't stand out as the most memorable part of the game.
Is there some subjective way in which Zelda is harder than Mario
I may not actually understand what you're asking, but the obvious answers are objectives, and time limits.
In the classic Mario games there was a clear goal for every level, and you had a time limit to make it there. So you could hypothetically try every possible combination of buttons within the time limit to see which ones succeed.
Zelda has no time limit, and the goals must be discovered.
I do actually think Zelda has higher human computational complexity than Mario (specifically, than Super Mario Bros; Mario 64 has a small degree of such complexity). In adventure games and "Metroidvania" games, when you discover a new item or ability, you have to think about everything you've seen and what new places and areas that item or ability may open up; they're not just non-linear in the "find where to go next" sense, but in the sense that you can go many places. And that doesn't just map to the classic "colored keys open matching doors", either, because obstacles in the world don't always seem like obvious "doors", and which items will help you progress doesn't always look obvious either when well done. Some games make it more blatant, blocking the way with something that clearly has only one solution, but other games reward exploration and allow "sequence breaking", or at least don't prevent it.
Zelda's main quest tends to have a lesser degree of this in practice; often it falls back on "use the item you just got in this dungeon to progress in this dungeon". And some games take it too far in the other direction, leading to the adventure game trope of "poke everything with everything else until something happens". But a good balance rewards players who remember huge parts of the world and reason about what could help them progress.
From a player perspective, Zelda is harder due to: --Larger world with set of objectives which must be completed in some order. IE: You need the bow, before you get the lance, before you get the ice wand. A program could endlessly wander in the wrong temple for centuries before it decided it exhausted the whole area. (Not to mention the hidden walls/areas). ++Mario levels are completed in a mostly linear fashion (ignoring the short cuts).
--Limited resources. Bombs, arrows, etc. ++Mario can always jump/squish, and fireballs are infinite.
--Game changes as items are acquired. A block may be liftable in phase3 of the game, but not in phase1/2. An area may drown you in phase1-4, but may be swimmable in phase5. ++Mario death is always death.
My number one reminder why Zelda would be harder is that temple where most of the walls/floors are bombable and drop you back to the bottom (except one). A computer learning without manual training of some sort would be very interesting to watch.
I don't think computational complexity classes are any more than an extremely rough metric for how challenging games can be. Sudoku, for example, is known to be NP-complete yet puzzles range from the utterly trivial (even to beginners) to the nigh-impossible for a human mind.
This is all putting aside the other ways in which video games can be difficult for humans but trivial for computers. Games which emphasize reflexes, timing, accuracy, communication, etc. are all orthogonal to the question of computational complexity.
Indeed. I'd say there is surprisingly little correlation between computational complexity and how a human experiences complexity.
A similar example, is that we know that 2-color match-Ns (and some further generalizations therefrom) such as Tic Tac Toe, Connect 4, and even wilder variants like Lumines have solved, polynomial solutions and machines can play them better than humans ever will. Humans will probably play some of these games forever, and its still a continual surprise to me how many people don't know the generalized Tic Tac Toe solution, much less that the only way to win is not to play.
Lumines will probably remain interesting to humans for a long time for those orthogonal reasons such as timing and accuracy (and music). But the interesting comparison here is to Tetris which we also generally know to be NP-hard as a direct relative to the generalized packing problem. I would think that to a human both games "feel" equally complex and yet in terms of computational complex you have easy solved algorithm in Lumines and computationally hard problem in Tetris. Lumines certainly feels at first glance to a human like an equal to the packing problem, even though it is not.
What NES games aren't NP-hard? I don't think complexity class is useful for games analysis.
It's interesting that all of the classic board games --- chess, checkers, go --- are NP-hard. I think there's something about NP-hard problems that attracts us, and it's fascinating how experts seem to understand the gestalt of a board position without enumerating the oucomes.
I doubt it, simply because the feel of the game is such a significant factor which an algorithm presumably has no regard for.
Can someone explain what is NP-Hard in a few sentences?
Without using any math terms at all:
Suppose you've got a list of numbers:
And I ask: "Do any of these numbers together add up to 126?5, 11, 26, 13, 215, 55, 68, 99, 3, 7, 41You might have to try every combination of numbers to get an answer. It can be very slow to do, trying every single combination (imagine a list with thousands of numbers, and a very long goal number). Maybe there are no combinations!
But once you have an answer:
It is very easy to verify that the provided answer is correct (are all those numbers in my list? Yes, verified!)11 + 13 + 99 + 3 = 126Compare that problem to this one: Is this list of numbers in ascending order?
The answer is "No, because of the 6." Finding the answer is much faster because you can do it on one read-through of the list. You aren't checking a huge number of potential combinations or anything.4, 7, 11, 22, 6, 35The first problem is in the class of problems called NP-Hard.
Oof. Getting lengthy so I'll shush here. Hope that gives you an intuitive feel for it.
That's just NP though. NP-hard means that if you have an algorithm that runs in NP to an HP-hard, you can solve all of them (with a polynomial-time transformation).
Thank you!
Problems are solved with algorithms. Algorithms are either efficient or not efficient. Algorithms that are efficient can be solved in polynomial time (i.e. time can be estimated with Big Oh notation). So they have a deterministic algorithm. For NP problems, you only have a brute force solution that is inefficient.
By far my favorite explanation of it all, starts simple and explores it very well: https://www.youtube.com/watch?v=YX40hbAHx3s
This is my algorithms professor :D Dope!
This seems strange to me. Mario doesn't "feel" NP-hard. I guess I'll have to read the paper tonight.
Playing the game isn't NP-hard, rather the task of deciding whether a level can be completed or not is NP hard (in fact, NP-complete for Super Mario Bros. and PSPACE-complete for Zelda games).
Being able to complete a level requires knowing that the level can be completed.
And/or play some video games.
So as someone with only a lay understanding of what NP-Hard means - does anyone remember that neural network that someone trained to play the game[1]?
So if you can train a neural network to solve an NP-Hard problem, does that mean by definition (since NP refers to a whole class of problems) that a neural network could eventually be trained to solve any given NPH problem given the time and compute resources to do so?
A neural network does not give any guarantee of solving the problem within any number of iteration. NP-hard problems can be solved, but the solution take a lot of time to find and a slightly larger problem is even harder to solve.
Neural networks is an AI method of searching the solution space in a more intelligent way than "trying everything" (true for most AI methods actually).
If a problem is NP-Hard, it does not mean it cannot be solved. Rather, it means it cannot be solved efficiently (in polynomial time). Most NPH problems, now including Mario and 3SAT, can be solved given the time and compute resources to do so.
Well, to be exact, it's an open question whether they can be solved efficiently or not. The general assumption is that they can't, but it hasn't been proven yet.
The actual games are not NP-hard problem generators. The rules of games can be generalized to create NP-hard problems.
Amplifying on the other posts, just because a problem is an instance of a class that is NP-hard doesn't mean the specific problem is that hard. As mentioned elsewhere in the conversation, subset sum is NP-complete [1], but, metaphorically, if Mario is capable of expressing the generalized subset sum problem, the human-played levels all amount to "Is there a submultiset of the numbers {1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1} that adds to 4?" Not only are all the levels completeable, they're basically trivially so, because what Mario game is there that involves solving sizable logic problems to progress? (Even the Ghost houses are just searches of a very small graph by computer science standards.)
Why is this even a surprise, people have been participating in AI challenges for long time (like these : http://ants.aichallenge.org/ ) and are well aware that those are hard problems, they develop heuristics since its not computationally possible to obtain perfect solution.
Genuinely curious - who claimed that this was a surprise?
Side note: The results of research and insights derived thereof are worth sharing in their own right. It doesn't matter how obvious the result may be to a certain subset of people.
big NES fan here, not a low level programmer - can someone ELI5?
Let's make quantum computers play Nintendo games then.
Quoting Wikipedia:
https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_...BQP is suspected to be disjoint from NP-complete and a strict superset of P, but that is not known. Both integer factorization and discrete log are in BQP. Both of these problems are NP problems suspected to be outside BPP, and hence outside P. Both are suspected to not be NP-complete. There is a common misconception that quantum computers can solve NP-complete problems in polynomial time. That is not known to be true, and is generally suspected to be false.[82]
I figured that out when I was 3.
I thought your comment was funny, and thought "well maybe the downvoters are being a bit too trigger happy"; but I think it's right to downvote. HN needs to stay vigilant about the quality of content offered- we've all see the slippery slope online communities tread on. Please keep comments on-topic and providing interesting insights to the post at hand. HN will be a better place for it.
Yeah nothing says "off topic" like relating to the topic by agreeing the games are hard. A little nostalgia never hurt anyone. Instead of letting the downvotes do the "voting" you had to outline why you did it, contributing to the off topic discussion. Thanks for "providing interesting insights to the post at hand." Thanks for making HN a better place.
I try my best, even if I don't have the ability to downvote. I'm a scrub!
I was being sarcastic - I'm not certain your comment helped the discussion at all. Welcome to HN, I hope you enjoy your stay as long as I have.
I didn't pick up on your sarcasm at all! So lol!
Although, if by explaining to the original downvoted poster why he was being downvoted, perhaps the poster will post more constructive comments in the future.
Maybe the opposite happened, and I merely contributed to an off-comment thread and dragging the OP and the HN community in general down with me.
I don't have the metrics, so no one can tell for sure, which means I'll defend with viscous hostility the belief that I am right.
Hurray internet!
What is that even supposed to mean? The abstract doesn't clarify what "NP-hardness" means in terms of video games.
This looks really click-baity.
In terms of writing a Nintendo game, the solution is a fixed constant: the game's binary.
In terms of solving a Nintendo game, (playing to completion), the solution is in constant time: the amount of time it takes to play the game.
Edit: Great, downvotes.
From the paper:
> 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? 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. Most of our NP-hardness proofs are by reduction from 3-SAT.
Thanks.
Without having time to read the paper, this seems like a proof by obscurity. It's very conceivable that this problem is solvable in polynomial time with very high bounds. The problem is also so vaguely worded that it is practically meaningless, and the interpretation of "how the game designers intended" is also ambiguous.
The collection of games is also odd. Is Pitfall NP-complete? What about how Pitfall was designed to be played? Is Tetris NP-Hard? Is it even hard? ...
What about Minesweeper? Or Pong?
In particular, this article heading totally disregards the result from the first section:
> We can obtain some positive results if we bound the "memory" of the game. For example, recall that in Super Mario Bros. everything substantially off screen resets to its initial state. Thus, if we generalize the stage size in Super Mario Bros. but keep the screen size constant, then reachability of the goal can be decided in polynomial time: the state space is polynomial in size, so we can simply traverse the entire state space and check whether the goal is reachable. Similar results hold for the other games if we bound the screen size in Donkey Kong Country or the room size in Legend of Zelda, Metroid, and Pokemon. The screen-size bound is more realistic (though fairly large in practice), while there is no standard size for rooms in Metroid and Pokémon.
So already revising the definition of the games themselves.
I don't know if you're actually interested in the theory behind analyzing game complexity or just trying to be negative without doing your homework.
Classifying traversal and 2-D games is not a new thing, and they simply apply previous methodologies and proofs to classic Nintendo games. They do not do this via "proofs by obscurity" but rather by classical NP-Hard proofs built upon previous theorems. Specifically, I will point you to the following two papers on fundamentals of proving NP-Hardness of 2-D and traversal games respectively:
- http://link.springer.com/article/10.1007%2Fs00224-013-9497-5
- http://link.springer.com/chapter/10.1007%2F978-3-642-13122-6...
They chose the collection of games because of their relevance to the authors. They wanted to study classic Nintendo games. Other games have also been studied including some, if not all, of the games you mentioned. If you did your research, you would already know the answers to the complexity of games like Tetris or Pong.
If you're genuinely interested in the underlying proofs or the theory behind game complexity, I urge you to read through the papers and their citations first before jumping to conclusions.
Well, I'm a programmer and a game programmer so I wouldn't say it's my homework and I have other things to do with my time.
But I guess I'm not that interested.
Some of my examples were chosen as games that can't be decided as a decision problem: namely those that use analog electronics, involve chance, have multiple players, or have been solved. Or games that are excessively simple, as I think NP-hard is a pretty unimpressive bound to put on a problem.
I'd rather see someone prove that an extremely simple game can be solved in polynomial time rather than prove a classic or simple game can't be solved in polynomial time.
And having played the games, the result didn't intuitively make sense to me which is why I had to read part of the article to understand that they had extended the games in odd ways, such as making boundless levels. In addition, they have made certain assumptions on the design. They are also not generalized problems so speaking of a generalized solution is... not very sensible.
For example, to say that the original Zelda game or one of the first Pokemon games can't be solved in polynomial time is dishonest. The game is fixed. A program that determines if the player can get from the beginning to end is trivial: return true. Otherwise, it wouldn't have been published. Writing the proof that that program is correct might take quite a bit more time ;). The question is, does that game logic, with any arbitrary campaign or level design, hold to that same standard, and then the answer is no.
The paper itself comes very close to refuting its thesis in the first page, when it dictates that there is a finite state that the game machine can have and a finite space for the game. If the hardware that the game runs on has a state space of M, and the level has a size of N, then to prove that a level could never be solved would take on the order of M*N many decisions, at most.
The paper and its thesis are completely reliant on its own definitions, which are not clear in the title or the abstract. Really the heading should read: "Classic Nintendo Games Are NP-Hard in Theory"
When I have time I will surely read the papers on the field that you have provided.