You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914799926902784 |
|---|---|
| author | MIT Hardness Group Ani, Hayashi Demaine, Erik D. Hall, Holden Ruiz, Ricardo Venkat, Naveen |
| author_facet | MIT Hardness Group Ani, Hayashi Demaine, Erik D. Hall, Holden Ruiz, Ricardo Venkat, Naveen |
| contents | 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. Our New Super Mario Bros. constructions fit within one standard screen size. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_10546 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games MIT Hardness Group Ani, Hayashi Demaine, Erik D. Hall, Holden Ruiz, Ricardo Venkat, Naveen Computational Complexity 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. Our New Super Mario Bros. constructions fit within one standard screen size. 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. |
| title | You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2405.10546 |