Slashdot Mirror

← Back to Stories (view on slashdot.org)

Pac-Man Is NP-Hard

Posted by samzenpus on 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."

58 of 195 comments (clear)

  1. Tetris isn't NP-hard anymore by tepples · · Score: 5, Interesting

    I am reminded of an proof from a few years ago 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. This randomizer incidentally allows playing forever.

    1. Re:Tetris isn't NP-hard anymore by Anonymous Coward · · Score: 5, Insightful

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

    2. Re:Tetris isn't NP-hard anymore by Formalin · · Score: 5, Interesting

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

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

    3. Re:Tetris isn't NP-hard anymore by b4dc0d3r · · Score: 2

      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.

    4. Re:Tetris isn't NP-hard anymore by VortexCortex · · Score: 2

      It was probably Bastet (Bastard Tetris).

    5. Re:Tetris isn't NP-hard anymore by EdIII · · Score: 4, Funny

      most versions of tetris use pure randomizers, faggot.

      LMAO.

      How can you get so emotionally involved in an algorithm used in a 20+ year old game? It's a game man. You think he is wrong about the algorithm so it is cause to call him a faggot?

      You AC's crack me up sometimes. Faggot!

      If the waiter brings you too much ice in your drink do you yell at him and call him a faggot too? I can hear Beavis and Butthead in the background telling you, "That was uncalled for dude".

  2. nothing of value was gained by kyrio · · Score: 3, Funny

    I'm pretty sure we knew this from actually playing the games.

    1. Re:nothing of value was gained by fuzzyfuzzyfungus · · Score: 5, Insightful

      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.

    2. Re:nothing of value was gained by martin-boundary · · Score: 4, Insightful

      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.

    3. Re:nothing of value was gained by johnnyb · · Score: 2

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

      --
      Engineering and the Ultimate
    4. Re:nothing of value was gained by VortexCortex · · Score: 5, Interesting

      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 that was non deterministic (pseudorandomly so) as well as had many differing levels.

    5. Re:nothing of value was gained by EdIII · · Score: 3, Insightful

      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.

    6. Re:nothing of value was gained by serviscope_minor · · Score: 2

      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 game so we played and replayed and re-re-re-replayed it. After a while, a straightforward runthrough on UV wasn't challenging.

      Of course once it lost that challenge we would adopt various ad-hoc challenges, like doing levels on nightmare starting with a pistol, or completeing every UV level starting with just a pistol, or doing things fast, etc at which point reloading isn't part of the game anymore.

      [*]Though it was a useful strategy to figure out how to do a challenging level, before going back and actually doing it properly.

      Perhaps it was because it somehow felt like cheating to do anything other than save at the level transition. After all, why not jyst hit iddqd idkfa and randomly blast away at stuff for an hour?

      I don't know the answer. Perhaps it's quicksave and quickload that are the problem. It was mildly annoying to save levels in Doom, so you wouldn't do it unless you were really sure. With more modern games, I find myself hammering on quicksave even though it does in some way spoil the experience.

      That said, when a game is good enough even that doesn't matter...

      I remember playing Half Life. There was a classic moment which I expect will be remembered by everyone who played it with sound on. You crawl into a duct, then you hear a marine say "Sarge, I hear something..." (the first time the phrase is used in the game), then they start shooting at the duct from underneath and with each bullet hole a shaft of light appears until the duct finally collapses into a room full of marines.

      It was an astonishingly memorable sequence. I was blown away. Even by the already ground breaking feel of Half Life, it was outstanding.

      I remember I had quicksaved before crawling into the duct and I actually survived first time. What I did after was to save my state (for later continuation) and then replay the same bit about 10 times simply because it was so cool.

      I remember doing the same thing at several really good points in the game (though I have a vague memory that HL actually autosaved before something cool happened just to make it all the more cool).

      --
      SJW n. One who posts facts.
    7. Re:nothing of value was gained by delinear · · Score: 2

      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 don't want games that need weeks of practice to beat; why they will make more frequent use of save games; why they get frustrated with games that don't help you get back into the experience after a prolonged period away (through lack of objectives or no timeline to remind you what you were doing); why they will move onto another game if they're not enjoying the experience or don't feel they're making progress in the game.

  3. Re:Yeah... by ZeroSumHappiness · · Score: 4, Funny

    Wouldn't that more be NPH-ard?

  4. What does the hell does NP Hard mean? by hairyfish · · Score: 5, Insightful

    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?

    1. Re:What does the hell does NP Hard mean? by RJFerret · · Score: 3, Informative

      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

    2. Re:What does the hell does NP Hard mean? by cslax · · Score: 5, Informative

      http://web.mit.edu/newsoffice/2009/explainer-pnp.html

    3. Re:What does the hell does NP Hard mean? by JustSomeProgrammer · · 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 for the best algorithms we have to solve it. (think minutes -> days -> decades for orders of magnitude larger problem space)

      There's a bit more math to a detailed explanation and this isn't entirely accurate in measurements, but this is the gist of it.

    4. Re:What does the hell does NP Hard mean? by jd · · Score: 3, Informative

      http://en.wikipedia.org/wiki/Computational_complexity_theory

      http://en.wikipedia.org/wiki/P_versus_NP_problem
      http://en.wikipedia.org/wiki/NP-hard
      http://en.wikipedia.org/wiki/PSPACE
      http://en.wikipedia.org/wiki/PSPACE-complete

      --
      It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
    5. Re:What does the hell does NP Hard mean? by Anonymous Coward · · Score: 3, Informative

      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.

    6. Re:What does the hell does NP Hard mean? by lgw · · Score: 2, Insightful

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

      --
      Socialism: a lie told by totalitarians and believed by fools.
    7. Re:What does the hell does NP Hard mean? by snowgirl · · Score: 4, Informative

      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.

      --
      WARNING! This girl exceeds the MAXIMUM SAFE standards established by the FDA for BRATTINESS
    8. Re:What does the hell does NP Hard mean? by Anonymous Coward · · Score: 5, Informative
      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.

    9. Re:What does the hell does NP Hard mean? by Faulkner39 · · Score: 2, Informative

      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 make a new decision every time, you can solve this problem using permutations: you have n choices for the first city, then n-1 choices for the next city, then n-2 choices for the next city, and so on. To check ALL of the possible routes you can take and select the shortest, you need to check (n)*(n-1)*(n-2)* ... * (2) * (1) things. That's a factorial, and is denoted n!.

      So for 12 cities:
      12*12 = 144
      12! = 479,001,600

      For 20 cities:
      20*20 = 400
      20! = 2.432902008×10^18

      The "search space" for problems that are NP Hard explodes to quickly to solve any reasonably sized problem. So basically, computers can solve problems that are PSpace hard, but they can't really solve any NP hard problems that are worth solving. E.g., to solve the NP Hard "traveling salesperson" problem I described above for all the cities in Italy, there's something like 12000 cities, which is (almost) impossible to solve with a computer. For fun:

      12000*12000 = 144,000,000
      12000! = 1.201858406×10^43741 (and that's just nuts)

      The above is not the only way a problem can be NP Hard, but all these kinds of problems have "similar" classes of "time complexity". If you model this "time complexity" (that is, count the number of things you have to check) as a function, PSpace hard problems are polynomials at worst. NP Hard are worse than polynomials. The notation used here is called "Big Oh", and the above two problems are O(n^2) and O(n!), respectively.

    10. Re:What does the hell does NP Hard mean? by Anonymous Coward · · Score: 5, Informative

      Roughly speaking, NP-hard (NP = non-polynomial) means that it scales non-polynomially fast ... e.g. if an algorithm is O(n^n) then it is NP-hard but if it is O(n^3) than it is only P-hard. By this definition, even O(n^lg(n)) is NP-hard and O(N^100) is "only" P-hard.

      No, no, no, no. NP does not mean "non-polynomial". In fact, all "P" problems are also "NP". NP means "nondeterministic polynomial", i.e, polynomial in a non-deterministic machine (think a computer with an infinite number of CPUs). It is unlikely that they are "P" ("deterministic polynomial"), but it has not been proven either way. Also, a problem being NP-hard doesn't imply that it is NP. It actually may be harder than NP: in general, to say that a problem is X-hard means that there is no problem of class X that is "harder" than it.

      For the precise definition of "harder", the wikipedia article http://en.wikipedia.org/wiki/P_versus_NP_problem is pretty good.

      (Hmm. it seems I can't log in from the comment box...)

    11. Re:What does the hell does NP Hard mean? by KhabaLox · · Score: 2

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

      Ow.

      --
      Ceci n'est pas un sig.
    12. Re:What does the hell does NP Hard mean? by dkf · · Score: 2

      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.

      --
      "Little does he know, but there is no 'I' in 'Idiot'!"
    13. Re:What does the hell does NP Hard mean? by FrootLoops · · Score: 2

      Also not quite. NP-hard problems can be as difficult as one likes. The key is that, given an oracle for an NP-hard problem, you can solve any NP problem within a polynomial amount of time (where calls to the oracle take unit time).

      Another point to be mindful of is that there are runtimes between polynomial and exponential.

    14. Re:What does the hell does NP Hard mean? by Faulkner39 · · Score: 2

      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.

    15. Re:What does the hell does NP Hard mean? by sustik · · Score: 3, Informative

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

    16. Re:What does the hell does NP Hard mean? by lgw · · Score: 2

      But could you verify the solutions in polynomial time?

      --
      Socialism: a lie told by totalitarians and believed by fools.
    17. Re:What does the hell does NP Hard mean? by AmbushBug · · Score: 5, Interesting

      Heh, heh, yeah. Here, try wikipedia's "simple" version: http://simple.wikipedia.org/wiki/P_versus_NP.

    18. Re:What does the hell does NP Hard mean? by Morty · · Score: 4, Informative

      Mod parent down, please. The definition of NP above is circular -- if NP actually stood for non-polynomial, then P!=NP by definition. That would be begging the question.

      Rather, NP means "nondeterministic polynomial time." It is the class of problems whose solutions can be verified in polynomial time. NP-hard are the "hardest" problems in this class. All algorithms known to solve problems in this class are super-polynomial. The question of "P==NP?" really amounts to "is there an undiscovered polynomial solution to every problem that we currently think is NP-hard?" or even more simply, "if a problem's solution can be verified in polynomial time, can the solution be discovered in polynomial time?"

    19. Re:What does the hell does NP Hard mean? by ProfessorPillage · · Score: 2

      Right, except that NP-hard problems don't have to be in the NP class, they can be harder. They are the problems, not necessarily in NP, that are at least as hard as the hardest problems in NP. You're thinking of NP-complete or equivalent.

    20. Re:What does the hell does NP Hard mean? by elsurexiste · · Score: 2

      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, no one has proven it :) .

      He left out what he meant about complexity, though...

      --
      I rarely respond to comments. Also, don't ask for clarifications: a brain and Google are faster, believe me!
    21. Re:What does the hell does NP Hard mean? by Jason1729 · · Score: 2

      Totally wrong. First, as the previous response said NP-hard is a separate set from NP. The intersection of the two sets is called NP-complete. NP-hard are the "hardest" problems in this class is axiomatically wrong because NP-hard is not a subset of NP.

      Second, by definition of NP-hard, given a polynomial-time solution to any NP-hard problem, you can solve *every* NP problem in polynomial time, so what you meant to say is The question of "P==NP?" really amounts to "is there a polynomial-time solution to any problem that has been rigorously proven to be NP-hard?

    22. Re:What does the hell does NP Hard mean? by YoopDaDum · · Score: 2

      You can't have an "infinite number" of anything. Infinity doesn't work that way. It simply means arbitrarily large, as in "given any finite value N, I have more than N CPU's in my computer". There's no concept of an infinite number.

      There is definitely a concept of infinite, and actually there are several different kinds of infinite. With some infinite bigger than others (size of set of natural numbers vs. real for example), which usually give a "wow" moment the first time you encounter this concept.

      There's plenty of funny things with infinite sets. For example, what about the size of the set of positive integers N, and the size of the set of pairs of integers NxN? In a way, for each integer you can have a subset of NxN as large as N: think all (0, n), (1, n), etc. So surely NxN is much bigger than N? Nope, they're actually the same size because you can find a one to one mapping between N and NxN. Think about a growing linear spiral over a 2D grid for example.

      For more on this, you can look-up "Aleph number" on wikipedia, or look-up various articles there on infinite and infinity.

    23. Re:What does the hell does NP Hard mean? by ildon · · Score: 3, Interesting

      Wow, an actual use for the simple version of wikipedia. Who knew?

  5. Re:Pac-Man Was 'Solved' by UnknownSoldier · · Score: 5, Informative

    Yup, posted on /. a while back

    http://games.slashdot.org/story/10/12/03/2237200/pac-mans-ghost-behavior-algorithms

    --->

    http://gameinternals.com/post/2072558330/understanding-pac-man-ghost-behavior

    --->

    http://home.comcast.net/~jpittman2/pacman/pacmandossier.html

    I don't know what it is but reading about the internals of how games worked (algorithms, data structures, tricks, etc.) is neat.

  6. Re:What is the ideal level of complexity? by GoodNewsJimDotCom · · Score: 2

    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.

    --
    God spoke to me
  7. Re:Pacman is NOTHING!!! by godrik · · Score: 3, Funny

    NP-hard Pacman's got nothing on Undecidable Ms. Pacman.

    There is a known theorem that says: "As soon as you throw women in, nothing is decidable anymore!"

  8. Re:and Pac-Man never was by hal2814 · · Score: 5, Interesting

    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.

  9. What I got from the comments is.. by Anonymous Coward · · Score: 4, Insightful

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

  10. How you define the problems matter by JoshuaZ · · Score: 4, Interesting

    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.

    1. Re:How you define the problems matter by ildon · · Score: 2

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

  11. he got at least one detail wrong by PJ6 · · Score: 2
    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.

  12. Re:Yeah... by hairyfeet · · Score: 5, Interesting

    Hey Pac Man is only 13 years old according to TFA! That's great that means i'm only in my 30s again!...oh wait a tick this is Slashdot where editors never edit... :-(

    You wanna know what's hard? finding out your twitch skills have gone further south than a 43 year old's D cups whose nursed 3 kids. I used to be death incarnate on games like DOOM, Mechwarrior 3 & 4, SoF 1&2, bodies would be piled up like cordwood. Then over the Xmas holiday my boys were like "Hey you've got your new netbook right? Why don't we fire up some TF2 and play together!" and boy that was a rude awakening let me tell you. the heavy, the soldier, it didn't matter what i played i got the living shit slapped out of me. I got so irritated i decided to whip out my CC and buy 3 copies of HL:DM to show these kiddies a thing or two and...ooow, I ended up with so many rockets up my ass my little Freeman is probably walking funny to this very day. Didn't help the oldest was announcing a play by play for the house while my GF laughed her ass off "Oh he's dead, and he's dead again, oh look he didn't even see the death coming that time, will he make it around the corner? nope he's dead" while the youngest made smartass remarks about how he'd "get me a walker with a controller built into the handles for my birthday"

    So enjoy it while you can young ones, all of you that kick royal ass on MW or CoD just as we ruled the arcades will blink twice and the next thing you know your kids will be pimp smacking you on every game while making geriatric jokes. man it sucks getting old :-(

    --
    ACs don't waste your time replying, your posts are never seen by me.
  13. Re:This is why religion is still popular by TapeCutter · · Score: 2

    fucking magnets [how do they work]"

    "I'm not going to be able to give you an answer as to why magnets attract each other, except to say that they do." - Feynman.

    --
    And did you exchange a walk on part in the war for a lead role in a cage? - Pink Floyd.
  14. Re:and Pac-Man never was by TuringTest · · Score: 4, Insightful

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

    --
    Singularity: a belief in the "God" idea with the "demiurge" relation inverted.
  15. Re:Pac-Man Was 'Solved' by slim · · Score: 2

    Indeed, PacMan was solved, but that doesn't mean it can't be NP-Hard.

    People solve Sudokus every day; a computer can do it in a flash - yet Sudoku is NP-Complete. In a 9x9 grid, the scale of the problem remains small enough that you can brute-force it. Make a bigger Sudoku -- or a bigger pacman maze -- and it would become significantly more difficult to solve.

  16. Key words: prior to 2001 by tepples · · Score: 3, Informative
    Most Tetris products prior to 2001, such as Super Tetris 3 for Super Famicom, use the old randomizer, possibly with some slight modification to ensure no immediate repeats.
    • Tetris for Game Boy has a 2/32 chance of the same piece and a 5/32 chance of each other piece.
    • Tetris for NES will reroll once if the piece matches the last piece.
    • Tetris the Grand Master will reroll three or five times if matches one of the last four pieces.
    • The New Tetris for Nintendo 64 deals from a 63-card deck with nine of each shape.
    • New games, such as Tetris Worlds, Tetris DS, and Tetris Party, all use the new randomizer that shuffles sets of all 7 shapes. Start a new game of Tetris DS and notice how the falling piece and the next 6 pieces are all different.
    1. Re:Key words: prior to 2001 by Stuarticus · · Score: 2

      As far as I'm aware super tetris 3 is truly random, the best kind of random! I am a big fan of TGM3, despite it's slightly cheating re-roll randomiser, but for some reason it there's a bug in Mame that causes me grief when I try to play it in 2 player mode that causes the blocks to fall straight down for one of the players.

      --
      If you think someone isn't free to have a different definition of "freedom" you may be a tyrant.
  17. I'm ridin' spinners, they don't stop by tepples · · Score: 4, Informative

    tetris DS does get to the point where the piece lands nearly as soon as it appears

    This behavior is called 20G, and it's also seen in "Death" mode of Tetris the Grand Master 2 and "Shirase" mode of Tetris the Grand Master 3.

    however you can keep it from fixing to the stack by rotating it and wiggling it constantly.

    This infinite spin behavior has become the standard since 2001, despite reviewers' assertions that "it actually breaks Tetris".

  18. cognitive clip change by epine · · Score: 2

    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 chicken drumsticks completely indifferent to pistol fire prowling nearby, and hordes of regulars to baste you with hot lead from all directions if you miss half a pivot. When you died, you were about -200 in health by the time your knees hit the ground. Even if you scored the instant kill out of the gate for the weapon drop, chances were slim you'd live to pick it up, much less lock and load.

    The key for me was obtaining a mental state of unsentimental aggression bordering on contempt. If you tarried to dwell on your prowess for so much as a tenth of a second, the game earned its name. After hours and hours of seemingly little progress at all, I reached the point where I could survive the first 10s a little more than half the time.

    Essentially you had to think of yourself as bringing a handgun to a knife fight: a couple of quick kills at close quarters was the only possible cover, as well as a significant boon: your adversaries were insects with guns. IFF was a million years down the road in their evolutionary future.

    Things happened too fast to consciously play the angles. I think the cognitive adaptation was learning to hash every perceptible threat into precise buckets of 1/4 second duration and treating everything past the fifth bucket (1.25 seconds) as the distant future. Some other part of your brain was running the instruction prefetch decoder on threats 1 to 3 seconds into the future.

    One had to transition from melee tactics to sniper tactics seamlessly after scoring the critical kills. How many times The Bride would be standing knee deep in corpses with heaving chest, then get pinked by a paper boy with a pen knife who ducked out from behind a column--game over. The initial mayhem was such an intense cognitive over-commit, the mind would pause to inhale after the flurry abated and some lone chump would take you down.

    It was almost like the brain had to eject an empty clip in order to reload the next cognitive frame. Dying during the cognitive clip-change was the most F**** frustrating things of all time.

    When I got past it, I never considered Doom hard again.

  19. Re:and Pac-Man never was by hal2814 · · Score: 3, Insightful

    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.

  20. Re:Yeah... by jekewa · · Score: 2

    Hey Pac Man is only 13 years old according to TFA! That's great that means i'm only in my 30s again!...oh wait a tick this is Slashdot where editors never edit... :-(

    Or more likely that Slashdotters don't read TFA. The 13 is a reference to the number of games researched, not their age. Pac-Man is noted as a game from 1980. Neither the introduction article (first link) or the research paper itself (led to by second link) suggest Pac-Man is only 13 years old.

    What does this really mean? You're old again.

    --
    End the FUD
  21. Re:Yeah... by Creepy · · Score: 2

    People that play these games every day can school people that don't every time because they have every nuance down. I played a game of HL2 where I was dying constantly and never saw it coming. Later I watched the guy that had been sniping me and he was hitting targets that I couldn't even see because they were so faint and far away and getting head shots every time. It was insane (I learned later that he won several half life tourneys and we didn't stand a chance - he was mid-30s at the time, so age is only half the battle - practice like crazy is the other half).

    I also remember a game of Battlefield 2 where I was killed within seconds wherever I spawned on the map by either a plane of a helicopter, and I never saw either (I heard them both, but they were very far away). I switched sides and watched the helicopter and they had 3 snipers sitting in the door picking off everyone at the spawn point and a guy resupplying them from behind. I couldn't see the plane, but I'm guessing it was just bombing the spawn from high up (by that point in the game there was only one uncaptured spawn, so it was pretty easy to target).

    Note that the HL2 game was coordinated teams of people I knew in the office and the second game was random people, and one side was far more coordinated than the other (not to mention very good). The DOOM and Mechwarrior days didn't require a headset and extremely coordinated teams of players.

    I wonder if Sinistar is NP-hard... I remember that game being insanely hard... or how about Defender with the hard dips turned on? Ever see that? Defender was crazy hard to begin with and they had dip switches that made it even harder.