Paper by Erik D. Demaine

Reference:

MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, and Naveen Venkat, “You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games”, 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, 22:1–22:20.

BibTeX

@InProceedings{MarioUndecidable_FUN2024,
  key           = {MIT},
  AUTHOR        = {{MIT Hardness Group} and Hayashi Ani and Erik D. Demaine and Holden Hall and Ricardo Ruiz and Naveen Venkat},
  TITLE         = {You Can't Solve These {Super Mario Bros.}\ Levels: Undecidable {Mario} Games},
  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         = {22:1--22:20},

  withstudent   = 1,
  length        = {20 pages},
  updates       = {See <A HREF="https://www.youtube.com/watch?v=vA1UHszv5Mo&list=PLCZQ5yzonfsakI_-C1yQnPTDhneZ6OZ2f">videos of the counters in action</A> and <A HREF="https://github.com/65440-2023/mario-hardness-gadgets">playable ROMs for the counters</A>.},
  papers        = {MarioUndecidable_TCS},
  doi           = {https://dx.doi.org/10.4230/LIPIcs.FUN.2024.22},
  dblp          = {https://dblp.org/rec/conf/fun/GroupADHRV24},
  comments      = {This paper is also available from <A HREF="https://doi.org/10.4230/LIPIcs.FUN.2024.22">LIPIcs</A> and as <A HREF="https://arXiv.org/abs/2405.10546">arXiv:2405.10546</A>.},
}

Abstract:

We prove RE-completeness (and thus undecidability) of several 2D games in the Super Mario Bros. platform video game series: the New Super Mario Bros. series (original, Wii, U, and 2), and both Super Mario Maker games in all five game styles (Super Mario Bros. 1 and 3, Super Mario World, New Super Mario Bros. U, and Super Mario 3D World). These results hold even when we restrict to constant-size levels and screens, but they do require generalizing to allow arbitrarily many enemies at each location and onscreen, as well as allowing for exponentially large (or no) timer.

In our Super Mario Maker reductions, we work within the standard screen size and use the property that the game engine remembers offscreen objects that are global because they are supported by “global ground”. To prove these Mario results, we build a new theory of counter gadgets in the motion-planning-through-gadgets framework, and provide a suite of simple gadgets for which reachability is RE-complete.

Comments:

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

Updates:

See videos of the counters in action and playable ROMs for the counters.

Length:

The paper is 20 pages.

Availability:

The paper is available in PDF (3983k).

See information on file formats.

[Google Scholar search]

Related papers:

MarioUndecidable_TCS (You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games)