49
$\begingroup$

I read the Wikipedia entry about "List of NP-complete problems" and found that games like super mario, pokemon, tetris or candy crush saga are np-complete. How can I imagine np-completeness of a game? Answers don't need to be too precise. I just want to get an overview what it means that games can be np-complete.

$\endgroup$
  • 4
    $\begingroup$ See the reference question about NP-completeness. I think your question is too broad for the stack exchange format. $\endgroup$ – Kyle Jones Feb 6 '17 at 19:04
  • 5
    $\begingroup$ In minecraft, you can create.... well a computer... running.... minecraft? $\endgroup$ – djsmiley2k - CoW Feb 7 '17 at 13:02
  • 4
    $\begingroup$ Building calculators using Magic: the Gathering cards. Big fun :-) $\endgroup$ – Mast Feb 7 '17 at 14:23
  • $\begingroup$ This isn't quite an answer to the question you're asking, but is so closely related that it is important to point out: the well-known game designer (and proponent of formal methods in game design) Raph Koster has theorized that the computational complexity of games is critical to our continued enjoyment of them. He defines "fun" as essentially a response to learning to improve performance of a difficult task in a non-threatening environment, and points out that continuing to do this in a constrained system like a game relies on that system having behaviour patterns that are ... $\endgroup$ – Jules Feb 7 '17 at 20:37
  • $\begingroup$ ... difficult or impossible to completely predict quickly enough to use those predictions, therefore forcing us to learn in a less direct way (usually using heuristics). Problems with a high complexity (he often suggests NP Hard) are the most reliable way of generating such behaviour patterns, which (if he is correct) is probably why they crop up in so many well-known games. See these conference slides and this book for more. $\endgroup$ – Jules Feb 7 '17 at 20:42
71
$\begingroup$

It just means that you can create levels or puzzles within these games that encode NP-Hard problems. You can take a graph coloring problem, create an associated Super Mario Bros. level, and that level is beatable if and only if the graph is 3-colorable.

If you want to see the specific way the NP-Complete problems are translated into the games, I recommend the paper "Classic Nintendo Games are (Computationally) Hard". It's well written and easy to follow.

An important caveat to keep in mind is that the NP-hardness requires generalizing the games in "obvious" ways. For example, Tetris normally has a fixed size board but the hardness proof requires the game to allow arbitrarily large boards. Another example is off-screen enemies in Super Mario Bros: the proof is for a variant of the game where off-screen enemies continue moving as if they were onscreen, instead of ceasing to exist and being reset to their starting position when Mario comes back.

$\endgroup$
  • 4
    $\begingroup$ Not worth an answer on it's own, but the following has a nice video lecture: courses.csail.mit.edu/6.890/fall14/lectures/L05.html - Crystal clear explanations. $\endgroup$ – user340082710 Feb 6 '17 at 23:22
  • 4
    $\begingroup$ It may be worth including a precise statement of a theorem from the (hugely interesting!) paper that you linked, which succinctly and precisely explains exactly what it means to say that a game is NP-hard: It is NP-hard to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros $\endgroup$ – ymbirtt Feb 7 '17 at 11:58
  • $\begingroup$ unrelated perhaps, but with the latest Pokemon games (Sun and Moon), the proof in the article is no longer true (at least, as-is), as enemy trainers no longer move towards the player to battle them. $\endgroup$ – simonalexander2005 Feb 8 '17 at 15:39
  • 2
    $\begingroup$ To be NP-Complete you must both be able to encode NP-Hard problems, and be in NP. The second clause is missing from the above answer. $\endgroup$ – Yakk Feb 8 '17 at 16:57
  • $\begingroup$ Although this answer is technically good, does it really illuminate the problem to someone unknowledgeable enough to have asked the question in the first place? I really don't think it does... $\endgroup$ – MaxW Feb 11 '17 at 7:44
20
$\begingroup$

I honestly don't know exactly what kind of model is used by the people making those claims; however, what seems reasonable to me would be talking about the $\mathcal{NP}$-completeness of deciding something about a game situation.

Let's take as an example Tetris, since it's the only one from those you quote that I understand enough to talk about. Tetris has a rule called "perfect clear", that gives the player a large bonus if a piece drop clears the board entirely. One might wonder if, given an ordered sequence of pieces $\{P_i\}$ and an integer $k$, there exists a legal sequence of moves for the pieces $P$ that achieves at least $k$ perfect clears. Problem statements such as those are sufficiently abstract that can be modeled with the tools of complexity theory.

Long story short, "$\mathcal{NP}$-complete" means one thing and one thing only, fancy claims such as "Super Mario is $\mathcal{NP}$-complete" have to be translated into a formal statement before they make any actual sense.

$\endgroup$
1
$\begingroup$

Here's a simplistic hand-waving explanation:

Such games are in NP because "running" a player's behavior over the course of a game and checking whether s/he wins or loses can be done efficiently (we need it to be in polynomial time in the length of the game, but it's probably linear or $O(n \log(n))$-ish).

Such games are NP-hard because the player's behavior is very expressive. While at any given point a player may only have a limited, even a fixed, number of possible actions, that's enough to create a space of behaviors or strategies exponential in the length of the game; and while you may be able to provide a simple condition or logical formula on the validity/benefit/correctness of a player's actions locally, globally you get a similar effect as with a large combinatorial circuit, or a k-CNF formula.

Hopefully this makes some intuitive sense and also rings enough CS theory bells.

PS - Some games are much more (computationally) complex than that. For example, the boardgames Hex, Go and and Reversi are PSPACE-complete. That's essentially because the formula you need to satisfy for a winning strategy is a repeatedly-alternating-quantifier formula: The exists a move by player 1, such that for every move by player 2, there exists a move by player 1 etc. etc. such that with all those moves having been played, either some of player 2's moves are invalid or we have a valid sequence player 1 has won. With NP games, it's typically just one player's behavior/strategy/choice of moves.

$\endgroup$
  • $\begingroup$ "Hopefully this makes some intuitive sense" -- doesn't to me... $\endgroup$ – Raphael Feb 8 '17 at 21:30
1
$\begingroup$

For single player games, you can always ask the question "is there a winning strategy for the player", and that question often has a "YES" answer that can be verified in polynomial time, and may very well be NP complete.

For two-player games, the answer can very often not be verified in polynomial time, because to verify that a move for A is a winning move, you must demonstrate that for every response of B there would be again a winning move for A and so on.

$\endgroup$
0
$\begingroup$

Well, it's certainly in NP, because a possible solution is just a finite number of inputs (in each input frame you can select any of the k buttons, we represent each selection of the buttons for each frame with a letter) that brings you to the win-screen. We know that this game has been beaten before, so we know, that there exists a solution. An NTM goes over it's tape and guesses magically a correct certificate of length n. Then it simulates Super Mario with the input and verifies it. The verification can be done in polynomial time (linear time actually, if the solution is correct, it will take exactly n frames to win).

To show NP-completeness, we could reduce 3-SAT to it by building a 3-Sat checker with the level generator (which is built through arbitrary code execution https://www.youtube.com/watch?v=IOsvuEA2h4w).

So we have a 3-SAT CNF input, that we check for correct formatting first. If it's badly formatted, we just translate it into one 'jump'-input (it's not possible to to beat Super Mario within one frame by doing a jump).

We call the length of the 3-CNF input n.

If it's correctly formatted, we translate it into a number of inputs, that builds the 3-CNF checker for us (always the same code of length k), translates the 3-CNF into a String of inputs, that builds the specific 3-CNF in the checker (in O(n)),and checks all possible solutions by brute-force. It idles and does nothing, if after going thru all solutions, none is found. It restarts the game and uses a known solution for Super Mario to beat the game (the code to do that is has the length j). Our transformation is thus in O(n), so it is within polynomial time.

If the CNF is badly formatted, we don't win (by definition our input is not winning, if we haven't won one frame after the execution of it). If the CNF is not satisfiable, we don't win (you can't win by idling for one frame in the level generator, we ensured that in our code). If the CNF is satisfiable, the checker finds a solution restarts and wins the game. Thus the polynomial reduction of 3-Sat to Super Mario is complete and we have proven, that Super Mario is NP-complete.

