Forgot your password?
typodupeerror
Math Games Idle

Pac-Man Is NP-Hard 195

Posted by samzenpus
from the not-all-fun-and-games dept.
MrSeb writes "An Italian researcher with a penchant for retro games — or perhaps just looking for an excuse to play games in the name of science! — has used computational complexity theory to decide, once and for all, just how hard video games are. In a truly epic undertaking, Giovanni Viglietta of the University of Pisa has worked out the theoretical difficulty of 13 old games, including Pac-Man, Doom, Lemmings, Prince of Persia, and Boulder Dash. Pac-Man, with its traversal of space, is NP-hard. Doom, on the other hand, is PSPACE-hard."
This discussion has been archived. No new comments can be posted.

Pac-Man Is NP-Hard

Comments Filter:
  • by tepples (727027) <tepples AT gmail DOT com> on Thursday January 26, 2012 @07:38PM (#38834799) Homepage Journal
    I am reminded of an proof from a few years ago [slashdot.org] that Tetris is NP-hard. But this proof is for old versions of Tetris that used a pure randomizer, not the new bag style generator in games since 2001 [harddrop.com]. This randomizer incidentally allows playing forever [harddrop.com].
    • by Anonymous Coward on Thursday January 26, 2012 @07:45PM (#38834851)

      It would be more accurate to say Tetris isn't Tetris anymore.

    • by Formalin (1945560) on Thursday January 26, 2012 @08:04PM (#38834967)

      I think the gameboy one stopped speeding up and some point, letting you play forever, well at least until you ran into a batch of randomness that gave you too many bad pieces.

      The NES one, on the other hand, was actually impossible after a certain level... the blocks fell faster than you could get them to the edges of the screen.

      There was a version of tetris someone made, maybe from here... that always gave you the worst possible piece.
      Googling 'ragetris' tells me it was called 'hatetris [qntm.org]'.

      Not entirely related to things being NP-hard, but yeah.

    • They use a pretty conveniently screwed up variant of Pac-Man for their proof, not the actual Pac-Man, where there's free choice and arbitrarily fast transitions between the different ghost modes, so it's even further from true here than for Tetris.

      • by hal2814 (725639) on Thursday January 26, 2012 @09:49PM (#38835677)
        They didn't actually use Pac-Man in their proof. They modeled up a close approximation which is not Pac-Man at all. For example, FTA:

        "We assume full configurability of the amount of ghosts and ghost houses, speeds, and the durations of Chase, Scatter, and Frightened modes (see [1] for definitions)."

        That's all well and good but there is no configurability with the level designs, amount of ghosts, or ghost houses.
        • by TuringTest (533084) on Friday January 27, 2012 @04:30AM (#38837151) Journal

          "We assume full configurability of the amount of ghosts and ghost houses, speeds, and the durations of Chase, Scatter, and Frightened modes (see [1] for definitions)." That's all well and good but there is no configurability with the level designs, amount of ghosts, or ghost houses.

          There was, while they designed the game.

          The PacMan videogame is one instance of a problem class. Algorithmic complexity is calculated for classes of problems, since for any particular instance you can always design a trivial, constant time algorithm if at least one solution is known...

          • by hal2814 (725639) on Friday January 27, 2012 @09:57AM (#38838749)
            I agree, but that means that PacMan itself is not NP Hard. The class of games defined in the paper (to which PacMan belongs) is NP-Hard. That's a significantly different claim.
          • by cpu6502 (1960974)

            I think Pac-man and Ms. Pac-man are quite easy, and don't comprehend anybody who uses the word "hard" in conjunction with them. Sure when you first start out, you need to develop the skills, but it doesn't take that long.

            The Atari console variants are particularly easy (read: boring). Why are all the ghosts running around randomly, instead of chasing the player? Poor programming.

            The Jr. Pac-Man port is the superior version on that old console.

        • there is no configurability with the level designs

          Where you read "Pac-Man" in this article, add a "Ms." in front. Ms. Pac-Man has four boards, as an extant example of how level design may be configured.

    • by b4dc0d3r (1268512)

      I am embarrassed to say, this is the most interesting comment I have seen on this site in well over X;X3 years. You know the changes in the Tetris engine, and links to a strategy guide for playing Tetris infinitely.

      Screw mod points, I salute you, sir or madam or intermediate.

  • by kyrio (1091003) <slashdot@lurkmo r e .com> on Thursday January 26, 2012 @07:38PM (#38834801) Homepage
    I'm pretty sure we knew this from actually playing the games.
    • by fuzzyfuzzyfungus (1223518) on Thursday January 26, 2012 @07:56PM (#38834905) Journal
      It would actually be somewhat surprising(especially with games where the twitch factor keeps the player from strategizing too deeply) if you could discern the computational complexity of a game just by playing it....

      Naively, I'd imagine that a human player most closely resembles a stochastic hill-climbing agent, providing the input at each tick that seems most likely to improve their situation in the relatively short term. That would make them brutally efficient at some problems, miserably hung up on local maxima or discontinuities in others; but not necessarily provide much correlation between difficulty of play and difficulty of problem.
      • by martin-boundary (547041) on Thursday January 26, 2012 @08:32PM (#38835171)

        Naively, I'd imagine that a human player most closely resembles a stochastic hill-climbing agent,

        That's too naive. Most game players don't just play the game once (start game, yay, play, win a little, die, never play this game again). Instead, they play many times, and use their previous knowledge as leverage to improve their performance.

        That puts the hill climbing analogy into more modern optimization territory, like multiple randomized restarts, adaptive strategies, etc. As such, the odds of winning are high when players are willing to put in the hours.

        • by VortexCortex (1117377) <VortexCortexNO@S ... t-retrograde.com> on Friday January 27, 2012 @01:44AM (#38836671)

          Most game players don't just play the game once (start game, yay, play, win a little, die, never play this game again).

          I'd have to disagree, as both a Game Player and Game Developer. Gone are the days when Sonic or MegaMan sat in your console for weeks while you tried endlessly to beat it. Today's game players are EXACTLY like what you describe. That's why we have to baby them & lead them into playing the game -- They have many other options, a virtually endless supply of games to Try and fail at until one lets them win.

          I sit "average" gamers of all age ranges in front of the games from yesteryears and the majority do exactly what you describe when given a choice to switch between any classic game on the shelf. They play the longest on familiar or easy to play titles.

          PacMan is HARD. Rarely will you find a decent arcade with 5 lives instead of 3, and longer power-up periods (selectable via dip switches or .conf files). However, people don't play games to beat them, now they play to be entertained, and an unforgiving game that eats your quarters or $50 at once can't compete with the free casual games of today.

          I think some balance can be found -- A short introduction to get you interested in the mechanics and/or story, followed by an increasingly engaging experience, but there's a fine line between too steep a learning curve and too boring of a game.

          As for whether or not PacMan is NP Hard, I'd say that since it's 100% fully deterministic it's actually not. It's easy as hell to map out then play perfectly every single time afterwards, especially if you have the source code "running" through your brain and can can predict exactly what the Ghosts will do. Also, the same damn level over and over again is quite boring... That's why when I was required to learn JavaScript I created my own rendition [memebot.com] that was non deterministic (pseudorandomly so) as well as had many differing levels.

          • by EdIII (1114411) on Friday January 27, 2012 @03:21AM (#38836939)

            A pleasure to see you again my liege. I am still most grateful for your correction of my unconsciable grammar and spelling last time.

            I too lament how game players today have been turned into "whiny little pussies". I long for the days past when a kill screen was indicative of godhood.

            There was great value in a game that was actually hard to play, and was progressively impossible to beat. The point of that game was the journey of suffering itself, not the end. Those that actually reached the end, the aforementioned kill screens, were granted immediate entrance into Valhalla and spoken of in legends.

            I think the last game that I played that was actually hard might have been Doom or Doom II. To this day the sound of a Arch-Vile makes me twitch.

            In fact, thinking about, the harder a game is, and the more I have to constantly replay levels to achieve perfection, the more I enjoy it. Games these days seem to be more like interactive stories requiring a modicum of effort and designed with soft rubber corners so you don't trip along the way.

            Personally, I think it all went downhill the moment you had a save game state. The unrelenting suffering of being so close to finishing and seeing that start screen, and to keep coming back, was in my opinion, a rite of manhood in my day. It separated the boys from the men.

            • by KDR_11k (778916)

              I think that's why online multiplayer is so popular now, it's the only way to turn most modern games into a fun challenge.

            • I think the last game that I played that was actually hard might have been Doom or Doom II. To this day the sound of a Arch-Vile makes me twitch. ...

              Personally, I think it all went downhill the moment you had a save game state.

              I think you may be rewriting history a bit, there.

              Although it *is* interesting. Doom did havea s aave state, yet for some reason, I don't know anyone whose playing strategy was to repeatedly save and reload[*].

              Perhaps that's because there wasn't much choice and it was a fantastic gam

              • by delinear (991444)
                The biggest factor for me (and I'd guess a lot of other gamers) is having the spare time for games. The average gamer age is now mid thirties. When we were all kids it was easy to spend countless hours replaying the same games to perfect our speed runs etc. These days, even replaying the last ten minutes due to a stupid mistake seems like a massive chore when you can only manage to grab a spare hour here and there when work/real life isn't getting in the way. That, to me, is the obvious root of why people d
              • like doing levels on nightmare starting with a pistol

                There was one level in particular that I struggled for hours to survive the first 5 to 15s. I think that level was about 3/4 the way through. You start in a large chamber with a double-wide set of doors that open onto a large area that is essentially a wide hallway wrapped around three sides of a large pool concealed with some modest trellis work. You're stuck in the middle of the long side with fireballs coming from every direction, several pink chick

                • From memory, that sounds like E1M3.

                  I remember that being very difficult to get started on nightmare, and the beginning you described brings back some rather vivid memories.

          • by JTsyo (1338447)
            There are still games that are hard to beat. Super Meat Boy and Demon's Souls come to mind. Of course I haven't played either since I don't have the time to commit like I did to Contra and SuperC.
        • by marnues (906739)
          I think you actually add weight to the GP's premise, even if you tore down one of his points. We are optimization engines (at least us rational engineer types). But when we optimize we don't do it like computers. We don't check all possible routes as we consider many of them sub-optimal. But computational theory mandates that even the seemingly sub-optimal paths be explored. Some people do this kind of experimentation some times, but it's too time consuming so that's the exception rather than the rule.
      • by johnnyb (4816)

        Interestingly, there is a conference this summer dealing with humans and their abilities to perform computation. It's titled Engineering and Metaphysics [eandm2012.com], and deals with the relationship between humans, physics, and reality.

    • I was actually quite surprised that a game that is developed through a simple program would be NP-Hard and that a more advanced game with more stuff to do is actually easier.
  • by hairyfish (1653411) on Thursday January 26, 2012 @08:00PM (#38834931)
    Yes I RTFA and wiki'd it but that page makes no sense to me either. Can someone give me the NP Hard/PSpace Hard for dummies version? Or maybe give me an analogy using football fields?
    • by RJFerret (1279530) on Thursday January 26, 2012 @08:11PM (#38835011) Homepage

      I had the same issue, but better wiki luck... NP-hard was confusing as the article kind of defines it by itself. However, there is a link in it to a more sensible version:

      http://en.wikipedia.org/wiki/P_versus_NP_problem [wikipedia.org]

    • Re: (Score:3, Informative)

      It means it isn't computationally solvable in linear time. A computer would only be able to solve very very simple permutations of an NP hard problem in reasonable amount of time. The more complexity added to the problem space makes the time it takes to solve grow to be something most people would not wait around for.

      i.e. Traveling Salesman (look it up, its the classic problem) problem for 4 cities is pretty easy and quickly solved for by a computer. However 100 or 1000 cities takes much much longer f
      • Re: (Score:3, Informative)

        by Anonymous Coward

        An oversimplification though - it really means it's not solvable in deterministic polynomial time. An algorithm with O(n^12328372) would still fall under P, because it's solvable deterministically in Polynomial time.

      • by snowgirl (978879) on Thursday January 26, 2012 @08:47PM (#38835289) Journal

        It means it isn't computationally solvable in linear time.

        No, it can't be solved in POLYNOMIAL time. For instance, comparative sorting cannot be done in linear, yet is not NP-hard.

        Something that is O(n^12387349892319348917359872394872328349872398723985729375982734598275) is in fact insanely hard, yet still not NP-hard.

        • Mod up (or mod GP down). Confusing linear and polynomial time is a horrible mistake, and even then the GP assumes P != NP without saying so.
        • Right sorry. It has been a long time since I actually studied it.
      • by sustik (90111) on Thursday January 26, 2012 @09:21PM (#38835495)

        Assuming NP != P your first sentence is correct. And maybe this is what laymen should know about it. However for completeness...

        In general a problem is presented as a string of n bits and the algorithm (Turing Machine) has to decide whether it is acceptable or not (good or bad etc.) For example, take the graph coloring problem. This involves a graph on m vertices and you have to color it using k colors such that neighboring vertices have different colors. The input to the algorithm is a description of the graph and k as a bit-string. And the bit-string is acceptable if there is a proper coloring.

        If the Turing machine can decide whether the bit-string with n bits is acceptable in less than p(n) steps where n is a polynomial, then the problem is in P.

        NP does *not* stand for Not P.

        NP means that there is a witness to the acceptability of a bit-string that can be verified in p(n) steps. For example, the witness for the graph coloring is an actual assignment of the colors to the vertices. It is quite straightforward to verify that the coloring is proper (no neighboring vertices have the same color, it takes less than n^2 color comparisons. NP stands for Nondeterministic Polynomial, I am
        not a fan of the name.

        NP-Hard means that the problem is such that any NP problem can be reduced to it (with a polynomial correspondance). Therefore, if you had a polynomial algorithm for it than you had one for *all* NP problems. This would imply P=NP and is doubtful to be true. In other words a proof of NP-hardness means: Yes, it is harder than P, at least most scientists think so.

        I have no idea yet how the Pac-Man problem is represented as a bit-string. I will find out tomorrow on a lecture...

        It is worth mentioning the class co-NP. This is a the class of problems for which there is a witness that the input is *not* acceptable. Think what witness could easily verify that a graph is not k colorable... For example existence of a full k+1 subgraph would suffice but other constructions also prohibit k coloring which have no full k subgraph in them. I do not recall from the top of my head whether k coloring is co-NP or not. But I think it is not, here is why:

        There is a conjecture that may have more chance than P = NP. And that is: P = NP intersect co-NP. That is if both acceptability and non-acceptibility can be polynomially verified then there would be a guaranteed polynomial algorithm. So far this appears to be the case.
        The last famous problem that is NP and co-NP at the same time and was found to be in P was prime testing.

        And of course there are many, many other complexity classes...

    • by Hentes (2461350)

      It's all explained in the paper in the second link.

    • Re: (Score:3, Insightful)

      by lgw (121541)

      OK, without the wiki dive, here's the short version:

      • * P is the set of problems that can be solved in polynomial (or better) time.
        * NP-Complete is the set of problems that (probably) can't be solved in polynomial time, but the solution can be verified in polynomial time.
        * NP-Hard is the set of all problems that can't be solved in polynomial time.

        Only two of those are actiually distinct. We think P and NP-complete are different, which would mean NP-Complete and NP-Hard are the same (IIRC).

      • by Anonymous Coward on Thursday January 26, 2012 @08:53PM (#38835313)
        More or less correct, but you are slightly confused on the definition of NP-Hard.
        • NP is the set of problems that can be verified in polynomial time.
        • NP-Hard is the set of problems which are provably at least as hard as any problem in NP (in the sense that a solution to an NP-Hard problem can be used to solve any problem in NP with only polynomial additional effort).
        • NP-Complete is the intersection of NP-Hard and NP.

          It is believed that P != NP, and if any problem that is NP-Hard (usually one just says NP-Complete) turns out to be solvable in polynomial time, then P = NP.

        • Mod up. This is the only correct explanation so far.
      • by dkf (304284)

        We think P and NP-complete are different, which would mean NP-Complete and NP-Hard are the same (IIRC).

        There are many problems that are wholly outside polynomial complexity (used to work with some, years ago, and they were brutes even with a Top-500 supercomputer of the day). That means that NP-Hard must not be just NP-Complete; there's got to be higher levels in there.

    • Re: (Score:2, Informative)

      by Faulkner39 (955290)
      To solve a problem that has 'n' parts in it:

      PSpace hard means the problem is relatively simple, maybe check n things n times, which is only n*n things. For example, "For n cities, find the sum of all the distances between all the cities".

      NP hard usually means you have to start at one part, then make a new decision each time you want to move on to the next part. The classic example is: "for n cities, start at a city and find the shortest possible distance to visit each city once". Since you have to ma
      • Correction: I confused PSpace with P. The above definition is for P and NOT PSpace. Haven't spent much time thinking about complexities ABOVE NP hard. PSpace actually considers the "memory" you need to solve the problem. This is relevant when you talk about Turing machines, where you have to use "tape" that you "write on" while solving the problem. The thing that's been proved is that you only need a polynomial amount of memory (relative to 'n') to solve problems that need NP Hard time.
    • by godrik (1287354)

      I read so much wrong answer replying to you post I attempt a new explanation.

      A problem is in P if there is a polynomial time algorithm to solve it. It means, that there is a algo which will always find the correct answer AND the algorithm an instance of the problem in at most a*n^b operations, where a and b are constants and n is the size of the smallest file that can contain an instance of the problem. Example of problems in P includes: deciding whether a number is divisible by2, whether a number is prime,

    • by Surt (22457)

      So, most computer scientists assume P != NP. But there's no proof (yet).

      NP-hard is a class of problems, the solution of which is guaranteed not more efficient than NP. That is, there is a demonstrated way to convert an NP-complete problem (let's call that problem NPC) to the hard problem (NPH), and the conversion can be done in polynomial time.

      How does that work? Well, if you were able to solve the NPH problem more efficiently (in polynomial time or better), you'd first use the conversion (costing you o

      1. P -- problems that can be solved in time that grows according to some polynomial of the size of problem (e.g. sorting -- can be solved in n^2 time by bubble sort).
      2. NP -- problems that can be verified in polynomial time; we think that some of these problems cannot be solved in polynomial time. For example, graph three colorability is in NP and is not known to be in P; this means that if I show you a 3-colored graph, you can check that it is indeed 3-colored in polynomial time, but if I give you a graph and
    • Ron Fagin (a heavyweight in this topic) once told me about this in layman's terms. Can't remember precisely, but this is more or less what he said:

      I assume you know Sudoku. Solving a Sudoku game from the clues has a certain difficulty (complexity). Compare it with just verifying that a Sudoku with all its squares filled is a valid solution. You can see that verifying a solution is much faster than finding one! In general, we can accept that verifying is faster than solving... but even though it's intuitive,

  • Assuming that this method of measuring complexity is actually useful, is there an ideal level of theoretical complexity in a computer game?

    (This is not necessarily the same as the complexity of play - Doom is, after all, very easy to play but PSPACE-hard problems are extremely difficult problems to solve.)

    Any retro-gamers here want to determine the theoretical complexity of Wizardry, Atic Atac, Knightlore, Citadel or Cholo?

    Is there any correlation between the complexity and how long the game stuck in people

    • Speaking as a game designer/programmer, I like it when games are too hard to solve outright, but not too hard to employ strategies based on your current state. The more possible strategies people can employ in different situations gives people the fun-factor.
  • Holy shit I don't want to read an article, led alone a scientific, peer reviewed article. Isn't there a pretty picture of a graph somewhere?
  • by Anonymous Coward on Thursday January 26, 2012 @10:18PM (#38835807)

    ....that for a bunch of nerds nobody seems to know what NP really stands for

  • by JoshuaZ (1134087) on Thursday January 26, 2012 @10:24PM (#38835823) Homepage

    This is a good example of how you define the problems mattering. For example he declares Starcraft to be at least NP-hard. But if one is allowed to use trigger events and some other aspects of the scenario editor one can actually fully model a Turing machine in Starcraft. You do this in a straightforward way by giving trigger based instructions to a unit (say a probe) and have it move along a line where having some other specified unit in an adjacent spot represents a 1, or one has a 0 if the unit isn't there. This is a much stronger result than the result he has. But it seems that his version of Starcraft as defined doesn't let you use event triggers (or at least he doesn't mention them). So he only gets the weaker result of Starcraft being NP hard.

    In the 1970s and 1980s, showing something was NP-hard used to be a big deal and there are a lot of papers from that time period. As the techniques improved one occasionally got some fun with someone showing that some new game was NP hard or NP complete (Tetris was done a few years ago as was Minesweeper). But these are really not considered to have any real insight. This paper is a bit more impressive because of the sheer number of games, and the systematic way he approaches the games especially his Metatheorem 1 and Metatheorem 2. Those two results are not obvious. Overall this is quite clever and makes for a fun read.

    • by ildon (413912)

      It's pretty obvious he's only talking about unmodified multiplayer Starcraft. Once you get into mods (custom maps), it's hard to really still call them "Starcraft" (the game) despite them running within "Starcraft" (the piece of software).

  • by PJ6 (1151747) on Thursday January 26, 2012 @10:26PM (#38835841)
    For Load Runner -

    On the rst traversal, the avatar can safely land on top of the enemy and dig a hole on the left. The AI will make the enemy fall in the hole, so the avatar may follow it, land on its top again, and proceed through a ladder, while the enemy remains forever trapped in the hole below. The avatar cannot attempt to traverse the gadget a second time without getting stuck in the hole where the enemy previously was.

    That's just not true. Grain of skepticism += 1.

  • Doom is being lumped into the same game era as Pac-Man? Why am I suddenly getting a desire to have a lawn?

    • Doom is being lumped into the same game era as Pac-Man? Why am I suddenly getting a desire to have a lawn?

      Bad as that is, I found the lack of ANY reference to Calvinball far more distressing.

    • by EdIII (1114411)

      Let's be fair.

      If you played Doom without Godmode on, it was fairly hard. You had to spend some time doing it, and learn tactics. Not to mention a fair amount of luck.

      I put Doom and Pac-Man into the class of games that are enjoyable because they are hard, and progressively harder. The first few levels of Pac-Man are easy enough, but much like a good strong Habanero sauce, the beginning is fine but you start to figure out that you may have made a mistake about it being easy.

  • by treeves (963993)

    but only for N=1, obviously.

  • All fun and frolics, as long as you realize that the computational complexity of the "solution" has little to do with how difficult the game is for humans to play...

    I'm assuming that by "solution" here we mean an algorithm that will either win (or prove winning impossible) for any case, in a finite number of steps; as opposed to a heuristic or stochastic technique that could win more-often-than-not, but never prove un-winnability.

    Last time I looked, the human brain used some sort of complicated neural net

You can do this in a number of ways. IBM chose to do all of them. Why do you find that funny? -- D. Taylor, Computer Science 350

Working...