Forgot your password?
typodupeerror
Games Science

All the Best Games May Be NP-Hard 322

Posted by kdawson
from the easy-for-you-to-say dept.
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 hardNP-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?"
This discussion has been archived. No new comments can be posted.

All the Best Games May Be NP-Hard

Comments Filter:
  • by HarrySquatter (1698416) on Friday April 09, 2010 @11:33AM (#31790912)

    I would argue that Mindsweeper has a far larger audience. And, yes, there are competitive mindsweeper players and leagues.

  • Sokoban (Score:5, Interesting)

    by am 2k (217885) on Friday April 09, 2010 @11:33AM (#31790914) Homepage

    FYI, Sokoban is NP-hard as well (according to wikipedia). I'm seeing a pattern here...

  • by NitsujTPU (19263) on Friday April 09, 2010 @11:42AM (#31791050)

    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)

    by Hatta (162192) on Friday April 09, 2010 @11:43AM (#31791090) Journal

    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)

    by Zocalo (252965) on Friday April 09, 2010 @11:44AM (#31791108) Homepage
    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.
  • Fun == uncertainty (Score:5, Interesting)

    by arielCo (995647) on Friday April 09, 2010 @11:47AM (#31791148)

    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.

  • by bondsbw (888959) on Friday April 09, 2010 @11:59AM (#31791320)

    Even more, you have to know what problem you're trying to solve. There are two obvious possibilities:

    • What is the smallest number of moves I can make to complete a 14x14 puzzle?
    • Can I complete a given 14x14 puzzle in 25 moves?

    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.)

  • by Bob Hearn (61879) on Friday April 09, 2010 @12:03PM (#31791376) Homepage

    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.

  • by yariv (1107831) <yariv.yaariNO@SPAMgmail.com> on Friday April 09, 2010 @12:14PM (#31791538)

    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)

    by MobyDisk (75490) on Friday April 09, 2010 @12:15PM (#31791544) Homepage

    We just come with better software for it.

    We also come with better hardware for it. For now...

  • by Bob Hearn (61879) on Friday April 09, 2010 @12:29PM (#31791768) Homepage

    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]

  • by SomeJoel (1061138) on Friday April 09, 2010 @12:43PM (#31792044)
    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.
  • Re:No. (Score:3, Interesting)

    by amplt1337 (707922) on Friday April 09, 2010 @01:03PM (#31792372) Journal

    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.

  • by d474 (695126) on Friday April 09, 2010 @01:48PM (#31793054)

    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)

    by drsquare (530038) on Friday April 09, 2010 @03:00PM (#31793994)

    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)

    by phantomfive (622387) on Saturday April 10, 2010 @12:21AM (#31798110) Journal
    To be fair, there's not really a good way to explain it, even if you have good explanation skills. It's just really hard and complicated.

The reason that every major university maintains a department of mathematics is that it's cheaper than institutionalizing all those people.

Working...