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?