generalized Super Mario Bros. is computationally hard

image credit: Christopher Furniss

An interesting paper by G. Aloupis, E.D. Demaine, and A. Guo has shown NP-completeness of generalized Super Mario and Donkey Kong Country. Also interesting is a paper by "V.V. Vargomax". Among the two, G. Aloupis et al., in their paper entitled "Classic Nintendo Games are (NP-)Hard" have shown a more serious proof; actually, we can set aside the work of "V.V. Vargomax".

The paper "Classic Nintendo Games are (NP-)Hard", which came out in March 2012, has shown at least the NP-hardness of certain classic Nintendo games. They have used a general framework for the design of a particular game level to which 3-SAT, an NP-complete problem, is reducible in polynomial time. NP-complete is a class of mathematical problems, and 3-SAT is a Boolean satisfiability problem, which answers the question about whether a particular Boolean expression returns true. What do these results tell us? They tell us that determining whether a level design of a particular game has a solution, that it can be finished from the starting point, is computationally hard. So if a computer will try to check deterministically whether there is a solution to a particular level, e.g. through brute-force method, it cannot do it in polynomial time unless P=NP. P is a class of mathematical problems that can be solved deterministically in polynomial time, while NP is a class of problems that can be solved non-deterministically in polynomial time. Therefore, obtaining a solution to the given problem is computationally expensive under the current theoretical conditions in which, of course, the practical consequences depend.

The results at least show that the difficulty encountered by the game designers is justified since their work revolves around how the obstacles should be arranged such that the level can be challenging enough for the players but a solution still exists. So in the case of generalized Super Mario Brothers, how can a game designer arrange the blocks, Goombas, Koopas, Firebars, and others such that it can be an interestingly difficult but playable level? No wonder it can be such a struggle to finish the levels of Super Mario. It is a game that requires creativity and ingenuity on the part of the players, and perhaps this is one of the reasons why the game is considered a classic. Right now, several versions of this game exist, but they owe it to the success of the earlier versions. In fact, arguably, Super Mario Bros. 3 is still considered to be one of the best versions of the game even though the newer versions beat it when it comes to the technical aspects such as graphics, world features, and the things that Mario can do.