This repository is a collection of ips patches and level files so you can play the gadgets (pieces of levels) in our proofs that various Super Mario Bros. platforming games are computationally intractable. They were developed during MIT's 6.5440 class in Fall 2023 and subsequently appear in our two papers:
For Super Mario Bros. 3, Super Mario Land 2, and Super Mario World, we build door gadgets which prove PSPACE-hardness.
"PSPACE-Hard 2D Super Mario Games: Thirteen Doors"
by MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, and Matias Korman
in Proceedings of the 12th International Conference on Fun with Algorithms (FUN 2024)
For New Super Mario Bros. Wii, we build a counter machine, proving RE-completeness of a constant-size level in the game.
"You Can’t Solve These Super Mario Bros. Levels: Undecidable Mario Games"
by MIT Hardness Group, Hayashi Ani, Erik D. Demaine, Holden Hall, Ricardo Ruiz, and Naveen Venkat
in Proceedings of the 12th International Conference on Fun with Algorithms (FUN 2024)
For Super Mario Bros. 3, Super Mario Land 2, and Super Mario World, we provide IPS files which can be patched to an unmodified ROM using a utility like Floating IPS.
For New Super Mario Bros. Wii, we provide level files which can be added to a complete New Super Mario Bros. Wii filestructure to create a playable ROM.