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."
My favorite NP-hard game is adom. Just try it - see my sig.
#
#\ @ ? Colonize Mars
#
Kid Icarus for Nintendo is the most difficult game in the history of mankind.
Is "NP-hard" the next buzz word?
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.
Sock Puppets: damn_registrars=pudge_confirmer=jimmy_slimmy=raiigunner=cml4524=a_klavan=red4men=ronpaulisanidiot
Now Billy Mitchell's ego can finally get a much needed boost.
I Honestly don't understand what NP refers to.
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.
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."
I'm sure I've seen this before. Ahh, yes here it is, 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.
Lost at C:>. Found at C.
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
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.
Troll is not a replacement for I disagree.
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.
WARNING! This girl exceeds the MAXIMUM SAFE standards established by the FDA for BRATTINESS
For a gentler introduction, see P vs. NP.
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" becomes viable...
The IPS file for Super Mario Forever, the map pack featured in the Super Mario Frustration video, is still available.
Almost any interesting game will be NP-hard. Mostly only boring games will be NP-complete though.
NP is the second-most boring class of problems (and it might even be the most-boring class, if NP=P).
Look into some lecture of AI-planing, most problem solving problems are EXP(EXP())- complete, and if you want optimal solutions, it might even get harder....
Even more interesting than an NP-hard game is a game that simulates real life. With NP-hard game you know there is an optimal solution and you usually get a chance to try it over and take another decision path if you fail (even if you can't verify the optimality of your decision in polynomial time). In games that simulate real life, you know that you aren't playing optimally, and you don't get to try again and make another different decision, so NP-complete may be the third-most boring class of problems. As a simple example, take the secretary problem. Of course if you "replay" the secretary problem, you can get the optimal result (basically a P-problem with order 1), but if you can't, well isn't that more interesting?
On the other hand maybe such a game would be so interesting that it's boring (too much like real life, not escapist enough). Which leaves open the other possiblity that a game can be so boring, that it can be made interesting again. Say like a favorite drinking game, or playing inverse checkers for example.
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 play adom. Doing frequent and successful checks for willpower apparently increases it. Looks like adom is quite good at mimicking real life.
About adom, I especially love the single-life no-saving feature in adom. It trains your skills at solving ultra-complex problems with cold head. I still remember the adrenaline rush when in this turn-based game I was fighting Andor Drakon, planning many moves ahead and thinking several seconds before making next move. Lovely, especially the adrenaline!
One of my high scores says: "He saved the world with his brave efforts and became a great ruler while saving himself 2 times." Indeed I saved only two times in this game, and this winning-marathon took about 40h of playing. But also it took one month of dying, before I played the winning game. Heh, my last win was in 2008. But still I need to resist playing it now again. There is lots of interesting research for me to do.
Violence! This is very funny, but for me there is as much violence in adom, as you have in a game of chess. Indeed you can beat the pawns in chess, and they are killed. Same thing in adom, only more complex.
I wonder why I can't have that much fun from other "popular" games like Elder Scrolls or Twilight Princess. Only Diablo 1 is comparable, albeit much worse.
well... back to QED
#
#\ @ ? Colonize Mars
#