Classic Nintendo Games Are NP Hard
Written by Alex Armstrong   
Friday, 09 March 2012

You may have have thought that games like Mario, Donkey Kong and so on were hard at the time you were playing them, but you probably didn't guess that they were NP-hard.

NP-hard problems are in a sense the ones that are most difficult to solve by computational means because the time it takes to find a solution tends to increase so quickly with the size of the problem that it just isn't practical to perform the computation.

Now we have some results from computer scientists at Universite Libre de Bruxelles and MIT Computer Science and Artifi cial Intelligence Laboratory (CSAIL) that many classic games contain within them an NP-hard problem. It is a bit like the discovery of a black hole at the center of every galaxy. Should either fact be surprising?

 

mariofinishgadget

 

Computer games often involve an element of search, and many NP-hard problem are about searching for a path or some arrangement of things that satisfies a condition. These are the sorts of things that get put in games to add a splash of logical difficulty to the physical skill of clicking buttons at the right time. 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.

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.

With these small changes it is proved that the following games are NP-hard:

  • Mario
  • Donkey Kong
  • Legend of Zelda
  • Metroid
  • Pokemon

The results apply to

  • Super Mario Bros. 1, 3, Lost Levels
  • Super Mario World
  • Donkey Kong Country 1.3
  • All Legend of Zelda games except Zelda II: The Adventure of Link
  • All Metroid games
  • All Pokemon role-playing games

So are all platform games NP-hard?

Almost certainly not, but are all "good" platform games NP-hard - a much more interesting problem.

More information

Classic Nintendo Games are (NP-)Hard
arXiv:1203.1895v1

Further Reading

NP-Complete - Why so hard?

Physics Is NP Hard
Computational Complexity
Computability
Pancake flipping is hard - NP hard

Super Mario - Nintendo goes forward

Nintendo - the early history

blog comments powered by Disqus

 

To be informed about new articles on I Programmer, subscribe to the RSS feed, follow us on Google+, Twitter, Linkedin or Facebook or sign up for our weekly newsletter.

Banner


Imitation Game Opens London Film Festival
12/10/2014

The film about Alan Turing, starring Benedict Cumberbatch as the mathematician who used his genius as a code-breaker during World War II, had a red carpet premiere in London this week.



DukeScript - Java Everywhere Again?
06/10/2014

DukeScript is a Duke's Choice winner at JavaOne 2014 and it is another take on the Java dream of write once run anywhere. In this case the target is mobile and web apps. 


More News

Last Updated ( Sunday, 11 March 2012 )
 
 

   
RSS feed of news items only
I Programmer News
Copyright © 2014 i-programmer.info. All Rights Reserved.
Joomla! is Free Software released under the GNU/GPL License.