Depuis les travaux fondateurs de von Neumann et Morgenstern, l’algorithmique des jeux a fait l’objet de recherches considérables en intelligence artificielle (IA). D’un point de vue conceptuel, les jeux sont décrits par des règles qui spécifient, à chaque tour, les informations accessibles aux joueurs, les actions légales que les joueurs peuvent accomplir et les effets (potentiellement incertains) de ces actions. Ainsi, les jeux offrent un cadre simple pour modéliser et étudier de nombreux problèmes de décision séquentielle et de stratégie d’action du monde réel.

Deux grandes tendances ont émergé en IA pour résoudre les jeux : les approches dédiées, qui se concentrent sur la résolution d’un jeu particulier, et les approches génériques, qui peuvent s’appliquer à une grande variété de jeux. Notons que les approches génériques ne s’opposent pas aux approches dédiées : elles s’intéressent à différentes formes d’intelligence des jeux. Tandis que les approches dédiées cherchent à simuler une finesse de raisonnement et d’imagination propres aux experts d’un jeu particulier, les approches génériques visent à simuler les capacités humaines à s’adapter rapidement à de nouveaux jeux en utilisant l’expérience acquise sur d’autres jeux.

Des résultats spectaculaires pour les machines spécialistes

Les approches dédiées ont connu des succès spectaculaires en défiant les plus grands joueurs humains avec, par exemple, Deep Blue pour les échecs et récemment AlphaGo pour le Go. Même s’il est théoriquement possible pour une machine de résoudre de tels jeux en explorant l’arbre de toutes les séquences d’actions possibles, la taille de cet arbre – 10⁸⁰ nœuds pour le jeu d’échecs et 10¹⁵² nœuds pour le jeu de Go – rend une telle exploration impossible en pratique. Ainsi, pour atteindre des performances atteignant, ou dépassant, celles des meilleurs joueurs humains, les approches dédiées se sont efforcées de développer une expertise du jeu permettant de réduire la taille de l’arbre de recherche.

Il y a une vingtaine d'année, Gary Kasparov était battu par Deep Blue, une machine entièrement dédiée aux jeux d'échecs. Le défi des chercheurs est désormais de mettre au point des programmes "généralistes" capables de pratiquer n'importe quel jeu.

Il y a une vingtaine d'année, Gary Kasparov était battu par Deep Blue, une machine entièrement dédiée aux jeux d'échecs. Le défi des chercheurs est désormais de mettre au point des programmes "généralistes" capables de pratiquer n'importe quel jeu.

L.PSIHOYOS/CORBIS

L.PSIHOYOS/CORBIS

Partager

Partager

Pour Deep Blue, cette expertise est donnée sous forme de fonctions d’évaluation des positions, calibrées minutieusement par des spécialistes du jeu d’échecs. Pour AlphaGo, cette expertise est apprise automatiquement, par entraînement sur de nombreuses parties de Go, en utilisant deux réseaux neuronaux à couches profondes, l’un pour prédire le prochain coup (et donc réduire la largeur de l’arbre), l’autre pour prédire la valeur des positions (et donc réduire la profondeur de l’arbre).

L’émergence de programmes généralistes

De manière alternative, les approches génériques visent à jouer intelligemment à une grande variété de jeux, sans expertise ni technologie dédiée à un jeu particulier. Dans ce cadre, le General Game Playing (GGP)1 consiste à développer des algorithmes qui, juste après avoir reçu les règles d’un nouveau jeu, sont capables de jouer correctement à ce jeu sans aucune intervention humaine. Les règles du jeu sont décrites dans un langage logique, appelé Game Description Language (GDL). Les approches génériques recourent elles aussi à des méthodes basées sur l’exploration et la réduction de l’arbre des séquences d’actions possibles, mais elles s’appuient également sur d’autres techniques générales d’apprentissage et de planification utilisées en IA.

Le défi des jeux à information imparfaite

Avec le succès des approches dédiées et les progrès remarquables des approches génériques, on peut naturellement se demander si l’IA sera capable de résoudre, d’ici quelques années, la plupart des jeux. La théorie de la complexité en informatique nous incite cependant à nuancer ces propos. Dans la majorité des cas, les programmes dédiés et génériques sont aujourd’hui restreints aux jeux à information parfaite, où tous les joueurs ont une connaissance totale du plateau de jeu et des actions jouées par leurs adversaires.

Les problèmes de jeu à information imparfaite (appelés Partially Observable Stochastic Games), comme le poker ou Diplomatie, relèvent de classes de complexité bien plus élevées. Des résultats prometteurs ont récemment été obtenus par Cepheus, un programme dédié à une version limitée du Poker, le « heads-up limit Texas hold’em ». Une version étendue de GDL a également été proposée pour modéliser les jeux à information imparfaite. Mais, à cause de la complexité plus grande de ces jeux, nécessitant non seulement de prédire les bonnes actions, mais aussi de raisonner sur les connaissances des autres joueurs, de nombreux progrès restent à faire en IA avant d’atteindre le niveau des joueurs humains.

À lire sur le même sujet : « Jeu de Go : l’ordinateur plus fort que l’humain ? »

Les points de vue, les opinions et les analyses publiés dans cette rubrique n’engagent que leur auteur. Ils ne sauraient constituer une quelconque position du CNRS.