Pac-Man Is NP-Hard

Tetris isn't NP-hard anymore by tepples · 2012-01-26 11:38 · 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.

Re:Tetris isn't NP-hard anymore by Anonymous Coward · 2012-01-26 11:45 · Score: 5, Insightful

It would be more accurate to say Tetris isn't Tetris anymore.
Re:Tetris isn't NP-hard anymore by Formalin · 2012-01-26 12:04 · 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.
Re:Tetris isn't NP-hard anymore by EdIII · 2012-01-26 18:53 · 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".

nothing of value was gained by kyrio · 2012-01-26 11:38 · Score: 3, Funny

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

Re:nothing of value was gained by fuzzyfuzzyfungus · 2012-01-26 11:56 · 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.
Re:nothing of value was gained by martin-boundary · 2012-01-26 12:32 · 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.
Re:nothing of value was gained by VortexCortex · 2012-01-26 17:44 · 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.
Re:nothing of value was gained by EdIII · 2012-01-26 19:21 · 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.

Re:Yeah... by ZeroSumHappiness · 2012-01-26 11:45 · Score: 4, Funny

Wouldn't that more be NPH-ard?

What does the hell does NP Hard mean? by hairyfish · 2012-01-26 12:00 · 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?

Re:What does the hell does NP Hard mean? by RJFerret · 2012-01-26 12:11 · 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
Re:What does the hell does NP Hard mean? by cslax · 2012-01-26 12:13 · Score: 5, Informative

http://web.mit.edu/newsoffice/2009/explainer-pnp.html
Re:What does the hell does NP Hard mean? by JustSomeProgrammer · 2012-01-26 12:13 · 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.
Re:What does the hell does NP Hard mean? by jd · 2012-01-26 12:14 · 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)
Re:What does the hell does NP Hard mean? by Anonymous Coward · 2012-01-26 12:20 · 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.
Re:What does the hell does NP Hard mean? by snowgirl · 2012-01-26 12:47 · 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
Re:What does the hell does NP Hard mean? by Anonymous Coward · 2012-01-26 12:53 · 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.
Re:What does the hell does NP Hard mean? by Anonymous Coward · 2012-01-26 13:02 · 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...)
Re:What does the hell does NP Hard mean? by sustik · 2012-01-26 13:21 · 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...
Re:What does the hell does NP Hard mean? by AmbushBug · 2012-01-26 13:27 · Score: 5, Interesting

Heh, heh, yeah. Here, try wikipedia's "simple" version: http://simple.wikipedia.org/wiki/P_versus_NP.
Re:What does the hell does NP Hard mean? by Morty · 2012-01-26 13:45 · 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?"
Re:What does the hell does NP Hard mean? by ildon · 2012-01-27 01:23 · Score: 3, Interesting

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

Re:Pac-Man Was 'Solved' by UnknownSoldier · 2012-01-26 12:03 · 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.

Re:Pacman is NOTHING!!! by godrik · 2012-01-26 13:41 · 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!"

Re:and Pac-Man never was by hal2814 · 2012-01-26 13:49 · 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.

What I got from the comments is.. by Anonymous Coward · 2012-01-26 14:18 · Score: 4, Insightful

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

How you define the problems matter by JoshuaZ · 2012-01-26 14:24 · 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.

Re:Yeah... by hairyfeet · 2012-01-26 19:11 · 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.

Re:and Pac-Man never was by TuringTest · 2012-01-26 20:30 · 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.

Key words: prior to 2001 by tepples · 2012-01-27 00:59 · 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.

I'm ridin' spinners, they don't stop by tepples · 2012-01-27 01:06 · 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".

Re:and Pac-Man never was by hal2814 · 2012-01-27 01:57 · 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.

33 of 195 comments (clear)