Partager cet article

Le poker, prochain défi des superordinateurs

Le superordinateur Watson d'IBM vient de battre deux champions américains du jeu télévisé Jeopardy!. Prochaine étape, apprendre à s'adapter aux comportements humains.

Dans un sens, il n’avait pas tout à fait tort, Watson, le superordinateur qui participait au célèbre jeu télévisé Jeopardy! en 1992.

«Un coup sous la ceinture». C’était la réponse. Le jeu consistait à retrouver la question. Bien qu’il ne s’agissait alors que d’un tour de chauffe, organisé des années avant le premier vrai défi télévisé homme-machine de cette semaine, Watson était confronté à une vraie situation de jeu. À l’époque, le participant humain avait remporté le prix de 200$ en apportant la réponse correcte: «Qu’est-ce qu’un coup bas?». Après avoir scanné sa titanesque base de données, l’ordinateur dernier cri avait en revanche trouvé une solution tout autre: «Qu’est-ce qu’une branlette?»

L’époque de la branlette appartient désormais au passé pour Watson. À tel point que celui-ci affronte aujourd’hui les meilleurs participants de l’histoire du jeu. IBM déroule le tapis rouge pour son nouvel enfant-star à travers une grande campagne promotionnelle, tout en insistant bien sur le fait que, en dépit de tout le battage qui est fait autour, Jeopardy! n’est qu’une vitrine pour l’entreprise. Les ambitions d’IBM sont bien plus élevées: apprendre à une machine à comprendre un langage écrit pour les humains et non pour les ordinateurs. C’est l’un des Saints Graals de la recherche sur l’intelligence artificielle (AI), une technologie qui révolutionnerait tous les secteurs aujourd’hui handicapés par le fait que les ordinateurs sont nuls lorsqu’il s’agit de comprendre ce que l’on appelle «le langage naturel».

Les ordinateurs imbattables aux dames

Le projet Watson consiste, au moyen d’un jeu humain relativement simple, à apprendre à un ordinateur les facultés qui lui seront nécessaires pour réussir ailleurs dans la vie. Tous les jeux auxquels peuvent jouer les ordinateurs n’ont pas cette vertu. Aucun être humain ne peut battre une machine programmée pour jouer parfaitement aux dames, mais l’existence de logiciels sophistiqués de jeux de dames ne résout aucun des problèmes classiques de l’intelligence artificielle. Certes, on devrait bien pouvoir trouver quelque application aux algorithmes de prise de décision qu’ils utilisent, mais rien de comparable à la carrière post-Jeopardy! qui s’ouvre à Watson.

Pour faire simple, le développement de programmes informatiques capables de battre les plus grands champions humains aux dames (ou même aux échecs) n’a pas eu de grandes répercussions si ce n’est dans le monde des jeux de société. Mais cela n’a pas toujours semblé évident. Il y a quelques dizaines d’années, avant la victoire du Deep Blue d’IBM sur le champion du monde d’échecs Garry Kasparov, nous imaginions qu’un tel exploit ne pourrait être accompli que par une machine capable de penser de façon créative en exploitant les tendances et habitudes de son adversaire. Mais l’émergence des puissances de traitement massives semble avoir effacé le besoin d‘innovations majeures en matière d’IA. Cela fait 14 ans que s’est déroulé ce fameux match à New York. Comme l’a écrit Kasparov l’année dernière dans la New York Review of Books :

«Au lieu de concevoir un ordinateur qui aurait réfléchi et joué aux échecs comme un humain, avec une créativité et une intuition humaines, ils ont créé une machine, qui jouait comme une machine, en évaluant de manière systématique 200 millions de coups possibles par seconde pour finir par gagner grâce à la force brute des chiffres.»

L’un des chercheurs de l’équipe Watson avec qui j’ai pu parler a contesté cela, affirmant que l’élément stratégique tenait une place aussi importante dans le programme Deep Blue que la puissance de calcul (l’un des membres de la première équipe de Deep Blue travaille désormais dans l’équipe Watson). On peut cependant dire sans se tromper que les algorithmes qui ont eu raison de Kasparov n’ont pas révolutionné l’industrie. Les échecs n’étaient pas le jeu qu’il fallait aux informaticiens, voilà tout. Il existe, à vrai dire, une foule d’autres jeux dans lesquels les ordinateurs se révèlent incompétents et dont la maîtrise représenterait, en fait, une avancée extraordinaire pour l’intelligence artificielle. C’est notamment le cas du poker.

