If you’ve ever been frustrated at your inability to complete a level of Super Mario Brothers, here’s a little something to cheer you up. Computer scientists have demonstrated that solving a level in the popular video game is tantamount to solving some of the hardest problems in computational science.
Fun with computer algorithms: Mathematicians say Super Mario Brothers is NP-hard. (Image: Christine Daniloff/MIT)
They’re known as “NP hard” problems, as opposed to the class known as “P” problems, which are relatively easy to solve. A classic example of an NP hard problem is the Travelling Salesman problem: The salesman must find the shortest route to visit 100 cities.
It turns out that navigating the levels of Super Mario Brothers can be equivalent to solving these very difficult mathematical equations, according to MIT computer scientist and engineer Erik Demaine. One caveat: Demaine and his colleagues haven’t shown that the actual levels in commercial versions of Super Mario Brothers meet this standard — only that it is possible to construct levels that are NP hard using the raw materials of the game world, a task that’s actually possible with Super Mario Maker. More on this in a second.
Computer scientists are particularly interested in NP problems, because they’re the cornerstone of cryptography. As MIT’s Larry Hardesty explained in 2009:
Computer science is largely concerned with a single question: How long does it take to execute a given algorithm? But computer scientists don’t give the answer in minutes or milliseconds; they give it relative to the number of elements the algorithm has to manipulate.
Imagine, for instance, that you have an unsorted list of numbers, and you want to write an algorithm to find the largest one. The algorithm has to look at all the numbers in the list: there’s no way around that. But if it simply keeps a record of the largest number it’s seen so far, it has to look at each entry only once. The algorithm’s execution time is thus directly proportional to the number of elements it’s handling — which computer scientists designate N.
So if you’ve got an algorithm to find the largest number in a list of 100 numbers (N=100), the time it takes to complete the task is proportional to N — let’s say one second per operation. Things get more complicated if your algorithm is tasked with, say, figuring out the distances between a given number of airports on a map (where N is the number of airports). It takes longer — three hours rather than one second — because for every airport on the map, the algorithm must calculate the distance to all the others. The real trouble comes with exponential algorithms — say, to factor a 1000-digit number. Then it would take a whopping 300 quintillion years to complete the task.
That’s how long it takes to solve such a problem on its own, but if a computer is given the answer, it can quickly verify that the answer is correct. Think of it as being like a riddle: It’s hard to guess the answer, but once we’re told, the answer seems obvious.
So what does all of this possibly have to do with Super Mario Brothers? A couple of years ago, Demaine and his colleagues examined a generic version of a video game structure they dubbed a “locked door”. This version had two possible states for a path through the game: It’s either safe to use that path, or it is not. Those two states, open or closed, can correspond to the 0s and 1s of computer memory bits.
Demaine et al demonstrated that any computational problem could be represented by locked doors organised in just the right configuration. If a given problem is exponentially hard, so, too, will be figuring out how to complete that game level. In other words, that problem is NP hard.
Using the raw materials of the game world, they figured out how to construct these kinds of locked doors in Donkey Kong Country. They failed to do the same for Super Mario Brothers. They thought building a locked door in Super Mario was impossible and concluded that the game was at least as hard as the most difficult NP problems. But they couldn’t definitively prove that it was harder. For mathematicians, that’s a key distinction.
At the International Conference on Fun with Algorithms taking place this week in La Maddalena, Italy, Demaine will describe how the key to building a locked door in Super Mario Brothers is to exploit a monster called a “spiny”. A spiny can move between two barriers in the game but can’t leap over them — not without Mario’s help, anyway. If Mario bumps the floor just as the spiny approaches the barrier, it pops right over. The locked door Demaine et al eventually constructed is based on which side of a barrier the spiny is on. If it’s on one side, the path is open; if it’s on the other side, the path is closed. And there are separate paths that allow Mario to bump the spiny from one side to the other.
And here’s why it’s not just about video games. Mathematicians and computer scientists often talk about proving the general statement that P does not equal NP. If P does not equal NP, then there is no fast, general way to solve NP hard problems. Conversely, if P does equal NP, that would mean that even seemingly difficult problems could have fast, easy solutions. We just haven’t found them yet. And that has enormous implications for cryptography. All our protected data would become vulnerable. (For what it’s worth, most mathematicians believe it’s far more likely that P does not equal NP.)
Confused? Here’s Simon Singh, author of The Simpsons and Their Mathematical Secrets, giving his own take on P vs NP, illustrated with short clips from The Simpsons and Futurama:
For such an arcane mathematical concept, P vs NP gets cited a lot in popular culture. It’s served as a plot point in Elementary. And Charlie Epps, the brilliant mathematician played by David Krumholtz in Numb3rs, used the game Minesweeper to explain the concept to a group of FBI agents in an early episode.
Demaine has taught a class on such hardness proofs using video games, and thinks this can be an effective educational approach. “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 said in a statement. “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 limits of algorithms.”
[MIT]