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?"
I would argue that Mindsweeper has a far larger audience. And, yes, there are competitive mindsweeper players and leagues.
FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...
I should caveat all of this. The "no polynomial-time algorithm" bit is only true if P!=NP. If P=NP, then there is a deterministic polynomial-time algorithm for NP-Complete problems. NP-Hard, however, just means that it's at least as hard as NP, so, it's possible that there's no algorithm for that harder problem. You have to be really really precise when talking about this stuff.
are these games fun precisely because they're hard for computers to solve, and need a spark of human creativity?"
No. The human mind is created by the brain which is governed by the laws of physics. The laws of physics are mathematical, so fundamentally the human mind is an algorithm. Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot. It's not easier for humans to solve NP-hard problems. We just come with better software for it.
Give me Classic Slashdot or give me death!
Cool. I have a strategy that might work, but it involves getting the first piece dead centre in the bottom such that it creates a level "base", then building a platform up from that on which you can actually complete rows, albeit on a reduced height playing field. The pre-requistite is that the first piece is suitable for creating the platform which, depending on whether the screen width is an odd or even number of boxes across, is a different subset of the available pieces. If you get a "Z" or "S" piece to start though, I think it's pretty much game over, no matter what you do.
UNIX? They're not even circumcised! Savages!
Part of "fun" is uncertainty, a sense of challenge and the subsequent realization when you succeed, when there is no threat to more basic needs. Such feelings would be lessened if solving the problem was a sure thing (or if on the other extreme it looks unlikely to solve, but that's off the topic), and that's why we pick games/levels according to our skill.
Indeed, to me Minesweeper quickly becomes boring, since most of the clicking obeys pretty simple rules ("2-3-2 along an edge - that's clear-3mines-clear"); then at the end it often becomes undecidable and it's eeny-meeny-clicky-boom.
This post contains no rudeness or derision of any kind. All arguments are friendly. Terms and exclusions may apply.
Even more, you have to know what problem you're trying to solve. There are two obvious possibilities:
The first is NP-Hard. But the second may be much easier... if possible, come up with an algorithm to solve every puzzle of that nature in 25 moves. Then your answer would always be yes (a tautology), and the problem is no longer NP-Hard. It's the same as if I asked if every puzzle with at least 5 colors can be solved in 1 move. That's an obvious no (a contradiction), so that question is also not NP-Hard. (I don't know if every puzzle can be solved in 25 moves... perhaps so, but maybe not.)
All my liberal friends think I'm a conservative, all my conservative friends think I'm a liberal.
Ah, it doesn't mean that either. :-)
If a problem is NP-hard, it means it is at least as hard as any other problem that can be solved in polynomial time on a nondeterministic computer.
It is an open question (P=NP) whether this is equivalent to saying that there is no deterministic polynomial-time algorithm.
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
Sadly, you seem not to understand the term yourself. NP-Hard means that given an efficient (deterministic polynomial-time) algorithm to this problem, one can devise an efficient algorithm for any NP problem, so any problem for which solutions can be verified. It might not mean that they aren't solvable (they are solvable efficiently iff P=NP), and a problem might not be solvable and still not NP-Hard. Discrete logarithm and factorization, for example, are suspected to be neither polynomial time computable nor NP-Hard (on classical models, not quantum).
In general, the idea that we are attracted to NP-Hard problem seems quite unlikely to me. We might be attracted to hard problems, but since humans are unable to run algorithms in their heads, why would we use the notion of computational complexity for this "hardness"? It seems more likely that generating problems in the way we do is likely to produce NP-Hard problems than to say we're interested in them as games...
I'll mention it to my publisher, but honestly it would lose a lot without all the color figures.
The book is based on my Ph.D. thesis, which you can download for free:
http://www.swiss.ai.mit.edu/~bob/hearn-thesis-final.pdf
If you drive from Los Angeles to New York without using cruise control, it's hard to figure out exactly how many inches you'll drive (accounting for curves in roads on whichever route you choose), but there are ways, such as maps, to get pretty close approximations.
<Complete your profile by adding a signature!>
Who has no fucking idea what any of this means, and is only further confused by the wikipedia articles written by nerds who have no communication skills.