Deep Blue, des génies du poker, une rivalité entre universités, Cepheus, les World Series des robots, Phil Laak et, enfin, Libratus. L’évolution des IA de poker n’a pas été de tout repos.
Il y a quelques jours, Libratus venait à bout d’une équipe de spécialistes (humains) des heads-up, composée de Jason Les, Dong Kim, Daniel McAulay et Jimmy Chou.
Jamais une IA n’avait réalisé une telle performance et cela restera forcément comme une étape historique dans l’évolution du poker non humain.
Une étape qui arrive après de longues années passées à tenter de développer un programme efficace.
Le poker est un défi unique pour les développeurs, parce que c’est un jeu à information incomplète, contrairement par exemple aux échecs.
Alors pourquoi se lancer dans un tel projet ?
Eh bien parce que les informaticiens pensent que résoudre un jeu comme le poker pourrait avoir des applications dans d’autres domaines, comme la négociation, la santé et d’autres.
Nous allons revenir sur la longue histoire des IA, des débuts jusqu’à Libratus.
1984
Mike Caro et son programme de poker rudimentaire
Le joueur de poker professionnel Mike Caro développe un programme informatique appelé Orac qu’il confronte à plusieurs joueurs pros lors des WSOP 1984.
Caro a mis deux ans à mettre au point Orac (« Caro » à l’envers) sur un ordinateur Apple II.
Orac était très basique selon les standards actuels, mais le programme parvint tout de même à battre Doyle Brunson sur un match.
Petit détail intéressant : Orac scannait les cartes physiques via un code-barres. La partie ne se déroulait pas sur l’ordinateur.
Orac a également joué contre Bob Stupak pour un match de promotion, mais il a subi un gros bad beat.
Lors du premier match (au meilleur des trois matchs), Orac est allé à tapis et Stupak l’a suivi. Orac a touché un brelan au flop, mais d’après Caro, quelqu’un s’est pris les pieds dans le câble et a débranché l’ordinateur, qui a donc dû redémarrer et donc recommencé la partie à zéro. Triste.
1991
L’Université de l’Alberta se lance dans l’aventure
Le Groupe de recherche informatique de l’Université de l’Alberta, qui allait devenir l’un des plus grands développeurs d’IA poker, commence ses travaux.
Il s’agissait d’une équipe composée d’énormément de chercheurs, notamment Darse Billing, scientifique du jeu et joueur professionnel, Denis Richard Pap, Jonathan Schaeffer, Duane Szafron, Michael Bradley Johanson, Neil Burch et d’autres. Michael Bowling a rejoint l’équipe plus tard avant de devenir l’un acteurs les plus importants dans ce domaine.
1996
Deep Blue terrasse Kasparov
Le robot Deep Blue d’IBM affronte le champion du monde des échecs Garry Kasparov (avant de le battre).
Cet événement a énormément boosté les recherches dans le domaine des IA pour arriver à battre les humains au Go ou au poker.
C’est bien évidemment plus compliqué pour le poker qui, contrairement aux échecs, est un jeu à information incomplète, ce qui le rend plus difficile à maîtriser pour les ordinateurs.
Le projet Deep Blue (d’abord appelé Deep Thought) a été lancé à l’Université Carnegie Mellon par Feng-Hsiung Hsu.
L’Université Carnegie Mellon fait aussi partie des grands acteurs du domaine des IA de poker, comme nous le verrons aussi par la suite.
1997
Conception de Loki, l’une des premières véritables IA de poker
Le Groupe de recherche informatique de l’Université de l’Alberta présente Loki, après avoir utilisé le (légendaire) forum rec.gambling/poker comme source pour leurs recherches.
Darse Billings et deux étudiants ont développé Loki sous l’égide des informaticiens de l’Université de l’Alberta Jonathan Schaeffer et Duane Szafron.
Loki a été conçu pour jouer à une table complète (neuf joueurs), ce qui n’est toujours pas résolu par les ordinateurs en 2017.
Comme la plupart des IA, Loki était conçu pour le Limit Hold’em plutôt que le No-Limit.
L’équipe pensait que Loki pourrait un jour être assez sophistiqué pour participer aux WSOP, mais le Caesars a changé les règles de la compétition pour empêcher les non-humains de participer (en partie parce qu’une entreprise a tenté de faire participer un singe au Main Event 2006).
Loki a été la première IA à avoir un énorme impact dans le poker.
Cependant, son niveau était encore légèrement inférieur à celui d’un humain.
1999
De Loki à Poki, et un jeu vidéo
L’équipe derrière Loki décide de le renommer Poki et de se concentrer sur le Texas Hold’em à deux joueurs, moins complexe. Poki pouvait jouer au poker au niveau d’un joueur moyen.
La plupart de ces robots (anciens et récents) sont bâtis autour du concept d’un équilibre de Nash. Pour simplifier, il s’agit de prendre la meilleure décision possible tout en prenant en compte la décision de l’autre joueur.
Poki a finalement été utilisé pour le jeu vidéo Stacked, où l’on retrouvait également Daniel Negreanu.
2002
PsOpti / Sparbot, des robots avec du potentiel
L’Université de l’Alberta sort ensuite une gamme de robots, dont PsOpti et Sparbot, pour tenter de résoudre le poker en heads-up Limit.
Malgré des résultats encourageants, aucun d’entre eux n’a atteint un niveau supérieur à celui d’un joueur moyen de Hold’em à deux joueurs.
L’équipe a utilisé le joueur professionnel Gautam « thecount » Rao comme adversaire de l’IA. Voilà ce qu’il en disait à l’époque :
« C’est un programme très performant. Une fois qu’il aura le modelage de l’adversaire, il pourra démolir tout le monde. »
L’université allait donc passer quelques années à essayer d’intégrer l’apprentissage du jeu de l’adversaire à son robot.
2003
Les développeurs délaissent le modèle des échecs
C’était un tournant crucial dans le développement des IA de poker : les chercheurs commencent à se détourner de la méthodologie des échecs (qui avait permis de créer des IA comme Deep Blue).
C’est aussi le moment où Michael Bowling rejoint l’Université de l’Alberta, après un doctorat à Carnegie Mellon. Il sera le moteur de la recherche pour les dix années suivantes.
2004
Tuomas Sandholm et Carnegie Mellon travaillent sur une IA de poker
Carnegie Mellon et le professeur Tuomas Sandholm, l’équipe qui sera plus tard derrière l’IA Libratus, commencent à travailler sur les IA de poker.
Avec les années, Sam Ganzfried et Noam Brown ont également beaucoup apporté à ces recherches.
C’est aussi cette année-là que l’ICCM Poker Bot Challenge organise un tournoi de No-Limit Hold’em à destination des robots. Ace Gruber, de l’Université de Toronto, y participe.
2005
Les World Series des robots de poker
En plein boom du poker, le Golden Palace organise un tournoi de gala au Binion’s, avec un prix de 100 000 $ pour le vainqueur. Il y avait six participants.
PokerProbot, conçu par un concessionnaire de 37 ans venu de l’Indiana, Hilton Givens, s’impose. PokerProbot s’est imposé sur le fil face à Poki-X, une version conçue un peu dans la précipitation depuis l’AI Poki de l’Université de l’Alberta.
Phil Laak a aussi battu PokerProbot lors d’un heads-up « amical » pendant la compétition.
« D’ici 3 à 5 ans, ils seront capables de nous battre », estimait Kenneth « The Clone » Jones, joueur pro et concepteur de programmes informatiques, dans le LA Times.
2006
Lancement de la compétition annuelle de poker informatique
L’Annual Computer Poker Competition (ACPC ou, à l’origine, ACM) est lancée.
Les deux grandes équipes de l’Université de l’Alberta et Carnegie Mellon s’affrontent pour remporter plusieurs trophées, en laissant tout de même quelques indépendants et autres universités pointer le bout de leur nez avec les années.
2007
Polaris contre Phil Laak
L’Université de l’Alberta lance Polaris, qui va devenir l’un des robots de poker les plus connus suite à son opposition contre Phil Laak (perdue de peu par le robot).
Polaris est en réalité un composite de plusieurs robots en collaboration (dont l’Hyperborean08).
Le programme contient un certain nombre de stratégies fixes, parmi lesquelles il choisit tout au long du match.
Étonnamment, Polaris n’est pas extraordinairement puissant, puisqu’il peut tourner sur des machines vendues dans le commerce comme un MacBook Pro.
Polaris ne joue qu’en No-Limit Hold’em en heads-up.
2008
Polaris contre six humains lors d’un test non officiel
Polaris est confronté à six joueurs humains lors de la Gaming Life Expo, pour un bilan de trois victoires, deux défaites et un match nul.
La version de 2008 du robot était bien plus performante que son prédécesseur qui avait été opposé à Phil Laak l’année précédente.
2009
L’Université d’Auckland lance Sartre
L’Université d’Auckland commence à travailler sur le projet Sartre (Similarity Assessment Reasoning for Texas Hold’em via Recall of Experience).
Sartre allait s’imposer comme un acteur majeur dans le monde des IA et il a souvent bien figuré dans les compétitions.
C’est aussi l’une des rares IA à s’imposer sans venir de Carnegie Mellon ou de l’Université de l’Alberta.
2011
Full Tilt et PokerStars contre les robots
Pendant longtemps, les robots étaient loin d’avoir le niveau pour faire face aux joueurs humains sur Internet. Mais avec le perfectionnement des IA, ce n’était qu’une question de temps avant que des développeurs ne saisissent l’opportunité de se lancer sur un marché lucratif.
À partir de 2008, des rumeurs sur la présence de robots sur certains sites de poker ont commencé à courir.
Selon Darse Billings, de l’Université de l’Alberta, la plupart des robots de poker sont très mauvais : plus de 90 % d’entre eux perdraient de l’argent.
Cela n’empêche pas des entreprises comme Shanky Technologies de vendre des programmes soi-disant capables d’être compétitifs en Hold’em et en PLO.
Point culminant : début 2011, PokerStars et Full Tilt, les deux géants du secteur, ont tout fait pour éliminer les robots de leurs sites.
Lorsqu’un joueur est identifié comme « bot », il est immédiatement banni et l’argent gagné est confisqué.
Grâce aux programmes de reconnaissance humaine avancés, les bots ne posent plus de problèmes sur la plupart des sites de poker.
2014
Tom Dwan face à une machine de Limit Heads-Up : bingo
Tom Dwan remporte une grande somme d’argent en battant une machine de Limit Heads-Up appelée Texas Hold’Em Heads Up Poker.
Elle était conçue par IGT, un fabricant de machines à sous et de poker vidéo. La machine devait utiliser un système d’apprentissage de nouvelles stratégies.
Le programme au cœur de Texas Hold’Em Heads Up Poker a été conçu par Predrik Dahl de l’Université d’Oslo.
Phil Hellmuth et Johnny Chan ont ensuite assuré la promotion de la machine, mais elle ne s’est jamais vraiment diffusée, surtout comparé aux machines à sous traditionnelles.
L’une des machines d’Hellmuth est toujours présente au Bellagio à Vegas.
2015
Cepheus (Université de l’Alberta) résout le Limit Hold’em
Après des années de développement, l’Université de l’Alberta annonce la sortie d’un robot qui aurait résolu le Limit Hold'em fin 2015.
Cepheus a maîtrisé le Limit Hold’em en jouant contre lui-même pendant deux mois. Dernier d’une prestigieuse lignée de robots conçus par l’Université de l’Alberta (Loki, Poki, Vexbot, Hyberborean, Polaris...), Cepheus avait de quoi impressionner.
Cela a marqué un tournant dans l’histoire des IA de poker : le Limit Hold’Em est le plus grand jeu à information incomplète à être « résolu ».
Mais si à l’époque on décrit Cepheus comme « imbattable », c’est faux. En effet, bien que quasi impossible à battre sur un échantillon assez large, Cepheus peut cependant perdre de l’argent ponctuellement.
Et si Cepheus a résolu le Limit Hold’em, la version No-Limit ne l’est toujours pas. D’après certains scientifiques, cela pourra prendre encore plusieurs années en raison de la nature imprévisible du jeu.
L’objectif de Cepheus et des autres IA du même type est d’être utilisés dans d’autres domaines, comme aider les gouvernements à perfectionner leurs stratégies de sécurité ou les tactiques de négociation. Ou aider les docteurs à modifier les traitements de leurs patients.
Si vous voulez tester Cepheus, direction le site de l’Université de l’Alberta : poker-play.srv.ualberta.ca
Claudico défait par des humains lors d’un défi humains contre IA
Jamais contents d’être dépassés par l’Université de l’Alberta, Tuomas Sandholm et Carnegie Mellon ont présenté leur propre IA super intelligente appelée Claudico à l’été 2015.
La grande différence entre Claudico et Cepheus est que Claudico joue en No-Limit Hold’em, ce qui est bien plus difficile pour un robot.
L’équipe de Carnegie Mellon a lancé un défi à 100 000 $ à un groupe de joueurs de poker professionnels composé de Doug Polk, Jason Les, Bjorn Li et Dong Kim pour qu’ils affrontent Claudico, sur 20 000 mains par joueur sur une période de 13 jours au Casino Rivers.
L’équipe « humaine » s’est imposée, avec un profit de 732 713 $ par rapport à Claudico. Le défi a permis de mettre en avant les étranges montants des mises de l’IA.
Jason Les avait tout de même déclaré à PokerListings après le match que ce n’était qu’une question de temps avant que les IA ne soient capables de battre les humains.
2017
L’Université de l’Alberta lance l’IA DeepStack
L’équipe de l’Université de l’Alberta a frappé fort début 2017 en annonçant DeepStack, la première IA capable de battre les joueurs professionnels en heads-up de No-Limit Hold’em.
L’algorithme novateur de DeepStack est très avancé et a la capacité d’apprendre en jouant contre lui-même, un processus assez similaire à celui de l’AI AlphaGo qui a résolu le très complexe jeu de Go.
DeepStack utilise des réseaux neuronaux très complexes pour imiter l’intuition humaine et apprendre en pratiquant.
L’étude a inclus des dizaines de participants (même si aucun d’eux n’était aussi prestigieux que Doug Polk ou Dong Kim) pour 44 000 mains jouées. Par ailleurs, il y avait aussi des mesures incitatives pour les trois meilleurs joueurs.
Si DeepStack vaut le coup d’être mentionné, c’est aussi parce qu’il a été capable de gagner sans avoir été « formé » par des joueurs experts.
L’étude doit cependant encore être revue par des pairs, et l’Université de l’Alberta est encore en attente.
Tuomas Sandholm, de Carnegie Mellon, a déclaré à Wired Magazine que l’étude ne règle pas définitivement la question, étant donné que DeepStack a joué contre de bons joueurs, mais pas d’excellents joueurs comme Claudico ou Libratus.
Libratus s’impose sans conteste lors d’un deuxième défi humains contre IA
En janvier 2017, Libratus a enfin totalement révolutionné l’histoire des confrontations entre IA et humains.
Libratus, toute nouvelle IA de Carnegie Mellon, ne s’est pas contenté de battre ses adversaires humains, il les a terrassés.
À la fin des 20 jours (et 120 000 mains), Libratus comptait un profit hallucinant de 1 766 250 $.
L’équipe humaine était composée de certains des tout meilleurs joueurs de NLHE : Dong Kim, Dan McAulay, Jimmy Chou et Jason Les.
Kim, qui a été le meilleur adversaire de l’IA en ne perdant « que » 85 649 $, a admis s’être senti dépassé par moment.
« J’avais l’impression de jouer contre quelqu’un qui trichait, quelqu’un qui pouvait voir mes cartes », a-t-il confié à Wired Magazine. « Que ce soit clair, je n’accuse pas l’IA de tricher. Mais c’est pour dire à quel niveau il était. »
Et si Libratus, du latin « équilibré », est l’héritier de Claudico, il a en réalité était conçu de zéro.
Libratus n’utilisait donc pas une stratégie intégrée fixe, mais dépendait d’un algorithme qui intégrait les stratégies.
Les joueurs ont notamment remarqué des changements manifestes dans la manière dont jouait Libratus chaque jour, ce qui est probablement lié au fait que l’IA analysait tous les jours ses performances pour corriger les erreurs.
Les joueurs humains peuvent cependant se consoler : Libratus a besoin d’un superordinateur pour fonctionner, un ordinateur capable de fonctionner 7 250 fois plus vite que l’ordinateur portable moyen.
Par ailleurs, Libratus est purement une IA de heads-up : la tâche serait encore beaucoup plus complexe (et totalement différente) avec plus d’un adversaire.
Sandholm est assez confiant : il estime que la technologie sur laquelle s’appuie Libratus pourrait avoir énormément d’applications dans d’autres domaines.
Robots de poker : les infos essentielles
Voici quelques-uns des robots de poker les plus connus :
Université de l’Alberta
Loki
Poki
PsOpti/Sparbot
Vexbot
Hyperborean
Polaris
Cepheus
Université Carnegie Mellon
Tartanian
Claudico
Libratus
Université d’Auckland
Casper
Sartre
Indépendant - Fredrik Dahl
Texas Hold'Em Heads-Up Poker
