Researchers at the Massachusetts Institute of Technology (MIT) have opened new frontiers in the study of computational complexity with an unconventional approach, using the popular video game Super Mario Bros. as a testing ground. The team, led by Professor Erik Demaine, has determined that certain levels of the game are undecidable, that is, there is no algorithm capable of predicting whether they can be overcome without actually playing them, even with the most powerful supercomputer in the world.
This finding comes from a detailed study of several titles in the franchise, including New Super Mario Bros. and Super Mario Maker, recently published on the preprint server arXiv.
“Of the 2D Mario games published since New Super Mario Bros., we have shown that all of them, except Super Mario Wonder, are undecidable,” the scientists state in their study.
Super Mario Bros.: problems impossible to solve
Using computational complexity tools, the researchers discovered that some levels of the game belong to a category of mathematical problems known as NP-hard, the resolution of which becomes exponentially more complex. But Demaine and her team went further and showed that, for certain levels, answering whether they can be overcome is not only difficult, but impossible.
“It can’t be more difficult,” Demaine commented to New Scientist. “Can you reach the finish line? “There is no algorithm that can answer that question in a finite time,” she added.
Simply put, these undecidable problems, known as RE-complete, cannot be solved by any computer, regardless of its power or the time given to it.
“It’s fascinating to imagine that difficulty could be a substitute for fun,” Demaine tells New Scientist, who points out that we still don’t fully understand what makes a game fun from a mathematical perspective. However, the indecipherability inherent to these levels could offer clues to the appeal of the challenges they present, Demaine muses.
Simulation of a counting machine
To reach these conclusions, the researchers created custom levels, filling a single point with hundreds of enemies and removing the limits of game editors. This approach allowed them to build a counting machine within the game, a theoretical model that simulates the operation of a computer.
Using this method, they were able to relate the problem to the famous stall problem, which states that it is not possible to determine whether a computer program will terminate or run indefinitely except by running it. Thus, they demonstrated that no analysis can predict with certainty whether a level can be completed.
These investigations not only enrich mathematical and computational theory, but also suggest a new way of understanding video games and their design. So the next time you’re faced with a Mario level, remember that you’re dealing with one of the most complex puzzles in computing.
Keep reading:
* A closed copy of Super Mario 64 is auctioned for $1.5 million dollars
* Best-selling Nintendo Switch games
* Man discovers he has a tumor thanks to his Nintendo Switch!