Comment une intelligence artificielle ridiculise les meilleurs joueurs de poker

Après deux semaines de compétition, Libratus peut se targuer d’une position confortable, avec une banque (bankroll) largement positive de près de 1,2 million de dollars. En face, il n’y a guère que le sud-coréen Dong Kim qui limite la casse, avec un léger gain de l’ordre de 20 000 dollars. « Nous avons toujours une chance, mais si l’on gagne, ce ne sera pas de beaucoup », estimait l’un de ses compagnons au dixième jour de cette drôle de compétition. L’optimisme raisonnable s’en est allé : Jason Les affiche aujourd’hui une perte de 700 000 dollars. 

Baptisée Brains Vs. Artificial Intelligence : Upping the Ante (quelque chose comme « Cerveau contre Intelligence Artificielle : on monte la mise »), ce tournoi fait s’affronter l’homme et la machine. D’un côté, on trouve quatre joueurs pro, spécialistes du Texas Hold’em dans sa variante No-Limit en face à face (head’s up). De l’autre, on a affaire à Libratus, une intelligence artificielle développée par la Carnegie Mellon University de Pittsburgh. Le défi se tient dans un casino de Pennsylvanie, mais chacune de ces quatre parties peut être suivie sur Twitch, en direct et huit heures par jour. Les joueurs y commentent parfois le jeu de leur adversaire, qui serait à la fois déconcertant et terriblement efficace.

Au train où vont les choses, l’IA a donc de bonnes chances de s’imposer au terme des vingt jours de tournoi. Elle prendrait ainsi sa revanche sur l’Homme : en 2015, c’est le professionnel Doug Polk qui avait remporté la première édition de ce challenge. À l’époque, il affrontait toutefois une IA peu optimiste baptisée Claudico (dérivé de claudicare, claudiquer en latin). Le terme Libratus témoigne d’une certaine prise de confiance, puisqu’il évoque l’équilibre…

Développée par le professeur Tuomas Sandholm et son élève doctorant Noam Brown, Libratus illustre les progrès accomplis en matière de traitement informatique des « informations imparfaites », où la réflexion doit prendre en compte des données incomplètes ou dissimulées. C’est la grande différence entre le poker et le go ou les échecs, disciplines dans lesquels l’intelligence artificielle a déjà prouvé sa supériorité sur l’homme : bien qu’extrêmement complexes, ces jeux ne recèlent pas de piège, dans le sens où les deux adversaires visualisent en permanence l’ensemble du plateau et des pièces qui s’affrontent. La stratégie y relève donc de l’analyse combinatoire.

Pour simplifier, on pourrait dire qu’elle consiste à étudier, à chaque coup, l’ensemble des enchaînements possibles, de façon à ensuite identifier la meilleure action à tenir.

[large-image]

[/large-image]

No Limit Texas Hold’em : de l’art des probabilités

Le poker appelle des compétences différentes dans la mesure où des décisions doivent être prises avant que toutes les données de l’équation ne soient révélées. Au Texas Hold’em, variante la plus populaire du poker, chaque joueur reçoit deux cartes privées : il est le seul à les connaître. Le jeu prévoit ensuite que cinq cartes soient tirées progressivement et découvertes publiquement : trois au flop, une quatrième au turn et la dernière, surnommée river.

À chaque étape, les joueurs ont la possibilité de miser leurs jetons, et doivent accepter de suivre la mise de leur adversaire pour rester en lice jusqu’à la dernière carte. Le gagnant est celui qui affichera la meilleure combinaison entre ses deux cartes privées et trois des cartes étalées publiquement sur la table.

Présenté de la sorte, on serait tenté de résumer le Texas Hold’em à une affaire de probabilités. En fonction des deux cartes dont on dispose, on calculera (de façon mathématique ou à l’instinct) ses chances de victoire, et l’on choisira en fonction de suivre son adversaire, de le relancer (augmenter la mise) ou de se coucher (abandonner). Il n’y a cependant jamais de certitude, puisqu’on ne connaît pas la main de son adversaire. Autrement dit, le joueur base ses décisions sur l’analyse statistique d’un risque : précisément ce à quoi peut exceller un programme informatique.

