211service.com
Pac-Man bewezen NP-moeilijk door computationele complexiteitstheorie
In de afgelopen jaren zijn een paar toegewijde wiskundigen begonnen met het bestuderen van de computationele complexiteit van videogames. Hun doel is om de inherente moeilijkheidsgraad van de spellen te bepalen en hoe ze verband kunnen houden met elkaar en andere problemen.
Vandaag onthult Giovanni Viglietta van de Universiteit van Pisa in Italië een enorme hoeveelheid werk op dit gebied waarin hij een groot aantal games uit de jaren 80 en 90 classificeert, waaronder Pac-Man, Doom, Tron en vele andere.
Het werk van Viglietta omvat verschillende stappen. De eerste is om te bepalen tot welke klasse van computationele complexiteit het spel behoort. Vervolgens gaat hij na of als je weet hoe je het spel moet oplossen, je ook veel andere problemen in dezelfde klasse kunt oplossen, een eigenschap die complexiteitstheoretici 'hardheid' noemen. Ten slotte bepaalt hij of het spel compleet is, wat betekent dat het een van de ‘moeilijkste’ in zijn klasse is.
Zijn aanpak is relatief eenvoudig. Hij doorloopt eerst een aantal bewijzen die aantonen dat elk videospel met specifieke speleigenschappen in een bepaalde complexiteitsklasse valt.
Vervolgens classificeert hij de spellen op basis van speleigenschappen die ze hebben.
Een speltype houdt bijvoorbeeld in dat een speler zich door een landschap beweegt en een aantal locaties bezoekt. Hij noemt dit 'location traversal' en een voorbeeld is een spel waarin bepaalde items door een landschap worden verspreid en het doel is om ze allemaal te verzamelen.
Bij sommige locatie-traversal-spellen kan elke locatie slechts één keer worden bezocht. Zogenaamde padspellen voor eenmalig gebruik kunnen downhill-races omvatten.
Vervolgens gebruikt hij grafentheorie om te bewijzen dat elk spel dat zowel locatietraversal als paden voor eenmalig gebruik vertoont, NP-moeilijk is, dat is dezelfde klasse van complexiteit als het probleem van de handelsreiziger.
Het blijkt dat Pac-Man in deze categorie valt (het bewijs omvat het verspreiden van krachtpillen rond het doolhof op een manier die paden voor eenmalig gebruik afdwingt).
Hij laat zien hoe games ook in andere complexiteitscategorieën vallen. Games met drukkussens om deuren te openen en te sluiten zijn bijvoorbeeld moeilijk voor PSPACE als elke deur wordt bestuurd door twee drukplaten. Doom valt in deze categorie.
Enzovoorts.
De resulterende lijst is indrukwekkend. Hier zijn een paar van zijn resultaten:
Boulder Dash (First Star Software, 1984) is NP-hard.
Deflektor (Vortex Software, 1987) bevindt zich in L.
Prince of Persia (Brøderbund, 1989) is PSPACE-compleet.
Tron (Bally Midway, 1982) is NP-hard.
Zie onderstaand document voor de volledige lijst en redenering.
Dat was duidelijk een liefdeswerk voor Viglietta, gezien de titel van zijn paper: Gaming Is A Hard Job, But Iemand moet het doen!
Interessant is dat hij zegt dat dit soort analyse niet nodig is voor moderne games. De meeste recente commerciële games bevatten Turing-equivalente scripttalen die het gemakkelijk maken om onbeslisbare puzzels te ontwerpen als onderdeel van de gameplay, zegt hij.
In zekere zin maakt dat deze oudere games des te charmanter.
Referentie: arxiv.org/abs/1201.4995 :Gamen is een zware klus, maar iemand moet het doen!