Super Mario Bros prouvé NP-Hard

En janvier, nous avons examiné les travaux de Giovanni Viglietta à l'Université de Pise en Italie, qui avait prouvé la complexité de calcul de nombreux jeux informatiques des années 80 et 90, tels que Pac-Man et Tron.

Viglietta a souligné que ce type d'analyse n'est pas nécessaire pour les jeux modernes car la plupart intègrent des langages de script équivalents à Turing qui permettent facilement la conception d'énigmes indécidables dans le cadre du gameplay.

Cependant, cela laisse encore de nombreux classiques qui ne sont pas encore classés.

Aujourd'hui, Greg Aloupis de l'Université libre de Bruxelles en Belgique et quelques copains comblent ce vide, au moins en partie.

Ces gars-là prouvent que plusieurs jeux Nintendo classiques des années 80 sont tous NP-hard. La liste comprend les trois premières incarnations de Super Mario Bros, Donkey Kong et tous les jeux Legend of Zelda.

Tous ces jeux sont essentiellement les mêmes en ce sens qu'ils commencent à un moment précis dans le but d'atteindre un objectif. La question que se posent Aloupis et co est la suivante : étant donné la position de départ, est-il possible d'atteindre l'objectif ?

S'il est difficile de trancher même cette question, alors il est certainement difficile de trouver un chemin optimal, disent-ils.

Dans ce contexte, ils montrent ensuite que tous les jeux sont essentiellement des versions d'un autre problème appelé 3-SAT, connu pour être NP-complet. Le processus ici consiste à montrer que 3SAT se réduit à ces problèmes dans certaines circonstances, prouvant ainsi qu'ils sont NP-difficiles.

Donc, si votre jeunesse a été mal dépensée en jouant à Super Mario Bros, Donkey Kong ou à l'un des autres jeux que ces gars-là s'avèrent NP-Hard, alors savoir à quel point ils étaient durs pourrait vous rassurer un peu que vous n'avez pas perdu votre temps entièrement. Et puis, probablement pas !

Réf : arxiv.org/abs/1203.1895 : Les jeux Nintendo classiques sont (NP-)difficiles

cacher