Pac-Man prouvé NP-difficile par la théorie de la complexité computationnelle

Au cours des dernières années, quelques mathématiciens dévoués ont commencé à étudier la complexité informatique des jeux vidéo. Leur objectif est de déterminer la difficulté inhérente aux jeux et comment ils pourraient être liés les uns aux autres et à d'autres problèmes.

Aujourd'hui, Giovanni Viglietta à l'Université de Pise en Italie dévoile un corpus de travaux herculéens dans ce domaine dans lequel il classe un grand nombre de jeux des années 80 et 90 dont Pac-Man, Doom, Tron et bien d'autres.

Le travail de Viglietta comporte plusieurs étapes. La première consiste à déterminer la classe de complexité de calcul à laquelle appartient le jeu. Ensuite, il détermine si savoir comment résoudre le jeu permet également de résoudre de nombreux autres problèmes de la même classe, une propriété que les théoriciens de la complexité appellent « dureté ». Enfin, il détermine si le jeu est complet, ce qui signifie qu'il est l'un des « plus difficiles » de sa catégorie.

Son approche est relativement simple. Il travaille d'abord sur un certain nombre de preuves montrant que tout jeu vidéo avec des propriétés de jeu spécifiques tombe dans une certaine classe de complexité.

Il classe ensuite les jeux en fonction de leurs propriétés ludiques.

Par exemple, un type de jeu implique un joueur se déplaçant à travers un paysage visitant un certain nombre d'endroits. Il appelle cela « parcours de localisation » et un exemple serait un jeu dans lequel certains objets sont éparpillés dans un paysage et le but est de tous les collecter.

Certains jeux de traversée de lieux permettent de visiter chaque lieu une seule fois. Les jeux de piste à usage unique peuvent inclure des courses de descente.

Il utilise ensuite la théorie des graphes pour prouver que tout jeu présentant à la fois des parcours de localisation et des chemins à usage unique est NP-difficile, c'est la même classe de complexité que le problème du voyageur de commerce.

Il s'avère que Pac-Man entre dans cette catégorie (la preuve consiste à distribuer des pilules de puissance dans le labyrinthe d'une manière qui impose des chemins à usage unique).

Il montre comment les jeux entrent également dans d'autres catégories de complexité. Par exemple, les jeux qui comportent des coussins de pression pour ouvrir et fermer les portes sont PSPACE-hard si chaque porte est contrôlée par deux plaques de pression. Doom entre dans cette catégorie.

Etc.

La liste qui en résulte est impressionnante. Voici quelques-uns de ses résultats :

Boulder Dash (First Star Software, 1984) est NP-hard.

Deflektor (Vortex Software, 1987) est dans L.

Prince of Persia (Brøderbund, 1989) est PSPACE-complet.

Tron (Bally Midway, 1982) est NP-difficile.

Pour la liste complète et le raisonnement, voir le document ci-dessous.

C'est clairement un travail d'amour pour Viglietta, étant donné le titre de son article : Le jeu est un travail difficile, mais quelqu'un doit le faire !

Fait intéressant, il dit que ce type d'analyse n'est pas nécessaire pour les jeux modernes. La plupart des jeux commerciaux récents intègrent des langages de script équivalents à Turing qui permettent facilement la conception d'énigmes indécidables dans le cadre du gameplay, dit-il.

D'une certaine manière, cela rend ces jeux plus anciens encore plus charmants.

Réf : arxiv.org/abs/1201.4995 : Le jeu est un travail difficile, mais quelqu'un doit le faire !

cacher