Contact
msalomon [at] dataanalyticpost.com (Mathilde Salomon)

Bluffant : quand l’intelligence artificielle joue au poker !

Libratus et DeepStack. Ce sont les noms des deux intelligences artificielles qui, en février 2017, à quelques jours d’intervalle, ont vaincu les meilleurs joueurs de poker. Une première mondiale. Un pas de plus, et non des moindres, vers des capacités d’apprentissage renforcées.

Cet article, rédigé par Vianney Perchet et Julien Audiffren, respectivement professeur et chercheur au CMLA de l’ENS PARIS-SACLAY, est publié sur Data Analytics Post (DAP), le média d’information et de réflexion autour des « data sciences » porté par le master MVA de l’ENS Paris-Saclay.

Echec, jeu de go, poker… les jeux de stratégie sont de formidables « terrains de jeu » pour l’intelligence artificielle (IA). Après le succès de DeepBlue en 1997 contre Garry Kasparov aux échecs et celui d’AlphaGo en 2016 contre un des meilleurs joueurs mondiaux de go, Lee Sedol, c’est au poker que se sont frottés avec succès deux intelligences artificielles. Pas n’importe quel poker : le Texas Hold’em No limit*, une des variantes les plus complexes du célèbre jeu de bluff. Libratus a joué successivement contre quatre joueurs de premier plan mondial tandis que DeepStack a affronté onze joueurs professionnels. Les deux fois, l’IA a vaincu chacun des joueurs de manière statistiquement significative. Le défi a duré 120 000 mains, soit 30 000 par joueur pour Libratus et 3 000 mains par joueur pour DeepStack.

A la recherche de la stratégie optimale

Le poker présente une difficulté supplémentaire par rapport aux échecs : l’information est incomplète (les joueurs ne voient pas les cartes de leurs adversaires). Ils sont donc obligés d’envisager de très nombreuses possibilités. Par ailleurs, même si le nombre de cartes et le montant maximum des mises donc le nombre de stratégies sont en nombre fini, leur total est vertigineux : de l’ordre de 10^165 (1 suivi de 165 zéros) soit plus que le nombre d’atomes dans l’univers. Ainsi, même s’il existe théoriquement une « stratégie optimale » en heads-up, il est exclu d’explorer toutes ces possibilités de façon exhaustive pour la trouver, même avec un calculateur haute performance.

Pourtant, Libratus et DeepStack sont, en quelques sortes, parvenues à se rapprocher de cette stratégie optimale, plus que les joueurs qu’elles ont vaincus. Et on ne peut pas supposer que la chance a joué en la faveur de Libratus. Des contraintes sur l’ensemble des mains avaient été définies pour la réduire au maximum, notamment grâce à un effet « miroir » : si l’IA était favorisée par le tirage, la même main était jouée à l’envers avec un autre joueur sans, bien sûr, que Libratus ne puisse utiliser cette information.

Simplifier le jeu ou anticiper moins de coups

Comment fonctionnent ces intelligences artificielles ? Toutes les deux utilisent un apprentissage par renforcement (via un algorithme de type CFR ou Counter Factual Regret Minimization), une méthode essai-erreur qui permet aux IA de jouer contre elles-mêmes sur des millions de mains en augmentant (ou diminuant) la probabilité associée à l’utilisation de chaque option selon le succès (ou l’échec). Elles diffèrent par leur méthode d’entrainement : Libratus, développée par des chercheurs de Carnegie Mellon autour de Noam Brown (un étudiant) et de Tuomas Sandholm (un professeur), cherche la stratégie optimale d’un jeu simplifié (on parle « d’abstraction de jeu ») grâce à un algorithme d’abstraction. Celui-ci est combiné à un nouveau type d’algorithme Safe Endgame Solving (ou ES**) lorsque le jeu devient plus complexe et comporte des actions peu communes. Libratus obtient ainsi une solution approchée de la stratégie optimale de cette nouvelle situation.

DeepStack, conçue par le professeur Michael Bowling et son équipe de l’université d’Alberta explore, pour sa part, le vrai jeu, de manière exhaustive, mais à quatre coups seulement : l’IA utilise un entrainement à base de réseau de neurones profond, une approche comparable à celle utilisée par AlphaGo. DeepStack évalue chaque situation de façon rapide et dynamique, en termes de chances de victoire et de défaite et choisit l’action qui la rapproche du meilleur futur possible. L’efficacité d’une telle méthode dépend entièrement de la qualité de sa fonction d’approximation. L’apprentissage de celle de DeepStack est assurée via du deep learning, en ingérant plus de 10 millions de parties de poker.

A partir de leur apprentissage, les IA choisissent comment jouer dans chaque situation. Les stratégies restent néanmoins probabilistes (comme l’est d’ailleurs la stratégie optimale de la partie complète) : par exemple, avec telles cartes dans telle situation, renoncer dans 40 % des cas, et relancer dans 60 % des cas. Pour Libratus, l’étape d’apprentissage a été menée sur le calculateur haute performance Bridges du centre de Pittsburgh, d’une puissance supérieure à 1 téraflops (mille milliards d’opérations par seconde) et disposant de 274 téraoctets de mémoire vive. Soit 15 millions d’heures-coeurs de calcul. Les IA continuent ensuite à améliorer leurs performances sur les données réelles, durant les matchs contre les joueurs de pokers. L’une et l’autre ont abouti à une victoire sans appel !

Data Analytics Post (DAP)

Média d’information et de réflexion autour des « data sciences », DAP est porté par le master MVA de l’ENS Paris-Saclay

Depuis 20 ans, le master MVA est la formation phare du domaine en France par son ancrage dans la recherche au meilleur niveau international, son inscription dans un écosystème d’entreprises et de startups - dont les problématiques nourrissent la formation - et par son bassin de recrutement, puisqu’il accueille des étudiants de la plupart des grandes écoles françaises.

L’objectif du DAP est d’informer, décrypter et ouvrir le débat autour des problématiques de traitement et d’analyse des données, depuis leurs fondements jusqu’aux perspectives scientifiques et économiques prometteuses grâce à la plume et à la rigueur de notre équipe de journalistes scientifiques.

Sont abordés entre autres : les travaux de recherche, les réalisations, les solutions, les nouveaux usages, ainsi que les acteurs et leurs parcours professionnels dans les métiers impliqués.

Notre ambition est d’animer l’écosystème que constituent les équipes de recherches académiques, les entreprises -des startups jusqu’aux grands groupes internationaux- et les filières de formations (enseignants, étudiants et alumni).

 

*Le Texas hold ’em (littéralement « Texas retiens-les ») est la variante du poker la plus jouée, notamment dans sa forme no-limit, c’est-à-dire sans restriction maximale de mise ou de relance. Le hold’em se joue à partir de deux joueurs en face à face (heads-up) et jusqu’à dix joueurs en table complète (full ring).

** L’Endgame Solving permet de trouver une stratégie optimale en information complète lorsque toutes les « fins » (comme « échec et mat ») peuvent être explorées : l’information est propagée de manière récursive aux coups d’avant en « remontant le temps ». Cette méthode théorique n’est néanmoins pas adaptée aux jeux trop complexes comme le go. Quand l’information est incomplète comme au poker, deux familles d’approximation ont été développées : « Unsafe » et « Safe » Endgame Solving, la deuxième bénéficiant de garanties théoriques au prix d’une complexité et d’un temps de calcul accru.