Des scientifiques ont créé un programme informatique époustouflant, capable de gagner au Poker en toutes circonstances et contre n’importe quel adversaire. Au-delà de cette innovation déjà exceptionnelle, les chercheurs pensent avoir trouvé un moyen de résoudre des problèmes complexes même lorsque de nombreux paramètres sont manquants. DGS vous explique tout sur cet algorithme très prometteur.
Le programme de Texas Hold’em Poker conçu par l’équipe de Michael Bowling à l’Université de l’Alberta au Canada et le développeur finlandais Oskari Tammelin joue littéralement de manière parfaite, en toutes circonstances. Cela représente l’étape suivante de Deep Blue, l’ordinateur créé par IBM qui en 1997, a battu le champion du monde d’échecs de l’époque : Garry Kasparov. Cela signifie que cette variante de Poker peut être considérée comme « essentiellement résolue », tout simplement.
La stratégie mise en place par les créateurs est tellement proche de la perfection qu’elle « rendrait tout travail supplémentaire inutile sur ce jeu de cartes », a expliqué Eric Johnson, un chercheur informatique spécialisé dans le Poker en Californie. « Je pense que les experts seront surpris de voir qu’un jeu aussi complexe puisse avoir été résolu aussi vite. » D’autres jeux avaient été solutionnés avant. En 2007, une équipe venant de la même université canadienne avait déjà résolu le jeu de dames. Pourtant, le Poker est plus difficile à résoudre que les dames. Ce dernier, comme les échecs, est un exemple de jeux dans lesquels les joueurs ont une connaissance parfaite des évènements passés et de la situation actuelle de la partie.
Au contraire dans le Poker, il y a de nombreuses choses qu’un joueur ne connait pas, comme les cartes des adversaires. Cette catégorie de jeux à information incomplète intéresse particulièrement les économistes et les théoriciens car cela inclut des problèmes pratiques tels que trouver la stratégie optimale pour les négociations et les ventes aux enchères. Au Poker, le challenge principal est de gérer l’immense nombre de façons dont une partie peut être jouée. Avec seulement deux joueurs dans sa version en face à face (heads-up), le jeu devient limité étant donné que les mises sont fixées et qu’il existe un nombre limité de surenchères. Il existe 3,16 x 10^7 états que ce jeu peut atteindre et 3,19 x 10^14 étapes durant lesquelles un joueur doit prendre une décision.
Michael et son équipe ont conçu leur algorithme de telle manière qu’il apprend au fur et à mesure de ses expériences, acquérant ses aptitudes de champion en jouant environ 1500 parties. Au début, il prenait des décisions aléatoires mais lorsque il s’est mis à jour en se faisant ajouter une « notion de regret » à chaque décision, il a rapidement progressé, éliminant tous les mauvais mouvements déjà effectués par le passé. Cette procédure connue sous le nom de minimisation contrefactuelle du regret a été largement adoptée à la compétition annuelle de poker sur ordinateur, qui existe depuis 2006. Les chercheurs l’ont grandement améliorée en permettant à l’algorithme d’évaluer les décisions considérées comme mauvaises lors de précédentes parties. L’autre innovation de taille est la prise en charge de grandes quantités d’informations qui nécessitent d’être stockées pour développer de telles stratégies (de l’ordre de 262 téraoctets). Les scientifiques ont trouvé une méthode de compression qui réduit ce volume à 11 téraoctets.
« Je pense que l’algorithme de regret contrefactuel est l’avancée majeure de ce projet », déclare Jonathan Shapiro, de l’université de Manchester au Royaume-Uni. « Mais ils ont réalisé quelques prouesses supplémentaires pour rendre ce problème faisable par un ordinateur. » L’ordinateur a en outre appris à injecter une certaine dose de bluff dans ses parties. Bien que le bluff semble être un élément très humain et psychologique, il fait en fait partie de la théorie du Poker. « Vous pouvez réellement calculer à quelle fréquence vous devez bluffer ou non pour obtenir les meilleurs résultats. » Bien sûr, aucun algorithme de Poker ne peut garantir de gagner toutes les parties, puisque le jeu possède une large part de chance basée sur la main que vous recevez. Pourtant, à long terme, l’algorithme de Michael et ses collègues a prouvé qu’il gagnait à chaque fois.
Reste à discuter sur le point « essentiellement résolu », qui signifie qu’il existe une marge, bien qu’extrêmement petite, dans laquelle l’ordinateur pourrait être battu par un joueur extrêmement fort. Cette marge reste apparemment négligeable en pratique, aucun humain n’était en théorie assez expérimenté pour y parvenir sans une dose de chance énorme. Michael explique que cette approche du Poker pourrait être utile dans des situations de la vie réelle lorsque quelqu’un doit prendre des décisions en ne possédant que des informations incomplètes. Par exemple, pour la gestion d’un portfolio d’investissements. L’équipe se focalise maintenant sur l’application de leur algorithme sur les décisions à prendre dans le milieu médical, en collaboration avec des spécialistes du diabète.
Nous sommes très impressionnés par ce programme expert en Poker ! Les meilleurs joueurs de la rédaction n’oseraient même pas jouer une partie contre lui :P. Félicitations aux chercheurs qui ont mis au point un ordinateur si fort. Pensez-vous qu’un jour, un ordinateur sera capable de battre les hommes dans toutes les disciplines ?
