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."
It would be more accurate to say Tetris isn't Tetris anymore.
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?
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.
....that for a bunch of nerds nobody seems to know what NP really stands for
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.
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.
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.