L’intelligence artificielle, joueuse de poker hors pair

Une IA capable de jouer pour mieux ressembler aux humains ?

Comment des algorithmes pourraient-ils réaliser des tâches complexes aussi bien que les humains ? Pour répondre à cette question, les scientifiques ont d'abord étudié la reconnaissance d'images dès la fin des années 1950. « Mais ce n'était que le début, souligne Vianney Perchet, coresponsable de l'équipe-projet FAIRPLAY et professeur au CREST (Centre de recherche en économie et statistique) à l'ENSAE Paris (École nationale de la statistique et de l'administration économique). Pour aller plus loin, il fallait se poser la question différemment : quelle action humaine, avec un impact sur son environnement et le futur, pourrait être automatisée et effectuée par une intelligence artificielle ? Les chercheurs se sont alors orientés vers des problèmes de décision à long terme. »

Dans ce cadre, c'est le jeu qui a été choisi, pas pour son aspect ludique, mais afin d'appréhender les conséquences des décisions prises par deux "agents" qui interagissent, les joueurs. Le jeu de dames a été étudié dans les années 1970, puis les échecs.

L'équipe FAIRPLAY, entre économie et théorie des jeux

La théorie des jeux, c'est justement la spécialité de la jeune équipe FAIRPLAY, créée en 2022, par l'entreprise Criteo, l'école d'ingénieurs ENSAE et Inria. Réunissant deux chercheurs d'Inria, cinq de l'ENSAE et cinq de Criteo, elle s'est donnée pour mission d'étudier les interactions entre cette théorie, le machine learning et l'économie. « Le rapprochement de nos trois entités au sein d'une équipe commune crée une situation gagnant-gagnant, estime Vianney Perchet. En particulier, notre coopération avec une entreprise privée nous permet de nous confronter à des problématiques réelles. Plutôt que choisir un sujet d'étude parce qu'il nous plaît, je trouve plus pertinent de partir des applications, de les abstraire mathématiquement pour résoudre une problématique. » En général, les recherches sur le machine learning se concentrent sur des cas avec un seul agent (un algorithme). L'équipe FAIRPLAY, elle, se distingue puisqu'elle s'intéresse aux systèmes économiques qui font interagir différents agents, par exemple plusieurs entreprises. Dans le cadre de ces modèles multi-agents, les chercheurs se montrent particulièrement attentifs au respect de la vie privée, de l'éthique et de l'équité.

Des algorithmes qui jouent au poker

Revenons aux jeux. Avez-vous entendu parler de l'ordinateur Deep Blue, vainqueur aux échecs contre le champion du monde Garry Kasparov en 1996 ? Ce n'était pas encore tout à fait de l'IA, mais à partir de là, la communauté scientifique a recherché des défis encore plus complexes pour faire progresser les algorithmes. Dans les années 2010, elle a opté pour le jeu de go dont la richesse combinatoire et la profondeur stratégique dépassent les échecs.

Mais que ce soit pour les dames, les échecs ou le go, chaque joueur voit le plateau et dispose donc des mêmes données. « Or, dans la vraie vie, tous les humains n'ont pas les mêmes informations pour décider », remarque Côme Fiegel, doctorant dans l'équipe FAIRPLAY. Toutefois, un jeu se rapproche de cette réalité : le poker. « Au poker, chaque joueur a des informations secrètes et dissymétriques », ajoute le jeune chercheur. En 2021, des scientifiques, qui collaborent aujourd'hui avec l'équipe FAIRPLAY, ont donc créé des algorithmes qui jouent au poker. Ils ont ensuite voulu s'assurer qu'ils pouvaient trouver la meilleure solution dans un temps fini. C'est le cas. Leurs algorithmes sont capables d'apprendre des stratégies quasi optimales relativement rapidement, que Côme Fiegel a perfectionnées dans le cadre de sa thèse, avec le soutien de l'équipe FAIRPLAY.

Le message clé […] de notre équipe est de porter la plus grande attention aux stratégies cachées, qui n'avaient jamais été abordées dans les recherches précédentes. Avec ce résultat, nous avons franchi un échelon de la recherche sur la question de jeux de plus en plus compliqués.

Vianney Perchet

Coresponsable de l'équipe FAIRPLAY et professeur au CREST à l'ENSAE Paris

Des bandits manchots pour optimiser les choix des joueurs

« L'arbre de décision permet l'exploration des prédictions de la solution optimale, précise le doctorant. Celui-ci n'était pas parfait et pour l'améliorer, j'ai appliqué l'idée des "bandits manchots". » Imaginez que vous entrez dans un casino rempli de machines à sous, appelées autrefois bandits manchots. Vous devez choisir sur quelle machine jouer. Chaque machine offre une récompense et l'objectif est de cumuler un maximum de gains.

« Pour trouver la meilleure machine, vous pouvez essayer chaque machine les unes après les autres. Mais cela va vous coûter très cher. De manière plus subtile, votre stratégie peut osciller entre l'exploitation - qui consiste à utiliser la machine qui récompense beaucoup - et l'exploration - qui consiste à tester une autre machine pour espérer gagner plus. » Pour résoudre ce dilemme entre exploitation et exploration, l'équipe FAIRPLAY a utilisé la méthode FTRL (Follow The Regularized Leader), qui est un algorithme d'optimisation. Le principe ? On choisit une machine au hasard, mais en favorisant les actions jusqu'ici les plus fructueuses. Ainsi, à terme, on opte avec une très grande probabilité pour la meilleure stratégie.

Méfions-nous de l'adversaire qui cache son jeu

Dans le domaine des jeux, le meilleur algorithme est celui qui sera optimal face à la pire situation possible. Par exemple, l'un des joueurs peut masquer une partie de son jeu pour tromper l'algorithme. « Il faut donc envisager cette option lors de l'exploration de l'arbre de décision, explique Côme Fiegel. Sinon, la stratégie de jeu ne sera pas optimale et l'algorithme sera moins rapide. » Une réalité qui n'était pas prise en compte jusqu'ici dans les algorithmes du jeu de poker et qui a servi de base à sa thèse.

En considérant tous les paramètres du problème, le doctorant a ainsi calculé l'algorithme afin qu'il soit le plus rapide possible dans le pire des cas. Une recherche très innovante, dont le résultat été distingué lors de la conférence de machine learning ICML avec l'attribution en 2023 d'un Best Paper Award. « Le message clé de l'article de Côme et de notre équipe est de porter la plus grande attention aux stratégies cachées, qui n'avaient jamais été abordées dans les recherches précédentes, résume Vianney Perchet. Avec ce résultat, nous avons franchi un échelon de la recherche sur la question de jeux de plus en plus compliqués ». L'étape suivante ? « Le jeu de poker avec plus de deux joueurs, pour refléter encore davantage la réalité de la société, poursuit le coresponsable de l'équipe FAIRPLAY. Une mission nettement plus complexe et loin d'être achevée car dans la vraie vie, nous sommes beaucoup plus que deux joueurs ! »

En savoir plus

• « L'homme reprend le dessus sur l'intelligence artificielle au jeu de go », Siècle Digital, 20/02/2023.
• « Une intelligence artificielle gagne au poker à six joueurs, une première », Les Échos, 13/07/2019.
• « Le champion de go détrôné par l'ordinateur », La Recherche, avril 2016.
• « Comment éviter les cas de discrimination tout en protégeant les données des utilisateurs ? » (Présentation de l'équipe FAIRPLAY), 29/03/2022.