Logo du CNRS Le Journal Logo de CSA Research

Grande enquête « CNRS Le Journal »

Votre avis nous intéresse.

Le CNRS a mandaté l’institut CSA pour réaliser une enquête de satisfaction auprès de ses lecteurs.

Répondre à cette enquête ne vous prendra que quelques minutes.

Un grand merci pour votre participation !

Grande enquête « CNRS Le Journal »
Donner du sens à la science

Vers l’intelligence artificielle généraliste

Vers l’intelligence artificielle généraliste

30.03.2016, par
Développer un programme capable de jouer à n’importe quel jeu de stratégie et battre les joueurs humains constitue un des Graal de l'intelligence artificielle. Le chercheur Frédéric Koriche explique pourquoi et comment on s'en approche.

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 – 1080 nœuds pour le jeu d’échecs et 10152 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.

Kasparov vs Deep Blue
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.
Kasparov vs Deep Blue
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.

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.

On peut
naturellement
se demander
si l’IA sera capable
de résoudre, d’ici
quelques années,
la plupart des jeux.

Les scientifiques français sont de plus en plus nombreux à s’intéresser au GGP. Par exemple, Ary, un programme générique développé par une équipe du Lamsade2, a gagné les compétitions GGP 2009 et 2010. Nos recherches au Centre de recherche en informatique de Lens (Cril) sont fondées sur la programmation par contraintes, qui ajoute à la recherche arborescente un raisonnement par propagation, permettant d’élaguer très rapidement des solutions inutiles. Notre algorithme s’est qualifié parmi les trois premiers lors de la dernière compétition GGP 2015.

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.
 

Notes
  • 1. « General Game Playing : Overview of the AAAI Competition », M. Genesereth et al., AAAI Magazine, 2005, vol. 26 (2) : 62-72.
  • 2. Laboratoire d’analyse et modélisation de systèmes pour l’aide à la décision (Univ. Paris-Dauphine).

Commentaires

0 commentaire
Pour laisser votre avis sur cet article
Connectez-vous, rejoignez la communauté
du journal CNRS