Paper by Erik D. Demaine

Reference:

MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, and Matias Korman, “PSPACE-Hard 2D Super Mario Games: Thirteen Doors”, in Proceedings of the 12th International Conference on Fun with Algorithms (FUN 2024), edited by Andrei Z. Broder and Tami Tamir, LIPIcs, volume 291, La Maddalena, Italy, June 4–8, 2024, 21:1–21:19.

BibTeX

@InProceedings{MarioDoors_FUN2024,
  key           = {MIT},
  AUTHOR        = {{MIT Hardness Group} and Hayashi Ani and Erik D. Demaine and Holden Hall and Matias Korman},
  TITLE         = {{PSPACE}-Hard {2D} {Super Mario Games}: Thirteen Doors},
  BOOKTITLE     = {Proceedings of the 12th International Conference on Fun with Algorithms (FUN 2024)},
  bookurl       = {https://sites.google.com/unipi.it/fun2024},
  EDITOR        = {Andrei Z. Broder and Tami Tamir},
  SERIES        = {LIPIcs},
  VOLUME        = 291,
  ADDRESS       = {La Maddalena, Italy},
  MONTH         = {June 4--8},
  YEAR          = 2024,
  PAGES         = {21:1--21:19},

  withstudent   = 1,
  length        = {19 pages},
  updates       = {See <A HREF="https://www.youtube.com/watch?v=gX05TcuMaeg&list=PLCZQ5yzonfsaxrs9jZ41pgMvK4nRHSTXh">videos of the door in action</A> and <A HREF="https://github.com/65440-2023/mario-hardness-gadgets">playable ROMs for the doors</A>.},
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2024.21},
  dblp          = {https://dblp.org/rec/conf/fun/GroupADHK24},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.FUN.2024.21">LIPIcs</A> and as <A HREF="https://arXiv.org/abs/2404.10380">arXiv:2404.10380</A>.},
}

Abstract:

We prove PSPACE-hardness for fifteen games in the Super Mario Bros. 2D platforming video game series. Previously, only the original Super Mario Bros. was known to be PSPACE-hard (FUN 2016), though several of the games we study were known to be NP-hard (FUN 2014). Our reductions build door gadgets with open, close, and traverse traversals, in each case using mechanics unique to the game. While some of our door constructions are similar to those from FUN 2016, those for Super Mario Bros. 2, Super Mario Land 2, Super Mario World 2, and the New Super Mario Bros. series are quite different; notably, the Super Mario Bros. 2 door is extremely difficult. Doors remain elusive for just two 2D Mario games (Super Mario Land and Super Mario Run); we prove that these games are at least NP-hard.

Comments:

This paper is also available from LIPIcs and as arXiv:2404.10380.

Updates:

See videos of the door in action and playable ROMs for the doors.

Length:

The paper is 19 pages.

Availability:

The paper is available in PDF (2224k).

See information on file formats.

[Google Scholar search]