The Computational Complexity of Super Mario Bros: Is it NP-Hard?
Julie Altamirano & Taylor Knibb
Introduction
Throughout the years Super Mario Bros has been a staple Nintendo game among children. Currently there are multiple versions of Super Mario Bros such as Super Mario Galaxy, Super Mario World, Super Mario Maker, etc., but our focus is on the original version released in 1985. In this version, the game’s main character is an Italian plumber named Mario, who explores a world of challenges. There is also a secondary character named Luigi, brother of Mario, who can be controlled if two players are gaming. A single player will control Mario’s persona with the goal of rescuing Princess Peach who has been kidnapped by Bowser, the enemy. Mario is able to complete this task as he travels through different worlds by reaching a final destination in each level of the world. Each world contains a certain amount of levels so Mario must pass every level in the game to accomplish his goal.
Mario and Luigi have multiple abilities such as running, jumping, crouching, and walking. Their abilities can be heightened due to power-ups such as the magic mushroom, super-star, one-up mushroom, and fire flower. These power-ups can help Mario and Luigi increase their life score, height, and strength in order to battle with enemies. Depending on the choices made by the player there are multiple paths that can be taken to reach the final destination. Although this game sounds simple, we will analyze its computational complexity. Is Super Mario Bros as simple as it sounds…
Complexity of NP-Hard Problems
What does NP-hard even mean? NP means nondeterministic polynomial time, which is a class used to describe the complexity level of a problem. If a problem is in NP that means it can be verified in polynomial time. A problem is NP-hard if it reduces to another problem in NP. If problem A reduces to problem B that means A can’t be any harder than B.
3-SAT is a known problem in NP-complete, so if we reduce Super Mario Bros to 3-SAT, then that proves that the game is NP-hard. 3-SAT is a version of the Boolean satisfiability problem SAT, that consists of a Boolean formula which contains clauses of 3 variables connected by an OR (such as A OR B OR C, where A, B, and C are clauses). To solve the problem, the variables are assigned to true or false statements, so that all the clauses evaluate to true at the same time.
General Framework for NP-Hardness
The framework for NP-hardness follows the logic of 3-SAT. The model proposes that players assign either true or false to variables through their actions as a character in the game. The character follows a path determined by these variable assignments, which then determines whether they reach the final gadget. If successful and the character reaches the end, this indicates a combination of the variables evaluated to true, which is similar to the Boolean equation equaling true in the 3-SAT proof. Because 3-SAT is NP-complete, any problem that fits this model is NP-hard.
In order for the authors to know if Super Mario Bros fits this framework, they only need to prove that the game has the “gadgets” necessary for the model. The gadgets consist of a start and finish gadget, variable gadgets (where the player has control and assigns variables to true or false), crossover gadgets (which prevents leakage from crossing paths), and clause gadgets (which the player can unlock and navigate only if they have chosen the correct variables).
Translating the Gadgets Into Super Mario Bros
The start gadget is represented in the game when Mario begins the game as regular Mario. In order to win the game and reach the finish gadget, which is done by jumping on the flag at the end of the level, Mario must have the magic mushroom power-up to be Super Mario. Refer to Figure 2 for context.
The variable gadget is demonstrated in the game by the player’s choices. Once a player makes a decision they cannot undo it which means that when a variable is set to true or false it can not be negated after. As seen in the framework, the variable gadget will determine the clause gadget. In Super Mario Bros the clause gadget is the path that the player is granted due to their choices. For instance in Figure 3, the three blocks represent variables that are specific to that clause statement. Each block can grant Mario with a power-up that can allow the player to continue the game by getting through the fireballs on the left.
Finally the crossover gadget is demonstrated in Super Mario Bros through paths that can only be traversed in a unidirectional way. The following example, Figure 4, shows an instance of a crossover gadget. Mario has two options: either traverse left-to-right or bottom-to-top. Both paths of traversal prohibit leakage from occurring from the vertical path to the horizontal path.
Consequently, Super Mario Bros adheres to the gadgets that are required for the NP-Hard framework. Since these gadgets exist, Super Mario Bros reduces to the NP-hardness framework that the paper established; proving that the game is NP-hard.
Discussion
Although, the game of Super Mario Bros is essentially a children’s game it has an underlying complexity that is prevalent in theory of computation. Though the objectives of the authors of Classic Nintendo Games are (Computationally) Hard is to demonstrate the theory behind Super Mario Bros, it is not necessary to understand the complexity of this proof entirely and we hope our breakdown helped clarify the difficulty of this proof. We recommend reading the paper as it is very interesting and informative while providing readers with some remarkable insights of Super Mario Bros.
It is important to note that the analysis of how Super Mario Bros fits into the framework is done by “generalizing the original Super Mario Bros” and assuming “that the screen size covers the entire level, because the game forbids Mario from going left of the screen” (Aloupis et al.). This presumption and generalization are why certain nuances might’ve been overlooked in this paper. Believing this paper’s result of Super Mario Bros being NP-hard as the one true solution to the complexity of Super Mario Bros isn’t sufficient; further research should be done to assure this analysis truly represents the definitive answer. It may be possible that the game is even more complex than we might think….
References
- https://arxiv.org/pdf/1203.1895
- https://www.mariowiki.com/Super_Mario_Bros
- https://en.wikipedia.org/wiki/Boolean_satisfiability_problem
- https://cs.brown.edu/courses/csci1010/files/doc/notes/Lecture-13-Reducibility.pdf
Both authors equally contributed to the final version of this paper. Julie Altamirano Bello lead the Introduction and the Application of Gadgets in Super Mario Bros portions. Taylor Knibb lead the Complexity of NP-Hard Problems and the General Framework for NP-Hardness portions. Both authors co-wrote the Discussion portion of this post.