Een onderzoeksteam van het MIT heeft aangetoond dat een aanzienlijk aantal games uit de 2D Super Mario Bros.-serie wordt geclassificeerd als "PSPACE-hard". In de theoretische informatica betekent dit dat het vaststellen of een specifiek level in deze spellen oplosbaar is, behoort tot een van de meest complexe categorieën van computationele problemen.
De zogenaamde MIT Hardness Group heeft in een wetenschappelijke publicatie bewezen dat vijftien verschillende titels binnen de 2D-platformserie van Super Mario Bros. deze status hebben. Voorheen was enkel de oorspronkelijke Super Mario Bros. als PSPACE-hard bekend, een resultaat dat al in 2016 werd gepresenteerd. Hoewel sommige van de bestudeerde games in 2014 al als NP-hard waren aangemerkt, breidt dit nieuwe onderzoek de theoretische complexiteit van de reeks aanzienlijk uit. De theoretische fundamenten voor dit type analyse worden onder meer behandeld in academische modules over NP en PSPACE in videogames, zoals beschikbaar via mit.edu.
De rol van 'deur-gadgets'
Om de PSPACE-hardheid aan te tonen, maakten de onderzoekers gebruik van zogenaamde "door gadgets". Dit zijn specifieke constructies binnen de spelwereld die functioneren als logische poorten. Deze gadgets kunnen worden geopend, gesloten of getraverseerd. Voor elke game werden unieke spelmechanieken gebruikt om deze functionaliteiten te implementeren.
Volgens de publicatie op arxiv.org verschilden deze constructies per titel. Terwijl sommige ontwerpen leken op het werk uit 2016, waren de gadgets voor Super Mario Bros. 2, Super Mario Land 2, Super Mario World 2 en de New Super Mario Bros.-serie fundamenteel anders. De onderzoekers gaven specifiek aan dat het ontwerpen van de "deur" voor Super Mario Bros. 2 een bijzonder grote uitdaging vormde.
Uitzonderingen en NP-hardheid
Niet alle 2D Mario-games konden in de categorie PSPACE-hard worden geplaatst. Voor twee specifieke titels, Super Mario Land en Super Mario Run, bleek het onmogelijk om de benodigde deur-constructies te realiseren. Desondanks konden de wetenschappers wel bewijzen dat deze twee games ten minste NP-hard zijn. Hoewel dit nog steeds wijst op een aanzienlijke computationele complexiteit, is dit minder extreem dan de PSPACE-classificatie.
Het onderzoek is gepresenteerd tijdens de 12e internationale conferentie over 'Fun with Algorithms' (FUN 2024) in La Maddalena, Italië. De volledige details van het onderzoek en de specifieke reducties zijn opgenomen in de erikdemaine.org.
Academische context en toegankelijkheid
Het project is een resultaat van de MIT Hardness Group, met bijdragen van onderzoekers zoals dblp.org, Lilly Hall, Hayashi Layers en Matias Korman. Om de theoretische bewijzen tastbaarder te maken, heeft de groep aanvullend materiaal beschikbaar gesteld. In de documentatie wordt verwezen naar video's waarin de functionele "deuren" in actie te zien zijn.
Daarnaast zijn er speelbare ROM's van de betreffende gadgets beschikbaar via GitHub, waardoor andere informatici en geïnteresseerden de mechanieken zelf kunnen testen. De verspreiding van dit werk is verder gewaarborgd via academische kanalen, waaronder de dagstuhl.de (LIPIcs, volume 291), wat de integratie van dit onderzoek in de bredere informatica-gemeenschap bevestigt.