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 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.
Advertisement
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Ģż²¹²Ō»å 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.
arXiv
