undefined | Better HN

0 pointsiamandoni10y ago0 comments

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.

0 comments

xigency10y 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.

j / k navigate · click thread line to collapse