Classic Nintendo Games Are NP-Hard [Slashdot]

[DP ServBot]

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

Read more of this story at Slashdot.


More...

[kedawa]

What does that even mean?

[NayusDante]

I've yet to see a plain-English explanation of it, but it refers to the complexity of a given problem. It has something to do with how many obstacles lie between the start and end of a given situation.

If you read the actual report, they don't actually cite levels or areas in the games. They create hypothetical levels that, given the rules of the game, present an NP-Hard problem. Problems of that complexity don't necessarily appear in those games as they were originally designed.

If you were writing a bot to play Mario or Donkey Kong Country, this kind of information would be helpful. Metroid and Zelda, however, are a lot more complicated. The study merely examines the problem of getting from one point to another, not finding tools that can assist progress.

[kupomogli]

What's NP Hard mean?

[megasdkirby]

For some reason, I though NP-Hard meant something sexual.

[NayusDante]

What's NP Hard mean?

Non-deterministic Polynomial-time Hard

[misfits859]

Non-deterministic Polynomial-time Hard

Oh. Okay.

[DOAsaturn]

I honestly thought this meant "Non-playable hard" as in "Double Dragon III only gives me one life and throws a ridiculous amount of enemies on the screen. It's NP-hard man!"

Otherwise - interesting read, learned something new