Slashdot Mirror
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."
Harder than Battletoads? I think not.
Skype is too convoluted... Now I'm reverse-engineering the Kyoto Protocol.
Now Billy Mitchell's ego can finally get a much needed boost.
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.
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.
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.
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".
There's no sense in being precise when you don't even know what you're talking about. -- John von Neumann
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.
For a gentler introduction, see P vs. NP.
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.
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.)
Ezekiel 23:20
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!
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.
Desert Bus is WAY harder to beat.
SJW: Someone who has run out of real oppression, and has to fake it.
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.
The enemies of Democracy are
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."
I Honestly don't understand what NP refers to.
Nintendo Power.
http://crummysocks.com