4 ms·

Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how "enjoyably challenging" a game is. There's a reason these games are such clas

Interesting - I wonder if NP-hardness can be used as a sufficient indicator of how "enjoyably challenging" a game is. There's a reason these games are such classics, and I dont think its entirely because of their timing, polish, and marketing. Miyamoto's games always had that special "something" (opinion, I know), maybe this has something to do with it?

lost_name 11y ago
I doubt it, simply because the feel of the game is such a significant factor which an algorithm presumably has no regard for.
sevensor 11y ago
It's interesting that all of the classic board games --- chess, checkers, go --- are NP-hard. I think there's something about NP-hard problems that attracts us, and it's fascinating how experts seem to understand the gestalt of a board position without enumerating the oucomes.
CydeWeys 11y ago
What NES games aren't NP-hard? I don't think complexity class is useful for games analysis.
canjobear 11y ago
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.
- dec0dedab0de 11y ago
  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.
- chongli 11y ago
  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.
  - WorldMaker 11y ago
    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.
- 11y ago
deleted 11y ago
[deleted]
JoshTriplett 11y ago
Probably not formally, but I do tend to find that how much I enjoy a game correlates inversely with how easily I can imagine teaching a computer to play it. Most of the time, if I start thinking "I could write an algorithm for this game", I very quickly lose interest in playing it. 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.
- lostcolony 11y ago
  This is why I never enjoyed Sudoku. I finally just spent some time in between classes writing a solver that solved it in as optimal a fashion one can deterministically solve it in, and said "Okay. Done. I will never feel any guilt over dismissing these again". (EDIT: Writing the solver was actually enjoyable though; far more than manually solving a Sudoku ever was)
  - philh 11y ago
    > in as optimal a fashion one can deterministically solve it in I'm curious what you mean by this? Sudoku is mechanically solvable, but not all sudoku puzzles feel that way, to me. Uh, I haven't actually done sudoku in a long time, so let me talk about kakuro (https://en.wikipedia.org/wiki/Kakuro https://en.wikipedia.org/wiki/Kakuro) instead. I think the feelings I have about them are similar. So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column. And getting a computer to implement that sort of algorithm would be challenging. (http://www.sudokuhints.com/ http://www.sudokuhints.com/ seems to do something like it for sudoku, to let it give you a number and tell you how you could have found that number yourself. But trying a fiendish puzzle, it's not explaining itself very well.) (Obviously, if you don't enjoy sudoku, that's fine. I'm not trying to convince you that you should. It just feels to me like the skills I use for sudoku, aren't ones that I could trivially teach to a computer.)

lost_name 11y ago

I doubt it, simply because the feel of the game is such a significant factor which an algorithm presumably has no regard for.

sevensor 11y ago

It's interesting that all of the classic board games --- chess, checkers, go --- are NP-hard. I think there's something about NP-hard problems that attracts us, and it's fascinating how experts seem to understand the gestalt of a board position without enumerating the oucomes.

CydeWeys 11y ago

What NES games aren't NP-hard? I don't think complexity class is useful for games analysis.

canjobear 11y ago

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.

dec0dedab0de 11y ago
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.
chongli 11y ago
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.
- WorldMaker 11y ago
  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.
11y ago

deleted 11y ago

[deleted]

JoshTriplett 11y ago

Probably not formally, but I do tend to find that how much I enjoy a game correlates inversely with how easily I can imagine teaching a computer to play it. Most of the time, if I start thinking "I could write an algorithm for this game", I very quickly lose interest in playing it. 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.

lostcolony 11y ago
This is why I never enjoyed Sudoku. I finally just spent some time in between classes writing a solver that solved it in as optimal a fashion one can deterministically solve it in, and said "Okay. Done. I will never feel any guilt over dismissing these again". (EDIT: Writing the solver was actually enjoyable though; far more than manually solving a Sudoku ever was)
- philh 11y ago
  > in as optimal a fashion one can deterministically solve it in I'm curious what you mean by this? Sudoku is mechanically solvable, but not all sudoku puzzles feel that way, to me. Uh, I haven't actually done sudoku in a long time, so let me talk about kakuro (https://en.wikipedia.org/wiki/Kakuro https://en.wikipedia.org/wiki/Kakuro) instead. I think the feelings I have about them are similar. So yes, I expect it would be fairly easy to write a backtracking kakuro solver. But the way I solve kakuro is very little like naive backtracking. I do things like - this row can only have numbers two to six, and this column can only have numbers five-plus, so this square is either five or six. But the row can only have one of those numbers, which means this square is two to four, and of those, four is the only number that fits in this column. And getting a computer to implement that sort of algorithm would be challenging. (http://www.sudokuhints.com/ http://www.sudokuhints.com/ seems to do something like it for sudoku, to let it give you a number and tell you how you could have found that number yourself. But trying a fiendish puzzle, it's not explaining itself very well.) (Obviously, if you don't enjoy sudoku, that's fine. I'm not trying to convince you that you should. It just feels to me like the skills I use for sudoku, aren't ones that I could trivially teach to a computer.)