le joueur base ses décisions sur l’analyse statistique d’un risque : précisément ce à quoi peut exceller un programme informatique

Libratus doit cependant faire face à une difficulté supplémentaire, qui compromet la stabilité des modèles statistiques : elle affronte ses adversaires dans une version no limit du Texas Hold’em, ce qui signifie que les mises ne sont pas plafonnées et qu’il faut pondérer le risque mesuré au niveau des cartes en fonction de la quantité de jetons déjà engagés sur la table et des capacités de relance de l’adversaire. Les amateurs de cash game le savent, c’est là que se niche la vraie part imprévisible du poker, qu’on l’appelle bluff ou audace.

En termes comptables, on estime qu’une partie de no limit en face à face ouvre un éventail de 10 puissance 160 possibilités…

Bots et poker, une longue histoire troublée

Les cartes et le silicium entretiennent une histoire d’amour compliquée, née avec l’avènement des premiers grands casinos virtuels permettant de jouer du vrai bon argent en ligne. Sans surprise, certains ont très tôt vu l’opportunité de développer des programmes capables de jouer pendant des jours, sans jamais se lasser, jusqu’à accumuler des gains substantiels.

Ces bots (robots informatiques) fonctionnent généralement comme des calculatrices perfectionnées : ils étudient les cartes reçues, calculent les probabilités de victoire, et n’engagent des jetons que si celles-ci dépassent un certain seuil. Ce faisant, ils ratent de belles opportunités, se font avoir par les tentatives de bluff et perdent des mains qu’un joueur humain avisé aurait gagné. Mais la force du modèle statistique réside dans la répétition. Dès lors qu’il joue des mises constantes, un robot bien conçu finit en théorie toujours par gagner plus qu’il n’a perdu.

Poker en ligne

Cette perspective de gain facile a motivé la mise en place d’une véritable économie parallèle à celle du poker en ligne. Il vous suffit aujourd’hui d’une simple recherche sur votre moteur favori pour tomber sur des sites marchands proposant pour quelques dizaines de dollars un bot capable de jouer de façon autonome. L’efficacité est généralement affichée sous la forme d’un retour sur investissement, avec des taux qui font rêver : l’éditeur de cette licence vendue 389 euros promet par exemple des gains de l’ordre de 60 % des sommes engagées.

Evidemment, l’efficacité de ces logiciels frauduleux n’est pas garantie, loin de là. D’abord parce que le poker est un jeu suffisamment riche pour que la stratégie probabiliste ne donne qu’un maigre avantage si elle n’est pas soutenue par de vrais algorithmes de pointe. Ensuite, parce que toutes les salles en ligne cherchent à détecter les programmes qui se font passer pour des joueurs légitimes pour les évincer au plus vite.

Dans ce jeu du chat et de la souris, parades et contournements deviennent de plus en plus complexes. Pour jouer de façon autonome, un bot doit faire plus que prendre des décisions : il doit aussi savoir reconnaître les cartes affichées par le logiciel de poker, ou interagir avec ce dernier de façon naturelle. Les clients des grands noms du secteur intègrent par exemple tous des algorithmes d’analyse du mouvement du pointeur de la souris, pour repérer tout ce qui pourrait ressembler à un modèle prédéfini. De l’autre côté, il faut donc programmer les déplacements de façon à reproduire le plus fidèlement possible un comportement humain.

Plusieurs grands noms du poker en ligne ont entrepris une démarche de transparence

Quelques affaires médiatisées confirment que les bots passent parfois au travers des mailles du filet. Début 2016, cinq internautes comparaissaient par exemple en Suède, accusés d’avoir gagné de façon indue l’équivalent de 400 000 euros aux dépens de milliers d’autres joueurs.

Le casino lui-même n’échappe plus à la suspicion. Après tout, ne dit-on pas que c’est toujours le croupier qui gagne ? En France et dans plusieurs pays européens, les opérateurs de jeux d’argent en ligne ont obligation de laisser une autorité indépendante auditer leurs outils et logiciels avant d’obtenir l’agrément leur permettant d’exercer. La démarche vise à lutter contre le blanchiment d’argent et la fraude fiscale, mais aussi contre la triche ou contre la mise en œuvre de faux joueurs chargés d’appâter de vrais clients…

