Ordinateurs

Pac-Man est NP-difficile, comme le problème du voyageur de commerce – High-teK.ca

Ce site peut gagner des commissions d’affiliation à partir des liens sur cette page. Conditions d’utilisation.

Un chercheur italien avec un penchant pour jeux rétro – ou peut-être cherchez-vous simplement une excuse pour jouer à des jeux au nom de la science ! – a utilisé la théorie de la complexité computationnelle pour décider, une fois pour toutes, à quel point les jeux vidéo sont difficiles. Dans une entreprise véritablement épique, Giovanni Viglietta de l’Université de Pise a élaboré la difficulté théorique de 13 jeux anciens, dont Pac-Man, Perte, Lemmings, Prince de Perseet Tiret de rocher.

Pour commencer, Viglietta définit quelques mécanismes de jeu de base et les trie en catégories de théorie de la complexité. Traversée de lieux et chemins à usage unique, ala Pac-Man, est NP-difficile. Plaques de pression, ala Prince de Perse ou Portail, est PSPACE-difficile s’il y a deux plaques de pression, et NP-difficile s’il n’en faut qu’une seule pour ouvrir une porte. Dans le cas des commutateurs, un commutateur est P-hard, deux sont NP-hard et trois ou plus sont PSPACE-hard.

Viglietta utilise ensuite ces caractéristiques pour classer chacun des 13 jeux. Tiret de rocherqui consiste à traverser une carte parsemée de rochers, est NP-difficile. Prince de Persegrâce à ses plaques de pression, est PSPACE-complet. Perteavec ses multiples commutateurs, est PSPACE-hard (et Viglietta affirme que la plupart des autres FPS et jeux d’aventure sont les mêmes).

Lemmings, NP-dursLes lemmings se sont avérés un peu plus difficiles à classer : si vous utilisez uniquement Bashers et Miners, c’est un problème de traversée et NP-difficile. Viglietta n’essaie pas de s’attaquer à la complexité de l’utilisation d’autres types de lemmings. Un tronçon similaire lui permet de classer StarCraft comme NP-difficile, où chaque joueur essaie de produire les bonnes unités pour lui permettre de parcourir un certain chemin (jusqu’à la base ennemie).

Psssssst :  Le MIT perfectionne la détection précise et bon marché des mouvements à travers les murs et des battements de cœur grâce au Wi-Fi - High-teK.ca

Si vous n’avez jamais entendu parler de la théorie de la complexité computationnelle, l’exemple le plus connu est le problème de voyageur de commerce (TSP), qui est NP-difficile. Dans le TSP, vous devez concevoir l’itinéraire le plus optimal qui visite une liste d’emplacements. Cela peut être optimisé comme l’itinéraire le plus court, le plus rapide, le chemin de moindre résistance, etc. Des variantes du TSP sont utilisées pour optimiser les systèmes de transport, les conceptions de CPU, les algorithmes informatiques, etc. PSPACE représente des problèmes et des puzzles beaucoup plus complexes qui prennent en compte des jeux comme Mahjong, Reversi ou Perte. Si vous voulez en savoir plus, aller sur Wikipédia – mais attention, la théorie de la complexité est un peu bête.

Lire la suite sur Examen de la technologieou consulter le document de recherche (qui a le meilleur nom de tous les temps)

[Image credit]

Bouton retour en haut de la page