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."
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.
Was that you watching me last night?
Tic-Tac-Toe, Global Thermonuclear War, and relationships all have the same winning move.
Wouldn't that more be NPH-ard?
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?
To the Yar'eth degree
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.
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.
That should please Ms. Pac Man
Hey Pac Man is only 13 years old according to TFA! That's great that means i'm only in my 30s again!...oh wait a tick this is Slashdot where editors never edit... :-(
You wanna know what's hard? finding out your twitch skills have gone further south than a 43 year old's D cups whose nursed 3 kids. I used to be death incarnate on games like DOOM, Mechwarrior 3 & 4, SoF 1&2, bodies would be piled up like cordwood. Then over the Xmas holiday my boys were like "Hey you've got your new netbook right? Why don't we fire up some TF2 and play together!" and boy that was a rude awakening let me tell you. the heavy, the soldier, it didn't matter what i played i got the living shit slapped out of me. I got so irritated i decided to whip out my CC and buy 3 copies of HL:DM to show these kiddies a thing or two and...ooow, I ended up with so many rockets up my ass my little Freeman is probably walking funny to this very day. Didn't help the oldest was announcing a play by play for the house while my GF laughed her ass off "Oh he's dead, and he's dead again, oh look he didn't even see the death coming that time, will he make it around the corner? nope he's dead" while the youngest made smartass remarks about how he'd "get me a walker with a controller built into the handles for my birthday"
So enjoy it while you can young ones, all of you that kick royal ass on MW or CoD just as we ruled the arcades will blink twice and the next thing you know your kids will be pimp smacking you on every game while making geriatric jokes. man it sucks getting old :-(
ACs don't waste your time replying, your posts are never seen by me.
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.
Hey Pac Man is only 13 years old according to TFA! That's great that means i'm only in my 30s again!...oh wait a tick this is Slashdot where editors never edit... :-(
Or more likely that Slashdotters don't read TFA. The 13 is a reference to the number of games researched, not their age. Pac-Man is noted as a game from 1980. Neither the introduction article (first link) or the research paper itself (led to by second link) suggest Pac-Man is only 13 years old.
What does this really mean? You're old again.
End the FUD
When you get older, the thing to do is play Civilization style games. The youngsters with their trendy ADHD won't last more than a few minutes, You can basically bore them into losing, just by playing non stop for an hour or two and letting them know how far there may be to go before a result.
It's a bit like watching cricket, highly recommended if you're over 40 and need to look after a child or two. After half an hour tops they fall asleep and you can get happily drunk.
To have a right to do a thing is not at all the same as to be right in doing it
I hear you. While some of it for me is not practicing nearly as much.
I have a wife, two kids, and (in my opinion) a great paying, challenging, but demanding 50-60 hour a week IT job. When I was in grade school, high school, then college, then single 20s, I had seemingly endless time to play and get very good at my games of choice. Mainly FPSs and strategy-RTS. Also I was lucky and got to be in modern competitive gaming at the beginning of such LAN and then online multiplayer vs. games, so the learning curve was incremental. New games built upon skills I learned from older ones. Now-a-days I usually only have time for a real gaming session (3+ hours in one block) game once maybe twice a week. That's time I have to make an effort to find and jealously defend on my weekly schedule. Not complaining- I wouldn't trade my earlier life for my current one, but it's just how it is once you are (somewhat) successful and have some responsibility. When you don't play 3-8 hours a day, you skills aren't has sharp as those that do.
Unfortunately I also do feel my reflexes slowing down a bit now that I'm pushing 40. I'm just not as fast as I used to be. Not by a huge amount, but in twitchy FPS or RTS games, a few split seconds make all the difference. I'm no longer "death incarnate" either. I remember ruling DM servers for hours in UT 99, Quake 1,2,3, Tribes, 1, etc.
This is somewhat compensated however by a very big bag of tricks I've built up over the years. It's always fun to use techniques/strategies to win that I learned and developed years ago against younger guys who can kick my ass in straight reaction time. Having a strong understanding of map/recourse control brings you a long way, and allows me to stay at least competitive.
But yeah- in such games, you can definitely feel your reflexes starting to go south as you rack up the years. Just the way it is!
People that play these games every day can school people that don't every time because they have every nuance down. I played a game of HL2 where I was dying constantly and never saw it coming. Later I watched the guy that had been sniping me and he was hitting targets that I couldn't even see because they were so faint and far away and getting head shots every time. It was insane (I learned later that he won several half life tourneys and we didn't stand a chance - he was mid-30s at the time, so age is only half the battle - practice like crazy is the other half).
I also remember a game of Battlefield 2 where I was killed within seconds wherever I spawned on the map by either a plane of a helicopter, and I never saw either (I heard them both, but they were very far away). I switched sides and watched the helicopter and they had 3 snipers sitting in the door picking off everyone at the spawn point and a guy resupplying them from behind. I couldn't see the plane, but I'm guessing it was just bombing the spawn from high up (by that point in the game there was only one uncaptured spawn, so it was pretty easy to target).
Note that the HL2 game was coordinated teams of people I knew in the office and the second game was random people, and one side was far more coordinated than the other (not to mention very good). The DOOM and Mechwarrior days didn't require a headset and extremely coordinated teams of players.
I wonder if Sinistar is NP-hard... I remember that game being insanely hard... or how about Defender with the hard dips turned on? Ever see that? Defender was crazy hard to begin with and they had dip switches that made it even harder.
Fire up something a bit more tactical like BF3, though I would call TF2 a twitch shooter. If it was your first time playing, might just need time to learn the maps and classes.
Yeah, I shall not soon forget the ass-whuppin I got when I tried to play Super Smash Brothers Melee on the Gamecube with my nephews. The fail was epic.
But maybe its just me, but the newer games don't really seem to have much of a chance for aquiring a "bag of tricks' because everyone just runs like a chicken with their head cut off. that is what I miss about MechWarrior 3/4, i used to get accused of cheating until i would tell them my exact loadout and they were always "Uhhh...what the hell? you only got one shot!" but that was the point, i stripped down my mech and made it into a walking blunderbuss. no secondary weapons, no lasers, just one big ass shot. if i missed and my teammates didn't cover me i was toast but if i hit you...ohhh mama...even the biggest assualts would be hurting and anything medium or below was dead meat.
Working here at my little shop though i know what you mean, between the shop, working on the new album with my new band, my GF, and spending time with the boys i just don't get to blast like I used to. hell i think more than a third of the Steam Xmas sale games i got along with the GOG Xmas sale games i picked up i haven't even gotten a chance to fire up yet and with the GF about to use her vacation time so we can have a week just the two of us before the grandbaby is born I just don't have the time to spend hours learning, although like I said from what I saw games like TF2 are more chicken with their head cut off. But you don't realize how bad time catches up until you hit the big 4.0. and you fire up a game you used to rule like HL:DM with your two college bound boys and find them handing you your ass on a platter. Man it was worse than schooling, it was bitch slapping time.
ACs don't waste your time replying, your posts are never seen by me.
Play Smarter:
Love your reference to mechwarrior 3 ;) I played as Buzz_Litebeer :)
To put it in perspective, I used to play Mech3 at the best level, won money, played MOHAA at highest level (top 10 team) original call of duty (WW2) COD4 at a high level.
The way I had to change was to move to play that emphasized knowledge of the maps I play on over twitch skill.
You simply are not going to beat the kid that can fly around the corner, fire, and always nail you in the head.
BUT, if you play correctly, you are already 2 -3 shots ahead of them at this point, and you win through simple manipulation of their lack of experience.
To go against the kids with both twitch and a good head for how to play against people... well just be lucky there aren't that many.
But to put my skill in perspective, in Call of duty 4 (I havent kept up with the new ones) I was often able to get 15 kill streaks, and many times 7-1 or better Kill Death Ratios, simply by knowing the map and playing deliberately instead of relying on pure twitch skills.
It just takes a different way of thinking!
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.
It's not getting old. It's lack of practice.
If you ignore ACs because they are anonymous - you're an idiot.