Paper by Erik D. Demaine

Reference:

Erik D. Demaine, Giovanni Viglietta, and Aaron Williams, “Super Mario Bros. is Harder/Easier than We Thought”, in Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), La Maddalena, Italy, June 8–10, 2016, 13:1–13:14.

Abstract:

Mario is back! In this sequel, we prove that solving a generalized level of Super Mario Bros. is PSPACE-complete, strengthening the previous NP-hardness result (FUN 2014). Both our PSPACE-hardness and the previous NP-hardness use levels of arbitrary dimensions and require either arbitrarily large screens or a game engine that remembers the state of off-screen sprites. We also analyze the complexity of the less general case where the screen size is constant, the number of on-screen sprites is constant, and the game engine forgets the state of everything substantially off-screen, as in most, if not all, Super Mario Bros. video games. In this case we prove that the game is solvable in polynomial time, assuming levels are explicitly encoded; on the other hand, if levels can be represented using run-length encoding, then the problem is weakly NP-hard (even if levels have only constant height, as in the video games). All of our hardness proofs are also resilient to known glitches in Super Mario Bros., unlike the previous NP-hardness proof.

Comments:

Modified ROMs of Super Mario Bros. implementing the gadget levels are available here and from Giovanni's website.

Availability:

The paper is available in PDF (560k).

See information on file formats.

[Google Scholar search]