Forgot your password?
typodupeerror
NES (Games) Math Games News

Classic Nintendo Games Are NP-Hard 204

Posted by Soulskill
from the travelling-plumber-problem dept.
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."
This discussion has been archived. No new comments can be posted.

Classic Nintendo Games Are NP-Hard

Comments Filter:
  • by Janek Kozicki (722688) on Friday March 09, 2012 @12:43PM (#39301795) Journal

    My favorite NP-hard game is adom. Just try it - see my sig.

    • by K. S. Kyosuke (729550) on Friday March 09, 2012 @01:03PM (#39302061)
      Adom may or may not be NP-hard, but first and foremost, it's insanely complex for anyone but a basement gaming zombie. I adore the whole concept, but I don't have the time for playing something like that. The endless stream of "What? The game takes XYZ into account, in addition to all the food, curse, day of the year etc. stuff?" kind of wore me down rather quickly. Now if you excuse me, I'd like to finish eating my uncursed large bat. (Mmm, tastes like chicken.)
      • 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.

        • by Ihmhi (1206036)

          Check out Dwarf Fortress. It's an easy game that's fun to play and certainly not in any way addictive! Really!

          HELP ME.

          • 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)

    by donotlizard (1260586) on Friday March 09, 2012 @12:44PM (#39301803)
    Kid Icarus for Nintendo is the most difficult game in the history of mankind.
    • by kerohazel (913211) on Friday March 09, 2012 @12:46PM (#39301843) Homepage

      Harder than Battletoads? I think not.

      • Re: (Score:3, Insightful)

        by lambent (234167)

        There's a pretty big difference between "hard" and "fundamentally broken".

        Battletoads was hard because it was designed poorly.

        • by Anonymous Coward on Friday March 09, 2012 @01:01PM (#39302043)

          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.

          • Control of player 2 doesn't even work in some parts of Battletoads. How is that not designed poorly?
            • by J-1000 (869558)
              Never experienced the two-player bug, but that does not mean the single player game was designed poorly. I beat the game on single player, and while extremely tough it was certainly not poorly designed or fundamentally broken.
        • 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

        • Battletoads was fairly well programmed by the folks at RARE. Some of the hit detection was off, but otherwise a decent game. I have read it was intentionally made hard to complete to encourage people to buy vs. renting the game. Another game that comes to mind that was well programmed and impossible to beat (mostly because it was long and lacked a save feature) is Blaster Master.
      • by pecosdave (536896) *

        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)

          by gauauu (649169) on Friday March 09, 2012 @01:26PM (#39302327)

          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.

        • You've never seen the SECOND jet ski level then?

          It was harder even still than the first one.

      • Re: (Score:3, Insightful)

        by Hatta (162192)

        Ahem. Silver Surfer.

      • by PRMan (959735)
        C'mon. I solved Battletoads. It was hard, but not that hard.
      • 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.

    • by tepples (727027)
      Is Kid Icarus harder than Super Mario Frustration [youtube.com]? (Video; swearing; mute if at work)
    • by PRMan (959735)
      Not true. My friend solved it. That alone makes it easier than SunSoft's Fester's Quest (which he never solved) or Batman (which he also solved somehow once, he's the only person I knew that solved it).
    • Re:Kid Icarus (Score:5, Insightful)

      by elrous0 (869638) * on Friday March 09, 2012 @01:31PM (#39302385)

      Desert Bus is WAY harder to beat.

    • by Surt (22457)

      Harder than QWOP?

    • Teenage Mutant Ninja Turtles 1 for NES. Most of the game was pretty easy, but once you get to the last few levels, you pretty much have to utilize bugs in the game just to proceed. Same thing for beating Big Boss in Metal Gear.
    • by Gotung (571984)
      You clearly haven't played any non-lemmings titles by Psygnosis
  • "Isn't it great we can usually beat an 8-bit video game?"

    This was the early 2000s on an ancient Nintendo box.
  • Scoring is NP-hard (Score:2, Interesting)

    by DigiShaman (671371)

    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.

    • My understanding, admittedly layman's, is that a lot(all of?) the early console systems were hardware constrained as hell and certainly didn't have the luxury of a hardware RNG or even many peripheral interfaces with the unpredictable outside world, so their games tended to not only lack randomness; but rely on techniques for faking randomness sufficiently rudimentary that "luck manipulation" [tasvideos.org] becomes viable...
      • One situation where then "non-randomness" comes to mind is bowling games. Once you figure out the right settings (angle and speed, some of the fancy games let you choose ball weight and alley slickness too), you can pretty much score a perfect game every time by just repeating the same settings each frame.
    • by Surt (22457)

      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)

    by Anonymous Coward on Friday March 09, 2012 @12:46PM (#39301837)

    Is "NP-hard" the next buzz word?

    • Re:Buzz (Score:5, Insightful)

      by TheVelvetFlamebait (986083) on Friday March 09, 2012 @12:57PM (#39301991) Journal

      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)

        by Anonymous Coward

        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)

        by jellomizer (103300) on Friday March 09, 2012 @01:27PM (#39302337)
        Buzzwords have a well defined meaning... They just abuse them. Using them in cases where they shouldn't be used.

        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.
      • So did REST, if you read the thesis, but it didn't help.

      • Re:Buzz (Score:5, Insightful)

        by phantomfive (622387) on Friday March 09, 2012 @02:17PM (#39303021) Journal
        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 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)

      by robthebloke (1308483) on Friday March 09, 2012 @01:04PM (#39302083)
      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!
      • Re:Buzz (Score:5, Funny)

        by Chris Burke (6130) on Friday March 09, 2012 @01:55PM (#39302713) Homepage

        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 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.
    • 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."

    • by JDG1980 (2438906)

      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)

    by Anonymous Coward on Friday March 09, 2012 @12:46PM (#39301851)

    Now Billy Mitchell's ego can finally get a much needed boost.

  • by Anonymous Coward

    I Honestly don't understand what NP refers to.

    • was about to say the same thing. The Wikipedia entry makes my head hurt, like watching 'Lost' for the first time in the middle of the 2nd season, i throw my hands up in the air and say "WTF?".
      • by tepples (727027) <{tepples} {at} {gmail.com}> on Friday March 09, 2012 @12:59PM (#39302017) Homepage Journal
        There are three classes of problems at issue here:
        • NP, problems for which you can verify a solution in polynomial time (e.g. O(x^2) or O(x^3) operations);
        • NP-hard, problems that are at least as hard as the hardest problems in NP; and
        • NP-complete, problems that are both NP and NP-hard.

        For a gentler introduction, see P vs. NP [wikipedia.org].

      • 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]

      • by Surt (22457)

        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)

      by Anubis IV (1279820) on Friday March 09, 2012 @12:56PM (#39301971)

      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, Funny)

      by basscomm (122302) <{moc.skcosymmurc} {ta} {mmocssab}> on Friday March 09, 2012 @05:58PM (#39306369) Homepage

      I Honestly don't understand what NP refers to.

      Nintendo Power.

  • pointless (Score:5, Interesting)

    by khipu (2511498) on Friday March 09, 2012 @12:49PM (#39301871)

    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.

    • by tepples (727027)

      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?

    • 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)

    by gstoddart (321705) on Friday March 09, 2012 @12:52PM (#39301899) Homepage

    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.

  • Pfft, they were... (Score:5, Insightful)

    by Anubis IV (1279820) on Friday March 09, 2012 @12:53PM (#39301915)

    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.

  • by Chemisor (97276) on Friday March 09, 2012 @12:54PM (#39301929)

    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.

    • by Whatsisname (891214) on Friday March 09, 2012 @01:35PM (#39302437) Homepage

      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.

    • 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).

  • by cyberfringe (641163) on Friday March 09, 2012 @12:56PM (#39301963) Journal
    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".
    • by wstrucke (876891)
      After all, that's how Eli got on the Destiny.
    • by timeOday (582209) on Friday March 09, 2012 @01:08PM (#39302133)
      NP hard doesn't necessarily mean something is hard in any practical sense. It might be a tiny problem instance (like traveling salesman with 3 or 4 cities). Or more commonly, it might be very hard to definitely find an optimal answer, but easy to get a good answer (within a couple percent of optimum), which is the normal way living things get by in the world. And since the computer is solving a mathematical model of your real problem and not the real problem itself, optimizing the model to the tenth decimal point is often a complete waste of time.
    • by Hatta (162192)

      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.

    • 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]

    • by The Raven (30575)

      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

      • There isn't a huge difference between a pretty good and the best solution in the real world.

      • by mattack2 (1165421)

        I wager no human has ever gotten the 'optimal' play through of any of the listed games.

        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.]

    • They are doing this already for pay and then it becomes less of a game.

  • Infinite Mario (Score:4, Interesting)

    by wisnoskij (1206448) on Friday March 09, 2012 @12:57PM (#39301975) Homepage

    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.

  • by snowgirl (978879) on Friday March 09, 2012 @12:57PM (#39301985) Journal

    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.

  • Those games aren't hard, modern games are just too easy.

    Anyone played Demon's Souls? That's how hard games should be.

    • 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.

  • 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.

  • 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.

  • Looks at my name. You think my scores are low?

  • ...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 :)
  • by Dwedit (232252)

    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 rememb

  • Nah, just keep throwing Magikarp out there, no matter what the circumstances. His splash attack is devestating!

You are in a maze of little twisting passages, all different.

Working...