Super Mario Bros. is Harder/Easier Than We Thought

Authors Erik D. Demaine, Giovanni Viglietta, Aaron Williams



PDF
Thumbnail PDF

File

LIPIcs.FUN.2016.13.pdf
  • Filesize: 0.54 MB
  • 14 pages

Document Identifiers

Author Details

Erik D. Demaine
Giovanni Viglietta
Aaron Williams

Cite AsGet BibTex

Erik D. Demaine, Giovanni Viglietta, and Aaron Williams. Super Mario Bros. is Harder/Easier Than We Thought. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.13

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.
Keywords
  • video games
  • computational complexity
  • PSPACE

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta. Classic Nintendo games are (computationally) hard. Theoretical Computer Science, 586:135-160, 2015. Google Scholar
  2. Speed Demos Archive. Super Mario Bros. URL: http://kb.speeddemosarchive.com/Super_Mario_Bros.
  3. doppleganger. A comprehensive Super Mario Bros. disassembly. URL: http://giovanniviglietta.com/files/SMB/source.asm.
  4. Michael Garey and David S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979. Google Scholar
  5. TASVideos. Super Mario Bros. URL: http://tasvideos.org/GameResources/NES/SuperMarioBros.html.
  6. TV Tropes. Nintendo Hard. URL: http://tvtropes.org/pmwiki/pmwiki.php/Main/NintendoHard.
  7. Tom C. van der Zanden. Parameterized complexity of graph constraint logic. In Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), Leibniz International Proceedings in Informatics (LIPIcs), pages 282-293. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.IPEC.2015.282.
  8. Vargomax V. Vargomax. Generalized Super Mario Bros. is NP-complete. In Proceedings of the 6th Binarennial Workshop about Symposium on Robot Dance Party of Conference in Celebration of Harry Q. Bovik’s 0x40th Birthday (SIGBOVIK 2007), pages 87-88, 2007. Google Scholar
  9. Giovanni Viglietta. Gaming is a hard job, but someone has to do it! Theory of Computing Systems, 54(4):595-621, 2014. Google Scholar
  10. Giovanni Viglietta. Lemmings is PSPACE-complete. Theoretical Computer Science, 586:120-134, 2015. Google Scholar
  11. Video Game Sales Wiki. Mario. URL: http://vgsales.wikia.com/wiki/Mario.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail