Calculer n’est pas jouer !

L’IA Libratus est le deuxième logiciel qui défie des humains au Heads-up no limit texas hold’em 2 mois après la victoire écrasante de Deepstack sur 33 joueurs du circuit professionnel ayant joué 3 000 mains chacun. Dans ce nouveau tournoi, quatre des meilleurs joueurs ont joué le jeu en acceptant un duel de 30 000 mains chacun, contre l’algorithme avec une cagnotte de 200 000$ en cas de victoire. Le nom du tournoi qui avait lieu du 11 au 30 janvier 2017 avait un titre explicite : Brains Vs Artificial Intelligence. Et devinez quoi ? Et bien c’est le système binaire qui a encore « gagné » contre les professionnels. Toutefois, une petite analyse s’impose !

Le résultat du tournoi

Depuis le début des années soixante-dix, des tentatives de modélisation des jeux ont été réalisées par les chercheurs du MIT (Institut de technologie du Massachusetts) pour mieux comprendre les processus d’apprentissage humains à des fins purement scientifiques. Venant de la théorie des jeux, l’algorithme à arborescence le plus connu, Min-Max calcule toutes les combinaisons possibles, l’élagage Alpha-Bêta permettant de délimiter les nœuds sans issus. Cette méthode a permis de connaître toutes les variantes de jeux déterminés à informations complètes comme pour le tic-tac-toe (ou morpion), le Hex ou l’Awalé.

Lorsque le nombre de combinaisons est devenu trop élevé les informaticiens ont fait appelle à la connaissance des experts humains pour réduire le nombre de branches à parcourir en éliminant les ramifications inopérantes et donc le temps de calcul comme pour le Jeu de dame avec 1032 combinaisons ou encore le Jeu d’échec qui dépasse le googol (unité de mesure de 10100) avec ses 10120 combinaisons, soulageant le supercalculateur DeepBlue de nombreux calculs inutiles. Pour le jeu de Go et ses 10170 combinaisons, l’arbre des possibles était impossible à construire de façon brute pour nos pauvres supercalculateurs et les experts humains n’arrivaient pas à proposer de solutions efficaces pour optimiser les programmes. C’est le Deep Learning, algorithme d’apprentissage non linéaire, qui sera utilisé par la société Google pour battre les meilleurs joueurs de Go en 2015 avec AlphaGo.

Le joueur de Go professionnel Lee Se-dol joue contre AlphaGo le 10 mars 2016

Au début des années 80, les meilleures stratégies du Backgammon étaient connues grâce aux programmes informatiques. Dans le domaine de la connaissance brute, nécessitant d’énormes bases de données, c’est Watson qui battra les humains à Jeopardy ! (Questions pour un champion à l’américaine) en 2011. Dans un jeu comme le Poker, les stratégies sont moins évidentes qu’au Backgammon et le nombre de combinaisons possibles est tout simplement aussi faramineux qu’au jeu de Go. Ce jeu de stratégie mixte à information incomplète, comme le dirait si bien Michel Boutin, ne permet pas de voir les cartes de son adversaire et implique une part de bluff lorsque les joueurs parient leurs jetons.

Jusqu’à aujourd’hui, les IA avait tendance à créer leurs propres stratégies à partir d’algorithmes prédéfinis sans « s’adapter » au style de jeu des humains. C’est le cas de Cepheus, un logiciel de poker développé par Mike Howling et son équipe de l’Université d’Alberta. Ces chercheurs ont répertorié toutes les combinaisons possibles lors d’un heads-up en Limit Hold’em, soit un total de 316 000 000 000 000 000, et ont fait jouer la machine contre elle-même comme dans le film WarGames (1983) pour le morpion. Pour cela, 200 processeurs ont calculé sans arrêt pendant 70 jours et ont généré une base de données de 11 téraoctets pour résoudre l’ensemble des situations possibles de ce jeu. Pour IEEE Spectrum, le problème de la variante sans limite, c’est que même un superordinateur ne peut couvrir les 10160 potentialités décisionnelles liées au enchères. Plusieurs universités se sont pourtant mis au défis de battre les meilleurs joueurs de cette variante du Texas hold’em très populaire sur les campus des universités technologiques anglophones. Deux groupes de chercheurs se sont basés sur des méthodes assez différentes pour créer des algorithmes permettant de gagner au Heads-up no limit texas hold’em.

La première, qui est au cœur de Claudico (du latin être bancal), est une forme d’intelligence artificielle « classique » basé sur l’algorithme Min-Max (d’où son surnom). En mai 2015, cette IA avait virtuellement perdu plus de 730 000 dollars en 10 jours de poker No-Limit contre quatre joueurs professionnels avec 1 500 mains jouées par jour. La cause principale de sa défaite serait liée à la capacité d’adaptation des joueurs, 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.

Déjà utilisée pour le jeu de Go, la méthode sur laquelle se base Deepstack, s’appelle le Deep Learning. DeepStack est le fruit d’une collaboration entre des chercheurs de l’université d’Alberta (Canada) et de deux universités tchèques, Charles et Polytechnique de Prague. Il sera le premier programme à battre des joueurs de Poker professionnels en surclassant son concurrent Claudico. L’affrontement de Deepstack s’est passé entre novembre et décembre 2016 contre 33 joueurs professionnels de la Fédération internationale de Poker (IFP). Dans ce tournoi chaque joueur affrontait l’algorithme DeepStack sur une unique partie de 3 000 mains, ne permettant pas au logiciel et surtout aux joueurs de changer de stratégie en cours de jeu. Le tournoi contre Libratus qui vient d’être organisé par le Rivers Casino de Pittsburgh était d’un tout autre genre.

