One level of Super Mario Bros. is difficult — extremely difficult, a new paper suggests.
A joint research conducted by University of Ottawa, Bard College at Simon's Rock and Massachusetts Institute of Technology (MIT) concluded that solving one level in Super Mario Bros. is as challenging as the most difficult problems in PSPACE complexity class.
This means that completing a level in the famous Nintendo game is even harder than factoring large numbers or the equivalency of P=NP.
In the game, Mario needs to run along terrains that unwind from the screen's right side. When fighting monsters, tasks must be completed, requiring Mario to navigate through the structures and obstacles that may either pop out from the floor or float in the air without any support. Level completion is achieved as soon as Mario secures the flag attached to a pole.
PSPACE Construction
While the researchers are not saying that any particular level of the game is equally hard as the PSPACE, the game provides a desirable avenue to create PSPACE-hard levels in Super Mario using the raw materials.
The researchers followed up on their previous paper [PDF] that detailed Super Mario Bros. is equal to the NP complexity class. During their early research, the authors couldn't establish whether or not the game could become even harder.
The Algorithm
Algorithms, according to theoretical computer scientists, are categorized depending on their times of execution. Execution time is measured by the amount of items in a data that can be manipulated by an algorithm.
For example, finding the biggest number in a list of N numbers has an execution time proportional to N. To find the distance of flight between N airports is proportional to the N2 since the space between each airports must be calculated as well.
Algorithms with a running time raised to a power are considered polynomials. If these polynomial algorithms have an execution time proportional to N3, their running time is longer than those with a running time proportional to N. However, the difference in execution time is much less important compared to the execution time of exponential algorithms that have a running time proportional to 2N.
An algorithm having an execution time proportional to N means that performing a computation for 100 elements would only take one second. On the other hand, an algorithm with an execution time proportional to N3 can take as much as 3 hours to complete, and an exponential algorithm with a completion time of 2N can be completed in 300 quintillion years.
Similar to NP, PSPACE has problems that take exponential time to complete. However, PSPACE-hard problem also requires exponential time for it to be verified. Because of this, a game is a perfect avenue for it to exist.
Finding out the ways to navigate and finish Super Mario Bros.' hard levels may be time-consuming, despite the availability of the solution.
Going Back To The Basics
In their early work, the researchers presented a basic video-game system called "locked door." The locked door has a path players must go through, which can either be safe or unsafe, and the players must be able to convert the path's safety status.
Since the path has two potential statuses, it denotes a small amount of computer memory. Additionally, because the path can be opened or closed, it serves as a computational circuit element.
The authors showed that the lock doors put together in a correct configuration could describe a computational problem. This means the difficulty of level completion is proportional to the difficulty of the computational problem.
The researchers successfully inserted locked door structures into different versions of Donkey Kong Country and did not think it was possible to do it in Super Mario Bros.
In their paper, the team used a monster from Super Mario Bros. called "spiny" that continuously moves back and forth between two obstacles but does not jump at any of them. As the monster moves toward an obstacle, Mario can knock the ground and push it over. However, in the new version with the locked door, when the monster is on one side of the obstacle, the path is closed. If it is on the other one, the path can be traversed. There are also different paths that permit Mario to knock out the monster.
A previous Tech Times report, detailed how an AI system was able to create Super Mario levels by just watching YouTube videos.
With researchers' latest analysis on the video game's problems, future versions of Super Mario Bros. can be improved to make levels even harder.
Fun With Algorithms
"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," said MIT Electrical Engineering and Computer Science professor and co-author Erik Demaine.
University of Applied Sciences and Arts of Southern Switzerland research Professor Fabrizio Grandoni said it would be possible for these complex mathematical results to become useful in the future.
"From the point of view of complexity theory, studying video games is interesting mostly for didactical reasons," said Grandoni. "It's a simple, natural way to attract students to study this specific topic."
The researchers will present their work during the International Conference on Fun with Algorithms in the coming week.
Photo: Ryan Somma | Flickr
