Depuis qu’Alphago a « craqué » le jeu de go, existe-t-il encore un jeu capable de résister à l’avancée de l’intelligence artificielle ? En fait, contrairement aux échecs et au Go, le poker, du moins dans ses formes les plus complexes, a jusqu’ici résisté à toute tentative d’automatisation. La cause en est qu’il s’agit d’un jeu « à information incomplète ». Autrement dit, la machine ne connaît pas l’ensemble des cartes possédées par son adversaire. Ce qui implique une nouvelle forme d’algorithmique. Il existe plusieurs variantes du poker, mais celle qui intéresse le plus les chercheurs est celle qui est nommée Heads Up Texas hold’em, dans laquelle certaines cartes sont visibles et d’autres sont connues seulement du joueur (heads up signifie face à face, ce qui veut dire que la partie oppose seulement deux joueurs). Cette variante se décline à son tour en deux versions : celle « avec limites » et celle « sans limites ». Dans la seconde, les joueurs peuvent relancer les paris tout au long de la partie. Le « sans limite » recèle 10¹⁶⁰ possibilités de jeu différentes, soit, nous rappelle IEEE Spectrum, peut être plus que le nombre d’atomes dans l’univers. Un bot nommé Cepheus a déjà été vainqueur de la version « avec limites », qui n’offre que 10¹⁴ possibilités.

Le poker a attiré l’attention de la presse spécialisée ces derniers jours à cause de deux annonces différentes, provenant de deux équipes cherchant à résoudre la complexité du « sans limites ». Tout d’abord une équipe de l’université Carnegie Mellon, dirigée par Tuomas Sandholm, est en train de soumettre leur logiciel à un test contre des joueurs professionnels de haut niveau : la compétition à commencé le 11 janvier et se terminera le 30 (il est possible de suivre le déroulement de ce match en temps réel sur ce site). Parallèlement, un autre groupe, mené par Michael Bowling, à l’Université d’Alberta, a proposé un nouveau programme, Deepstack (.pdf). Les chercheurs affirment avoir fait jouer leur programme contre 33 joueurs professionnels, chacun jouant environ 3000 parties contre la machine, et Deepstack se serait montré au niveau de ses adversaires. En gros les deux équipes concurrentes se basent sur deux théories différentes. La première, celle qui est au centre de Libratus, est une forme d’intelligence artificielle « classique ». La seconde, sur laquelle se base Deepstack, est le fameux Deep Learning.

Les humains sous pression

Libratus est le descendant de Claudico, un autre programme qui avait affronté des humains en 2015, sans grand succès. La méthode propre à Libratus est celle qui a prévalu jusqu’ici dans les logiciels de poker. Il s’agit grosso modo de construire un « arbre de la partie », envisageant tous les coups possibles jusqu’à la fin de cette dernière. Pour cela, Libratus doit se baser sur les calculs d’un superordinateur. Alors que Claudico tournait sur une unique machine, son successeur repose sur un superordinateur situé à distance, et sa puissance de calcul, nous apprend triblive.com serait l’équivalent de 10 000 machines tournant simultanément.

Petit problème, nous rappelle IEEE Spectrum, même un superordinateur ne peut couvrir les 10¹⁶⁰ potentialités de la variante sans limite du Texas hold’em. Sandholm et son équipe ont donc trouvé un moyen de réduire la taille de cet arbre et également, contrairement à ce que faisait Claudico, d’apprendre de ses erreurs.

L’expérience menée avec Claudico s’était conclu par la victoire des humains. La cause principale serait liée à la capacité d’adaptation de ces derniers, qui ont très vite compris la stratégie du bot – alors que celui-ci n’a pas été capable de s’adapter à la stratégie humaine. Sandholm a déclaré à propos desdits joueurs : « j’ai été très impressionné par leur adaptation rapide, ils ont appris très vite à partir d’un très petit nombre de mains ».

