Sign In

Communications of the ACM

ACM TechNews

'super Mario Brothers' Is Hard


View as: Print Mobile App Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
Completing a game of Super Mario Brothers can be hard.

Researchers found the problem of solving a level in the "Super Mario Brothers" video game as difficult as the most vexing problems in the PSPACE complexity class.

Credit: Christine Daniloff/MIT

Researchers from the Massachusetts Institute of Technology (MIT), the University of Ottawa, and Bard College found the problem of solving a level in the "Super Mario Brothers" video game is just as challenging as the most vexing problems in the PSPACE complexity class.

The research follows earlier work showing the game is at least as hard as the toughest problems in NP.

The previous research defined a generic video-game structure called a locked door, which must have a path through it that can be either safe to traverse or not, and a way for the player to switch the state of the path. The two possible states of the locked door means it can represent a bit of computer memory, and because it has a path through it that can be opened or closed, it can function as an element of a computational circuit.

The researchers demonstrated that any computational problem could be described by locked doors threaded together in the right configuration, and if the problem is exponentially hard, then determining how to finish the level also is exponentially hard. "Super Mario Brothers" thwarted the researchers' best attempts to build a locked door, but the latest research found a way.

MIT professor Erik Demaine says the work could have significant ramifications, given the mathematical similarity between video games and computational models of real-world physical systems.

From MIT News
View Full Article

 

Abstracts Copyright © 2016 Information Inc., Bethesda, Maryland, USA


 

No entries found