Super Mario Brothers—the iconic Nintendo video game that spearheaded the 1985 home console revolution—is hard. Objectively, mathematically, scientifically hard. This is one of the key findings of a new paper due to be presented at the International Conference on Fun with Algorithms in La Maddalena Italy.
The study compares Super Mario Bros to PSPACE puzzles, widely considered the most challenging algorithms in computational complexity theory, because they can theoretically take forever to solve and forever to verify. Designating Super Mario Bros as PSPACE-hard puts Nintendo's fiendishly complex levels in company with forms of Boolean algebra, Lambda calculus and, alas, checkers.
"I'm really excited about these kinds of hardness proofs," coauthor Erik Demaine, professor of electrical engineering and computer science at MIT, said in a press statement. "It really does build up a lot of expertise that makes it easier to conquer problems. 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."
Now, nobody is saying that any one Super Mario Bros level—even one of these nightmares—is as difficult as Lambda calculus. But Demaine found that, using the raw materials available in Super Mario Bros, they could concoct levels that would theoretically take an exponential amount of time for a computer to figure out and an exponential amount of time to actually perform in the game.
This is, more or less, the definition of a PSPACE puzzle. Computer scientists effectively pigeonhole algorithms based on how long it would take a computer to solve them. Since computers are incredibly good at math, this consideration is almost always based not on the complexity of the math but on the amount of time and processing power it would take to run all of the numbers and then verify them.
To borrow an example from Demaine and his team, if we tell a computer to find the largest number in a long list of numbers called n (because we enjoy forcing our robot slaves carry out useless tasks), how long it takes to solve that problem is directly related to how long the list of numbers is—in other words, it's proportional to n.
As problems become more complex, however, that dynamic changes. If we tell a computer to calculate distances between n airports, for instance, the run time of that problem is proportionate to n^2. This is called a polynomial algorithm, and puzzles that fall within that realm are called NP. Then there's PSPACE. These algorithms take exponential time to solve—in other words, 2^n instead of n^2.
If that math is getting too theoretical, try this illustration: if an algorithm proportional to n takes one second to solve a puzzle with 100 elements, it would take two hours to solve the n^3 version—and 300 quintillion years to solve the 2^n (PSPACE) version.
For this study, researchers built a theoretical Mario Bros level that involved a door that Mario must enter, blocked by a Spiny—yes, that spiked turtle thing—pacing on a platform. In order to access the door, Mario must head butt Spiny in one of his classic Question Block maneuvers, clearing the path to the door. Seems simple enough.
But beneath this simple level is a world of computational possibilities. Essentially, the door has a path that is either safe to traverse or not, depending on a specific action from the player (bumping Spiny). Since there are two possible states, the researchers motion that the one-door version of their Mario level represents one bit of computer memory that can be either 1 or 0—an accessible door or a blocked door.
Add a few doors and a few Spinies, however, and you can theoretically concoct an exponentially hard level (remember 2^n, which took 300 quintillion years to solve?). And if those doors are arranged in a configuration that makes the problem PSPACE hard, beating the level will take an exponential amount of time. Even stranger, as the computer is chugging along processing these exponential strings of 1s and 0s, it'll be doing almost the exact same math as if it were solving a problem in Lamda calculus or Boolean algebra.
In other words, it is as hard for a computer to solve an exponential Super Mario Bros level as it is for that same computer to perform some types of calculus. The authors admit that we don't necessarily need to know this right now—because the fate of the planet does not depend on how long it would take a computer to solve a Super Mario Brothers level so complex that only a computer could develop it in the first place. But that doesn't mean there won't be applications down the line for the math.
"From the point of view of complexity theory, studying video games is interesting mostly for didactical reasons," coauthor Fabrizio Grandoni, professor at University of Applied Sciences and Arts of Southern Switzerland, said in a press statement. "But 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."