L’arborescence DeepStack

Comme son cousin Claudico, Libratus fonctionne sur un arbre des possibles sauf que le dernier né du Pittsburgh Supercomputing Center (PSC) est moins prévisible et apprend de ses erreurs. Alors que l’algorithme de Claudico tournait sur une seule machine, son successeur repose sur un superordinateur situé à une distance de 25 km du casino avec une puissance de calcul équivalent à 10 000 machines tournant simultanément. Selon ses concepteurs, Libratus est doté d’une méthode de « détermination d’équilibre », d’où son surnom venant du latin mettre en équilibre. C’est une référence à l’équilibre de Nash, situation où aucun joueur n’a intérêt à changer de stratégie en théorie des enchère, système d’analyse se situant à la limite entre la science économique et de la théorie des jeux. La méthode utilisée a permis à l’algorithme d’identifier rapidement les axes les plus prometteurs pour jouer une main et donc écarter les manœuvres imprudentes. Avec Libratus, c’est comme si on changeait l’algorithme de façon aléatoire durant la partie, ou tout du moins en fonction du score, pour éviter que les humains ne s’adaptent trop facilement aux stratégies gagnantes utilisées par le supercalculateur. Des millions de mains sont passées entre les lignes de codes de la machine, les chercheurs faisant tourner le programme depuis plus de 2 ans.

Libratus s’est confronté à quatre des meilleurs joueurs de Heads-up. Deux joueurs humains jouaient depuis le casino et deux autres depuis une salle privée en coulisse. Chaque jour, l’ordinateur tirait les mêmes mains pour deux paires de joueurs. Des séances de débriefing étaient organisées pour que les joueurs puissent confronter leurs stratégies et analyser celle de Libratus. Au bout du premier jour, le programme repart avec 81 716 $ contre 7 228 $ pour les humains, Dong Kim ayant perdu 60 305$ et Jason Les 21 411$ alors que McAuley mène de 4 938$ et Jimmy Chou de 2 290$. Le robot a doublé ses gains le deuxième jour et a continué dans cette voie le troisième jour. Les humains ont ensuite remonté la pente le sixième jour mais la machine a changé de stratégie et a repris la main sur trois des joueurs. Au trois quart du tournoi, seul Dong Kim faisait jeu égal avec la machine. A cinq jours de la fin du tournoi, Jason Les déclare que la stratégie de Libratus est de plus en plus fine au cours du temps lui permettant de voler de plus en plus de jetons, traitant de la machine de « gangster sans émotions ». A la fin du tournoi, Libratus avait très significativement battu l’ensemble des joueurs du tournoi en remportant virtuellement 1 766 250 $. Les joueurs n’ont clairement pas réussi à tirer avantage des séances de débriefing pour comprendre la stratégie de Libratus en discutant sur leurs parties et/ou à l’aide de leur propres logiciels d’analyse.

Sur la gauche, les joueurs Daniel McAulay et Jimmy Chuo. Au centre, le professeur Tuomas Sandholm et le doctorant Noam Brown. Sur la droite, les joueurs Jason Les et Dong Kim.

Cette réussite des l’IA pose de nombreuses questions. Tout d’abord, d’un point de vue ludique, que va-t-il se passer dans le monde du poker en ligne si tout un chacun peut se faire remplacer par un programme de ce type ? Va-t-il y avoir un tournoi entre les deux IA qui ont battue les humains ? Le niveau des joueurs professionnels va-t-il augmenter en s’appuyant sur les stratégies de ces programmes comme cela avait été le cas avec l’ouvrage de Doyle Brunson en 1979 ? Dans le domaine scientifique, on peut s’interroger sur la raison qui pousse les chercheurs à s’attaquer aux pratiques ludiques avec tant de virulence. Qui finance ces programmes et pourquoi étudient-ils ce sujet ? Quels en sont les buts ? En effet, on crée par ce biais des technologies d’aide à la décision qui pourraient permettre de prendre l’avantage sur l’autre, sur l’humain, que ce soit politiquement, économiquement ou militairement. Influencer une élection, modifier les cours de la bourse ou encore lancer de fausses informations de façon « aléatoire » sont-ils des applications envisageables au travers de ces algorithmes ? Elon Musk affirme que la prochaine étape sera d’hacker le cerveau humain. Peut-être n’a-t-il pas Thor…

Une réflexion sur “ Calculer n’est pas jouer ! ”

  • 23 octobre 2017 à 22 h 16 min
    Permalink

    Qu’en est-il du calcul des probabilités qui explique le nombre de mains jouées expliquant les 11 To de données?
    À l’heure actuelle le heads up …holdem est mathématiquement résolu grâce à ces super calculateurs.
    La prochaine étape sera de pouvoir établir une victoire sur l’homme mais certains paramètres humains sont pour l’instant difficile à appréhender par l’IA.
    les programmes actuelles sont prometteurs mais le plaisir du jeu existera toujours pour les joueurs passionnés de poker.
    De plus, il n’est pas prévu d’intégrer à l’heure actuelle des ordinateurs dans les tournois.
    L’avenir nous le dira…

    Réponse

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée. Les champs obligatoires sont indiqués avec *