Forgot your password?
typodupeerror
NES (Games) Math Games News

Classic Nintendo Games Are NP-Hard 204

Posted by Soulskill
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."
This discussion has been archived. No new comments can be posted.

Classic Nintendo Games Are NP-Hard

Comments Filter:
  • by Janek Kozicki (722688) on Friday March 09, 2012 @12:43PM (#39301795) Journal

    My favorite NP-hard game is adom. Just try it - see my sig.

  • Scoring is NP-hard (Score:2, Interesting)

    by DigiShaman (671371) on Friday March 09, 2012 @12:46PM (#39301829) Homepage

    I thought all games were NP-hard. That is, the path to optimal scoring is dynamic based on random events (true or simulated random). For example in a standard shoot-em-up, you're always thinking about the order in which kill an object and in what particular order all while avoiding being shot at.

  • pointless (Score:5, Interesting)

    by khipu (2511498) on Friday March 09, 2012 @12:49PM (#39301871)

    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.

  • by Chemisor (97276) on Friday March 09, 2012 @12:54PM (#39301929)

    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.

  • by cyberfringe (641163) on Friday March 09, 2012 @12:56PM (#39301963) Journal
    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".
  • Infinite Mario (Score:4, Interesting)

    by wisnoskij (1206448) on Friday March 09, 2012 @12:57PM (#39301975) Homepage

    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.

  • by K. S. Kyosuke (729550) on Friday March 09, 2012 @01:03PM (#39302061)
    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.)
  • by timeOday (582209) on Friday March 09, 2012 @01:08PM (#39302133)
    NP hard doesn't necessarily mean something is hard in any practical sense. It might be a tiny problem instance (like traveling salesman with 3 or 4 cities). Or more commonly, it might be very hard to definitely find an optimal answer, but easy to get a good answer (within a couple percent of optimum), which is the normal way living things get by in the world. And since the computer is solving a mathematical model of your real problem and not the real problem itself, optimizing the model to the tenth decimal point is often a complete waste of time.

The bogosity meter just pegged.

Working...