Using the tools of computational complexity, researchers have discovered it is impossible to figure out whether certain Super Mario Bros levels can be beaten without playing them, even if you use the world’s most powerful supercomputer.
Figuring out whether certain levels in the Super Mario Bros series of video games can be completed before you play them is mathematically impossible, even if you had several years and the world’s most powerful supercomputer to hand, researchers have found.
“We don’t know how to prove that a game is fun, we don’t know what that means mathematically, but we can prove that it’s hard and that maybe gives some insight into why it’s fun,” says Erik Demaine at the Massachusetts Institute of Technology. “I like to think of hard as a proxy for fun.”
To prove this, Demaine and his colleagues use tools from the field of computational complexity – the study of how difficult and time-consuming various problems are to solve algorithmically. They have previously proven that figuring out whether it is possible to complete certain levels in Mario games is a task that belongs to a group of problems known as NP-hard, where the complexity grows exponentially. This category is extremely difficult to compute for all but the smallest problems.
Now, Demaine and his team have gone one step further by showing that, for certain levels in Super Mario games, answering this question is not only hard, but impossible. This is the case for several titles in the series, including New Super Mario Bros and Super Mario Maker. “You can’t get any harder than this,” he says. “Can you get to the finish? There is no algorithm that can answer that question in a finite amount of time.”
While it may seem counterintuitive, problems in this undecidable category, known as RE-complete, simply cannot be solved by a computer, no matter how powerful, no matter how long you let it work.
Demaine concedes that a small amount of trickery was needed to make Mario levels fit this category. Firstly, the research looks at custom-made levels that allowed the team to place hundreds or thousands of enemies on a single spot. To do this they had to remove the limits placed by the game publishers on the number of enemies that can be present in a level.
They were then able to use the placement of enemies within the level to create an abstract mathematical tool called a counter machine, essentially creating a functional computer within the game.
That trick allowed the team to invoke another conundrum known as the halting problem, which says that, in general, there is no way to determine if a given computer program will ever terminate, or simply run forever, other than running it and seeing what happens.
These layers of mathematical concepts finally allowed the team to prove that no analysis of the game level can say for sure whether or not it can ever be completed. “The idea is that you’ll be able to solve this Mario level only if this particular computation will terminate, and we know that there’s no way to determine that, and so there’s no way to determine whether you can solve the level,” says Demaine.
For more such insights, log into www.international-maths-challenge.com.
*Credit for article given to Matthew Sparkes*