Comment by canjobear | Hacker News Reader

Comment by canjobear | Hacker News Reader

Parent Full thread

I had initially thought the same thing, and further that the computational complexity of a game as defined in this paper might be a metric of how challenging a game is.

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.

Is there some subjective way in which Zelda is harder than Mario

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.

I do actually think Zelda has higher human computational complexity than Mario (specifically, than Super Mario Bros; Mario 64 has a small degree of such complexity). In adventure games and "Metroidvania" games, when you discover a new item or ability, you have to think about everything you've seen and what new places and areas that item or ability may open up; they're not just non-linear in the "find where to go next" sense, but in the sense that you can go many places. And that doesn't just map to the classic "colored keys open matching doors", either, because obstacles in the world don't always seem like obvious "doors", and which items will help you progress doesn't always look obvious either when well done. Some games make it more blatant, blocking the way with something that clearly has only one solution, but other games reward exploration and allow "sequence breaking", or at least don't prevent it.

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.

From a player perspective, Zelda is harder due to: --Larger world with set of objectives which must be completed in some order. IE: You need the bow, before you get the lance, before you get the ice wand. A program could endlessly wander in the wrong temple for centuries before it decided it exhausted the whole area. (Not to mention the hidden walls/areas). ++Mario levels are completed in a mostly linear fashion (ignoring the short cuts).

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

I don't think computational complexity classes are any more than an extremely rough metric for how challenging games can be. Sudoku, for example, is known to be NP-complete yet puzzles range from the utterly trivial (even to beginners) to the nigh-impossible for a human mind.

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.

Indeed. I'd say there is surprisingly little correlation between computational complexity and how a human experiences complexity.

A similar example, is that we know that 2-color match-Ns (and some further generalizations therefrom) such as Tic Tac Toe, Connect 4, and even wilder variants like Lumines have solved, polynomial solutions and machines can play them better than humans ever will. Humans will probably play some of these games forever, and its still a continual surprise to me how many people don't know the generalized Tic Tac Toe solution, much less that the only way to win is not to play.

Lumines will probably remain interesting to humans for a long time for those orthogonal reasons such as timing and accuracy (and music). But the interesting comparison here is to Tetris which we also generally know to be NP-hard as a direct relative to the generalized packing problem. I would think that to a human both games "feel" equally complex and yet in terms of computational complex you have easy solved algorithm in Lumines and computationally hard problem in Tetris. Lumines certainly feels at first glance to a human like an equal to the packing problem, even though it is not.

Reply on news.ycombinator.com