La même chose se produira-t-elle avec Libratus ? Trop tôt pour juger, bien sûr (la compétition ne se terminera que le 30 janvier). Après une première phase où Libratus était en tête, les humains ont ensuite remonté la pente le 17 janvier. Mais Le fil tweeter de Jason Les, l’un des joueurs en compétition contre le programme, mentionne le 18 que la machine a repris la main.

Mais les humains ont un avantage. Une fois la partie finie, les joueurs discutent et réfléchissent aux stratégies à adopter. Oliver Roeder, dans fivethirtyeight.com (le célèbre site web dirigé par Nate Silver), relate une de ces séances de débriefing :

« Après la session de la journée, un log de chaque main jouée est fourni numériquement aux joueurs. Ce mercredi, alors qu’ils chargent les données, des nombres colorés, des cartes thermiques, des graphes linéaires et des probabilités clignotent dans la fenêtre de leur logiciel d’analyse (…). Ils ont passé en revue toutes les plus grandes mains de la journée, les digérant presque instantanément, tout comme un maître d’échecs pourrait jouer un jeu dans sa tête en quelques secondes. Ils ont cherché à déterminer les défauts de leur propre stratégie et à attaquer celles du bot. Lentement mais sûrement, il semblait qu’ils démontaient la méthode de jeu de Libratus. »

Ce qui est intéressant dans ces propos, c’est qu’on découvre que les joueurs, eux aussi, utilisent aujourd’hui des ordinateurs et des algorithmes pour élaborer leurs plans. Autrement dit, l’idée de joueurs « purement humains » s’opposant à des machines semble relever déjà largement de l’ordre du mythe…

Toujours est-il qu’une victoire potentielle de Libratus pourrait sérieusement nuire à l’avenir du poker en ligne. Déjà, nous raconte triblive.com, les joueurs commencent à se méfier des interactions virtuelles pour préférer les rencontres face à face : par internet, ils ne savent pas s’ils se trouvent en lutte contre un humain ou un bot. De plus, le monde du poker en ligne est en crise depuis plusieurs années, après ce qu’on a appelé en 2011 le Black Friday, jour où les trois principales plateformes de poker en ligne ont été fermées pour fraude. Il n’existerait plus aujourd’hui assez d’argent et de parties disponibles pour permettre aux joueurs pros de gagner leur vie. Aujourd’hui, selon fivethirtyeight.com, la situation est particulièrement difficile pour les adeptes du Heads-up Texas hold’hem no limit, car il n’existerait, selon Jason Les, qu’environ 20 bons joueurs dans le monde. Si Libratus sort vainqueur de la compétition, le jeu pourrait bien mourir…

Les réseaux neuronaux, le Deep Learning, peuvent-ils jouer un rôle important dans la résolution des problèmes liés à l’information incomplète ? Selon Wired, Deepstack commence comme les programmes plus classiques, par construire un arbre des possibilités. Mais lui ne va pas jusqu’à la fin. Il analyse chaque main en fonction du contexte, et prend sa décision également en fonction des paris effectués.

Les chercheurs comparent la technique d’approximation de DeepStack à l’instinct d’un joueur humain quand un adversaire bluffe ou tient une main gagnante, même si la machine doit baser son évaluation sur la façon dont l’adversaire parie plutôt que sur son langage corporel. «Cette estimation peut être considérée comme l’intuition de DeepStack», écrivent-ils.

Mais souligne Wired, Deepstack présente une importance supplémentaire. S’il s’avère que la méthode utilisée est efficace pour un jeu comme le poker, l’algorithme pourrait être étendu à d’autres domaines bien plus importants, comme l’économie, la guerre ou la négociation.

Mais le Deep Learning n’est pas le seul à avoir cette ambition. Tumoas Sandholm considère lui aussi que son programme Libratus est un point de départ pour la résolution de toutes sortes de situations impliquant une information incomplète.

Autrement dit, les IA joueuses de poker se rapprocheraient d’une IA réelle, capables de gérer les situations complexes que les êtres humains rencontrent… Les casinos seront-ils la porte d’entrée de la Singularité ?

Rémi Sussan

MAJ au 31 janvier : la compétition est terminée, et Libratus à gagné….