3 ms·

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 hi

by xigency 11y ago

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.

iamandoni 11y ago
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/article/10.1007%2Fs00224-013-9497-5 - http://link.springer.com/chapter/10.1007%2F978-3-642-13122-6_22 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.
- xigency 11y ago
  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.

by xigency 11y ago

iamandoni 11y ago

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/article/10.1007%2Fs00224-013-9497-5 - http://link.springer.com/chapter/10.1007%2F978-3-642-13122-6_22 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.

xigency 11y ago
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.