Search Results

Documents authored by Hall, Holden

Document
DOI: 10.4230/LIPIcs.FUN.2024.21
PSPACE-Hard 2D Super Mario Games: Thirteen Doors

Authors: MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, and Matias Korman

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

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.
Cite as

MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, and Matias Korman. PSPACE-Hard 2D Super Mario Games: Thirteen Doors. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.21,
  author =	{MIT Hardness Group and Ani, Hayashi and Demaine, Erik D. and Hall, Holden and Korman, Matias},
  title =	{{PSPACE-Hard 2D Super Mario Games: Thirteen Doors}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.21},
  URN =		{urn:nbn:de:0030-drops-199295},
  doi =		{10.4230/LIPIcs.FUN.2024.21},
  annote =	{Keywords: video games, computational complexity, PSPACE}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.22
You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games

Authors: MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, and Naveen Venkat

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

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.
Cite as

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 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 22:1-22:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.22,
  author =	{MIT Hardness Group and Ani, Hayashi and Demaine, Erik D. and Hall, Holden and Ruiz, Ricardo and Venkat, Naveen},
  title =	{{You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{22:1--22:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.22},
  URN =		{urn:nbn:de:0030-drops-199302},
  doi =		{10.4230/LIPIcs.FUN.2024.22},
  annote =	{Keywords: video games, computational complexity, undecidability}
}
Document
DOI: 10.4230/LIPIcs.FUN.2024.24
Tetris with Few Piece Types

Authors: MIT Hardness Group, Erik D. Demaine, Holden Hall, and Jeffery Li

Published in: LIPIcs, Volume 291, 12th International Conference on Fun with Algorithms (FUN 2024)

Abstract
We prove NP-hardness and #P-hardness of Tetris clearing (clearing an initial board using a given sequence of pieces) with the Super Rotation System (SRS), even when the pieces are limited to any two of the seven Tetris piece types. This result is the first advance on a question posed twenty years ago: which piece sets are easy vs. hard? All previous Tetris NP-hardness proofs used five of the seven piece types. We also prove ASP-completeness of Tetris clearing, using three piece types, as well as versions of 3-Partition and Numerical 3-Dimensional Matching where all input integers are distinct. Finally, we prove NP-hardness of Tetris survival and clearing under the "hard drops only" and "20G" modes, using two piece types, improving on a previous "hard drops only" result that used five piece types.
Cite as

MIT Hardness Group, Erik D. Demaine, Holden Hall, and Jeffery Li. Tetris with Few Piece Types. In 12th International Conference on Fun with Algorithms (FUN 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 291, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{mithardnessgroup_et_al:LIPIcs.FUN.2024.24,
  author =	{MIT Hardness Group and Demaine, Erik D. and Hall, Holden and Li, Jeffery},
  title =	{{Tetris with Few Piece Types}},
  booktitle =	{12th International Conference on Fun with Algorithms (FUN 2024)},
  pages =	{24:1--24:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-314-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{291},
  editor =	{Broder, Andrei Z. and Tamir, Tami},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2024.24},
  URN =		{urn:nbn:de:0030-drops-199322},
  doi =		{10.4230/LIPIcs.FUN.2024.24},
  annote =	{Keywords: complexity, hardness, video games, counting}
}
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact