Classic Nintendo Games Are NP-Hard 204
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."
Not just nintendo games (Score:4, Interesting)
My favorite NP-hard game is adom. Just try it - see my sig.
Re:Not just nintendo games (Score:5, Interesting)
Re: (Score:3)
I'm not a basement gaming zombie ;) I'm a scientist.
I'm careful to avoid playing adom more often than once per 2 or 4 years. Otherwise a month is lost.
Re: (Score:3)
Check out Dwarf Fortress. It's an easy game that's fun to play and certainly not in any way addictive! Really!
HELP ME.
adom vs. dwarf fortress (Score:3)
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 p
Kid Icarus (Score:3, Funny)
Re:Kid Icarus (Score:5, Funny)
Harder than Battletoads? I think not.
Re: (Score:3, Insightful)
There's a pretty big difference between "hard" and "fundamentally broken".
Battletoads was hard because it was designed poorly.
Re:Kid Icarus (Score:5, Funny)
There's a pretty big difference between "hard" and "fundamentally broken".
Battletoads was hard because it was designed poorly.
Sounds like SOMEONE'S still bitter they couldn't even beat the Turbo Tunnel.
When 2P is completely broken (Score:2)
Re: (Score:2)
Re: (Score:3)
Battletoads was hard because it was designed poorly.
I'm not sure what your basis for that statement is. Every time I've lost at that game the Toads had done everything I had told them to do. I lost because I didn't order them properly.
There is a distinction there. I've played MANY games where the design really was poor, it was the fault of the game that I couldn't succeed. Maybe jumps had to be too precise. Maybe your path was obscured and required luck to find. Maybe the button presses didn't register at all. I'd go into more detail, but instead I'll
Re: (Score:2)
Re: (Score:2)
Impossible, what? I've finished Blaster Master a couple times.
Re: (Score:2)
I never could get past that lava jet ski level!
I could whoop up all the way there and I kept getting just a little bit further, but then, nothin.
I'll bet the final baoss wasn't that hard!
Re:Kid Icarus (Score:4, Informative)
I never could get past that lava jet ski level!
I could whoop up all the way there and I kept getting just a little bit further, but then, nothin.
I'll bet the final baoss wasn't that hard!
No, the final boss level (and final boss) were as tough as the rest of the game. I spent a couple months in college where I dug out my old nes and vowed to beat Battletoads (on the real thing, with no save state cheating). It was incredibly painful. It was hard all the way through. The only real hope you have is juggling the vultures on the 2nd level to gets tons of 1-ups.
Re: (Score:2)
You've never seen the SECOND jet ski level then?
It was harder even still than the first one.
Re: (Score:3, Insightful)
Ahem. Silver Surfer.
Re: (Score:2)
Re: (Score:2)
I concur, I've finished Kid Icarus multiple times, without dying even. I also finished a bunch of those games without dying including Zelda, SMB1, Megaman 1 and 2.
Ghosts'n Goblins was another tough mofo. I remember finishing it once, and then when I saw the "You must do it again" screen, I gave up.
But Battletoads I finished exactly once, and it was quite an ordeal. Really the hardest game I ever finished.
Re: (Score:2)
Did spy hunter have an ending? I don't think I ever made it past fall.
Re: (Score:2)
I have landed in Top Gun, maybe 2-3 out of 5000 tries. Never won in Days of Thunder, have beaten Double Dragon though.
What about Boy and his Blob? I could never figure out WHAT to do to beat that game.
Re: (Score:2)
Re: (Score:2)
Syobon Action is hellish too, although mostly because the traps are hidden.
Super Mario Forever IPS (Score:4, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re:Kid Icarus (Score:5, Insightful)
Desert Bus is WAY harder to beat.
Re: (Score:2)
Harder than QWOP?
Re: (Score:3)
Re: (Score:3)
Quote from a friend while playing NES games: (Score:2)
This was the early 2000s on an ancient Nintendo box.
Re: (Score:2, Interesting)
Re: (Score:3)
Re: (Score:2)
Re: (Score:2)
There are almost no games where it's true random. It's pretty universally simulated random, and in fact poorly simulated random because quality PRNGs are typically slow. The advent of MT a few years ago at least improved the quality, but it's still PRNG.
Buzz (Score:3, Insightful)
Is "NP-hard" the next buzz word?
Re:Buzz (Score:5, Insightful)
No, NP-Hard cannot be, nor ever become, a buzz word, because NP-Hard has a clear, well-defined meaning. Buzzwords are defined by their own lack of definition, making them perfect for marketing and generally impressing people without saying anything meaningful.
Re: (Score:2, Insightful)
Should NP-hard become a buzzword, it would be first spread by people who understand it badly, and then by people who have completely misunderstood the idea but think it's neat. It doesn't matter that it has a precise technical meaning, if only a few people understand that meaning. In fact many buzzwords start out being well defined in some community of experts, but whatever meaning there was to begin with is quickly diluted to another feel-good word associated with a vague cloud of ideas.
Re:Buzz (Score:5, Insightful)
For example
Synergy: Is when the output of a team or groups activity is greater then the sum of each member.
This happens when you are working together and you come up with a solution together that no one by themselves would come up.
The word had been misused because of its closeness to Synchronous and Energy and used more to express things working well together.
Re: (Score:2)
OB Dilbert:
http://search.dilbert.com/comic/Leveraged%20Synergy [dilbert.com]
Re: (Score:2)
So did REST, if you read the thesis, but it didn't help.
Re:Buzz (Score:5, Insightful)
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 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! [bbc.co.uk]), 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.
Re:Buzz (Score:5, Funny)
Re:Buzz (Score:5, Funny)
Where have you been for the last 5 weeks? Didn't you get the tweet? The term "NP-hard" has been superseded by "NP-cloud-based-social-media-hipster". Keep up!
An "NP-cloud-based-social-media-hipster" would be proof that P=NP, since you're saying this cloud-based-social-media-hipster is in NP(Non-Pretentious), when it has already been proven that all hipsters are in P.
Castlevania (Score:2)
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.
Tool-assisted speedrun (Score:3)
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."
Re: (Score:2)
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.
Or you could use Fire Bombs (aka Holy Water) with the Double or Triple Shot. If you aim at the Reaper's platform as he lowers from the ceiling and keep throwing there, he will get stuck and die before he can even create a single scythe.
Castlevania is actually a pretty easy game once you've memorized what h
Fantastic (Score:4, Funny)
Now Billy Mitchell's ego can finally get a much needed boost.
What? (Score:2)
I Honestly don't understand what NP refers to.
Re: (Score:2)
For a gentler introduction (Score:5, Informative)
For a gentler introduction, see P vs. NP [wikipedia.org].
Re: (Score:2)
P=NP
Now where is my $1M prize?
Re: (Score:2)
Post above yours: "N****** pussy"
Yours: "was about to say the same thing."
Unfortunate alignment, but I had to chuckle.
To compensate: http://en.wikipedia.org/wiki/NP-hard [wikipedia.org]
Re: (Score:3)
Here's a slightly inaccurate explanation that will hopefully give you the gist:
P problems are easy to solve with computers. The number of operations required to solve them can be described by some polynomial, for example for a problem of size X, perhaps X-squared steps. In this example, a problem of size 100 would take 100-squared = 10,000 computer operations. Virtually any modern computer can do 10,000 operations faster than you can blink.
NP problems are hard to solve with computers. The best known co
Re:What? (Score:4, Informative)
For an intro to NP and NP-hard, might I suggest Wikipedia's entry on NP-hard [wikipedia.org]? You get to stuff like this in any classes that cover computational complexity, such as coursework covering algorithms. NP comes up every few weeks on Slashdot since it's an interesting-ish topic for most of us.
Re: (Score:2, Informative)
"Not polynomial."
It refers to the complexity of a computing problem being significant enough that it cannot be guaranteed to be solved in polynomial time.
So doing an operation on a two digit number is easy, but as the number of digits goes up, and you try to do the same operation on the bigger numbers, it gets harder at a rate which is greater than polynomial with the size of the input.
It's a little more complex than that, but that's basically it.
Re:What? (Score:4, Informative)
Re: (Score:2)
Yes, you're correct, my bad. Although for a first-order approximation, it doesn't matter, because people today generally aren't dealing with nondeterministic machines. The distinction probably doesn't matter unless you're writing a paper about it or the world changes radically.
Re: (Score:3)
No, NP stands for "nondeterministic polynomial time". Informally, it means that the problem can be solved in polynomial time if you are really, really lucky.
Re: (Score:2)
Wrong. N=Non-deterministic, like the Turing machine.
Re:What? (Score:4, Funny)
I Honestly don't understand what NP refers to.
Nintendo Power.
pointless (Score:5, Interesting)
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.
Re: (Score:2)
What is "NP-hard" is some generalization of these games chosen by the authors
Isn't a generalization like this realizable using ROM hacking tools such as Mario Improvement or Lunar Magic?
Re: (Score:2)
Another possible example: the best way to collect all pickups in Metroid while minimising the encounters hazards (and the chance of getting killed).
I'm sure ... (Score:4, Informative)
I'm sure I've seen this before. Ahh, yes here it is [slashdot.org], 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.
Try ten years ago (and 6 weeks ago) (Score:2)
I'm sure I've seen this before. Ahh, yes here it is [slashdot.org] almost two years ago.
Tetris is Hard: NP-Hard [slashdot.org] from 2002!
Or, more recently, Pac-Man Is NP-Hard [slashdot.org] 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.
Pfft, they were... (Score:5, Insightful)
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.
Re: (Score:3)
Re:Pfft, they were... (Score:4, Insightful)
Better than "80's arcade hard" 8-(
No, you don't have an excuse (Score:5, Interesting)
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.
Re:No, you don't have an excuse (Score:5, Insightful)
This post isn't correct. It's just as hard for humans as computers, if you are searching for the optimal solution.
You're claiming it's easier for humans because we don't actually need the optimal solution, which changes the problem.
When you change the terms of the problem to accept a "good enough" solution, there are also computer algorithms that can find "good enough" solutions very quickly and are very useful for problem sets that are out of the realm for a human being to solve in a reasonable amount of time.
Re: (Score:2)
Right good enough is what really works. To get that extra 9 in accuracy just doesn't matter much solving practical problems. This is why AI has failed so far is because to have artificial intelligence, you need to throw in a little artificial stupidity (P=NP).
Human brains solve NP-Hard problems (Score:5, Interesting)
Re: (Score:2)
Re:Human brains solve NP-Hard problems (Score:5, Interesting)
Re: (Score:3)
Nonsense. Just because someone can solve a specific instance of an NP hard problem in a finite amount of time doesn't mean he's capable of solving NP hard problems in P time.
Re: (Score:3)
This suggests to me that reformulating problems of interest into a form that the brain can process (e.g., video games)
That's what "gamification" is. Not a new idea. It even has its own Wikipedia page.
http://en.wikipedia.org/wiki/Gamification [wikipedia.org]
Re: (Score:2)
Sorry, the wiki page is about the way marketing people use it.
Re: (Score:3)
Not exactly... there's a huge difference between getting a solution to a problem, and getting the best solution to a problem.
The traveling salesman problem is a classic NP Hard one. But that doesn't mean you can't get an OK answer just by looking at the possible routes and making a pretty good choice. Human brains (and computer algorithms) can get 'pretty good' answers on many NP Hard issues. That's not the same as finding the best solution. I wager no human has ever gotten the 'optimal' play through of any
Re: (Score:2)
There isn't a huge difference between a pretty good and the best solution in the real world.
Re: (Score:2)
Depends upon what your definition of optimal is. Speed runs are something that people have been doing for a while. I haven't ever watched much of any of the videos, but one site with a lot of videos is http://speeddemosarchive.com./ [speeddemosarchive.com.]
Re: (Score:2)
They are doing this already for pay and then it becomes less of a game.
Infinite Mario (Score:4, Interesting)
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.
What? (Score:3)
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.
Get off my lawn (Score:2)
Those games aren't hard, modern games are just too easy.
Anyone played Demon's Souls? That's how hard games should be.
Re: (Score:2)
Some modern games I've played that are bloody hard are DMC4 and Prince of Persia: Warrior Within. Dunno about Demon's Souls, haven't played it.
It's really interesting (Score:2)
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.
since when is.. (Score:2)
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.
Low scores!?!? (Score:2)
Looks at my name. You think my scores are low?
Next step on this... (Score:2)
Re: (Score:2)
TAS (Score:2)
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.
Fuck NP hard, ya, fuck it hard (Score:2)
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 rememb
Pokemon? NP hard? (Score:2)
Nah, just keep throwing Magikarp out there, no matter what the circumstances. His splash attack is devestating!
Try Battle Kid (Score:2)
Re: (Score:3)
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....
Even more interesting than an NP-hard game is a game that simulates real life. With NP-hard game you know there is an optimal solution and you usually get a chance to try it over and take another decision path if you fail (even if you can't verify the optimality of your decision in polynomial time). In games that simulate real life, you know that you aren't playing optimally, and you don't get to try again and make another different decision, so NP-complete may be the third-most boring class of problems.
Re: (Score:2)
constant is a polynomial of degree 0
c*x^0 + 0 * x + 0 * x^2 + .... = c
Re: (Score:2)
There is only one phrase in the wikipedia article that you need to understand what is NP-hard is assuming you know NP-complete:
A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H (i.e., LTH). In other words, L can be solved in polynomial time by an oracle machine with an oracle for H.
Assuming you do not know what is NP-complete the relevant phrase to understand NP-hard from the article is :
NP-complete is a subset of NP, the set of all decision problems whose solutions can be verified in polynomial time; NP may be equivalently defined as the set of decision problems that can be solved in polynomial time on a nondeterministic Turing machine.
So here is my explanation :
A NP-hard problem is a problem H that can formally be transposed in a polynomial number of steps to a problem L for witch it takes a polynomial amount of time to verify it's solution. Ex.: To verify the traveling sales(TSP) man problem*1 [google.com], given a rou