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