Slashdot Mirror
All the Best Games May Be NP-Hard
Catullus writes "Following in the footsteps of Tetris and Minesweeper, the simple yet addictive multiplatform game Flood-It is the latest puzzle to be proven to be hard — NP-hard, to be exact. This means that there's no way to write an efficient program to beat the game, unless P=NP. This research by computer scientists from Bristol University raises the intriguing question: are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"
Since I had to suffer through at least one professor who didn't understand basic complexity theory last night, and I know that Slashdot generally screws it up to.
NP-Hard means that there's no (deterministic) polynomial-time algorithm to solve the games. Additionally, you always have to generalize these games in order to make that claim. Since computational complexity is defined in terms of the length of the input, and certainly all of these games are being played on an input of fixed length.
However, there are effective approaches to solving NP-Hard problems. There are solvers for known NP-Hard problems. If you Google "sat solver" you'll find at least 5 that you can just download. SAT solvers are used in VLSI validation and other practical things. These solvers use heuristics to improve search performance, generally proposing answers and checking them (for NP-Complete problems).
Also, there are tons of games known to be NP or PSPACE complete. The reductions for those games are kind of a standard problem, since the AI community writes a bunch of these solvers.
You can play it here. I'd say it's undecidable.
All my liberal friends think I'm a conservative, all my conservative friends think I'm a liberal.
Chess and Go are actually EXPTIME-complete, even harder than NP-complete problems and PSPACE-complete problems.
In general, one-player games of bounded length (like Flood-It, or Sudoku) tend to be NP-complete; one-player unbounded games (like sliding-block puzzles, or Sokoban) tend to be PSPACE-complete; two-player bounded-length games (like Hex, or Amazons) also tend to be PSPACE-complete, and two-player unbounded games (like Chess, Checkers, and Go) tend to be EXPTIME-complete.
I can't resist here a plug for my book (with Erik Demaine), Games, Puzzles, and Computation, which discusses all these issues in detail. A theme running throughout the book is the same as the view expressed in this paper: most interesting games and puzzles seem to be as hard as their "natural" complexity class, outlined above.
The minesweeper decision problem is actually: "Given these mine hints, is there any possible way mines could be set on the field so that you would get these hints when uncovering these squares?". It's a reduction from SAT. It's NP because given an answer, you can check if the mine hints would be what the problem states. It's NP-hard because SAT is. Together, NP and NP-hard makes NP-complete.
Note that NP-hardness isn't about the average case, it's about the worst case. Many proofs of puzzles being NP-hard essentially go: "I can make a playing field so that the puzzle is only solvable if a related Boolean circuit can be satisfied, and I can transform any Boolean circuit into a playing field in this manner". Such a proof only tells you that these "gadget puzzles" (transformed circuits) are as hard as SAT, it says nothing about the average puzzle.
As another example, consider a problem where the input is either 0, an integer, and a number of integers; or 1, and a number of integers. Then the decision problem is defined as "if the first number is 0, then true if the second is the sum of all the subsequent integers of the input; if the first number is 1, then true if the circuit defined (in some given format) by the subsequent integers can be satisfied". Obviously, this problem is NP-complete because you can turn any SAT problem into an instance of this problem; but if the first number is 0, the problem is trivially decided.
Incidentally, that's part of the reason why cryptosystems based on NP-hard problems have done so badly: while the cryptosystem might be hard to crack, worst case, it usually turns out most instances of encryption can be broken.