If you've ever got stuck playing Super Mario, don’t feel so bad.
Completing all 8 worlds of “Super Mario Brothers” can be hard — frustratingly hard. But this difficulty may come down to more than just gaming skills.
Erik Demaine, an MIT professor of electrical engineering and computer science, along with co-authors Giovanni Viglietta, a postdoc in electrical engineering and computer science at the University of Ottawa, and Aaron Williams, a professor of computer science at Bard College at Simon’s Rock, showed that the problem of solving a level in “Super Mario Brothers” can be as hard as the hardest problems in the “complexity class” PSPACE — requiring exponential time to both solve an equation and prove it algorithmically.
In layman's terms, all the computers in the world couldn’t solve it, even if they spent the lifetime of the universe trying.
But that doesn’t mean World 1 of the classic video game fits into this category. In fact, none of the “commercial” levels in the game do — even though sometimes it may feel that way. Rather, the researchers say, by using the building blocks of a Mario level, they could achieve that difficulty quite easily.
How? By building a video game structure within Super Mario called a locked door.
A locked door structure must have a path through it that is either safe to travel through or not, but there must also be a way for the player to switch the state of the path. The team’s locked door is the monster called “spiny” which moves back and forth continuously between two barriers, but will never spontaneously jump either of them.
SEE ALSO: A Hacker Stole Over 117 Million LinkedIn Usernames and Passwords
As spiny approaches a barrier, Mario can bump the floor beneath it and send it over. If spiny is on one side of the barrier, the path is impassable, but if spiny is on the other side, the path is open.
The researchers showed that any computational problem could be described by a series of locked doors as long as they are put together in the right way. And if the problem is exponentially hard, then figuring out how to complete the level is also exponentially hard.
According to the researchers, this could have implications far beyond making even tougher versions of Super Mario. Mathematically, video games are not very different from models of real-world physical systems.
“Studying video games is interesting mostly for didactical reasons,” said Fabrizio Grandoni, a research professor at the University of Applied Sciences and Arts of Southern Switzerland, told Larry Hardesty of MIT News. “It’s a simple, natural way to attract students to study this specific topic.”
Grandoni continued, “we know that when we solve mathematical problems, there are chances that at some point in the future, we will need those mathematical results. The mathematics that we use now for some problems was developed centuries ago, in some cases. It was not possible to forecast the applications at the time.”
The team will be presenting their results at the International Conference on Fun with Algorithms next week.
Read next: Collective Gaming Shows Human Can Still Outthink Computers
Facebook comments