If you grew up thinking the original “Super Mario Brothers” was entirely way too challenging at some points, then don’t feel bad, because top computer scientists at the University of Ottawa and Bard College would agree with you.
In fact, according to MIT’s news site, a game of “Super Mario Brothers” can be just as rigorous as the hardest problems in the “complexity class,” PSPACE.
PSPACE is a facet of computational complexity theory which involves solving all decision problems by using a polynomial amount of space.
This means that some computer scientists believe that Super Mario Bros. can be more complex than the “traveling-salesman problem,” factoring large numbers, or any of the complex problems that make computer science majors lose sleep at night everywhere.
In the original Super Mario game, players traverse the beloved plumber across the entire two-dimensional realm of the Toadstool Kingdom. From the left side of the screen towards the right, Mario’s journey unwinds until reaching that long sought-after flagpole, or the Princess who can’t seem to stay put.
Sounds simple enough, and certainly not on par with the rigors of computer science. But computer scientists claim that players of Super Mario can go beyond the commercial level design and possibly venture through levels of PSPACE difficulty.
CSAIL principal investigator of the Super Mario difficulty level and MIT professor of electrical engineering and computer science, Erik Demaine, said, “PSPACE is its final home.” He indicates that the game does indeed have the potential to produce head-splitting computational level design.
Demaine co-authored a paper two years ago on computer science and Mario with his colleagues — Giovanni Viglietta (postdoc in electrical engineering and computer science at the University of Ottawa), and Aaron Williams (professor of computer science at Bard College at Simon’s Rock).
The trio only discovered that Super Mario is at least harder than your typical NP equation in computer science back then. Next week, at the International Conference on Fun with Algorithms, the computer science elite will expand on their previous Super Mario research with evidence showing that the game could be harder than they originally thought.
The earlier paper primarily touched on fundamental components describing a generic video-game structure that they call a “locked door.”
Super Mario Bros. — a standard classic, being as generic as they come — possesses the “locked door,” which has a path through it that can be either safe to traverse or not.
Given that the player has the option of choosing the safe path to their best ability — i.e. not falling into a lava pit or becoming a snack for a Piranha Plant — Super Mario Bros. players experience these decisions all of the time.
— meh 🙂 (@mehishartist) January 27, 2016
And this is where computer science comes into play when playing Super Mario. Since the locked door has two possible states, it can represent a bit of computer memory.
The path of the locked door opening and closing serves as an algorithmic element of a computational circuit in computer science.
Computer scientists say that basically any computational problem could be described by locked doors strung together in the right configuration, MIT writes.
In theory, if the problem is exponentially hard, then figuring out how to complete the level is exponentially hard, too.
Damaine says that mathematically, games like Super Mario Bros. aren’t that different from real life complexities, and that hopefully more research like this will be conducted in the future to better understand them.
“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. 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.”
Perhaps the “M” on Mario’s hat stood for Mathematics all along?
[Photo by ngorkapong/Shutterstock]