Nav: Home

'Super Mario Brothers' is harder than NP-hard

May 31, 2016

Completing a game of "Super Mario Brothers" can be hard -- very, very hard.

That's the conclusion of a new paper from researchers at MIT, the University of Ottawa, and Bard College at Simon's Rock. They show that the problem of solving a level in "Super Mario Brothers" is as hard as the hardest problems in the "complexity class" PSPACE, meaning that it's even more complex than the traveling-salesman problem, or the problem of factoring large numbers, or any of the other hard problems belonging to the better-known complexity class NP.

In a standard "Super Mario Brothers" game, Mario runs across terrain that unspools from the right side of the screen. While battling monsters, he must complete various tasks, which can involve navigating brick structures that may rise from the ground plane of the game but may also hang in the air unsupported. The completion of a level is marked by Mario's reaching a flagpole.

The new paper doesn't attempt to establish that any of the levels in commercial versions of "Super Mario Brothers" are PSPACE-hard, only that it's possible to construct PSPACE-hard levels from the raw materials of the "Super Mario" world.

The work follows on a paper from two years ago, with two of the same coauthors, which showed that "Super Mario Brothers" is at least as hard as the hardest problems in NP. But at the time, the researchers couldn't determine whether it was any harder. "PSPACE is its final home," says Erik Demaine, an MIT professor of electrical engineering and computer science and a co-author on both papers.

Demaine and his colleagues -- Giovanni Viglietta, a postdoc in electrical engineering and computer science at the University of Ottawa and a coauthor of the earlier paper; and Aaron Williams, a professor of computer science at Bard College at Simon's Rock -- will present their new paper at the International Conference on Fun with Algorithms next week.

Questions of proportion

Theoretical computer scientists categorize algorithms according to their execution times, which they measure in terms of the number of data items the algorithms manipulate. An algorithm for finding the largest number in a list of N numbers, for instance, has a running time proportional to N. An algorithm that, say, calculates the flying distances between N airports on a map has a running time proportional to N^2, because for every airport, it has to calculate the distance to each of the others.

Algorithms whose running times are proportional to N raised to a power are called "polynomial." A polynomial algorithm whose running time is proportional to, say, N^3 is slower than one whose running time is proportional to N. But those differences pale in comparison to the running times of exponential algorithms, whose running time is proportional to 2^N.

If an algorithm whose execution time is proportional to N takes a second to perform a computation involving 100 elements, an algorithm whose execution time is proportional to N^3 takes almost three hours. But an algorithm whose execution time is proportional to 2^N takes 300 quintillion years.

The complexity class NP is a set of problems whose solutions can be verified in polynomial time, even if finding those solutions takes -- as far as anyone knows -- exponential time. To use the most familiar example, factoring a 1,000-digit number is probably beyond the capacity of all the computers in the world in the lifetime of the universe, but verifying a solution -- multiplying the factors together -- is something a smartphone could do.

Like NP, PSPACE contains problems that appear to require exponential time to solve. But the hardest problems in PSPACE -- the PSPACE-hard problems -- also take exponential time to verify. In some sense, that makes PSPACE a natural place for a video game to reside. Figuring out how to complete a fiendishly difficult level of "Super Mario Brothers" could take a long time, but so could navigating that level, even with the solution in hand.

Fundamental components

In their earlier paper, Demaine, Viglietta, and colleagues described a generic video-game structure that they call a locked door. The structure must have a path through it that can be either safe to traverse or not, and there must be a way for the player to switch the state of the path.

Because the locked door has two possible states, it can represent a bit of computer memory, and because it has a path through it that can be opened or closed, it can serve as an element of a computational circuit. The researchers were able to show that any computational problem could be described by locked doors strung together in the right configuration. If the problem is exponentially hard, then figuring out how to complete the level is exponentially hard, too.

In the earlier paper, Demaine, Viglietta, and their colleagues demonstrated how to build locked doors in several versions of the game "Donkey Kong Country," but they couldn't figure out how to build one in "Super Mario Brothers." "We thought it was impossible," Demaine says.

But it's not. The locked door described in the new paper uses a monster from the "Mario Brothers" world called a "spiny," which will move back and forth continuously between two barriers but will never spontaneously jump either of them. As the spiny approaches a barrier, however, Mario can bump the floor beneath it and send it over. In the researchers' new locked door, if the spiny is on one side of a barrier, the path through the structure is untraversable; if it's on the other, the path is open. And separate paths through the structure allow Mario to bump the spiny from one side to the other.

