3 ms·

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 a

by 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.
  - chipsy 13y ago
    I had this argument with my brother too, who is a mathematician. He was able to enjoy it on its own terms, I wasn't. As he concluded, "they couldn't solve an interesting problem, so they solved an uninteresting one instead." And from a certain stance, these fabricated problems do hold a bit of interest, especially when you consider how many mathematicians go out of their way to be impractical. Referencing the games confuses their work more than anything else, though.
  - algorias 13y ago
    A straight up implementation of TSP (I assume you mean the decision variant) needs some kind of door that shuts with a timer. How do you plan to encode arbitrary graphs? This poses a challenge for 2d platformers. In case of any 2d game, how do you encode non-planar graphs? You would need some kind of teleportation device. A graph with few edges and large edge values will also be problematic if you plan on keeping your input size polynomial (in |V| and |E|), as you'd need a widget capable of encoding an arbitrarily long edge in constant map space. Once you have solved all the above problems, feel free to write a paper about it ;).
    - Dylan16807 13y ago
      Those features are nice but unnecessary. Just use planar graphs. Then you don't have to enforce single-visiting either. Limited scrolling will bound the longest edges but you don't need arbitrary edges. Only problems of a limited size will be able to fit in the limited memory of the game but that's still NP-complete over what does fit.
cbhl 13y ago
The key word in the original paper (from 2012 (!)) is "Generalized". IIRC, it's trivial that to "solve" Zelda Polynomial time (with an emulator) -- the entire state space of the console can be represented in constant space, so a trivial algorithm would be to traverse the state space tree with breadth-first search.
- Dylan16807 13y ago
  Picking a 'constant' of 2^k, with k the entire memory space of the console, is a rather inaccurate representation. It's like arguing that a desktop computer is not turing complete: true in such a narrow sense that using it to win a bar bet is going to lead to someone getting punched in the face.

by shasta 13y ago

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.
- chipsy 13y ago
  I had this argument with my brother too, who is a mathematician. He was able to enjoy it on its own terms, I wasn't. As he concluded, "they couldn't solve an interesting problem, so they solved an uninteresting one instead." And from a certain stance, these fabricated problems do hold a bit of interest, especially when you consider how many mathematicians go out of their way to be impractical. Referencing the games confuses their work more than anything else, though.
- algorias 13y ago
  A straight up implementation of TSP (I assume you mean the decision variant) needs some kind of door that shuts with a timer. How do you plan to encode arbitrary graphs? This poses a challenge for 2d platformers. In case of any 2d game, how do you encode non-planar graphs? You would need some kind of teleportation device. A graph with few edges and large edge values will also be problematic if you plan on keeping your input size polynomial (in |V| and |E|), as you'd need a widget capable of encoding an arbitrarily long edge in constant map space. Once you have solved all the above problems, feel free to write a paper about it ;).
  - Dylan16807 13y ago
    Those features are nice but unnecessary. Just use planar graphs. Then you don't have to enforce single-visiting either. Limited scrolling will bound the longest edges but you don't need arbitrary edges. Only problems of a limited size will be able to fit in the limited memory of the game but that's still NP-complete over what does fit.

cbhl 13y ago

The key word in the original paper (from 2012 (!)) is "Generalized". IIRC, it's trivial that to "solve" Zelda Polynomial time (with an emulator) -- the entire state space of the console can be represented in constant space, so a trivial algorithm would be to traverse the state space tree with breadth-first search.

Dylan16807 13y ago
Picking a 'constant' of 2^k, with k the entire memory space of the console, is a rather inaccurate representation. It's like arguing that a desktop computer is not turing complete: true in such a narrow sense that using it to win a bar bet is going to lead to someone getting punched in the face.