10 ms·
Classic Nintendo Games Are NP-Hard (2012)
- alttab 11y agoI figured that out when I was 3.
- badloginagain 11y agoI 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.
- alttab 11y agoYeah 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.
- badloginagain 11y agoI try my best, even if I don't have the ability to downvote. I'm a scrub!
- alttab 11y agoI 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.
- badloginagain 11y agoI 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!
- headcanon 11y agoInteresting - 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?
- lost_name 11y agoI doubt it, simply because the feel of the game is such a significant factor which an algorithm presumably has no regard for.
- sevensor 11y agoIt'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.
- CydeWeys 11y agoWhat NES games aren't NP-hard? I don't think complexity class is useful for games analysis.
- canjobear 11y agoI 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.
- CJefferson 11y agoI 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:
- deleted 11y ago[deleted]
- xigency 11y agoMisleading article title and misleading paper title.
- echelon 11y agoThis seems strange to me. Mario doesn't "feel" NP-hard. I guess I'll have to read the paper tonight.
- theseatoms 11y agoAnd/or play some video games.
- canjobear 11y agoPlaying 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).
- xigency 11y agoBeing able to complete a level requires knowing that the level can be completed.
- deleted 11y ago[deleted]
- Karunamon 11y agoSo 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? [1]: https://www.youtube.com/watch?v=xOCurBYI_gY https://www.youtube.com/watch?v=xOCurBYI_gY
- gohrt 11y agoThe actual games are not NP-hard problem generators. The rules of games can be generalized to create NP-hard problems.
- yoavz 11y agoIf 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.
- lorenzhs 11y agoWell, 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.
- runholm 11y agoA 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).
- jerf 11y agoAmplifying 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.) [1]: https://en.wikipedia.org/wiki/Subset_sum_problem https://en.wikipedia.org/wiki/Subset_sum_problem
- fiatjaf 11y agoCan someone explain what is NP-Hard in a few sentences?
- eli 11y agohttps://www.reddit.com/r/explainlikeimfive/comments/1glcly/eli5_np_nphard_npcomplete/ https://www.reddit.com/r/explainlikeimfive/comments/1glcly/e...
- Datsundere 11y agoProblems 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. https://simple.wikipedia.org/wiki/P_versus_NP https://simple.wikipedia.org/wiki/P_versus_NP
- simonsarris 11y agoWithout using any math terms at all: Suppose you've got a list of numbers: 5, 11, 26, 13, 215, 55, 68, 99, 3, 7, 41 And I ask: "Do any of these numbers together add up to 126? You 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: 11 + 13 + 99 + 3 = 126 It is very easy to verify that the provided answer is correct (are all those numbers in my list? Yes, verified!) Compare that problem to this one: Is this list of numbers in ascending order? 4, 7, 11, 22, 6, 35 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. The 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.
- fryguy 11y agoThat'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).
- mtgx 11y agoLet's make quantum computers play Nintendo games then.
- lorenzhs 11y agoQuoting Wikipedia: 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] https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_computational_complexity_theory https://en.wikipedia.org/wiki/Quantum_computing#Relation_to_...
- xigency 11y agoWhat 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.
- iamandoni 11y agoFrom 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.
- xigency 11y agoThanks.
- deleted 11y ago[deleted]
- deleted 11y ago[deleted]
- xigency 11y agoWithout 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.
- newsignup 11y agoWhy is this even a surprise, people have been participating in AI challenges for long time (like these : http://ants.aichallenge.org/ 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.
- autoreleasepool 11y agoGenuinely 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.
- tekknolagi 11y agoThis is my algorithms professor :D Dope!
- BorisMelnik 11y agobig NES fan here, not a low level programmer - can someone ELI5?