(Hope I haven't messed this up somewhere. We do run into a storage problem, if the 3-CNF is too long, but limited storage is usually ignored in these contexts, I believe)

$\endgroup$
  • $\begingroup$ "Well, it's certainly in NP, because a possible solution is just a finite number of inputs" Being in NP requires that the solution be polynomially bounded in the size of the input. Just being finite isn't enough. $\endgroup$ – David Richerby Feb 11 '17 at 20:07
0
$\begingroup$

I rewrote this answer to try to address some comments on a previous version.

I assume that you've read the Wikipedia definition for NP-completeness which really doesn't focus on games. I'll water down the exact meaning of NP-completeness and game theory just a bit and explain the essence of a NP-Complete game.

Let's consider a 2-player game with alternate moves, more restrictively this is essentially about Combinatorial games. Basically a game which the you have some number of moves that can be made and you must chose one of them. You would like to play "perfectly" which means that you'd never make a "bad" move. So of the allowable moves you'd like to select the best one. (Of course your opponent has the same goal...)

Note that perfect play doesn't mean that you'll always win. The rules of the game can be such that the first or the second player should win. Also some games like Tic-Tac-Toe should end in a draw. Thus what "perfect play" means in this discussion is:
(1) That you'll never be in a winning position and then lose the game because you made a "bad" move
(2) You'll never miss an opportunity to get into the winning position if such an opportunity arises.

Given the current state of the game what you'd like is to be able to use an "efficient algorithm" to calculate the best move. On the other hand let's note that an algorithm that has to search through the whole game tree is an "inefficient algorithm."

Now lets define "efficiency" a bit more formally. I'm going to simplify this a bit but the essence is correct. Consider the number of calculations, $C$, that must be done to chose the next move, that one the average each move has $B$ possibilities (the branching factor) and that there are $n$ moves left in the game. The notion is also that each calculation takes the same time so that the effort can be translated into time complexity, $T$, instead of raw calculations.

  • An "efficient algorithm" will have:
    $T \varpropto aB^a + bB^{\alpha-1} + cB^{\alpha-2} + ... + hB^0$
    where $\alpha$ is a "small integer," and a-h are some real numbers. Thus the efficient algorithm executes in polynomial time since this is a polynomial expression.
  • An "inefficient algorithm" will have:
    $T \varpropto aB^n$
    and this algorithm executes in exponential time (i.e. nonpolynominal time). The point here is that as $n$ gets larger a combinatorial explosion results.

Now the important point is that it is impossible to have an efficient algorithm, polynomial time, which plays perfectly for a game which NP-complete. To play perfectly a NP-complete problem must, by definition, be solved by an inefficient algorithm that runs in nonpolynomial time.

Note that the running time is about the intrinsic number of calculations, not the response time perceived by a human. For a small game like Tic-Tac-Toe the computer could play all possible future moves and still respond quickly as perceived by a human.

For Nim it is possible to create an polynomial time algorithm. At any point in the game the algorithm can calculate which player has a winning move and what that move should be.

On the other hand let's take the game of Qubic. (You're trying to make a line of 4 in a 3D grid. So it is essentially tic-tac-toe on a 4x4x4 grid.) Qubic is NP-complete thus there is no polynomial time algorithm to calculate the next perfect move. The only way to know if you currently have a winning move is to try all the possible moves of both players to verify that a particular move is a winner, or at least not a loser.

Truthfully the whole game tree for Qubic is small enough so that it can be encoded into a computer program which can play perfectly. What encoding means is that the whole game tree has been explored and all the moves worked out in advance. So the program can essentially do a quick database call using the current board state and get back the best move for that board state without having to do the tree search each time a move is to be made. This is really a "cheat" for our purposes here.

Now let's discuss chess to discuss the evaluation function ignoring some of the other features of chess playing programs. Chess is still an unsolved game. It is unknown if the first or second player should win. It is not possible to be given any board position and predict with certainty who will win. In fact chess has such a large game tree that it is just impossible to search the whole game tree. You'd need computers which are not just 10 or 100 times faster but billions of billions of time faster than any current computer. (There is the hope that quantum computing could cut through this Gordian knot.)

Think of the chess evaluation function as giving each possible next move a probability of being the best move. What a chess program does is to combine look aheads with the evaluation function. Thus the program looks at all possible future moves until it gets to a point where a "good" score can be given to the board position. The computer evaluates all possible paths through the tree this way and then chooses the path with the best score. Since the search never got to the end of the game for all the paths being evaluated, all chess programs ultimately use an imperfect evaluation function. (If you're near the end of the game then the computer might be able to look at all possible future moves.) That means that might be possible to beat the program even if the program had a winning position at some point.

$\endgroup$
  • $\begingroup$ "it is /impossible/ to have an efficient algorithm, polynomial time, for a game which NP-complete. A NP-complete problem must, by definition, be solved by an inefficient algorithm that runs in nonpolynomial time." - That is not correct. It is not known whether it is possible to solve NP-complete problems in polynomial time: most researchers strongly expect that the answer is "no", but we don't know that for sure, and it's not by definition. I encourage you to spend more time reading about the actual definition of NP-complete. You can find some resources on this site, and on Wikipedia. $\endgroup$ – D.W. Feb 11 '17 at 17:55
  • $\begingroup$ @D.W. - Yes, I dumbed the answer down a bit. I said that in the first paragraph. If you read the bit below Qubic I also explained how a polynomial time algorithm can be used for a "small" game. I was trying to give an answer the OP would understand not write a book on NP-completeness and game theory. $\endgroup$ – MaxW Feb 11 '17 at 18:01
  • $\begingroup$ @@D.W. - It occurred to me that I thought that I was implicitly taking about perfect play. I explicitly added that qualification. $\endgroup$ – MaxW Feb 12 '17 at 20:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.