Zelfs met de krachtigste supercomputer ter wereld is het onmogelijk om op voorhand vast te stellen of bepaalde Super Mario-levels kunnen worden gehaald.
Onderzoekers hebben ontdekt dat het onmogelijk is om op voorhand uit te zoeken of bepaalde levels in de videogameserie Super Mario Bros. kunnen worden voltooid. Zelfs als je meerdere jaren en ‘s werelds krachtigste supercomputer tot je beschikking hebt, moet je de levels eerst spelen om daarachter te komen.
‘We weten niet hoe we kunnen bewijzen dat een spel leuk is, we weten niet wat dat wiskundig betekent, maar we kunnen wel bewijzen dat het moeilijk is. Dat geeft misschien enig inzicht in waarom het leuk is’, zegt informaticus Erik Demaine van het Massachusetts Institute of Technology in de VS.
Nobelprijswinnaar Anne L’Huillier: 'Het duurde 14 jaar voordat ons idee slaagde'
We spraken Nobelprijswinnaar Anne L’Huillier over haar grootste ontdekking en over haar huidige werk.
Moeilijker kan niet
Demaine en zijn collega’s gebruikten technieken uit de computationele complexiteit: de studie van hoe moeilijk en tijdrovend het is om problemen algoritmisch op te lossen. Eerder bewezen de onderzoekers dat uitzoeken of het mogelijk is om bepaalde levels in Super Mario-games te voltooien een ‘NP-moeilijk probleem’ is. Dat is een groep problemen waarbij de complexiteit exponentieel toeneemt, zodat alleen de kleinste problemen uit de groep met een beperkte hoeveelheid computerkracht zijn op te lossen.
Nu hebben Demaine en zijn team aangetoond dat het bepalen van de haalbaarheid van deze Mario-levels niet alleen moeilijk, maar zelfs onmogelijk is. Deze taak valt namelijk in een categorie van problemen die bekendstaat als RE-compleet. Dergelijke problemen kunnen simpelweg niet door een computer worden opgelost, hoe krachtig die ook is en hoe lang je die ook laat rekenen.
Dit geldt voor levels uit verschillende titels in de Mario-serie, waaronder New Super Mario Bros en Super Mario Maker. ‘Moeilijker dan dit kun je het niet maken’, zegt Demaine. ‘Kun je de finish bereiken? Er bestaat geen algoritme dat die vraag in een eindige hoeveelheid tijd kan beantwoorden.’
Veel vijanden
Demaine geeft toe dat er een klein beetje gesjoemeld moest worden om de Mario-levels in deze categorie te laten passen. Ten eerste keken de onderzoekers naar aanpasbare levels, waarin ze honderden of duizenden vijanden op één plek konden plaatsen. Daarvoor verwijderden ze de limieten die de spelmakers hadden gesteld aan het aantal vijanden dat in een level aanwezig kan zijn. Vervolgens konden de onderzoekers de plaatsing van vijanden in een level gebruiken om een zogeheten tellermachine in het spel in te bouwen. Daarmee plaatsten ze in wezen een computer in het spel.
Dankzij deze truc kon het team voor zijn bewijs gebruikmaken van het zogeheten haltingprobleem. Dat zegt dat er in het algemeen geen manier is om vast te stellen of een bepaald computerprogramma ooit zal eindigen of voor altijd zal blijven draaien, behalve door het programma uit te voeren en te kijken wat er gebeurt.
Hierdoor kon het team uiteindelijk bewijzen dat geen enkele analyse van de Mario-levels met zekerheid kan zeggen of het level ooit voltooid kan worden of niet. ‘Het idee is dat je zo’n level alleen kunt halen als dit computerprogramma tot een eind zal komen. We weten dat er geen enkele manier is om te bepalen of dat gebeurt of niet. En dus is er ook geen manier om te bepalen of je het level kunt halen’, zegt Demaine.
