Pacman ist NP-Hart, Prince of Persia ist PSPACE-Complete

Giovanni Viglietta von der Universität of Pisa hat sich damit beschäftigt, wie Computerspiele in Komplexitätsklassen eingeordnet werden können. Er hat sich in seinem Paper auf Arxiv nicht nur einzelnen Spielen gewidmet, sondern ein paar grundlegende Theoreme bewiesen, die er dann auf eine Vielzahl von Spielen anwenden konnte.

Das schöne an dem Paper ist, dass heutige Spiele meist mit eigenen Programmiersprachen gescripted sind, die das Design von unentscheidbaren Problemen sofort ermöglichen. Das macht die heutige Spielwelt für die theoretische Analyse eher uninteressant, so dass sich das Paper den ganzen schönen Oldschool-Krachern widmet, die wir auch teilweise vom Amiga oder dem C64 noch kennen :-) Pacman und Prince of Persia habe ich ja schon erwähnt, aber auch Boulder Dash, Doom, Lemmings und viele Klassiker mehr sind mit von der Partie. Und als besonderes Feature gibt es auch: StarCraft. Herrlich!

Comments

Aufgrund von Caching kann es bis zu zwei Minuten dauern, bis ein Kommentar erscheint!

Da ich gerade ziemlich viel Spam bekomme, und es sich dabei um manuellen Spam handelt, ist die Kommentarfunktion mal ein paar Tage abgeschaltet. Wenn's pressiert, mailt mir!