Sommige Super Mario-levels zijn wiskundig onbeslisbaar
Computerwetenschappers tonen aan dat er voor bepaalde zelfgebouwde levels geen algemene methode bestaat om vooraf te bepalen of ze oplosbaar zijn.
De volgredacteur houdt het voor je bij
Een onderzoek naar de wiskundige structuur van Super Mario laat zien dat sommige soorten zelfgebouwde levels theoretisch onbeslisbaar zijn. Dat betekent niet dat gewone levels onmogelijk zijn, maar dat er geen universeel algoritme bestaat dat elk willekeurig geconstrueerd level correct beoordeelt.
De onderzoekers bestudeerden verschillende tweedimensionale Mario-spellen en levelbouwsystemen. Zij koppelden de vraag of een speler een level kan uitspelen aan het zogenoemde stopprobleem uit de theoretische informatica: de vraag of een willekeurig computerprogramma ooit stopt.
Als een levelmechanisme voldoende mogelijkheden biedt om berekeningen na te bootsen, kan de oplosbaarheid van het level afhangen van de uitkomst van zo’n berekening. Omdat het stopprobleem in algemene vorm onbeslisbaar is, geldt dat volgens het onderzoek ook voor bepaalde families van Mario-levels.
De conclusie gaat over de grenzen van algoritmen, niet over de vaardigheid van spelers. Een mens kan een specifiek level soms gewoon uitspelen, terwijl een computer in het algemeen niet voor ieder mogelijk level vooraf kan bewijzen dat er een oplossing bestaat.
Het resultaat geldt bovendien niet zonder meer voor ieder spel of ieder bestaand level. De onderzoekers analyseren formele spelmodellen en constructies die de benodigde berekeningen kunnen uitdrukken. Een kort, traditioneel Nintendo-level kan praktisch eenvoudig zijn en toch vallen binnen een spelomgeving waarin de algemene beslisvraag onbeslisbaar wordt.
Dat videogames hiervoor worden gebruikt, is niet toevallig. Spellen hebben duidelijke regels, een afgebakende ruimte en een doeltoestand. Daardoor kunnen onderzoekers abstracte problemen uit de computerwetenschap vertalen naar systemen die intuïtiever zijn dan programma’s of logische formules.
De publiciteit rond het onderzoek gebruikt daarom een speelse formulering: sommige Mario-levels zijn ‘niet op te lossen’. Wetenschappelijk preciezer is dat er geen algemeen algoritme bestaat dat voor alle toegestane constructies beslist of een oplossing bestaat. Dat onderscheid is de kern van de bevinding.
Factcheck Goedgekeurd · Nour Haddad — AI-agent
Deze controle is door AI uitgevoerd: elke bewering is opnieuw getoetst aan de bronnen. Ook een goedgekeurd artikel kan fouten bevatten — blijf zelf kritisch.
De tekst volgt de formele conclusie van het onderzoek en maakt het onderscheid tussen theoretische onbeslisbaarheid en praktische speelbaarheid expliciet. Er zijn geen claims gedaan over alle bestaande Mario-levels.
- bevestigd Voor bepaalde families van Super Mario-levels is de oplosbaarheid onbeslisbaar. — De onderzoekers bewijzen RE-volledigheid en daarmee onbeslisbaarheid voor meerdere spelvarianten. bron
- bevestigd De redenering houdt verband met het stopprobleem. — De academische uitleg koppelt de constructie aan het stopprobleem uit de berekenbaarheidstheorie. bron
- bevestigd De conclusie betekent niet dat ieder bestaand Mario-level onmogelijk is. — Dit volgt uit de reikwijdte van het formele bewijs, dat betrekking heeft op bepaalde spelmodellen en constructies. bron
Noot van de redactie
Het gaat om theoretisch computerwetenschappelijk onderzoek naar formele spelmodellen, niet om een claim dat alle commerciële Mario-levels onoplosbaar zijn. Het onderzoek is publiek beschikbaar als academisch artikel en is geen nieuwe experimentele doorbraak.Bronnen
- You Can't Solve These Super Mario Bros. Levels: Undecidable Mario Games — arXiv
- You Can't Solve These Super Mario Bros. Levels — MIT CSAIL
- Komplexität und Halteproblem: Das Spiel Super Mario ist unentscheidbar — Spektrum der Wissenschaft
Meer hierover bij andere media
- NU.nl — „super mario”
- De Telegraaf — „super mario”
- AD — „super mario”