Slashdot Mirror
Pac-Man Is NP-Hard
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."
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.
Wouldn't that more be NPH-ard?
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.
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?
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.
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.
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.
....that for a bunch of nerds nobody seems to know what NP really stands for
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.
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.
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.
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.
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".