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

Buzz

[Anonymous Coward]

Is "NP-hard" the next buzz word?

Pfft, they were...

[Anubis IV]

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:Kid Icarus

[lambent]

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

Battletoads was hard because it was designed poorly.

Re:Buzz

[TheVelvetFlamebait]

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:Buzz

[Anonymous Coward]

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

Re:Kid Icarus

[Hatta]

Ahem. Silver Surfer.

Re:Buzz

[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

[jellomizer]

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.

Re:Pfft, they were...

[GameboyRMH]

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

Re:Kid Icarus

[elrous0]

Desert Bus is WAY harder to beat.

Re:No, you don't have an excuse

[Whatsisname]

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:Buzz

[phantomfive]

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.