Des informaticiens de l’université d’Alberta, au Canada, ont programmé un joueur de poker IA qui ne peut jamais perdre au cours d’une série de mains de Texas hold’em limite en heads-up.
Nommé Cepheus, le programme utilise une stratégie pour une partie de poker Texas hold’em limite à deux joueurs qui est si brillante qu’une analyse statistique indique que même si une personne passe toute sa vie à jouer au poker contre ce programme, celui-ci ne perdra jamais. L’IA n’arrivera jamais qu’en tête ou à égalité. Elle ne fera jamais d’erreur, même si elle ne sait pas quelles cartes son adversaire détient.
Il ne s’agit pas de gagner toutes les mains – l’IA recevra des cartes nulles aussi souvent que son voisin – mais elle a compris comment retourner les pires situations pour arriver en tête : “[Elle] perdra si elle reçoit une main inférieure, mais elle minimisera ses pertes du mieux qu’elle peut mathématiquement et prendra lentement mais sûrement votre argent en prenant la décision “parfaite” dans n’importe quel scénario”, explique Jason Koebler à Motherboard. “On peut dire que le hold’em limite heads-up a été “résolu”.”
La différence entre le poker “limit” et le poker “no limit” se résume à l’argent – vous êtes soit limité à des montants fixes que vous pouvez miser, soit vous pouvez miser autant que vous le souhaitez. Ce dernier point serait impossible à résoudre par un programme informatique, car prévoir des sommes d’argent aléatoires et illimitées est un exploit en soi. Mais cela ne rend pas moins impressionnant ce que ce programme peut faire.
Comparez ce qu’il fait à d’autres jeux qui ont été “résolus” par des joueurs IA. Même nos faibles cerveaux humains peuvent trouver le moyen d’être imbattables au jeu des petits chevaux. Des jeux comme les échecs et les dames sont encore plus complexes en raison des différentes possibilités à chaque tour, mais toutes les informations sont toujours présentes sur le plateau. L’adversaire ne peut rien cacher, si ce n’est sa stratégie, mais cela n’a pas d’importance, car l’IA connaît déjà toutes les possibilités de jeu et a déjà trouvé la stratégie parfaite pour contrer chaque coup avant même que la partie ne commence.
Mais qu’en est-il du poker ? Le programme tricherait s’il savait ce que contiennent les deux cartes cachées que son adversaire détient à chaque tour. Comme le fait remarquer M. Koebler, Cepheus doit, d’une manière ou d’une autre, savoir comment prendre les 3 x 10^14 décisions possibles dans une partie de poker à limites, dans laquelle, à tout moment, il ne connaît pas toutes les informations. L’équipe de l’Université de l’Alberta appelle ce type de jeu, où toutes les informations ne sont pas connues, un jeu à “information imparfaite”.
“Les solutions pour les jeux à information imparfaite nécessitent que les ordinateurs gèrent la complication supplémentaire liée au fait de ne pas savoir exactement quel est l’état du jeu, comme par exemple ne pas connaître la main de l’adversaire”, a déclaré l’ un des membres de l’équipe, Neil Burch, à Jeremy Hsu, à IEEE Spectrum. “De telles techniques nécessitent plus de mémoire et de puissance de calcul pour les ordinateurs.”
Combien de mémoire, exactement ? Environ 262 téraoctets. Oups. Et que fait-il avec toute cette mémoire ? Cepheus exécute un algorithme appelé CFR+, qui a été inventé par l’équipe comme une amélioration d’un algorithme existant connu sous le nom de “counterfactual regret minimisation” (CFR).
La minimisation des regrets consiste essentiellement à apprendre de ses erreurs. Ainsi, comme l’explique Arielle Duhaime-Ross à The Verge, si le Cepheus pense à la possibilité d’augmenter une mise, qu’il décide de jouer au hasard à la place et qu’il perd, il reviendra sur ses pas, calculera combien il aurait pu gagner s’il avait augmenté sa mise et stockera ce montant en tant que “valeur de regret”.
Cette valeur est attribuée à chaque occasion où l’ordinateur peut prendre la même décision, afin qu’il évite de commettre la même erreur. C’est très différent de la façon dont les humains jouent – si nous subissons une grosse perte, nous nous concentrons sur la façon de la regagner, plutôt que sur la façon d’utiliser cette information pour perfectionner le reste de notre jeu. Cepheus continuera à se mettre à jour avec ces valeurs de regret jusqu’à ce qu’il atteigne ce que l’équipe appelle le “jeu parfait”.
“CFR+ fonctionne toujours comme les anciens algorithmes CFR en développant progressivement de meilleures solutions en jouant des milliers et des centaines de milliers de mains de poker”, écrit Hsu à IEEE Spectrum. “Mais il peut développer une très bonne solution beaucoup plus rapidement que n’importe quel algorithme CFR antérieur en étant plus efficace ; en gros, cela revient à faire moins de pas, mais plus grands, vers la meilleure solution.”
L’équipe a publié ses conclusions dans la revue Science.
Selon IEEE Spectrum, une fois que l’équipe a compris la stratégie, elle a réussi à réduire les besoins en mémoire à moins de 11 téraoctets pour stocker les valeurs contrefactuelles et à 6 téraoctets pour calculer la stratégie principale. Au final, il a fallu 24 trillions de mains de poker sur 70 jours et 200 ordinateurs exécutant l’algorithme CFR+ avec 32 Go de RAM et 24 unités centrales de traitement pour entraîner Cepheus à “résoudre” le jeu. “Nous pourrions continuer à l’entraîner, et il continuerait à s’améliorer”, a déclaré l’un des membres de l’équipe, Michael Bowlin, à Arielle Duhaime-Ross à The Verge. “Mais nous avons arrêté à ce stade parce que nous ne pouvons pas le distinguer d’être parfait”.
L’équipe va maintenant travailler à ajuster l’algorithme pour jouer au poker no limit heads-up. Ils savent qu’en raison des variables, il sera probablement impossible de créer un joueur IA “imbattable”, mais ils espèrent créer un joueur capable de battre les meilleurs joueurs humains du monde. Tel est l’objectif. Ils réfléchissent également à la manière d’utiliser cette technologie pour aider les gouvernements et les entreprises privées à créer de meilleurs systèmes de sécurité qui ne peuvent pas être piratés.
Vous voulez vous mesurer à Cepheus ? Cliquez ici pour jouer contre lui. J’espère seulement que vous apprécierez la sensation de perdre.
Sources : Motherboard, The Verge, IEEE Spectrum