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.

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 !

Vianney Perchet, professeur à l’ENS Paris-Saclay
Julien Audiffren, chercheur au CMLA de l’ENS PARIS-SACLAY

*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.

Pour en savoir plus

– méthode CFR, Counter Factual Regret Minimization
http://www.cs.cmu.edu/~noamb/papers/17-AAAI-Refinement.pdf
Safe and Nested Endgame Solving for Imperfect-Information Games , de Noam Brown et Tuomas Sandholm (8 pages)
https://arxiv.org/pdf/1701.01724.pdf
DeepStack: Expert-Level Artificial Intelligence in Heads-Up No-Limit Poker. De Matej Moravcik et al., 37 pages