PSPACE-Hard 2D Super Mario Games: Thirteen Doors
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914756772757504 |
|---|---|
| author | MIT Hardness Group Ani, Hayashi Demaine, Erik D. Hall, Holden Korman, Matias |
| author_facet | MIT Hardness Group Ani, Hayashi Demaine, Erik D. Hall, Holden Korman, Matias |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_10380 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | PSPACE-Hard 2D Super Mario Games: Thirteen Doors MIT Hardness Group Ani, Hayashi Demaine, Erik D. Hall, Holden Korman, Matias Computational Complexity 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. |
| title | PSPACE-Hard 2D Super Mario Games: Thirteen Doors |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2404.10380 |