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

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.

Re:What does the hell does NP Hard mean?

[lgw]

OK, without the wiki dive, here's the short version:

• * P is the set of problems that can be solved in polynomial (or better) time.
  * NP-Complete is the set of problems that (probably) can't be solved in polynomial time, but the solution can be verified in polynomial time.
  * NP-Hard is the set of all problems that can't be solved in polynomial time.

  Only two of those are actiually distinct. We think P and NP-complete are different, which would mean NP-Complete and NP-Hard are the same (IIRC).

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

[EdIII]

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

Re:and Pac-Man never was

[hal2814]

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.