Slashdot Mirror

← Back to Stories (view on slashdot.org)

All the Best Games May Be NP-Hard

Posted by kdawson on 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 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?"

6 of 322 comments (clear)

  1. Re:The fun is in the simplicity by HarrySquatter · · Score: 4, Interesting

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

  2. Sokoban by am+2k · · Score: 4, Interesting

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

  3. Fun == uncertainty by arielCo · · Score: 4, 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 (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.
  4. Re:chess and go aren't np-hard, but they are also by Bob+Hearn · · Score: 4, 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

  5. Re:Just to throw this out there by SomeJoel · · Score: 4, Interesting

    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!>
  6. hands up... by drsquare · · Score: 3, 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.