Super Mario Bros. Is Harder/Easier than We Thought
Mario is back! In this sequel, we prove that solving a generalized level of Super Mario Bros. is PSPACE-complete, strengthening the previous NP-hardness result (FUN 2014). Both our PSPACE-hardness and the previous NP-hardness use levels of arbitrary dimensions and require either arbitrarily large sc...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
2016
|
| Online Access: | http://hdl.handle.net/1721.1/103079 https://orcid.org/0000-0003-3803-5703 |
| _version_ | 1826210172323758080 |
|---|---|
| author | Demaine, Erik D. Viglietta, Giovanni Williams, Aaron |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Viglietta, Giovanni Williams, Aaron |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | Mario is back! In this sequel, we prove that solving a generalized level of Super Mario Bros. is PSPACE-complete, strengthening the previous NP-hardness result (FUN 2014). Both our PSPACE-hardness and the previous NP-hardness use levels of arbitrary dimensions and require either arbitrarily large screens or a game engine that remembers the state of off-screen sprites. We also analyze the complexity of the less general case where the screen size is constant, the number of on-screen sprites is constant, and the game engine forgets the state of everything substantially off-screen, as in most, if not all, Super Mario Bros. video games. In this case we prove that the game is solvable in polynomial time, assuming levels are explicitly encoded; on the other hand, if levels can be represented using run-length encoding, then the problem is weakly NP-hard (even if levels have only constant height, as in the video games). All of our hardness proofs are also resilient to known glitches in Super Mario Bros., unlike the previous NP-hardness proof. |
| first_indexed | 2024-09-23T14:45:02Z |
| format | Article |
| id | mit-1721.1/103079 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:45:02Z |
| publishDate | 2016 |
| record_format | dspace |
| spelling | mit-1721.1/1030792022-09-29T10:21:03Z Super Mario Bros. Is Harder/Easier than We Thought Demaine, Erik D. Viglietta, Giovanni Williams, Aaron Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Demaine, Erik D. Mario is back! In this sequel, we prove that solving a generalized level of Super Mario Bros. is PSPACE-complete, strengthening the previous NP-hardness result (FUN 2014). Both our PSPACE-hardness and the previous NP-hardness use levels of arbitrary dimensions and require either arbitrarily large screens or a game engine that remembers the state of off-screen sprites. We also analyze the complexity of the less general case where the screen size is constant, the number of on-screen sprites is constant, and the game engine forgets the state of everything substantially off-screen, as in most, if not all, Super Mario Bros. video games. In this case we prove that the game is solvable in polynomial time, assuming levels are explicitly encoded; on the other hand, if levels can be represented using run-length encoding, then the problem is weakly NP-hard (even if levels have only constant height, as in the video games). All of our hardness proofs are also resilient to known glitches in Super Mario Bros., unlike the previous NP-hardness proof. 2016-06-09T14:59:32Z 2016-06-09T14:59:32Z 2016-06 Article http://purl.org/eprint/type/ConferencePaper http://hdl.handle.net/1721.1/103079 Demaine, Erik D., Giovanni Viglietta, and Aaron Williams. "Super Mario Bros. Is Harder/Easier than We Thought." 8th International Conference of Fun with Algorithms (June 2016). https://orcid.org/0000-0003-3803-5703 en_US http://www2.idsia.ch/cms/fun16/accepted-papers/ Proceedings of the 8th International Conference of Fun with Algorithms Creative Commons Attribution http://creativecommons.org/licenses/by/4.0/ application/pdf MIT web domain |
| spellingShingle | Demaine, Erik D. Viglietta, Giovanni Williams, Aaron Super Mario Bros. Is Harder/Easier than We Thought |
| title | Super Mario Bros. Is Harder/Easier than We Thought |
| title_full | Super Mario Bros. Is Harder/Easier than We Thought |
| title_fullStr | Super Mario Bros. Is Harder/Easier than We Thought |
| title_full_unstemmed | Super Mario Bros. Is Harder/Easier than We Thought |
| title_short | Super Mario Bros. Is Harder/Easier than We Thought |
| title_sort | super mario bros is harder easier than we thought |
| url | http://hdl.handle.net/1721.1/103079 https://orcid.org/0000-0003-3803-5703 |
| work_keys_str_mv | AT demaineerikd supermariobrosishardereasierthanwethought AT vigliettagiovanni supermariobrosishardereasierthanwethought AT williamsaaron supermariobrosishardereasierthanwethought |