Texas Hold'Em

Il peut paraître étrange qu’il soit plus facile de concevoir une machine capable de gagner à Jeopardy! qu'un ordinateur capable de remporter une vraie partie de poker. Le jeu télévisé, après tout, aborde tous les sujets possibles et imaginables, tandis que les jeux de cartes sont basés sur les interactions de 52 unités individuelles, selon des probabilités a priori calculables. Les bon joueurs de Texas Hold'Em (une variante du poker) parviennent à estimer leur chance de constituer telle ou telle main en fonction des cartes qu’ils ont en main et de celles qu’ils voient sur la table. On ne voit donc pas pourquoi un ordinateur ne pourrait pas faire un malheur au casino.

Pour un Hold’Em à deux joueurs avec mises limitées, les ordinateurs sont plutôt bons. En 2008, un programme baptisé «Polaris» a affronté une équipe de joueurs professionnels avec comme résultats deux parties gagnées, une perdue et une ex aequo. Les ordinateurs sont plus faciles à battre en «no-limit» —les enchères illimitées compliquent les algorithmes et modifient la stratégie optimale— mais les chercheurs pensent que ce problème finira par être réglé. Ce type de jeu à deux joueurs est, d’une certaine manière, assez prévisible. Mais dès que l’on ajoute un troisième joueur, c’est la panique.

«Dans les jeux à deux joueurs, une bonne réponse est toujours fondamentalement possible» afin de déterminer la décision à prendre, affirme Michael Bowling, responsable du groupe de recherche sur le poker électronique de l’Université d’Alberta. «C’est un jeu équitable —sur le long terme, je suis certain de ne pas perdre d’argent. À chaque fois que mon adversaire fait une erreur, j’en tire profit.» Cela revient à dire qu’il est possible de développer une stratégie optimale, puisqu’il y a toujours un meilleur coup qu’un autre à faire. Que tout le monde se rassure: les ordinateurs sont bien incapables de décrypter la gestuelle ou le comportement de leurs adversaires. Un poker à deux joueurs est essentiellement une question de mathématiques.

De deux à trois joueurs

Ajouter un troisième joueur revient à peu près à passer d’un monde en 2D à un monde en 3D: le «un contre un» du début cède la place à un trio de relations «un contre deux». Le concept du «bon coup» adapté à chaque situation est relégué aux oubliettes et le fragile équilibre stratégique est rompu. Les stratégies des trois joueurs deviennent interdépendantes et reposent désormais autant sur des considérations statistiques que psychologiques. Michael Bowling m’a décrit une expérience dans laquelle trois ordinateurs —ou «bots»— étaient parvenus à un ex-aequo virtuel lors d’une partie de Hold 'Em simplifiée à trois joueurs. Pour mettre à l’épreuve ce subtil équilibre, les chercheurs placèrent l’une des machines en mode «toujours relancer» (une stratégie généralement peu recommandable). À leur grande surprise, cette relance automatique ne pénalisa pas tant que ça le bot concerné. Celui placé à sa gauche, en revanche, nettoya la table—et celui de droite y laissa sa chemise.

C’est en cela que le poker pose un problème intéressant: afin de développer un excellent bot multijoueur, les programmeurs devraient modéliser non seulement les probabilités, mais aussi les gens. «Si nous souhaitons prendre en charge ces jeux à plusieurs, il va nous falloir travailler sur les comportements» a affirmé Bowling. Cela va au-delà de la théorie traditionnelle des jeux et au-delà de la force de calcul brute et des stratégies qui constituaient l’ADN de Deep Blue. Si un ordinateur ne peut interpréter le langage du corps, il pourrait en revanche glaner bon nombre d’informations à partir de schémas plus explicites du comportement humain. Chercheur en informatique à l’University of California, Los Angeles (UCLA), Leonard Kleinrock –dont l’étudiant le plus célèbre est le pro du poker Chris Ferguson– affirme que le moment et la vitesse auxquels une personne effectue ses mises pourraient, par exemple, faire partie des données exploitables par la machine (on peut, par exemple, penser qu’un joueur mise immédiatement lorsqu’il bluffe et qu’il met plus de temps lorsqu’il a une main moyenne). On pourrait également prendre en compte la fréquence à laquelle un adversaire est pris en train de bluffer, le type de mains qu’il aime le plus jouer et la manière dont ses mises changent au fil de la partie.

