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."
This shit is stupid.
Math and Slashdot make me NP-hard.
Hard for Neil Patrick.
I am reminded of an proof from a few years ago that Tetris is NP-hard. But this proof is for old versions of Tetris that used a pure randomizer, not the new bag style generator in games since 2001. This randomizer incidentally allows playing forever.
I'm pretty sure we knew this from actually playing the games.
Just program in the patterns.
Pac-Man is solved. There's a book on how to beat it (sorry, I don't know the title). Well, at least the book tells you how to play the game until the arcade glitches out...
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?
I guess he forgot to play the actual stand-up game. There's a pattern.
http://www.math.montana.edu/~hyde/pacman/
I used to play from the moment my mom went into the grocery store, until she checked out.
Assuming that this method of measuring complexity is actually useful, is there an ideal level of theoretical complexity in a computer game?
(This is not necessarily the same as the complexity of play - Doom is, after all, very easy to play but PSPACE-hard problems are extremely difficult problems to solve.)
Any retro-gamers here want to determine the theoretical complexity of Wizardry, Atic Atac, Knightlore, Citadel or Cholo?
Is there any correlation between the complexity and how long the game stuck in people's minds?
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
They use a pretty conveniently screwed up variant of Pac-Man for their proof, not the actual Pac-Man, where there's free choice and arbitrarily fast transitions between the different ghost modes, so it's even further from true here than for Tetris.
10 PRINT CHR$(205.5+RND(1)); : GOTO 10
NP-hard Pacman's got nothing on Undecidable Ms. Pacman. You don't even wanna know about sheer evil that is Mrs. Pacman.
Fuck systemd. Fuck Redhat. Fuck Soylent, too. Wait, scratch the last one.
Thats what my wife said.
This is just why the Italian economy is failed.
Holy shit I don't want to read an article, led alone a scientific, peer reviewed article. Isn't there a pretty picture of a graph somewhere?
We don't believe in radical loony monotheistic religions from the middle east -- we're Christians.
Though I 4ave never said. 'Screaming
The problem is actually NP-Easy, you insensitive clod! And I am Handi-capable!
You don't understand: I am not locked up in here with you, you are locked up in here with ME!
....that for a bunch of nerds nobody seems to know what NP really stands for
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.
On the rst traversal, the avatar can safely land on top of the enemy and dig a hole on the left. The AI will make the enemy fall in the hole, so the avatar may follow it, land on its top again, and proceed through a ladder, while the enemy remains forever trapped in the hole below. The avatar cannot attempt to traverse the gadget a second time without getting stuck in the hole where the enemy previously was.
That's just not true. Grain of skepticism += 1.
It is hard to believe since I played continually over 2 hours without loosing all lives, I remember I found a single path tha would allow me to continue playing with phantoms running at really fast pace, the hard part was to be constant, but doable nevertheless
I'm positive, don't belive me look at my karma
I would like an thorough analysis of how hard Bejeweled (PopCap Games) is.
(HTML5)
http://bejeweled.popcap.com/html5
since only a few years ago. The comments on this story are very disappointing.
Doom is being lumped into the same game era as Pac-Man? Why am I suddenly getting a desire to have a lawn?
Complex mathematical probability equations can make your brain hurt even if you are the person your non-techie friends and family call when their computer "got some viruses off the Internet". Personally, it helps me relate to why lesser folks can't understand simpler scientific principles (like fuckin' magnets) and prefer "that's how God made things" as their explanation.
---
DRM is like antifreeze, to the MPAA/RIAA it's sweet, to the consumers it's poison.
Susie: Mommy... Why do I have to die? Why is there no cure for cancer? (cough cough) Why is it that no one has figured out how to cure us?
Susie's Mommy: Because the people who could have figured it out were too busy playing Pac-Man, Susie. I'm sorry.
That should please Ms. Pac Man
but only for N=1, obviously.
...the future crusty old bastards are already drinking the Kool-Aid.
tetris DS does get to the point where the piece lands nearly as soon as it appears
This behavior is called 20G, and it's also seen in "Death" mode of Tetris the Grand Master 2 and "Shirase" mode of Tetris the Grand Master 3.
however you can keep it from fixing to the stack by rotating it and wiggling it constantly.
This infinite spin behavior has become the standard since 2001, despite reviewers' assertions that "it actually breaks Tetris".
there is no configurability with the level designs
Where you read "Pac-Man" in this article, add a "Ms." in front. Ms. Pac-Man has four boards, as an extant example of how level design may be configured.
There was one level in particular that I struggled for hours to survive the first 5 to 15s. I think that level was about 3/4 the way through. You start in a large chamber with a double-wide set of doors that open onto a large area that is essentially a wide hallway wrapped around three sides of a large pool concealed with some modest trellis work. You're stuck in the middle of the long side with fireballs coming from every direction, several pink chicken drumsticks completely indifferent to pistol fire prowling nearby, and hordes of regulars to baste you with hot lead from all directions if you miss half a pivot. When you died, you were about -200 in health by the time your knees hit the ground. Even if you scored the instant kill out of the gate for the weapon drop, chances were slim you'd live to pick it up, much less lock and load.
The key for me was obtaining a mental state of unsentimental aggression bordering on contempt. If you tarried to dwell on your prowess for so much as a tenth of a second, the game earned its name. After hours and hours of seemingly little progress at all, I reached the point where I could survive the first 10s a little more than half the time.
Essentially you had to think of yourself as bringing a handgun to a knife fight: a couple of quick kills at close quarters was the only possible cover, as well as a significant boon: your adversaries were insects with guns. IFF was a million years down the road in their evolutionary future.
Things happened too fast to consciously play the angles. I think the cognitive adaptation was learning to hash every perceptible threat into precise buckets of 1/4 second duration and treating everything past the fifth bucket (1.25 seconds) as the distant future. Some other part of your brain was running the instruction prefetch decoder on threats 1 to 3 seconds into the future.
One had to transition from melee tactics to sniper tactics seamlessly after scoring the critical kills. How many times The Bride would be standing knee deep in corpses with heaving chest, then get pinked by a paper boy with a pen knife who ducked out from behind a column--game over. The initial mayhem was such an intense cognitive over-commit, the mind would pause to inhale after the flurry abated and some lone chump would take you down.
It was almost like the brain had to eject an empty clip in order to reload the next cognitive frame. Dying during the cognitive clip-change was the most F**** frustrating things of all time.
When I got past it, I never considered Doom hard again.
All fun and frolics, as long as you realize that the computational complexity of the "solution" has little to do with how difficult the game is for humans to play...
I'm assuming that by "solution" here we mean an algorithm that will either win (or prove winning impossible) for any case, in a finite number of steps; as opposed to a heuristic or stochastic technique that could win more-often-than-not, but never prove un-winnability.
Last time I looked, the human brain used some sort of complicated neural net-like wetware system that was most definitely not a Turing machine, and hence pretty crap at running algorithms. If, however, there's a neat non-algorithmic tactic that wins 90% of the time (especially if its based on something humans are really good at, like pattern recognition) then humans are going to do well, even if the "complete" solution is NP-hard or even uncomputable.
Maybe humans use algorithmic approaches to some puzzles, but I'd wager money that the human Rubic Cube champions supplemented their algorithms with intuitive leaps based on pattern recognition... Likewise, something like Tetris is going to call on pattern recognition, Pong on our wetwired/learned ability to predict motion (which predated Newton by a few thousand years...)
Then, of course, you have issues like reaction times, distractions and physical control layouts. For example - I'd surmise that 1st person shooters are easier with a keyboard and mouse, whereas tower defense games are easier on a touch screen. Dedicated arcade consoles can have custom-designed controls for the particular game, so the otherwise identical version for generic machines might be "harder".
In a survey of 100 programmers, 111111 thought that duck-typing was a good idea.
Then let me rephrase: The product called Pac-Man is one special case of the generalized Pac-Man problem, where one of the inputs is the board layout. It's still an interesting problem in mathematics to determine how much generalization is needed to push the problem into each complexity class.