Bien qu’en France, l’Autorité de régulation des jeux en ligne (Arjel) ait fait de son mieux pour promouvoir ses activités, obtenir la confiance des joueurs demande des mesures supplémentaires. Pour séduire les joueurs avertis, plusieurs grands noms du poker en ligne ont entrepris une démarche de transparence, en permettant aux internautes de consulter les statistiques de leurs tables. On peut ainsi retracer le parcours d’un joueur, ou revivre le déroulé d’un tournoi. De quoi analyser ses coups passés… ou partir en chasse de bots supposés, comme en témoignent régulièrement les forums spécialisés.

Paradoxalement, l’exposition de ces données nourrit dans le même temps les travaux de ceux qui élaborent des algorithmes dédiés aux tables de poker, en leur permettant de confronter leurs modèles mathématiques à des parties déjà jouées.

[large-image]

[/large-image]

De l’analyse à la prise de décision

Les secrets de Libratus sont encore bien gardés, mais d’autres études permettent de se faire une idée de la façon dont on passe du bot, capable de faire illusion mais limité, à la véritable intelligence artificielle, douée au point d’aller rivaliser avec les meilleurs joueurs humains.

Deepstack est un projet de recherche mené entre les universités de l’Alberta (Canada) et de Prague (République tchèque). Cette IA a réussi en décembre dernier à aligner des gains significatifs face à onze adeptes du poker sur un ensemble de quelque 40 000 parties de No Limit Texas Hold’em. À la différence de Libratus, Deepstack n’affrontait pas une élite mais des joueurs ordinaires. Son fonctionnement a été détaillé dans un long article qui permet de comprendre les principes fondateurs d’une IA dédiée au poker.

En analysant ses regrets, l’IA fait tendre le risque vers 0

En simplifiant, le logiciel est capable d’analyser ses parties passées pour déterminer toutes les occasions qu’il aurait eues de mieux faire. L’algorithme va ainsi identifier toutes les situations de « regrets », puis parcourir à nouveau les embranchements possibles pour déterminer une somme d’itinéraires offrant un meilleur résultat. Répété sur des centaines de milliers de parties, le processus finit par permettre non pas de viser la victoire, mais plutôt de faire tendre le risque de défaite vers zéro, en partant du principe que c’est celui qui perd le moins qui finit par gagner. Cette technique baptisée Counterfactual Regret Minimization (CFR), ou « réduction des regrets contrefactuels », est un des fondamentaux de l’intelligence artificielle.

Avec Deepstack, les chercheurs ont voulu aller un cran plus loin, en introduisant une variable supplémentaire calculée en fonction de l’état actuel du jeu (cartes visibles, jetons déjà misés). Cette nouvelle donnée est une approximation élaborée par l’algorithme, qui va servir à réduire l’éventail des combinaisons qu’il doit traiter. De ce fait, il gagne en rapidité d’exécution, mais aussi en efficacité, avec un arbre qui passe de 10 puissance 160 à seulement 10 puissance 17 embranchements. Cette variable, présentée comme une véritable « intuition », au sens humain du terme, permet à Deepstack de fonctionner sur un matériel relativement modeste, en l’occurrence une unique carte graphique GeForce GTX 1080.

« L’ancien paradigme de gestion des informations imparfaites a déjà démontré son potentiel dans des applications comme la défense des ressources stratégiques ou la prise de décision consolidée requise dans la recommandation de traitements médicaux. Ce nouveau paradigme ouvrira selon toute attente de nombreuses nouvelles possibilités », se réjouissent les dix cosignataires de l’article dédié à Deepstack.

En attendant, Libratus étudie chaque nuit ses mains de la journée grâce aux ressources du supercalculateur de Pittsburgh, capitalise sur 15 millions d’heures / processeur de calculs préliminaires… et n’en finit pas d’impressionner ses adversaires.

« Après ces longues journées éreintantes, je trouve amusant de voir où j’ai été bluffé par le bot », commente Dong Kim, qui éprouve tout de même de plus en plus de difficultés à faire bonne figure. 

https://twitter.com/dongerkim/status/824458854394167296