Je leest:

Wiskundig vastgesteld: Mario is complex

Wiskundig vastgesteld: Mario is complex

Auteur: | 8 april 2012

Sommige problemen kunnen door een computer efficiënt worden opgelost, andere niet. In de complexiteitstheorie bestaat het vermoeden dat een bepaalde categorie van niet-efficiënt-op-te-lossen problemen, de zogeheten NP-volledige problemen, in feite allemaal hetzelfde zijn. In die categorie bevindt zich ook Mario, het befaamde Nintendospel uit de jaren tachtig en negentig van de vorige eeuw. Dat hebben wetenschappers van het Massachusetts Institute of Technology bewezen.

Een analyse van de computationele complexiteit van diverse Nintendospelletjes, waaronder Mario, Donkey Kong, Legend of Zelda en Pokémon, bewijst dat deze spelletjes verdomd moeilijk zijn. Moeilijk, in de zin dat het praktisch onmogelijk is om vast te stellen of een spel, hoe goed je ook speelt, überhaupt tot een goed einde gebracht kan worden.

Mario moet navigeren door een wereld vol met vijanden en obstakels. Zijn acties zijn beperkt tot lopen, hardlopen, kruipen en springen. Door het combineren van acties, kan hij meer geavanceerde acties uitvoeren, om zijn vijanden te ontlopen.

De versies die op de markt zijn gebracht, zijn natuurlijk zo ontworpen dat ze te doen zijn. Ook in het moeilijkste level is het nog mogelijk om Mario veilig langs alle bananenschillen, bliksemschichten, vliegende inktvissen en andere ongemakken te loodsen.

Erik Demaine van het Massachusetts Institute of Technology en zijn collega’s bestudeerden versies zonder die beperking: de obstakels kunnen in principe ook zodanig voorbijkomen, dat het voor Mario onmogelijk is om de eindstreep te halen, hoe goed je ook speelt. In hun geïdealiseerde versie kan het speelveld willekeurig groot worden. De vraag is nu: hoe bepaal je of het mogelijk is om de finish te halen?

De onderzoekers hebben bewezen dat deze vraag NP-volledig is. Dat betekent dat het beslissen of een spel tot een goed einde gebracht kan worden, ongeveer even moeilijk is als het ontbinden van een groot getal in zijn priemfactoren, of het vinden van de optimale route voor een reiziger die een aantal steden moet bezoeken (het befaamde Handelsreizigersprobleem). Naar efficiënte methoden om dergelijke problemen op te lossen, wordt al jaren gezocht, maar zonder succes. Daarom geloven de meeste wiskundigen dat zo’n efficiënt algoritme niet bestaat.

Donkey Kong.

Zulke intrinsiek moeilijke problemen heten ‘NP’ (non-deterministisch polynomiaal). De rekentijd om zulke problemen via trial and error op te lossen, groeit exponentieel naarmate de omvang van het probleem groter wordt. In het geval van het handelsreizigersprobleem is dat het aantal te bezoeken steden, bij de priemfactorisatie het aantal cijfers van het te factoriseren getal en bij de Nintendospelen de grootte van het speelveld.

Daartegenover staan de P-problemen (polynomiaal). Dat zijn de problemen die een computer relatief snel kan oplossen. Bijvoorbeeld het sorteren van een lijst getallen op grootte: de rekentijd neemt dan ongeveer evenredig toe met de lengte van de lijst.

Van de NP-problemen nemen sommige een speciale plek in. Dat zijn de zogeheten NP-volledige problemen. Voor die problemen geldt: als je voor één NP-volledig probleem een efficiënt algoritme vindt, werkt dit bij álle NP-problemen. En als je voor één NP-volledig probleem kunt bewijzen dat een efficiënt algoritme niet bestaat, geldt datzelfde voor alle NP-volledige problemen.

Pokémon.

Mocht je voor Mario, of een van die andere Nintendogames, een efficiënt oplossingsalgoritme kunnen vinden, dan heb je bewezen dat P = NP, dus dat álle NP-problemen – dat zijn er duizenden! – efficiënt op te lossen zijn, inclusief het ontbinden van grote getallen in priemfactoren. Bovendien ben je dan een miljoen dollar rijker, want het P-versus-NP-probleem staat op de lijst van zeven millenniumproblemen.

P = NP zou overigens een ramp betekenen voor de bankenwereld, want internetbankieren is dan niet meer mogelijk: de beveiliging daarvan berust nou juist op het feit dat het ontbinden van grote getallen praktisch niet uitvoerbaar is. De meeste wiskundigen geloven echter dat P ≠ NP. Dus denk nog even goed na voordat je probeert Mario op te lossen.

Het artikel van de MIT-onderzoekers is hier te vinden.

Zie ook:

Lees meer over games op Wetenschap24

Dit artikel is een publicatie van NEMO Kennislink.
© NEMO Kennislink, sommige rechten voorbehouden
Dit artikel publiceerde NEMO Kennislink op 08 april 2012

Discussieer mee

0

Vragen, opmerkingen of bijdragen over dit artikel of het onderwerp? Neem deel aan de discussie.

NEMO Kennislink nieuwsbrief
Ontvang elke week onze nieuwsbrief met het laatste nieuws uit de wetenschap.