Pac-Man Is NP-Hard 195
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."
Tetris isn't NP-hard anymore (Score:5, Interesting)
Re:Tetris isn't NP-hard anymore (Score:5, Interesting)
I think the gameboy one stopped speeding up and some point, letting you play forever, well at least until you ran into a batch of randomness that gave you too many bad pieces.
The NES one, on the other hand, was actually impossible after a certain level... the blocks fell faster than you could get them to the edges of the screen.
There was a version of tetris someone made, maybe from here... that always gave you the worst possible piece.
Googling 'ragetris' tells me it was called 'hatetris [qntm.org]'.
Not entirely related to things being NP-hard, but yeah.
Re:What does the hell does NP Hard mean? (Score:5, Interesting)
Heh, heh, yeah. Here, try wikipedia's "simple" version: http://simple.wikipedia.org/wiki/P_versus_NP [wikipedia.org].
Re:and Pac-Man never was (Score:5, Interesting)
"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.
How you define the problems matter (Score:5, Interesting)
This is a good example of how you define the problems mattering. For example he declares Starcraft to be at least NP-hard. But if one is allowed to use trigger events and some other aspects of the scenario editor one can actually fully model a Turing machine in Starcraft. You do this in a straightforward way by giving trigger based instructions to a unit (say a probe) and have it move along a line where having some other specified unit in an adjacent spot represents a 1, or one has a 0 if the unit isn't there. This is a much stronger result than the result he has. But it seems that his version of Starcraft as defined doesn't let you use event triggers (or at least he doesn't mention them). So he only gets the weaker result of Starcraft being NP hard.
In the 1970s and 1980s, showing something was NP-hard used to be a big deal and there are a lot of papers from that time period. As the techniques improved one occasionally got some fun with someone showing that some new game was NP hard or NP complete (Tetris was done a few years ago as was Minesweeper). But these are really not considered to have any real insight. This paper is a bit more impressive because of the sheer number of games, and the systematic way he approaches the games especially his Metatheorem 1 and Metatheorem 2. Those two results are not obvious. Overall this is quite clever and makes for a fun read.
Re:nothing of value was gained (Score:5, Interesting)
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 [memebot.com] that was non deterministic (pseudorandomly so) as well as had many differing levels.
Comment removed (Score:5, Interesting)
Re:What does the hell does NP Hard mean? (Score:4, Interesting)
Wow, an actual use for the simple version of wikipedia. Who knew?