Algorithme de jeu de poker
Le jeu de poker (tout du moins la plupart des variantes) est considéré d'une complexité hors d'atteinte des ordinateurs. Cependant, des méthodes sont développées pour obtenir une approximation de la stratégie parfaite (du point de vue de la théorie des jeux) dans un face à face (deux joueurs). Par ailleurs, des algorithmes de plus en plus efficaces sont conçus pour des situations où plus de joueurs interviennent. La stratégie parfaite a plusieurs significations dans ce contexte :
- pour la théorie des jeux et selon la méthode du minimax c'est celle qui l'emporte sur toute autre stratégie ;
- pour les programmes, le problème vient du fait que cette stratégie optimale varie en fonction de l'expertise de l'opposant et des faiblesses qu'il devient possible d'exploiter à ses dépens. Dans ce cas, la stratégie optimale revient à modéliser ces faiblesses afin d'en tirer avantage.
Certains de ces systèmes sont basés sur le théorème de Bayes, l'équilibre de Nash, les méthodes de Monte-Carlo et les réseaux de neurones.
L'unité de recherche la plus connue dans ce domaine est celle de l'Université de l'Alberta qui a développé Poki, PsOpt et Polaris. Parmi les membres de cette équipe, on peut citer Jonathan Schaeffer, instigateur en 1991 de ce groupe de recherche, Neil Burch et Darse Billing, deux des concepteurs de Polaris[1].
Polaris, qui joue au Texas hold'em, s'est mesuré à deux joueurs de poker américains de renommée mondiale, Phil Laak et Ali Eslami, lors de la Conférence annuelle sur l'intelligence artificielle qui s'est achevée le à Vancouver. Les deux joueurs humains ont gagné de justesse après quatre parties, avec un match nul, une victoire pour le logiciel et deux victoires pour les hommes. Afin d'équilibrer le caractère aléatoire du jeu, chaque humain jouait seul contre une instance du programme informatique, et Phil Laak recevait une main de deux cartes identique à celle que recevait l'instance de Polaris opposée à Ali Eslami[2].
Fin , un nouveau programme, Libratus, a gagné sans appel un match de Texas hold’em face à quatre des meilleurs joueurs mondiaux[3].
Notes et références
- (en) Site du groupe de recherche
- Article du Monde du 2 août 2007
- Description du match sur pokerlistings.