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:
  • Oblig XKCD (Score:3, Funny)

    by Zocalo (252965) on Friday April 09, 2010 @12:28PM (#31790828) Homepage
    I'd say that this [xkcd.com] is most definitely NP, for humans and AI alike.
  • by Pojut (1027544) on Friday April 09, 2010 @12:28PM (#31790838) Homepage

    Tetris, to me, is the ultimate video game. It can be played by anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros.

    No other video game in history has that kind of audience. The fact that, although variations on the original have been released, the most popular version is still the original version (which has remain mostly untouched throughout its existence) just gives more credit to its simplistic genius.

    • by HarrySquatter (1698416) on Friday April 09, 2010 @12:33PM (#31790912)

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

      • by Pojut (1027544)

        Not sure if I would agree with Minesweeper having a larger audience, however you are certainly correct in that Minesweeper also transcends gaming skill much in the same way as Tetris. I stand (sit?) corrected.

        • Re: (Score:2, Informative)

          by theaveng (1243528)

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

          • by quantumplacet (1195335) on Friday April 09, 2010 @01:00PM (#31791326)

            exactly, because every single windows user plays minesweeper, but not tetris which is unfortunately only available for ps2.

            • by theaveng (1243528)

              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.

              • Re: (Score:2, Informative)

                by jpcarter (1098791)

                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.

          • That doesn't mean they play mindsweeper. My mom has windows XP, but she uses my old gameboy to play tetris. Also, its not like there isn't a tetris clone made for every popular OS.

          • by Pojut (1027544)

            Come on...not everyone that uses Windows regularly plays Minesweeper.

            • by DrVomact (726065)

              Come on...not everyone that uses Windows regularly plays Minesweeper.

              That's because it's a lousy game—there's no guarantee that it can be solved by logic; often you reach a point where you must guess. There's a variant I had on my (now abandoned) Palm Treo that was guaranteed to be solvable by logic. Can't remember who made it now.

              Thinking about this, I was at first tempted to say that the first (Windows default) variant of the game is more difficult to solve by a computer (i.e. via an algorithmic solution), while a program could easily solve the second variety. But t

              • by Bigbutt (65939)

                Yep, I recall an interview with Bill Gates years ago regarding Minesweeper. He was asked what his best time was and it was something like 1 second. The interviewer asked how he did it. He said he'd just randomly click until he got the 1 second score.

                [John]

          • by poetmatt (793785)

            even higher yet. the thing is on every OS that exists, basically.

      • Is that what the army recruiter told you?

    • by Azarael (896715)
      I'd like to point out though, that just because a game has simple rules, doesn't mean it isn't very complicated to play. Look at how long it too for someone to completely 'solve' the game of checkers (using a computer).
      • by Pojut (1027544)

        Yes, but like checkers, just about ANYONE with basic cognitive functions can play Tetris...the concept itself very easy to understand.

        A minute to learn, a lifetime to master comes to mind...

        • by Azarael (896715)
          Yes, that was the point that I was attempting to make.
        • by theaveng (1243528)

          I remember when I first played Tetris on a Nintendo Gameboy. I was unimpressed.

          Later I tried it again, and determined it was more fun that I initially thought, but whenever I play Tetris I grow tired of it rather quickly (less than half an hour). My longterm gaming addictions are: Space Invaders (Atari 2600/VCS version), Asteroids, Missile Command, and Ms. Pac-Man (arcade). I can play these games hour after hour.

          I also like to revist simulations like Tom Clancy's Red Storm Rising. Boring graphics but

          • Have you played pac man C.E.? best pacman ever.

          • whenever I play Tetris I grow tired of it rather quickly (less than half an hour).

            That's why new versions of Tetris take five minutes to play through: either they're two- or three-minute time trials, or they speed up so fast that you're dead after 5 minutes. Watch this video [youtube.com] all the way through.

      • by Abcd1234 (188840)

        Heck, Go is even simpler than checkers, and it's nowhere even close to being solved (the current, top-ranked computer program is roughly 2p, and easily defeated by a strong professional player).

    • by eldavojohn (898314) * <eldavojohn.gmail@com> on Friday April 09, 2010 @12:43PM (#31791078) Journal

      Tetris, to me, is the ultimate video game. It can be played by anyone ranging from someone who doesn't even know what a video game is all the way to competitive level hardcore pros.

      No other video game in history has that kind of audience..

      Wrong. The concept of a game being easy to begin playing but difficult to master dates back to Chess and even Go. As far as modern day video games are concerned there are a lot that actually fall into this category. I believe the phrase was first coined by Nolan Bushnell [wolfsheadonline.com] but I could be wrong.

      You are free to say that in your opinion of "easy to learn, difficult to master" video games, Tetris is the ultimate. But even video games like Donkey Kong or Pac Man have the same simple laws that a novice understands which gradually become more and more restrictive until the true "mastery" title is nearly impossible to attain -- kill screen, anyone?

      If you're designing a new video game, that seems to be one of the fundamental requirements so that you aren't too off-putting to new players. You can play World of Warcraft at your own pace and although the UI and input is infinitely more complex than Tetris, it exhibits this basic rule of thumb for game design -- quite successfully. That's why it enjoys a worldwide audience of 10+ million.

      Tetris is legendary and fun but modern day video games (like the popular flash puzzle games) are building past Tetris while trying to maintain the principles that made it successful. I predict you're going to be upset that I might have just compared Tetris to Bejeweled but lets face it: they're both simple insanely popular video games that have a large swath of difficulties that seem to algorithmically scale in later levels.

      As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

      • by Pojut (1027544)

        Good points, all :-)

        As an avid Tetris player, I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

        My definition would be when one starts to compete in tournaments...hence the "competitive level" and "pro" sandwiching the "hardcore" label.

      • I must inquire when it is that one is given the "competitive level hardcore pro" title in Tetris?

        Usually that happens once you get into the 8000s on Tetris DS or you can get M in Master or Death on TGM2+. Then you get to the tournament (i.e. "competitive level") and find that this ni**a can still steal your colour [youtube.com]. Two places where the hardcore players hang out are harddrop.com and tetrisconcept.net.

      • by mdarksbane (587589) on Friday April 09, 2010 @01:32PM (#31791828)

        There's a problem, though - both Go and Chess are generally multiplayer games. Tetris is in its purest form singular. Any sort of competitive game is much harder to get into for a novice, as it is only fun for them to be playing other novices, and you have the situation you see in general with Chess and Go - the few people who are really good, and the many who rarely play because they do not have the dedication to compete.

        Look at the many addictive "casual" games - almost all of them are single player, and the ones that are multiplayer (such as farmville, or even wow) are multiplayer mostly in the social aspect than in the competitive aspect. There's a reason the majority of WoW players are on PvE. When you are facing a controlled computer opponent, you can apply a constantly ramping difficulty level that starts at a place a novice can still have fun. When you're playing competitively, the moment you have a significant skill imbalance the fun disappears.

    • by mqduck (232646)

      Tetris, to me, is the ultimate video game.

      You're in very good company. Warren Spector, especially when discussing video games as art, calls Tetris to be the greatest game ever. Something to do with it exemplifying how games, like all other art forms, can do things the others can't, which he believes is what game developers should make it their mission to do.

  • Sokoban (Score:5, Interesting)

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

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

    • by amplt1337 (707922)

      I'm seeing a pattern here...

      ..."People like puzzles"?

    • Re: (Score:3, Funny)

      by owlstead (636356)

      "I'm seeing a pattern here..."

      Are you sure? Maybe determining if the pattern is correct is also NP-hard.

  • by NitsujTPU (19263) on Friday April 09, 2010 @12:34PM (#31790934)

    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.

    • by Anonymous Coward on Friday April 09, 2010 @12:40PM (#31791022)

      I have no idea what you just said. Can you use a car analogy?

    • Re: (Score:2, Interesting)

      by NitsujTPU (19263)

      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.

    • Re: (Score:3, Interesting)

      by bondsbw (888959)

      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 w

    • Re: (Score:2, Interesting)

      by yariv (1107831)

      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 n

      • Re: (Score:3, Insightful)

        by tobiah (308208)

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

        The appeal of these puzzles is that they're hard to solve but easy to verify the solution. If the puzzle were easy you'd get bored, and if it was difficult to verify you'd get frustrated. That's why I always look for the "Certified NP-Hard" sticker on the side of my new board game purchases.

  • by martas (1439879) on Friday April 09, 2010 @12:37PM (#31790964)
    sorry to burst your bubble, but there are many poly-time approaches to solving NP-hard/complete problems that are "good enough" for many purposes. and vice versa - many (most? all?) problems that are poly-time, humans solve using heuristics that lead to often sub-optimal solutions. so what exactly is new here?
  • Probably because like any other good problem, they both offer a problem and they help start the solving process.

  • so where is the pattern?

  • NP-hard just means you (most likely) need an exponential search. Maybe you want to take this as evidence that human creativity is needed, but that's a stretch. Humans don't do better than computers on NP-hard problems. In fact, they almost certainly do worse, because if you cannot skip the search part, computers are tremendously faster at that. See how quickly a human solves a sudoku, vs. a computer. Even though it's NP-hard (for arbitrary dimensions).

    Of course the whole thing depends on the base of the exp

  • No. (Score:2, Interesting)

    by Hatta (162192)

    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.

    • by Dunbal (464142) *

      The human mind is created by the brain which is governed by the laws of physics.

      Rubbish. While the underlying biochemical reactions occurring in the brain are completely dependent on physical laws, the actual connections between neurons, expression of certain genes in certain cells, and levels of neurotransmitters and receptors are governed by a myriad of factors. These factors range from past experiences, conditioning and training to diet, to current amount of sunlight, etc. The brai

      • Re: (Score:3, Insightful)

        by Hatta (162192)

        While the underlying biochemical reactions occurring in the brain are completely dependent on physical laws, the actual connections between neurons, expression of certain genes in certain cells, and levels of neurotransmitters and receptors are governed by a myriad of factors. These factors range from past experiences, conditioning and training to diet, to current amount of sunlight, etc.

        All of which are fundamentally governed by the laws of physics. Math.

        Physics cannot explain why I, at this instant, cho

        • All of which are fundamentally governed by the laws of physics. Math.

          I think you're equivocating here. Governed by physics, yes, but not by math. Math is the language of description, not the laws themselves. So the equivocation here is between description and causation. Mathematics describes in a human/machine cipherable language the seemingly immutable physical principles of the universe. This type of sensual observation falls prey to Hume's complete skepticism, that we cannot say something is fundamental just because our experience of it has never been controverted. That'

    • Re: (Score:3, Interesting)

      by MobyDisk (75490)

      We just come with better software for it.

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

    • by amplt1337 (707922)

      The laws of physics are mathematical, so fundamentally the human mind is an algorithm.

      This is where your logic breaks down. The laws of physics are mathematical, but that does not imply that the things they govern are algorithmic. The laws of physics govern the roll of dice, too, but you aren't saying there's a dice algorithm, are you? (if you are, cut me in, let's go make billions in Monaco, sound good?)

      Because of Turing completeness, there's fundamentally nothing that the human mind can do that a computer cannot.

      ...love?

      • by Hatta (162192)

        The laws of physics govern the roll of dice, too, but you aren't saying there's a dice algorithm, are you?

        Of course there is. It's just incredibly complex. We could not possibly measure all the variables with enough precision to predict a dice roll. Doesn't mean there's not an algorithm.

        • Re: (Score:3, Interesting)

          by amplt1337 (707922)

          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

    • The idea the human mind is best understood as a physical object acting on itself, has always rubbed me the wrong way.

      While having a basis in fact, it is not the most USEFUL model of the human mind.

      It is like a book review that focuses on the number, length, and repetition of words in a book.

      Based in fact, yes. But useful? No.

  • Fun == uncertainty (Score:5, Interesting)

    by arielCo (995647) on Friday April 09, 2010 @12:47PM (#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.

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

      That's when you start playing games that slowly solve the boring stuff for you. My own Luminesweeper [pineight.com] is one of them: a line periodically sweeps across the screen and solves squares using the single-point method [neu.edu]. So it almost feels like you're playing co-op, and the goal is to do as much as you can to promote a healthy alternation between the hard stuff (your task) and the easy stuff (the CPU's task).

    • Re: (Score:3, Interesting)

      by d474 (695126)

      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.

  • What? The game can be theoretically played forever on an imperfect generator as long as you don't hit an endless stream of Z and S blocks. It's possible to roughly categorize the blocks and sort them efficiently as they come, perpetually lining up for a full Tetris every time a line comes down. Every piece that shows up has a computationally obvious columnar location under this strategy, but orientation is still obvious but less naively computable; it's pretty boring to play that way though.
    • by tepples (727027)

      The game can be theoretically played forever on an imperfect generator as long as you don't hit an endless stream of Z and S blocks.

      In fact, it's against the rules for the game to give you a long stream of blocks. Tetris games since 2001 dish out pieces 7 at a time [harddrop.com], and the most snakes in a row that you'll ever get is four: xxxxxSZ|ZSxxxxx. This leads to an easily computable strategy for playing Tetris forever [harddrop.com].

  • Look, I'll fire up a few smokes and toss back a cold one and sort out this whole P=NP problem for you.... I'm sure that I can come up with it right away... how hard can it really be? Tongue firmly in cheek!

  • by jefu (53450) on Friday April 09, 2010 @12:55PM (#31791256) Homepage Journal
    There is a fun book on this topic called "Games, Puzzles and Computation" by Hearn and Demaine that is well worth a read if you're interested in puzzles or complexity.
  • by Dr. Spork (142693) on Friday April 09, 2010 @12:58PM (#31791294)
    It seems to me that earning the title of being NP-hard is very easy for games. As someone said before, even sudoku is NP-hard, but intuition-less computers are still much faster at it than humans with all their intuition. So where is the list of the "boring" games that aren't NP-hard? If there aren't any such games, then this story is pretty trivial.
  • P = NP, eh? (Score:3, Funny)

    by clone53421 (1310749) on Friday April 09, 2010 @01:01PM (#31791346) Journal

    I already wrote a solver for this exact game. It just isn’t efficient.

  • I do not know about anyone else, but I never really got how anyone considered these games fun.

  • I think discussing your new iPhone game on slashdot is an NP-Easy way to get a substantial popularity boost.

  • I don't get why people talk about NP hard in games that generally have fixed-sized worlds. The whole point of complexity in computer science is to talk about how an algorithm can scale up with N, but when N is fixed I would argue that the algorithm's complexity doesn't even matter; it is fixed for that game.
    For example, who cares if an AI takes 10x longer every time you add 1 to the width of a tetris world? 99.999% of people play on a 10x20 board. When I hear someone say "blah" is NP hard, I always ask "wha

    • by Bob Hearn (61879)

      The reason that fun games tend to be NP-hard (or harder) is that if a game's "physics" supports interesting constructions requiring complex reasoning to solve, then probably that same physics can be used to build computational gadgets, which is how you show hardness of the generalized version. This quality expresses itself even on small, fixed-size board.

  • Math, math, blah, blah. Post your record people.

    24 turns, but I'm a beginner.
  • nonsense (Score:5, Insightful)

    by pydev (1683904) on Friday April 09, 2010 @01:45PM (#31792086)

    This means that there's no way to write an efficient program to beat the game, unless P=NP.

    All these games are small finite size in practice, so asymptotic complexity results tell you nothing about how difficult it is to solve them. In addition, the idea that "P = efficient program" is utter nonsense; for large problems, even quadratic complexity is a serious problem. A realistic notion these days is that a reasonable asymptotic complexity for "efficient programs" is no worse than n log^k n for small k. Anything larger than that and it won't scale. The converse is also nonsense. Just because a particular problem is NP hard in general doesn't mean that the problem instances you encounter in practice are hard cases. Furthermore, the assumption that you need to find an optimal solution is also wrong. In fact, in any competitive game, all you really care about is beating the other guy.

    P=NP is a neat theoretical issue in computer science, but its practical significance has been completely overstated.

  • hands up... (Score:4, Interesting)

    by drsquare (530038) on Friday April 09, 2010 @04: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: (Score:3, Interesting)

      by phantomfive (622387)
      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.

A bug in the code is worth two in the documentation.

Working...