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

Comments

Re:Tetris isn't NP-hard anymore

[Anonymous Coward]

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

Re:nothing of value was gained

[fuzzyfuzzyfungus]

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.

What does the hell does NP Hard mean?

[hairyfish]

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:nothing of value was gained

[martin-boundary]

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.

What I got from the comments is..

[Anonymous Coward]

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

Re:and Pac-Man never was

[TuringTest]

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