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?"
Re:The fun is in the simplicity (Score:4, Interesting)
I would argue that Mindsweeper has a far larger audience. And, yes, there are competitive mindsweeper players and leagues.
Sokoban (Score:5, Interesting)
FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...
Re:Just to throw this out there (Score:2, Interesting)
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.
No. (Score:2, Interesting)
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.
Re:Oblig XKCD (Score:3, Interesting)
Fun == uncertainty (Score:5, Interesting)
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 [wikipedia.org]. 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.
Re:Just to throw this out there (Score:3, Interesting)
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.)
Re:Just to throw this out there (Score:3, Interesting)
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.
Re:Just to throw this out there (Score:2, Interesting)
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...
Re:No. (Score:3, Interesting)
We just come with better software for it.
We also come with better hardware for it. For now...
Re:chess and go aren't np-hard, but they are also (Score:5, Interesting)
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 [mit.edu]
Re:Just to throw this out there (Score:5, Interesting)
Re:No. (Score:3, Interesting)
This is the old "is the universe deterministic" debate that's been raging for thousands of years.
My personal suspicion is that we would need to measure the variables to a sufficient degree of precision that we would hit the realm where physics is no longer strictly deterministic, i.e. that changes at the subatomic level could potentially alter the result. That's probably an overbold claim for dice (unless I want to throw in a "for sufficiently well-constructed dice" weasel), but even so, it may be the case for neurons, for which the normal level of operation is a lot smaller; a sufficiently accurate model would need to account for a lot of movement at the molecular level...
Either way, I think that in the absence of more data, the kind of strong determinism you're proposing is really just an article of faith.
More to the point, you aren't responding to my claim that brains can generate minds, something computers have never been shown capable of doing. I think that the ability to create a mind, and the ability to create concepts with "aboutness" through conceptual metaphor, both present in brains but not computers, are two fundamental hurdles to be overcome before we can really say that a brain is reducible to an algorithm/computer.
Re:Fun == uncertainty (Score:3, Interesting)
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
That's what my wife said when I asked her why she cheated on me.
hands up... (Score:4, Interesting)
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.
Re:hands up... (Score:3, Interesting)