Economie

Jusqu’ici, la plupart des travaux interdisciplinaires ont été réalisés avec des économistes, qui ont depuis longtemps incorporé la théorie du jeu dans leurs propres modèles. Les deux côtés font preuve d’un intérêt certain pour le poker. L’un des économistes avec qui j’ai pu parler, Roger McCain, a immédiatement émis la suggestion que les chercheurs en IA s’intéressent au «Three card draw», variante plus stratégique que le Hold 'Em, en partant du point de vue de la vulnérabilité de l’être humain. «On sait bien que les gens ne choisissent pas toujours la meilleure stratégie», souligne-t-il. Les autres modèles abordent le jeu en partant du principe que l’adversaire est extrêmement rusé. À vrai dire, le fait même de pouvoir «cerner» les adversaires représenterait une innovation majeure pour le monde de l’informatique. Comme souvent avec ces technologies émergentes, les applications les plus évidentes seraient dans la finance: le poker et la spéculation boursière reposant tous deux sur une prise de risque avec de l’argent en ligne de mire, il n’est pas difficile d’imaginer comment un modèle informatique créé pour le poker pourrait servir d’outil à tous ceux qui jouent sur les marchés. De manière plus générale, l’analyse des comportements des joueurs pourrait aider les économistes à comprendre certains changements brusques, voire irrationnels, de comportement (comme, par exemple, lorsque les gens déplacent leur argent, vendent leurs maisons, achètent des obligations d’État ou se montrent prêt à tout pour anticiper un changement de conjoncture).

Le développement d’un tel programme constituerait une entreprise majeure pour laquelle il ne suffirait pas d’enfermer dans une même pièce quelques informaticiens et quelques économistes. Nombre de chercheurs en IA estiment que les modèles économiques actuels sont irréalistes en matière de comportement, car ils considèrent que les gens vont agir de manière stratégique après avoir réfléchi à des milliers d’options différentes. «Au fond, [les informaticiens] critiquent les théories économiques parce qu’elles impliquent une grande puissance de calcul de la part des différents acteurs», commente Constantinos Daskalakis, théoricien du jeu au MIT. Il existe en économie une ligne de recherche bien plus prometteuse, que l’on nomme «rationalité limitée» et qui prend en compte le fait que les humains ne disposent que de telle ou telle puissance de calcul. Toutefois, ce sujet nécessite encore un certain développement avant de pouvoir être utilisé par les programmeurs.

À l’inverse des programmes de dames ou d’échecs, un programme de poker analysant les comportements des joueurs commencerait enfin à ressembler à ce que ne fut jamais Deep Blue: une machine jouant comme un humain. Il ne fait aucun doute que le premier ordinateur qui remportera le National Heads-Up Poker Championship aura gagné grâce à sa puissance de calcul brute. Mais il aura aussi compris une chose ou deux sur la personnalité de ses adversaires: qui ils sont, le type d’erreurs qu’ils sont capables de commettre, les moments où ils sont les plus vulnérables… Je vois d’ici Watson dans Poker After Dark, annonçant à ses adversaires humains de sa voix métallique: «Tapis!»

Chris Wilson

Traduit par Yann Champion

Photo: Le tournoi de poker à l'Empire Casino de Londres en 2009, REUTERS/Luke MacGregor 

En poursuivant votre navigation sur ce site, vous acceptez l’utilisation de cookies pour réaliser des statistiques de visites, vous proposer des publicités adaptées à vos centres d’intérêt et nous suivre sur les réseaux sociaux. > Paramétrer > J'accepte