5 ms·

Classic Nintendo Games are NP-Hard

50 points by JacksonGariety 13y ago

nateh 13y ago
The game's components (underlying rules) can be used to build NP-hard problems. The published games (specific world setups (are not NP-hard, even with generalizations to make them non-constant sized. This paper is fun and interesting, and it shows how a common abstract language underlies many diverse concrete games. However, one should not make bold statements about sophisticated challenges that 10-year-olds are solving. wert
daniel-cussen 13y ago
When designing a game [I didn't build], I realized one of the most important ways of making the game indefinitely interestingly was to make it really hard to solve. This meant making it NP-hard on purpose.
- sgift 13y ago
  This is helpful, but not sufficient. At the same time it has to be engaging and still look solvable i.e. the player must always have the feeling that "next time I'll do it!" or he will just stop playing. One of the last bosses in Zelda is an interesting example. It starts as a dragon with three heads. One which is only killable by fire, the other by ice, the last one is invincible but tries to bite you. When the outer heads are dead the third head transforms to a fast moving snake which you have to hit at a specific point to damage. Each time you hit it it gets faster. Now, if you die something interesting happens: The next snake will start slower i.e. easier, so players should be able to kill more parts of it. This repeats itself every time you die. I noticed this when my mother (who loves Nintendo games, but isn't a really good player) died 20 times or so at the snake. Every time it was a bit slower and every time she was like "Well I did manage to kill one more part. THIS time I kill it!" and ran in again. In the end she killed the boss and was happy.
  - nateh 13y ago
    That's manipulative :-( Making these easier by option, or by offering a "skip" or an "assist" to get past an obstacle, is one thing, but secretly nerfng is an abomination. That just teaches people have an over inflated opinion of themselves and to think that bullheaded religion is better than strategy or skill practice.
  - nolok 13y ago
    Also known as the difference between finishing a mario game, and finishing a mario game with all stars / 100% completion. Those levels are vicious.
  - iknowno_one 13y ago
    Zelda 2 is considered by so many weak-willed children of the 80s to be the "hardest" Zelda game, and yet it was not even included...
  - nijk 13y ago
    That's manipulative :-( Making these easier by option, or by offering a "skip" or an "assist" to gwt past an obstacle, is one thing, but secretly nerfng is an abomination. That just teaches people have an over inflated opinion of themselves and to think that bullheaded religion is better than strategy or skill practice.
maaaats 13y ago
I have a book called Games, Puzzles, and Computation (Hearn & Demaine). It discusses and proves the hardness of various games and puzzles. Not the scale of AAA titles, though. It's an interesting read. Not too mathy. They make clause gadgets in the same way as the example here for Super Mario Brothers and use that to prove things. Edit: Realized the author of this book is actually one of the authors of this paper. So, yeah, if you found this article/paper interesting be sure to pick up the book.
- kriro 13y ago
  Nice, I'll check it out.
shasta 13y ago
This is ridiculous. The real maps in these games didn't include even a hint of this kind of branching nonsense, so this kind of result says nothing about the actual difficulty of these games. And yet I sadly suspect "Zelda is NPC" is now going to become Internet folk wisdom. Groan. This paper is actively harmful if you ask me.
- Leszek 13y ago
  It's not about the actual difficulty of the games, it's about what sort of problems can be encoded using the gameplay.
- groovy2shoes 13y ago
  Any time I see papers like this, I'm reminded of Vargomax V. Vargomax's classic SIGBOVIK 2007 paper [1]. The presentation is also entertaining [2]. [1] http://www.cs.cmu.edu/~tom7/sigbovik/mariox.pdf http://www.cs.cmu.edu/~tom7/sigbovik/mariox.pdf [2] http://www.youtube.com/watch?v=HhGI-GqAK9c http://www.youtube.com/watch?v=HhGI-GqAK9c
- algorias 13y ago
  NP-completeness doesn't say anything about the difficulty of a specific instance of a given problem. It's trivial to construct CNF formulas that are solvable in polynomial time, for example. An algorithm that is able to determine for every Zelda level, in polynomial time, whether or not the exit can be reached from the start is something quite different. As shown in this paper, this would imply that the same algorithm can solve every instance of every problem in NP efficiently, a.k.a. answer the million dollar question. A cleaner way of stating the results of the paper would be: "The puzzle mechanics of Zelda are NPC". This statement is harder to misread, though I wouldn't hold my breath given the extreme illiteracy concerning theoretical computer science prevalent even among programmers with a degree, never mind the internet.
  - Dylan16807 13y ago
    Zelda is not simply a single instance of a static puzzle with a well-defined solution, it has code creating things dynamically. The title implies that the NP-complete problems are part of the actual gameplay. If you're only looking at mechanics you can pick nearly any game with movement and pull out traveling salesman.
sehugg 13y ago
It's worth pointing out that even tic-tac-toe is PSPACE-complete. Here is a StackExchange question discussing the "solvability" of PSPACE vs NP: http://cstheory.stackexchange.com/questions/5323/are-pspace-complete-problems-inherently-less-tractable-than-np-complete-prob http://cstheory.stackexchange.com/questions/5323/are-pspace-...

nateh 13y ago

The game's components (underlying rules) can be used to build NP-hard problems. The published games (specific world setups (are not NP-hard, even with generalizations to make them non-constant sized. This paper is fun and interesting, and it shows how a common abstract language underlies many diverse concrete games. However, one should not make bold statements about sophisticated challenges that 10-year-olds are solving. wert

daniel-cussen 13y ago

When designing a game [I didn't build], I realized one of the most important ways of making the game indefinitely interestingly was to make it really hard to solve. This meant making it NP-hard on purpose.

sgift 13y ago
This is helpful, but not sufficient. At the same time it has to be engaging and still look solvable i.e. the player must always have the feeling that "next time I'll do it!" or he will just stop playing. One of the last bosses in Zelda is an interesting example. It starts as a dragon with three heads. One which is only killable by fire, the other by ice, the last one is invincible but tries to bite you. When the outer heads are dead the third head transforms to a fast moving snake which you have to hit at a specific point to damage. Each time you hit it it gets faster. Now, if you die something interesting happens: The next snake will start slower i.e. easier, so players should be able to kill more parts of it. This repeats itself every time you die. I noticed this when my mother (who loves Nintendo games, but isn't a really good player) died 20 times or so at the snake. Every time it was a bit slower and every time she was like "Well I did manage to kill one more part. THIS time I kill it!" and ran in again. In the end she killed the boss and was happy.
- nateh 13y ago
  That's manipulative :-( Making these easier by option, or by offering a "skip" or an "assist" to get past an obstacle, is one thing, but secretly nerfng is an abomination. That just teaches people have an over inflated opinion of themselves and to think that bullheaded religion is better than strategy or skill practice.
- nolok 13y ago
  Also known as the difference between finishing a mario game, and finishing a mario game with all stars / 100% completion. Those levels are vicious.
- iknowno_one 13y ago
  Zelda 2 is considered by so many weak-willed children of the 80s to be the "hardest" Zelda game, and yet it was not even included...
- nijk 13y ago
  That's manipulative :-( Making these easier by option, or by offering a "skip" or an "assist" to gwt past an obstacle, is one thing, but secretly nerfng is an abomination. That just teaches people have an over inflated opinion of themselves and to think that bullheaded religion is better than strategy or skill practice.

maaaats 13y ago

I have a book called Games, Puzzles, and Computation (Hearn & Demaine). It discusses and proves the hardness of various games and puzzles. Not the scale of AAA titles, though. It's an interesting read. Not too mathy. They make clause gadgets in the same way as the example here for Super Mario Brothers and use that to prove things. Edit: Realized the author of this book is actually one of the authors of this paper. So, yeah, if you found this article/paper interesting be sure to pick up the book.

kriro 13y ago
Nice, I'll check it out.

shasta 13y ago

This is ridiculous. The real maps in these games didn't include even a hint of this kind of branching nonsense, so this kind of result says nothing about the actual difficulty of these games. And yet I sadly suspect "Zelda is NPC" is now going to become Internet folk wisdom. Groan. This paper is actively harmful if you ask me.

Leszek 13y ago
It's not about the actual difficulty of the games, it's about what sort of problems can be encoded using the gameplay.
groovy2shoes 13y ago
Any time I see papers like this, I'm reminded of Vargomax V. Vargomax's classic SIGBOVIK 2007 paper [1]. The presentation is also entertaining [2]. [1] http://www.cs.cmu.edu/~tom7/sigbovik/mariox.pdf http://www.cs.cmu.edu/~tom7/sigbovik/mariox.pdf [2] http://www.youtube.com/watch?v=HhGI-GqAK9c http://www.youtube.com/watch?v=HhGI-GqAK9c
algorias 13y ago
NP-completeness doesn't say anything about the difficulty of a specific instance of a given problem. It's trivial to construct CNF formulas that are solvable in polynomial time, for example. An algorithm that is able to determine for every Zelda level, in polynomial time, whether or not the exit can be reached from the start is something quite different. As shown in this paper, this would imply that the same algorithm can solve every instance of every problem in NP efficiently, a.k.a. answer the million dollar question. A cleaner way of stating the results of the paper would be: "The puzzle mechanics of Zelda are NPC". This statement is harder to misread, though I wouldn't hold my breath given the extreme illiteracy concerning theoretical computer science prevalent even among programmers with a degree, never mind the internet.
- Dylan16807 13y ago
  Zelda is not simply a single instance of a static puzzle with a well-defined solution, it has code creating things dynamically. The title implies that the NP-complete problems are part of the actual gameplay. If you're only looking at mechanics you can pick nearly any game with movement and pull out traveling salesman.

sehugg 13y ago

It's worth pointing out that even tic-tac-toe is PSPACE-complete. Here is a StackExchange question discussing the "solvability" of PSPACE vs NP: http://cstheory.stackexchange.com/questions/5323/are-pspace-complete-problems-inherently-less-tractable-than-np-complete-prob http://cstheory.stackexchange.com/questions/5323/are-pspace-...