Communications of the ACM
'super Mario Brothers' Is 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