Illustration via Christine Daniloff/MIT
Anyone who has played Super Mario Brothers can tell you how hard the game is, but now analysts have crunched the numbers, scientifically proving that it ranks high on a scale of complexity.
The complexity of early video games is often cited by nostalgic old-school gamers who feel the current generation of online multiplayer gamers get an easy ride with very little challenge.
Now, researchers from MIT have carried out a detailed analysis of the 1985 Nintendo classic Super Mario Brothers, which has shown that the game is not just hard, but really hard.
It’s all about computer science
The researchers showed that the problem of solving a level in Super Mario Brothers is as hard as the hardest problems in the complexity class known as PSPACE.
This makes it more complex than another complexity class called NP, which itself comes from computer science, which uses N as a measurement of the amount of time it takes an algorithm to execute.
So, for example, an algorithm that 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.
Let’s get polynomial
Algorithms whose running times are proportional to N raised to a power are called polynomial.
This plays into the complexity class NP, which is a set of problems whose solutions can be verified in polynomial time, something which the smartphone in your pocket can do quite adequately.
As with NP, PSPACE contains problems that appear to require exponential time to solve but also to verify, meaning that figuring out how to complete a challenging level of Super Mario Brothers could take a long time, but so could navigating that level, even with the solution in hand.
So, what now?
So what, aside from proving what everyone who played the game knew, ramifications for computer science could this analysis have?
“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,” said co-author of the paper, Erik Demaine.
“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.”
