All the Best Games May Be NP-Hard 322
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?"
Just to throw this out there (Score:5, Informative)
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.
Re:Oblig XKCD (Score:5, Informative)
Re:Just to throw this out there (Score:1, Informative)
Well to be pedantic, you aren't quite right either. NP-Hard means there is no KNOWN (deterministic) polynomial-time algorithm. If P==NP, then there will be some polynomial-time algorithm.
Re:The fun is in the simplicity (Score:2, Informative)
>>>Not sure if I would agree with Minesweeper having a larger audience
How many users of Windows are there? Approaching 1 billion homes? That's a bigger audience than even the best-selling console (~150 million PS2s) ever reached.
Book on the Complexity of Games and Puzzles (Score:3, Informative)
Re:chess and go aren't np-hard, but they are also (Score:5, Informative)
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 [amazon.com], 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.
Re:Oblig XKCD (Score:3, Informative)
I made a nice line yet got no points. I guess they weren't thight enough or they just never plugged in the points calculation :)
Re:Just to throw this out there (Score:3, Informative)
The "no polynomial-time algorithm" bit is only true if P!=NP.
And to the best of human knowledge, it happens to be the case that P!=NP.
Re:The fun is in the simplicity (Score:2, Informative)
I think my point is that Minesweeper has been sitting on nearly every desktop in the world, from Windows 3 (1990) to Windows 7 (2010). Other games have not. QED Minesweeper has far wider "coverage" to borrow a term from Nielsen television.
But if Windows users had the choice of the two, Minesweeper or Tetris, automatically available to them, I'm confident that Tetris would win hands down.
What was Peter playing in OfficeSpace? Not Minesweeper.
Re:The fun is in the simplicity (Score:2, Informative)
As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?
-
Watch this to the end, you'll see. [youtube.com]
Re:Sokoban (Score:5, Informative)
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.
Re:The fun is in the simplicity (Score:3, Informative)
Are you saying that you couldn't write a program to solve checkers in twelve lines of code?
Such a simple brute force solver still needs an executable specification of the rules that converts a board state and a move into a new board. For checkers this function is simple. For Go this function needs to check the freedoms of each cluster of stones and would thus require recursion. This alone would make it a more complex program than the checkers solver.
Re:Sokoban (Score:3, Informative)
Briefly (and wrongly, but it will do for a slashdot reply), NP complete problems require the computer to actually calculate all of the possible solutions and see which one is best rather than than using an algorithmic shortcut. For every extra item that has to be computed the complexity increases by quite a large amount relative to the difficulty of the smaller problem. The traveling salesman problem is the classic example - adding another town to visit means you have to recalculate all the routes because there just might be a better solution using the new town in any part of the route.
Anyway, there's nothing impossible about NP complete problems - the issue is that they get very hard very quickly as you make the problem space bigger. Quickly the time required to find the best solution (not just a good one) would take longer than the remaining lifetime of the universe.
One of the tricks with NP complete problems is that if you're looking for a merely good solution, not the absolute best, humans can often use some heuristic tricks to home in on a good solution quickly while a dumb computer algorithm would still be chugging away looking exhaustively for the best solution. Studying the kinds of guesses that humans make in these situations is a notable area of study in artificial intelligence.
In summary, a computer will kick you ass at minesweeper, but it still won't be able to solve a 10^14 x 10^14 board before the end of time.
Re:Oblig XKCD (Score:3, Informative)
First Person Tetris [firstpersontetris.com]
Re:The fun is in the simplicity (Score:2, Informative)
Actually, poking a random square is NP-easy, so to speak. It's just not guaranteed a solution.
Remember that NP-Hard means essentially there is no way to solve a problem short of basically trying all possibilities. And that's exactly what a human mind is doing in Minesweeper.
Re:The fun is in the simplicity (Score:4, Informative)
I think your using a poor choice in words. Your saying that go has a simpler rule base than checkers, ie it's easier to determine whether a rule is valid or not, correct? Not the actual strategy and hence wining of the game.
Considering that checkers is a solved game with 10^31 moves. Chess being 10^50 and Go an estimated 10^80 if I recall correctly.
So figuring out a valid move may be easier in Go than in checkers; however, it's the gameplay/strategy that really counts.