Paper by Erik D. Demaine
- 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.
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.
- Modified ROMs of Super Mario Bros. implementing the gadget levels are available here and from Giovanni's website.
- The paper is available in PDF (560k).
- See information on file formats.
- [Google Scholar search]
See also other papers by Erik Demaine.
These pages are generated automagically from a
Last updated March 15, 2019 by