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."
Buzz (Score:3, Insightful)
Is "NP-hard" the next buzz word?
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:Kid Icarus (Score:3, Insightful)
There's a pretty big difference between "hard" and "fundamentally broken".
Battletoads was hard because it was designed poorly.
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:Buzz (Score:1, Insightful)
It has a well-defined meaning for the people who understand it.
Re:Kid Icarus (Score:3, Insightful)
Ahem. Silver Surfer.
Re:Buzz (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:Pfft, they were... (Score:4, Insightful)
Better than "80's arcade hard" 8-(
Re:Kid Icarus (Score:5, Insightful)
Desert Bus is WAY harder to beat.
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: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.