Pourquoi avons-nous besoin de jouer? Cette question a depuis longtemps fasciné les philosophes et psychologues avec de nombreux essais nous expliquant pourquoi les jeux constituent une activité fondamentale chez les humains, enfants ou adultes. Il existe une grande variété de jeux, allant des jeux de plateau comme les dames, les échecs, ou le go, aux jeux vidéo de plus en plus élaborés, tels que Eve Online, ou World of Warcraft, nous immergeant dans des univers virtuels immenses. Le chiffre d’affaires de l’industrie vidéoludique mondiale représente aujourd’hui près de deux fois celui du cinéma. Il n’est donc pas étonnant que les jeux constituent un domaine phare de l’intelligence artificielle.
En fait, les jeux de plateau font partie des toutes premières applications de l’intelligence artificielle: dès 1950, Claude Shannon propose un algorithme de recherche pour jouer aux échecs et, peu après, Arthur Samuel chez IBM écrit le premier programme capable de jouer aux dames. Depuis lors, l’intelligence artificielle des jeux n’a cessé de progresser, avec des résultats spectaculaires comme DeepBlue pour les échecs, AlphaGo pour le go, et maintenant AlphaStar pour StarCraft.
Naturellement, ce résumé n’offre qu’un tour d’horizon rapide du vaste domaine qu’est l’intelligence artificielle des jeux. Nous commençons par présenter quelques catégories de jeux et d’intelligence artificielle, puis examinons quelques paradigmes algorithmiques pour résoudre les jeux.
Catégories de jeux. Afin d’appréhender l’intelligence artificielle des jeux, il est nécessaire de commencer par regrouper les jeux existants en catégories. Pour cela, la théorie des jeuxthéorie mathématique modélisant les interactions stratégiques entre un certain nombre d’agents (individus, organisations, robots, etc.), permettant de trouver les comportements optimaux, afin par exemple de tenter d’expliquer ou de prédire le comportement des agents. Les notions de solution en théorie des jeux, notamment la notion... More* offre un cadre formel permettant de classer les jeux selon diverses dimensions, telles que le type de jeu (compétitif ou coopératif), le nombre de joueurs, la présence du hasard, l’information dont disposent les joueurs, la durée des événements, etc. La catégorie la plus connue en intelligence artificielle est celle des jeux compétitifs à deux joueurs (zero-sum two-player games), dont font partie les jeux d’échecs, de dames ou de go. Dans ces jeux, définis dès les années 1940 par John von Neumann et Oskar Morgenstern, les joueurs ont une observation totale du plateau et leurs coups sont déterministes. De tels jeux peuvent être représentés sous forme extensive par un arbre, appelé game treeen français “arbre de jeu”, est une représentation arborescente d’un jeu, comme un ensemble de nœuds (représentant les différentes configurations possibles) reliés par des arêtes (les coups possibles), et dont les nœuds finaux (appelés feuilles) ont une valeur représentant l’évaluation de la situation pour les... More*, dont les feuilles capturent les états terminaux, ou fins de partie. En théorie, ces jeux peuvent être résolus par une stratégie MiniMaxrecherche arborescente pour les jeux à deux joueurs qui permet de prévoir l’évaluation de la situation plusieurs coups à l’avance. Cette méthode est par exemple à la base des programmes jouant aux échecs.... More* qui correspond à trouver un équilibre de Nashnotion proposée par John Nash en 1950. Un équilibre de Nash d’un jeu (voir Théorie des jeux*) représente une solution possible de ce jeu si tous les joueurs jouent individuellement de manière optimale (plus exactement il s’agit d’une situation possible du jeu où aucun des... More* du jeu. Au-delà de cette catégorie, on trouve la classe des jeux stochastiques (stochastic games) faisant intervenir le hasard (comme le backgammon), et plus généralement la classe des jeux stochastiques à information partielle (partially observable stochastic games) faisant aussi intervenir des éléments cachés (comme le poker ou Civilisation). Avec l’arrivée des jeux de stratégie temps-réel (comme StarCraft), les chercheurs en intelligence artificielle ont aujourd’hui identifié des classes encore plus élaborées, capturant la durée des actions et l’incertitude sur cette durée.
Catégories d’IA. Il existe deux grandes tendances en intelligence artificielle pour jouer: l’intelligence artificielle dédiée qui se focalise sur un seul jeu, et l’intelligence artificielle générique qui vise à résoudre toute une catégorie de jeux. Les objectifs sont différents. Pour l’intelligence artificielle dédiée, le but est d’intégrer les stratégies inventées par les experts humains pour un jeu donné et, potentiellement, d’apprendre des stratégies encore meilleures pour ce jeu. Les programmes tels que
DeepBlue (IBM), AlphaGo et AlphaStar (Google DeepMind) sont des systèmes d’intelligence artificielle dédiés, capables aujourd’hui d’affronter les meilleurs joueurs humains sur un jeu spécifique. Dans le cadre de l’intelligence artificielle générique, appelée aussi General Game Playing (GGP), le but est de comprendre quels sont les algorithmes efficaces pour traiter toute une variété de jeux et, à terme, de transférer les connaissances* acquises dans un jeu donné vers un autre. Dans ce cadre, le programme ne connaît pas à l’avance le jeu : il commence par recevoir les règles d’un nouveau jeu dans un langage déclaratif (appelé Game Description Language ou GDL) et, au bout de quelques minutes, doit s’affronter à un humain ou un autre programme.
Catégories d’algorithmes. Avec la richesse des jeux existants, il existe aujourd’hui une grande variété d’algorithmes d’IA pour les jeux, dédiés ou génériques. On peut néanmoins classer ces algorithmes selon trois grandes périodes dans l’intelligence artificielle des jeux. La première période est celle des années 1950-2000, avec l’invention d’algorithmes de recherche arborescente, équipés de techniques d’élagage (comme alpha-beta pruningen français “élagage alpha-beta”, technique utilisée dans les arbres de jeu (voir Game Tree*) pour éliminer (élaguer) des parties (branches) de l’arbre de jeu que l’on sait non prometteuses, afin de gagner en efficacité.... More*), de tables de transposition pour mémoriser des informations sur les états déjà rencontrés, et d’heuristiques* pour les fonctions d’évaluation des nœuds du game treeen français “arbre de jeu”, est une représentation arborescente d’un jeu, comme un ensemble de nœuds (représentant les différentes configurations possibles) reliés par des arêtes (les coups possibles), et dont les nœuds finaux (appelés feuilles) ont une valeur représentant l’évaluation de la situation pour les... More. La seconde période débute en 2006 avec l’arrivée des algorithmes de type Monte Carlo Tree Searchla recherche arborescente Monte-Carlo (MCTS) consiste à simuler de nombreuses séquences aléatoires d’actions ou d’étapes dans la résolution d’un problème, et d’en apprécier le résultat final sur un critère de coût ou d’utilité. Ces simulations conduisent au choix de la meilleure première action. Avant ce... More* (MCTS), utilisant à nouveau la recherche arborescente, mais incorporant des techniques d’échantillonnage et d’apprentissage (bandits multi-bras*) pour estimer la fonction d’évaluation. Enfin, depuis 2015, la troisième période est l’avènement de l’apprentissage par renforcement profondapprentissage par renforcement* qui utilise des réseaux de neurones profonds* pour la mise à jour de son modèle.... More* (Deep Reinforcement Learning) pour prédire le prochain coup (et donc réduire la largeur de l’arbre), et pour prédire la valeur des positions (et donc remplacer l’échantillonnage). Les joueurs AlphaGo et AlphaStar sont conçus sur de telles architectures profondes, permettant au programme de jouer des millions de parties contre lui-même et de découvrir de nouvelles stratégies gagnantes. Les programmes d’apprentissage par renforcement profondapprentissage par renforcement* qui utilise des réseaux de neurones profonds* pour la mise à jour de son modèle.... More ont été appliqués à de nombreux jeux, sans utiliser de connaissances préalables de ces jeux, où ils obtiennent de meilleurs résultats que les programmes dédiés.