Slashdot Mirror
Classic Nintendo Games Are NP-Hard
mikejuk writes "You may have have thought games like Super Mario Bros., Donkey Kong, and so on were hard at the time you were playing them, but you probably didn't guess they were NP-hard. Now we have some results from computer scientists at Universite Libre de Bruxelles and MIT Computer Science and Artificial Intelligence Laboratory that many classic games contain within them an NP-hard problem. It has been proven that the following game franchises are NP-hard (PDF): Mario, Donkey Kong, Legend of Zelda, Metroid and Pokemon. At least you now have an excuse for your low scores."
My favorite NP-hard game is adom. Just try it - see my sig.
#
#\ @ ? Colonize Mars
#
Kid Icarus for Nintendo is the most difficult game in the history of mankind.
"Isn't it great we can usually beat an 8-bit video game?"
This was the early 2000s on an ancient Nintendo box.
Tic-Tac-Toe, Global Thermonuclear War, and relationships all have the same winning move.
I thought all games were NP-hard. That is, the path to optimal scoring is dynamic based on random events (true or simulated random). For example in a standard shoot-em-up, you're always thinking about the order in which kill an object and in what particular order all while avoiding being shot at.
Life is not for the lazy.
Is "NP-hard" the next buzz word?
Solstice may be the most difficult game ever
Castlevania was harder than Mario, Zelda, or Metroid -- especially the Grim Reaper fight. If you didn't have triple-shot boomerangs, when the Reaper started spamming you with Scythes you were in trouble.
Battletoads was another one that was brutally hard...
I saw where someone thought the Mega-Man games were hard... but those always seemed easy to me.
Sock Puppets: damn_registrars=pudge_confirmer=jimmy_slimmy=raiigunner=cml4524=a_klavan=red4men=ronpaulisanidiot
Now Billy Mitchell's ego can finally get a much needed boost.
I Honestly don't understand what NP refers to.
These games aren't "NP-hard" because they are fixed size and fixed levels. Complexity results show you nothing about the difficulty of individual instances.
What is "NP-hard" is some generalization of these games chosen by the authors, with a particular chosen outcome (e.g., maximum score). Whether that generalization is still a good game, or even the same game, is questionable.
Battletoads was another one that was brutally hard
Is it hard to TAS, or just demanding in reaction time and memorization? Because the article is assuming tool-assisted speedrun conditions: "Indeed, the clicking of the button at the right time is factored out of these proofs of complexity - these are results that apply to a perfect player with infinite speed and reaction times of zero."
Almost any interesting game will be NP-hard. Mostly only boring games will be NP-complete though.
NP is the second-most boring class of problems (and it might even be the most-boring class, if NP=P).
Look into some lecture of AI-planing, most problem solving problems are EXP(EXP())- complete, and if you want optimal solutions, it might even get harder....
I'm sure I've seen this before. Ahh, yes here it is, almost two years ago.
I guess not the exact same thing, since the last story didn't explicitly mention Donkey Kong ... but certainly the NP-hard part has been discussed for a while.
Lost at C:>. Found at C.
They were "Nintendo hard" long before anyone realized they were NP-hard, and that's a much more meaningful measure for difficulty of video games on a practical level.
Whether a problem is NP-hard has nothing to do with it being hard for you. NP is hard only for computers, because they are restricted to brute force search for the solution. As a human being, you use your intuition to probabalistically arrive at a likely solution instead of using a logical process to arrive at an exact and perfect solution. People do not care much about absolute knowledge, which is the province of science; we care about practical knowledge, which is the province of engineering. For example, the infamous travelling salesman problem is NP-hard, which makes it impossible for a computer to come up with the optimal solution in a predictable amount of time. However, in real life this has minimal utility because the difference between the optimal solution and the "good enough" solution that millions of travelling salesmen come up with every day is likely not financially significant. This is true in most everyday situations: we simply don't care if the solutions we use are the best available, only that they are the best we can think of in a reasonable amount of time.
This is not to say that we don't need the absolute knowledge that science provides; in many cases it does indeed lead to the practical knowledge that improves our lives. But because most absolute knowledge has no useful applications, it does make sense to have a lot fewer scientists than engineers.
Assuming the analysis is correct and these games are NP-hard, then what is interesting is not that some of us failed miserably at the games but so very many people did quite well. The human brain is a special-purpose computer that excels at solving problems critical to the species' survival. This suggests to me that reformulating problems of interest into a form that the brain can process (e.g., video games) might be an excellent way to tap the computational power of the brain. Wouldn't it be interesting if the millions of brains playing games were actually solving major problems in physics, biochemistry, etc.? Call it "crowd-sourced computation".
There's no sense in being precise when you don't even know what you're talking about. -- John von Neumann
I think it might all come down to how you look at the problem.
many people have programmed AI to beat Mario, I believe a few years ago their was some random Mario level generator (possibly called Infinite Mario) and a contest to create AI to play it. The simple act of taking it one frame at a time, dodging and jumping, is not hard to program AI or resource intensive I think, but any problem can be made complicated. If you are saying take a static level, how do you get the absolute maximum score, now of course that is NP hard.
Troll is not a replacement for I disagree.
The proofs are based on showing that the problem of deciding if a goal point is reachable from a starting point is NP-hard. The games are also generalized in that the size of the board is increased.
But the goal points are always reachable from the starting point... otherwise it would be a really shitty computer game.
The fact that the games are not randomized every play-through, and of limited size...
Grr... "NP-Hard" doesn't mean actually hard to solve... There is a proper subset of generalized NP-Hard (NP-Complete even) problems that are not particularly difficult to solve.
While the original Super Mario Brothers may have had one level that has an actual real maze to it, and as such, the underlying principles of the game may be extrapolated to be NP-hard, the first level of Super Mario Brothers is clearly not. In fact, most of the original Super Mario Brothers doesn't have any splits or deviations from the linear path that do anything but take you to a point further along in the linear path.
What I'm saying is, it seems like they generalized at least some of the games beyond all meaningful criteria... especially when these early games were specifically constructed to ensure that they the goals remained always potentially reachable.
WARNING! This girl exceeds the MAXIMUM SAFE standards established by the FDA for BRATTINESS
Battletoads and Adventure Island are, on the other hand, mother-fucking-hard.
For a gentler introduction, see P vs. NP.
Is this Battletoads? No, it's Battle Kid.
Those games aren't hard, modern games are just too easy.
Anyone played Demon's Souls? That's how hard games should be.
Summation 2
... for non-polynomials that work out to a constant size.
to know how scientist use their resources, nowadays.
It'd be also very interesting in knowing how these breakthrough can help the mankind and the Science.
Sent as ripples into the electromagnetic field. No single photon has been harmed in the process.
It seems that these problems are not in NP, either, since one would hazard that a certificate that one has achieved the fastest possible run would involve exponentially much information. Proving that one has made the correct decision at each step seems hard if one doesn't include exponentially much information about the future.
pokemon considered np hard.
that's the simplest game i have played, it's just one big rock paper scissors simulator.
the video game version's of the card game on the other hand were hard because the ai cheated, it had a pool of all possible cards from it's deck. you only had what you had chosen.
I've played Mario, Donkey Kong, and legend of zelda and I enjoyed them, especially legend of zelda. The wikipeadia article on NP-Hard is so poorly written using broken circular logic I really have no clue what they were trying to express.
The IPS file for Super Mario Forever, the map pack featured in the Super Mario Frustration video, is still available.
Go ahead and use pedantic terms as much as you want when writing summaries - but it's rather annoying when you don't take .5 seconds to define them. Linking to a pendantic explanation of your pedantic writing makes it only marginally less annoying.
Like:
Here let me tell you a story where a vulpini went after a sciuridae in my back yard.
vs
Here let me tell you a story where a vulpini (fox for you plebeians) went after a sciuridae (squirrel) in my back yard.
Looks at my name. You think my scores are low?
"When information is power, privacy is freedom" - Jah-Wren Ryel
Isn't an NP hard game effectively any game you can't save, reload, and try again?
in simple words
in order to win you have to make that seemingly impossible jump
or you lose, you can make all the shorter jumps in between
but in the end you'll have to make that jump
there's no way around
god, i read that godawful wikipedia article
think i lost couple of braincells reading the examples section
And that is why they invented game genie.
So, impatient folks like myself could see what the game ending cut scene was with minimal effort in very little time.
...is to prove that it's also NP-complete, and in theory NP-hard problems can then be mapped to Mario Brothers and solved by avid gamers :)
KEEP CALM and KACHO ON
i'm from the NP-hard games generation, BITCHES!
That was a hard game. Probably the hardest I ever played.
Control of player 2 doesn't even work in some parts of Battletoads. How is that not designed poorly?
I'm NP Hard if you know what I mean. I mean I am a class of problems that are, informally, "at least as hard as the hardest problems in NP". And also that second thing.
... Nethack without spoilers. Without spoilers, not sure how you'd beat this.
That being said, I regret having the spoilers and forever depriving myself of the chance to do it. Is there any other nethack like game that would provide the same level of challenge?
BilldaCat
I'm sure I've seen this before. Ahh, yes here it is almost two years ago.
Tetris is Hard: NP-Hard from 2002!
Or, more recently, Pac-Man Is NP-Hard from January of this year.
It's still not a dupe, but really all of these should have been referenced and linked from the submission as relevant.
Because I'm NP-Awesome
Mod me down, I shall become more off-topic than you could possibly imagine.
Hahahahahaha. You go ahead and try defining NP-Hard to a layman (or plebeian ;-)) in .5 seconds. It would be easier to implement AI to simply hide all NP related stories for those who have not whet their feet in the theory of computation.
I love how the intro of the paper talks about Tool Assisted Speedruns, but then proceeds to claim that a solid wall will stop Mario. Anyone who's ever watched the TASs of Super Mario Bros will see the trick where Mario busts through a solid wall like it's nothing.
NP hard. I got your hard hanging.
Seriously, I tried to read the damn wiki on NP hard and it makes no fucking sense.
so NP hard is well, NP hard.
I know we got some really smart people here to probably use NP hard in every day conversation, but i'm guessing, you could easily say, that a lot of old nintendo games are pretty fucking challenging and hard to get a high score on.
But wtf is Pokemon doing in that list? That game isn't hard, it's fucking easy as all hell. It's a memory game. You got to remember what a pokemons weakness and strength is. Even if you don't, the game isn't hard to play. at all. Donkey Kong, sure, that gets hard. Pacman, yes, unless you memorize the patterns, which then makes the game easy and boring as all hell.
Well, whatever. Next time, maybe the explantion of NP hard shouldn't be, well, NP hard.
Be seeing you...
Nah, just keep throwing Magikarp out there, no matter what the circumstances. His splash attack is devestating!
#DeleteChrome
Isn't this just the halting problem? A game is a program whose inputs are discrete inputs from the player. So, before you can write a program that determines the winning solution to a game, the program has to be able to detect if there is any solution at all. Otherwise, the program will run forever. Isn't that just the halting problem, which is NP-hard?
I finished Sunsoft's Fester's Quest using just an NES gamepad and no rapid/turbo fire. It's not impossible but there were (to me) some very hard elements to the game, bordering on being cheap when first encountered, but those very difficult underground maze tricks always had a solution. Here are my tips, for anyone that may still be playing the game but hasn't beaten it.
* The first screen had to be milked for all of the blue "Gun" powerups--never pick up a red "Gun" that was a power down. Trying to get Blue "Gun" while progressing through the screens was just too hard to do. Don't even scroll the screen until all the blue "Gun powerups have been obtained (the three rapidly moving spikes that moved straight ahead, not in a wavy pattern which was one level down from max power).
* Once fully powered up and moving on, the hidden extra hit point had to be found, to get three hits rather than two. Going to that one building, then pressing toward that one wall gave that hidden extra hit point.
* Vice grips were absolutely necessary not just for the mosquitos, but also for the frogs and the red round mouths. Without vice grips, Fester remained stuck at half speed. With vice grips, it was as simple as get hit, slow down to half speed, use a vice grip, back to full walking speed.
* Those red mouths that took too many shots to do away with? Use one firecracker (or whatever they called it in the game) instead--place one just before the mouth gets to it, and the mouth will go away as soon as it hits the firecracker.
* Same goes for the whip--milk a scren for all the blue "Whip" powerups before moving on. Red "whip" was a whip powerdown. Basically, don't get ever red "Gun" or" Whip", even if it means having to stay in one place until it times out or fades away; otherwise, later in the game it becomes much harder to regain a blue "Gun" or "Whip" powerup.
* Boss fights were the closest to being cheap, I thought. Mainly consisted of drilling the boss with shots or the whip, getting hit by sometimes an undodgeable shot, then using the health to recharge when Fester got to only one hit left. This is why is was necessary to get that third hidden hit, otherwise Fester wouldn't last through some of the boss fights. (Dodging was quite difficult for many of the bosses--though possible but it was usually better to mostly stay still and keep hitting the fire button; however, I did not ever find the dodge pattern for the last boss.)
* Continuing started all the way at the beginning, even though all items were kept. I usually quit or start a whole new game rather than choose to continue.
That said, I finished Fester's Quest twice. The ending is short, but nevertheless there is an ending sequence to close out the game.
Also, I thought the main above ground theme was excellent music even if it wasn't an Addams Family tune. (Makes sense, Sunsoft also did Blaster Master which I thought had particuarly excellent Stage 1, 2, and 3 music.)
No love for the original castlevania? I've only met one person who beat it and he sold his soul to Satan to play video games. At least he claims he beat it. I never saw it done.
21st Century Renaissance Man
I tried dwarf fortress. Probably about 3 or 5 weeks in total. I learned the basics, tried the adventure mode, etc. Indeed it's a nice complex game with many possibilities. But after that time, and having fully configured dwarf therapist. I decided that this game is not fun for me. It's babysitting mixed with sim city. I decided that I do not want to spend more time learning its quirks.
Instead my adom nostalgia grown stronger. And after I was finished with dwarf fortress I successfully resisted the urge to play adom. Doing frequent and successful checks for willpower apparently increases it. Looks like adom is quite good at mimicking real life.
About adom, I especially love the single-life no-saving feature in adom. It trains your skills at solving ultra-complex problems with cold head. I still remember the adrenaline rush when in this turn-based game I was fighting Andor Drakon, planning many moves ahead and thinking several seconds before making next move. Lovely, especially the adrenaline!
One of my high scores says: "He saved the world with his brave efforts and became a great ruler while saving himself 2 times." Indeed I saved only two times in this game, and this winning-marathon took about 40h of playing. But also it took one month of dying, before I played the winning game. Heh, my last win was in 2008. But still I need to resist playing it now again. There is lots of interesting research for me to do.
Violence! This is very funny, but for me there is as much violence in adom, as you have in a game of chess. Indeed you can beat the pawns in chess, and they are killed. Same thing in adom, only more complex.
I wonder why I can't have that much fun from other "popular" games like Elder Scrolls or Twilight Princess. Only Diablo 1 is comparable, albeit much worse.
well... back to QED
#
#\ @ ? Colonize Mars
#
It featured a randomized attack scheme for the camp counselors/children.
Jason's whereabouts were randomized as well.
Not to mention, this game is ridiculously hard to beat.
Finally they prove these games are as hard as flipping pancakes!
Joking aside, being NP-Hard doesn't really correspond to difficulty. It was pointed out in another comment that since the levels are fixed, they cannot be NP-Hard. Another then said people have altered the levels on many of these games, but that still doesn't mean much. There is no set of levels that could prove it.
Being NP-Hard is a property of at least one of the mechanisms in the game. For the proof, the mechanism is shown be able to encode an NP-complete problem in such a way that if you could solve the game mechanism's problem quickly, it can be shown to quickly give solutions to the NP-complete problem. So it's not really any specific level, its the ability to embed other "hard" problems into the level and being able to translate the solution back quickly that's important. (IE, it's hard because it's solution can "automatically" solve other hard problems quickly)
Odds are if you saw the levels created by translating 3-Sat problems (or whatever they used for the reduction) into Mario levels, you'd think the levels were not fun in the slightest. Then again, it could be cool to let people input some 3-Sat problem and then go play the Mario level and see the answer they generated by beating the level. Anyone wanna make that? And then input the levels into Super Mario Crossover 2 so I can use the Blaster Master tank :)
Speaking of Blaster Master, I got a kick out of reading other people's experiences with those old NES games. It seems the harder those games were the more I liked them. Kid Icarus, Battletoads, Blaster Master, Fester's Quest, and Solomon's Key were mentioned, but also Teenage Mutant Ninja Turtles (the one with the swimming bomb-defusing second level), Friday the 13th (though once you know how Jason attacks it's too easy, even just throwing stones), the first Mega Man (without using the repeated select button trick), Bart vs. The Space Mutants, Double Dragon III, Ninja Gaiden Trilogy, Deadly Towers, Rush 'n Attack, Snake Rattle & Roll, Mike Tyson's Punch Out, Metroid, Gauntlet, Castlevania, Nightmare on Elm Street, Little Nemo, Legendary Wings, Bionic Commando, Guardian Legend, Zelda I & II, Marble Madness, Werewolf, Legacy of the Wizard. I've got nostalgia for each one (maybe because I spent enough time to memorize the levels, develop my strategy, and finally win), not to mention the various RPGs but those are generally less difficult. Thank goodness for emulators :)
Double dragon !!! Especially part two was np hard lol
Seriously people get paid to do the "research" on this ? There are countless diseases and other problems in the world and someone gets the new crop of university brainiacs working out how hard an f'ing computer game is ?
Well that'll be such a help to civilization!
He was funny to watch as he would move his entire body to make Mario jump.
A lot of beginner gamers do this, and it's what console makers depended on when designing the Wii Remote and the Kinect sensor.
So, what the heck does it mean in the context of video games? "A problem as hard as the hardest NP-problem" really doesn't clarify it for me thanx...
Never say never. Ah!! I did it again!
This paper is as close to marketing as science ever comes. The use of the words 'NP-Hard' and "video games" were chosen specifically because they sound impressive, not because they've shown anything useful. They came up with some way to connect those two words in a paper (by morphing Mario, and defining it in a way that never entered any cartridge. If you have a finite number of paths through Mario in an arbitrarily large map, and some choices make the game impossible to beat because you get stuck, then yes you have an NP-Hard search problem. But there is no Mario level like that, and never will be because it would be boring). It also fulfills the other requirement of marketing, that it makes me feel dumber after reading. This super-annoying movie comes very close to showing the method used in this proof [youtube.com]. It solves a problem that no gamer would ever face, and no GTA Wallpapers level designer would ever face either, unless his method was to randomly drop blocks on the screen, rearrange them into chunks of which some are impossible to pass, and then rearrange those randomly. Can you see how this has absolutely nothing to do with the game we call Super Mario Bros? In other words, the authors saw the attention people got for using the word "NP-Hard" in relation to Tetris (look! Made it on BBC! ), and though "wow, maybe if we use the word NP-Hard in relation to Super Mario Bros, we can get on the BBC too! There is absolutely nothing novel about this result, and in fact, it might be a homework problem you would give to students in an undergraduate class on computer theory. Given the right introduction, the students could easily do it. It is a blatant attention whore attempt.
Section Z was way more difficult!
Oh please, all you had to do was grind. That wasn't hard in the slightest.
What do I know, I'm just an idiot, right?