Fun and games

The result could have implications beyond the design of ever-more-baffling games of "Super Mario Brothers." Mathematically, video games are not very different from computational models of real-world physical systems, and the tools used to prove complexity results in one could be adapted to the other.

"I'm really excited about these kinds of hardness proofs, and I've been pushing them a lot in the last couple years," Demaine says. "I even taught an entire course about them. I'm pretty good at them, just through practice, and I wanted to somehow distill that into a form that other people could learn. So the class was a first attempt to do that. But it's already a really useful reference. I go and look at these lecture notes all the time to see, 'Is that variation of this problem hard?'"

"My hope is through this class and these kinds of papers to encourage more people to do this, because it really does build up a lot of expertise that makes it easier to conquer problems," he continues. "The more practice we get as a collective, the better we are at solving these types of problems. And it's important to know the limitations of algorithms."

Massachusetts Institute of Technology

Related Algorithm Articles:

Algorithm personalizes which cancer mutations are best targets for immunotherapy
As tumor cells multiply, they often spawn tens of thousands of genetic mutations.
Universal algorithm set to boost microscopes
EPFL scientists have developed an algorithm that can determine whether a super-resolution microscope is operating at maximum resolution based on a single image.
Algorithm designed to map universe, solve mysteries
Cornell University researchers have developed an algorithm designed to visualize models of the universe in order to solve some of physics' greatest mysteries.
Algorithm tells robots where nearby humans are headed
A new tool for predicting a person's movement trajectory may help humans and robots work together in close proximity.
Algorithm to transform investment banking with higher returns
A University of Bath researcher has created an algorithm which aims to remove the elements of chance, bias or emotion from investment banking decisions, a development which has the potential to reduce errors in financial decision making and improve financial returns in global markets.
Algorithm provides customized caffeine strategy for alertness
A web-based caffeine optimization tool successfully designs effective strategies to maximize alertness while avoiding excessive caffeine consumption, according to preliminary results from a new study.
New algorithm optimizes quantum computing problem-solving
Tohoku University researchers have developed an algorithm that enhances the ability of a Canadian-designed quantum computer to more efficiently find the best solution for complicated problems, according to a study published in the journal Scientific Reports.
Machine learning algorithm helps in the search for new drugs
Researchers have designed a machine learning algorithm for drug discovery which has been shown to be twice as efficient as the industry standard, which could accelerate the process of developing new treatments for disease.
Researchers create algorithm to predict PEDV outbreaks
Researchers from North Carolina State University have developed an algorithm that could give pig farms advance notice of porcine epidemic diarrhea virus (PEDV) outbreaks.
New algorithm provides a more detailed look at urban heat islands
Urban areas are warmer than the adjacent undeveloped land, a phenomenon known as the urban heat island effect.
More Algorithm News and Algorithm Current Events

Top Science Podcasts

We have hand picked the top science podcasts of 2019.
Now Playing: TED Radio Hour

Why do we revere risk-takers, even when their actions terrify us? Why are some better at taking risks than others? This hour, TED speakers explore the alluring, dangerous, and calculated sides of risk. Guests include professional rock climber Alex Honnold, economist Mariana Mazzucato, psychology researcher Kashfia Rahman, structural engineer and bridge designer Ian Firth, and risk intelligence expert Dylan Evans.
Now Playing: Science for the People

#540 Specialize? Or Generalize?
Ever been called a "jack of all trades, master of none"? The world loves to elevate specialists, people who drill deep into a single topic. Those people are great. But there's a place for generalists too, argues David Epstein. Jacks of all trades are often more successful than specialists. And he's got science to back it up. We talk with Epstein about his latest book, "Range: Why Generalists Triumph in a Specialized World".
Now Playing: Radiolab

Dolly Parton's America: Neon Moss
Today on Radiolab, we're bringing you the fourth episode of Jad's special series, Dolly Parton's America. In this episode, Jad goes back up the mountain to visit Dolly's actual Tennessee mountain home, where she tells stories about her first trips out of the holler. Back on the mountaintop, standing under the rain by the Little Pigeon River, the trip triggers memories of Jad's first visit to his father's childhood home, and opens the gateway to dizzying stories of music and migration. Support Radiolab today at