Le bridge, bac à sable pour une IA hybride et explicable ?
⏱ 4 minDames, échecs, go, poker… On les appelle « jeux de société ». Pourtant, c’est l’IA qui gagne désormais haut la main contre Homo sapiens. Lequel peut se targuer de résister toujours… au bridge. Pour combien de temps encore ?
L’idée d’utiliser les jeux pour expérimenter des méthodes relevant de l’intelligence artificielle est aussi ancienne que l’IA. La communauté du « computer game » (IA pour les jeux) met ainsi l’humain face à des logiciels depuis les années 1950. Chinook a battu des champions de jeu de dames anglaises (English draughts pour les Britanniques, English checkers pour les États-uniens) dès 1994, Deep Blue a maté Homo sapiens aux échecs en 1997, AlphaGo a fait de même au jeu de go en 2016, tout comme plus récemment Libratus en 2017, puis Pluribus en 2019, au poker. Seul le bridge résiste encore. « Ces jeux de réflexion constituent une bonne mesure de l’intelligence des algorithmes que nous développons », résume Tristan Cazenave, professeur à l’université Paris-Dauphine, chercheur au Laboratoire d’Analyse et de Modélisation de Systèmes pour l’Aide à la Décision (Lamsade) et coresponsable du groupe de travail Jeux du GdR (Groupement de Recherche) IA du CNRS.
De la force brute au Deep Learning, en passant par le « General Game Playing »
Tristan Cazenave retrace pour nous les principaux jalons de la recherche en IA appliquée aux jeux : « En 1997, c’est la force brute de Deep Blue, superordinateur conçu par des chercheurs de l’université Carnegie-Mellon (Pittsburgh, Pennsylvanie) et IBM, qui a battu le champion du monde des échecs Garry Kasparov. Grâce à la puissance de la machine, l’algorithme était capable d’explorer l’arbre de tous les coups possibles, jusqu’à une certaine« profondeur« . Après 2007, le défi est de concevoir des programmes de « General Game Playing« , capables de jouer à n’importe quel jeu en découvrant progressivement ses règles. Sur la base des travaux initiés par mon directeur de thèse, Jacques Pitrat, dès 1968, inspirés par les premiers résultats obtenus vers 2005 par une équipe de l’université de Stanford, ces programmes sont évalués dans le cadre d’une compétition annuelle organisée à Stanford. » Compétition que Tristan Cazenave a remportée en 2009 et 2010 avec son acolyte Jean Méhat (université Paris 8).
C’est dans ce cadre qu’ont été notamment développés les algorithmes de recherche arborescente « Monte Carlo » (Monte Carlo Tree Search, MCTS). Ces algorithmes explorent l’arbre des possibles en faisant un compromis entre l’exploitation des choix qui semblent prometteurs et l’exploration des branches encore peu analysées. En 2015, Tristan Cazenave a conçu le dernier en date, Generalized Rapid Action Value Estimation¹ (GRAVE).
En 2016, AlphaGo a été particulièrement salué. Cette combinaison de Monte Carlo Tree Search, de réseaux de neurones profonds et d’apprentissage par renforcement développée par DeepMind (filiale de Google) a battu un des meilleurs joueurs mondiaux de go, Lee Sedol. Ses successeurs, AlphaZero et surtout MuZero, sont eux capables d’apprendre par eux-mêmes à gagner à toutes sortes de jeux. Avec ces mêmes méthodes d’apprentissage par renforcement, en 2017, Libratus, une IA conçue par des chercheurs de l’université Carnegie Mellon, battait quatre grands joueurs de poker (précisément au « Texas hold’em no limit », une de ses variantes les plus jouées). Et deux ans plus tard, Pluribus, développée par Facebook et ces mêmes chercheurs, renouvelait l’exploit au cours de parties bien plus complexes, à six joueurs.
Le bridge continue de défier l’IA
Dès la fin des années 1990, les résultats encourageants obtenus par l’IA dans le domaine des jeux ont été perçus comme une promesse de révolutionner des domaines comme la recherche de médicaments ou la cybersécurité. « Mais, de fait, il y a eu très peu d’applications de grande envergure, les recherches en IA pour les jeux sont un gros échec de ce point de vue-là », constate Véronique Ventos, chercheure associée au Laboratoire de recherche en informatique de l’université Paris-Saclay. Elle a rejoint la communauté du computer game un peu par hasard, en 2013, entraînée par Olivier Teytaud, chercheur INRIA (désormais chez Facebook) dans le but d’affronter ce qui reste un des défis majeurs de cette communauté, le bridge².
Pourquoi le bridge résiste-il toujours à l’IA ? « C’est un jeu dont les règles sont en fait assez simples mais qui comporte une suite complexe de phases de jeux, dont des enchères, explique Véronique Ventos, qui est 59e au classement français féminin de bridge. D’autre part, l’information initiale est incomplète (chaque joueur ne connaît que ses 13 cartes sur un jeu de 52), les décisions de chacun doivent pouvoir être expliquées aux autres joueurs, à tout moment, et le jeu se joue à quatre par équipes (chacun a un partenaire et deux adversaires). » Pour toutes ces raisons, les techniques utilisées pour le jeu de Go sont inadaptées, de même que celles employées pour le poker.
La chercheure a navigué entre les deux principaux courants de l’intelligence artificielle, l’IA symbolique et l’IA connexionniste. « Je suis convaincue qu’il faut développer des méthodes hybrides, tirant partie des avantages des deux méthodes, pour produire des IA explicables, affirme-t-elle. Le bridge est un excellent modèle pour tester cette approche. »
Du bridge aux applications industrielles
Au moment où Véronique Ventos rejoint les computer gamers, son compagnon, Jean-Baptiste Fantun, polytechnicien, lui aussi féru de maths et champion de France de bridge en 2017, réfléchit aux contours d’une start-up. « Nous avons eu l’idée d’utiliser le bridge comme bac à sable pour créer des intelligences artificielles explicables pour répondre à des besoins industriels, raconte-t-elle. De fait, les caractéristiques du bridge sont très proches de nombreuses problématiques industrielles ou de la vie réelle, où l’on doit prendre des décisions en étant capable de les expliquer, dans un univers incertain où l’on ne dispose pas de toutes les informations. »
Ensemble, ils créent NukkAI en mai 2018. À la fois laboratoire privé de recherche en IA et start-up, NukkAI réunit déjà une vingtaine de collaborateurs : chercheurs (dont Tristan Cazenave), ingénieurs de recherche et doctorants. Leur objectif commun : mettre à profit les approches existantes et développer de nouveaux outils comme des IA hybrides dans le but de réaliser des applications industrielles. On l’aura compris, leur but n’est donc en aucun cas de craquer le bridge, mais le duo n’oublie pas sa passion commune : « Fin 2021, nous organiserons deux challenges de bridge : un premier avec notre robot qui jouera face à des champions, le second avec NuxBridge, un logiciel qui fournira des explications au joueur de bridge », se réjouit la bridgeuse.
Isabelle Bellin
Image à la une : © Vincent Devillard
1. T. Cazenave, “GRAVE : Generalized Rapid Action Value Estimation”, IJCAI, 2015. ijcai.org
2. V. Ventos et O. Teytaud, « Le bridge, nouveau défi de l’intelligence artificielle ? » RIA, 2017. hal.inria
