Les ordinateurs ont appris à bluffer. Et ça va tout changer. (2/2)

Dans le premier volet de cette série, nous avons présenté les principes de la théorie des jeux, ainsi que ses points de contact avec le machine learning et l’intelligence artificielle. Nous allons à présent vous parler du challenge d’apprendre aux machines à jouer ainsi que des toutes récentes avancées dans ce domaine, et pour finir les possibles champs d’applications. Suivez nous dans ce voyage !

Libratus : une avancée majeure pour la convergence entre théorie des jeux et machine learning

Des jeux de dames à Libratus…

Depuis 20 ans, d’importants progrès ont été réalisés dans la confrontation entre humains et IA sur des jeux donnés. En effet, un jeu tel que le jeu de dames ou les échecs peut être transformé en problème d’optimisation, sachant un nombre donné de combinaisons possibles. A titre de référence, il y a environ 10^80 atomes dans l’univers.

Complexité des différents jeux

Les premières victoires

1994 : Le logiciel Chinook bats au jeu de dames Marion Tinsley, considéré comme le meilleur joueur de tous les temps. Cette victoire est cependant en demi-teinte, car elle intervient après 6 parties nulles et un abandon de Tinsley. En effet, il est établi qu’aux dames, en cas de 2 joueurs parfaitement rationnels, l’issue attendue est un match nul. Depuis 2007, on connaît l’ensemble des coups à jouer, le jeu de dames est donc officiellement “résolu”.

1997 : DeepBlue bat Gary Kasparov aux échecs, et ce, sans match nul ; malgré une complexité de jeu bien supérieure au jeu de dames.Contrairement aux dames, les échecs n’ont pas encore été résolus par les programmes, bien que le champion du monde ait pu être battu.

Les premiers pas de mise en oeuvre de la théorie des jeux

2015 : Des chercheurs de l’université d’Alberta développent Cepheus, qui bats des joueurs professionnels au Texas Hold’Em avec limite. Ils ont résolu ce jeu, qui a cependant un nombre de combinaisons limité, en calculant un équilibre de Nash à chaque étape du jeu, ce qui le rend “imbattable”. Ils ont par la suite développé DeepStack pour le Texas Hold’Em No Limit. On peut noter que Cepheus nécessite 16 To de RAM et ne peut jouer que contre un seul joueur…

La même année, l’université Carnegie Mellon développe Claudico, qui a le même objectif que Cepheus, mais ne parvient pas à battre les joueurs professionnels. Par la suite, ils améliorent leur programme pour créer Libratus.

AlphaGo : une victoire attendue de la machine sur l’homme *

Mars 2016 : AlphaGo, le programme développé par DeepMind (Google) bat le Sud-Coréen Lee Sedol, champion du monde du jeu de Go. On monte encore d’un cran dans la complexité, le nombre de combinaisons étant abyssal. La machine, qui se basait sur des techniques connues et éprouvées, à savoir l’algorithme Monte Carlo tree search, le Deep Learning et le Reinforcement learning, a appris en deux phases. Dans un premier temps, elle a appris du maximum de parties jouées par l’homme, puis elle a affronté une autre machine afin d’améliorer seule son réseau neuronal, et pouvoir se confronter à Lee Sedol. Il est important de préciser que cette victoire de la machine sur l’homme au jeu de Go était attendue, puisqu’il ne s’agit “que” de stratégie combinatoire, mais qu’elle est arrivée plus tôt que prévu, ce qui est de bon augure pour l’IA. On peut également préciser qu’AlphaGo ne sait faire que du Go, et qu’en ce sens on est loin d’une vraie IA générale, qui n’existe pas encore et nécessite d’introduire des représentations générales du monde.

*Le 18 octobre 2017, Nature a publié “Mastering the game of Go without human knowledge” où AlphaGo Zero est présenté. DeepMind a en effet développé une nouvelle version d’AlphaGo qui ne nécessite plus de jouer contre un humain pour apprendre, mais où l’algorithme joue contre lui même. En jouant contre AlphaGo, AlphaGo Zero gagne 100-0, ce qui est plutôt significatif…

Libratus

Janvier 2017 : Libratus, développé par l’université de Carnegie Mellon, affronte en face à face 4 des meilleurs joueurs professionnels de poker Hold’Em “No limit” (Daniel McAulay, Jimmy Chou, Dong Kim et Jason Les). Cette variante du poker permet des relances infinies ainsi que toutes les formes de bluff. Les joueurs ont enchaîné pendant 20 jours plus de 120.000 mains différentes avec la machine. Le résultat des courses est sans appel : à la fin de l’expérience, Libratus avait ainsi pu récupérer plus de 1,5 million de dollars en jetons, les autres perdant chacun entre 84 054.

Pendant le jeu, Libratus a nécessité 2.6PB de stockage et environ 800 noeuds,  chacun ayant entre 128Go et 12 To de RAM.

Fonctionnement et hypothèses de Libratus

Contrairement aux échecs et au Go, le Poker est un jeu qui n’est pas « à information complète », ce qui signifie que les participants ne peuvent avoir accès à l’ensemble des informations relatives au jeu. Il y a de multiples inconnues, et le facteur chance, ainsi que l’élément psychologique priment.

Cette situation peut être conceptualisée grâce à la théorie des jeux par :

–       un jeu à deux agents (ou plus)

–       chacun souhaite maximiser ses gains et par conséquent battre son adversaire

–       chaque agent élabore des stratégies et fait des hypothèses sur la stratégie de l’adversaire, en se basant sur une information publique (les cartes déjà jouées) et une information privée (on connaît son propre jeu, pas celui de l’adversaire).

Ainsi, on est dans une situation de jeu répété, avec une asymétrie d’information, et une rationalité limitée des individus. En effet, personne n’est parfaitement rationnel.

On va alors essayer de « résoudre le jeu », et bluffer au besoin, ce qui revient à calculer un équilibre de Nash à chaque étape. On adopte alors la meilleure stratégie à chaque étape, ce qui revient à un problème d’optimisation sous contrainte d’information publique et de cartes à disposition.

De manière générale, cela illustre la capacité de Libratus à faire des raisonnements stratégiques en ayant une information imparfaite, et qui a surpassé celle des meilleurs joueurs humains. Or, c’est dans les prises de décisions du monde réel qu’une IA deviendra vraiment intéressante.

Grâce au Deep Learning et doté d’une énorme puissance de calcul, Libratus est capable, d’une partie à l’autre, d’apprendre comment jouent ses adversaires, y compris quand et comment ils bluffent.

Son algorithme se base sur l’équilibre de Nash afin d’optimiser ses gains. Pour finir, il joue de manière totalement imprévisible. «Chaque fois qu’on a trouvé la faille, le lendemain, elle avait disparu», confesse un des joueurs.

Au final, il est composé de trois blocs d’algorithmes : le premier apprend le comportement du joueur au fur et à mesure de la partie, le deuxième élabore des stratégies pour jouer, le troisième analyse les propres stratégies de Libratus pour les supprimer au fur et à mesure et garder un effet de surprise. Il peut par exemple être efficace de varier la fréquence des bluffs au long de la partie.

Le papier de recherche détaillant le fonctionnement de Libratus n’a pas encore été publié.

En revanche, des chercheurs d’Alberta ont développé un algorithme similaire, DeepStack, qui a également battu des professionnels au Texas Hold’em No Limit, bien que d’un peu moins haut niveau,