> 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:
So, I enjoy games where I feel like I can recognize patterns that have some depth and complexity, that make me feel like I can develop some skill, that don't seem trivially teachable to a computer.
(EDIT: Writing the solver was actually enjoyable though; far more than manually solving a Sudoku ever was)
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.
I may not actually understand what you're asking, but the obvious answers are objectives, and time limits.
In the classic Mario games there was a clear goal for every level, and you had a time limit to make it there. So you could hypothetically try every possible combination of buttons within the time limit to see which ones succeed.
Zelda has no time limit, and the goals must be discovered.
Zelda's main quest tends to have a lesser degree of this in practice; often it falls back on "use the item you just got in this dungeon to progress in this dungeon". And some games take it too far in the other direction, leading to the adventure game trope of "poke everything with everything else until something happens". But a good balance rewards players who remember huge parts of the world and reason about what could help them progress.
--Limited resources. Bombs, arrows, etc. ++Mario can always jump/squish, and fireballs are infinite.
--Game changes as items are acquired. A block may be liftable in phase3 of the game, but not in phase1/2. An area may drown you in phase1-4, but may be swimmable in phase5. ++Mario death is always death.
My number one reminder why Zelda would be harder is that temple where most of the walls/floors are bombable and drop you back to the bottom (except one). A computer learning without manual training of some sort would be very interesting to watch.
This is all putting aside the other ways in which video games can be difficult for humans but trivial for computers. Games which emphasize reflexes, timing, accuracy, communication, etc. are all orthogonal to the question of computational complexity.
Suppose you've got a list of numbers:
5, 11, 26, 13, 215, 55, 68, 99, 3, 7, 41
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
Compare that problem to this one: Is this list of numbers in ascending order?
4, 7, 11, 22, 6, 35
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.
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?
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).
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.
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]
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.
> 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.
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.
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.