Les chercheurs d'Amii produisent la première IA à surpasser les pros humains au Heads-Up No-Limit Poker

Vue d'ensemble

DeepStack comble le fossé entre les techniques d'IA pour les jeux à information parfaite - comme les dames, les échecs et le go - et celles pour les jeux à information imparfaite - comme le poker - pour raisonner pendant qu'il joue. Il utilise une "intuition" affinée par l'apprentissage profond pour réévaluer sa stratégie à chaque décision.

Dans une étude achevée en décembre 2016 et portant sur 44 000 mains de poker, DeepStack a battu 11 joueurs de poker professionnels - avec une seule victoire en dehors de la marge de signification statistique. Sur l'ensemble des parties jouées, DeepStack a gagné 49 big blinds/100 (une mesure du succès au poker ; une stratégie consistant à toujours se coucher ne perdrait que 75 bb/100), soit plus de quatre écarts-types par rapport à zéro, ce qui en fait le premier programme informatique à battre des joueurs de poker professionnels en heads-up no-limit Texas hold'em. L'article sur DeepStack a été publié dans le numéro de mai 2017 de la revue Science.

À propos de l'algorithme

Les jeux à information imparfaite (ou jeux à information cachée) fournissent un modèle mathématique général qui décrit comment les décideurs interagissent. La recherche en IA utilise depuis longtemps les jeux de société pour étudier ces modèles, mais l'attention s'est principalement portée sur les jeux à information parfaite, comme les dames, les échecs ou le go, où toutes les informations sur le jeu sont accessibles à tous les joueurs. Le poker est la quintessence des jeux à information imparfaite, où vous et votre adversaire détenez des informations que l'autre ne possède pas (vos cartes).

Jusqu'à présent, les approches de l'IA compétitive dans les jeux à information imparfaite ont généralement raisonné sur l'ensemble du jeu, produisant une stratégie complète avant le jeu. Cependant, pour que cette approche soit réalisable dans les jeux de type heads-up no-limit Texas hold'em - un jeu comportant beaucoup plus de situations uniques qu'il n'y a d'atomes dans l'univers - une abstraction simplifiée du jeu est souvent nécessaire.

Une approche fondamentalement différente

DeepStack est la première application théoriquement solide des méthodes de recherche heuristique - qui ont connu un succès célèbre dans des jeux comme les dames, les échecs et le go - aux jeux à information imparfaite.

Au cœur de DeepStack se trouve la résolution continue, un calcul de stratégie locale solide qui ne prend en compte que les situations qui se présentent pendant le jeu. Cela permet au DeepStack d'éviter de calculer une stratégie complète à l'avance, évitant ainsi le besoin d'une abstraction explicite. Au lieu de cela, DeepStack calcule une stratégie basée sur l'état actuel du jeu uniquement pour le reste de la main, sans en maintenir une pour toute la partie, ce qui conduit à une moindre exploitabilité globale.

Pendant la résolution, DeepStack n'a pas besoin de raisonner sur tout le reste de la partie car, au-delà d'une certaine profondeur, il remplace le calcul par une estimation approximative rapide, également appelée "intuition" de DeepStack - une intuition de la valeur de la détention de toutes les cartes privées possibles dans toutes les situations de poker possibles. Tout comme l'intuition humaine, l'"intuition" de DeepStack doit être entraînée. Nous l'entraînons avec l'apprentissage profond en utilisant des exemples générés à partir de situations de poker aléatoires (plus de parties que celles qui ont été jouées dans l'histoire de l'humanité). Enfin, DeepStack s'appuie sur des arbres de prévision clairsemés, dans lesquels il considère un nombre réduit d'actions, ce qui lui permet de jouer à une vitesse humaine conventionnelle. Le système résout les jeux en moins de cinq secondes à l'aide d'un simple ordinateur portable équipé d'un GPU Nvidia.

Recherche heuristique

D'un point de vue conceptuel, la résolution continue de DeepStack, la recherche locale "intuitive" et les arbres sparse lookahead décrivent la recherche heuristique, qui est responsable de nombreux succès de l'IA dans les jeux à information parfaite. Jusqu'à DeepStack, aucune application théorique de la recherche heuristique n'était connue dans les jeux à information imparfaite.

Bien qu'il utilise des idées issues de l'abstraction, DeepStack est fondamentalement différent des approches basées sur l'abstraction, qui calculent et stockent une stratégie avant le jeu. Bien que DeepStack restreigne le nombre d'actions dans ses arbres lookahead, il n'a pas besoin d'abstraction explicite car chaque re-solve commence à partir de l'état public actuel, ce qui signifie que DeepStack comprend toujours parfaitement la situation actuelle.

DeepStack est théoriquement solide, produit des stratégies beaucoup plus difficiles à exploiter que les techniques basées sur l'abstraction et bat les joueurs de poker professionnels au poker no-limit en tête-à-tête avec une signification statistique.

Test et évaluation

Matches professionnels

Nous avons évalué DeepStack en le confrontant à un groupe de joueurs de poker professionnels recrutés par la Fédération internationale de poker. 44 852 parties ont été jouées par 33 joueurs de 17 pays. Onze joueurs ont terminé les 3 000 parties demandées, DeepStack les battant tous sauf un, avec une marge statistiquement significative. Sur l'ensemble des parties jouées, DeepStack a surpassé les joueurs de plus de quatre écarts types par rapport à zéro.

Évaluation à faible variance

Les performances de DeepStack et de ses adversaires ont été évaluées à l'aide de l'AIVAT, une technique à faible variance sans biais prouvé, basée sur des variates de contrôle soigneusement construites. Grâce à cette technique, qui donne une estimation non biaisée des performances avec une réduction de 85 % de l'écart-type, nous pouvons montrer une significance statistique dans des matchs comptant aussi peu que 3 000 parties.

Remerciements

DeepStack a été développé conjointement par une équipe internationale de l'Université Charles, de l'Université technique tchèque - toutes deux situées à Prague, en République tchèque - et de l'Université d'Alberta à Edmonton, au Canada.

DeepStack a été développé par Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson et Michael Bowling.

Les chercheurs tiennent à remercier les joueurs professionnels qui ont consacré un temps précieux à jouer à DeepStack, ainsi que nos nombreux évaluateurs et nos familles et amis.

Nos recherches sont soutenues par la Fédération internationale de poker, IBM, l'Alberta Machine Intelligence Institute, le Conseil de recherches en sciences naturelles et en génie du Canada et la Charles University Grant Agency.

DeepStack a été possible grâce aux ressources informatiques fournies par Calcul Canada et Calcul Québec.