211service.com
Super Mario Bros bewezen NP-moeilijk
In januari keken we naar het werk van Giovanni Viglietta aan de Universiteit van Pisa in Italië, die de rekenkundige complexiteit van veel computerspellen uit de jaren 80 en 90, zoals Pac-Man en Tron, had bewezen.
Viglietta wees erop dat dit soort analyse niet nodig is voor moderne games, omdat de meeste Turing-equivalente scripttalen bevatten die het gemakkelijk maken om onbeslisbare puzzels te ontwerpen als onderdeel van de gameplay.
Dat laat echter nog steeds veel klassiekers over die nog niet zijn geclassificeerd.
Vandaag vullen Greg Aloupis van de Vrije Universiteit van Brussel in België en een paar maatjes dat gat, althans gedeeltelijk.
Deze jongens bewijzen dat verschillende klassieke Nintendo-spellen uit de jaren 80 allemaal NP-hard zijn. De lijst bevat de eerste drie incarnaties van Super Mario Bros, Donkey Kong en alle Legend of Zelda-games.
Al deze spellen zijn in wezen hetzelfde omdat ze op een specifiek punt beginnen met als doel een bepaald doel te bereiken. De vraag die Aloupis en co stellen is deze: is het mogelijk om het doel te bereiken, gegeven de uitgangspositie?
Als het moeilijk is om zelfs deze vraag te beslissen, dan is het zeker moeilijk om een optimaal pad te vinden, zeggen ze.
In deze context laten ze zien dat alle spellen in wezen versies zijn van een ander probleem genaamd 3-SAT, waarvan bekend is dat het NP-compleet is. Het proces hier is om aan te tonen dat 3SAT in bepaalde omstandigheden tot deze problemen reduceert, waarmee wordt bewezen dat ze NP-hard zijn.
Dus als je jeugd verkeerd is besteed aan het spelen van Super Mario Bros, Donkey Kong of een van de andere games die deze jongens NP-Hard bewijzen, dan kan het feit dat je weet hoe moeilijk ze eigenlijk waren, een beetje troost bieden dat je je tijd niet helemaal hebt verspild. Dan weer, waarschijnlijk niet!
Referentie: arxiv.org/abs/1203.1895 : Klassieke Nintendo-spellen zijn (NP-)moeilijk