Press "Enter" to skip to content

3.8. Jeux

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 jeux* 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 tree*, dont les feuilles capturent les états terminaux, ou fins de partie. En théorie, ces jeux peuvent être résolus par une stratégie MiniMax* qui correspond à trouver un équilibre de Nash* 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 pruning*), 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 tree. La seconde période débute en 2006 avec l’arrivée des algorithmes de type Monte Carlo Tree Search* (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 profond* (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 profond 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.