Slashdot Mirror

← Back to Stories (view on slashdot.org)

Classic Nintendo Games Are NP-Hard

Posted by Soulskill on 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."

12 of 204 comments (clear)

  1. Buzz by Anonymous Coward · · Score: 3, Insightful

    Is "NP-hard" the next buzz word?

    1. Re:Buzz by TheVelvetFlamebait · · 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.

      --
      You know, there is a difference between trolling and pointing out the flaws in your reasoning. Just saying.
    2. Re:Buzz by Anonymous Coward · · Score: 1, Insightful

      It has a well-defined meaning for the people who understand it.

    3. Re:Buzz by Anonymous Coward · · 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.

    4. Re:Buzz by jellomizer · · Score: 4, Insightful

      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.

      --
      If something is so important that you feel the need to post it on the internet... It probably isn't that important.
    5. Re:Buzz by phantomfive · · Score: 4, Insightful

      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. 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!), 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.

      --
      "First they came for the slanderers and i said nothing."
  2. Pfft, they were... by Anubis+IV · · 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.

    1. Re:Pfft, they were... by GameboyRMH · · Score: 3, Insightful

      Better than "80's arcade hard" 8-(

      --
      "When information is power, privacy is freedom" - Jah-Wren Ryel
  3. Re:Kid Icarus by lambent · · Score: 3, Insightful

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

    Battletoads was hard because it was designed poorly.

  4. Re:Kid Icarus by Hatta · · Score: 2, Insightful

    Ahem. Silver Surfer.

    --
    Give me Classic Slashdot or give me death!
  5. Re:Kid Icarus by elrous0 · · Score: 4, Insightful

    Desert Bus is WAY harder to beat.

    --
    SJW: Someone who has run out of real oppression, and has to fake it.
  6. Re:No, you don't have an excuse by Whatsisname · · Score: 4, 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.