Les jeux, d’une manière générale ont toujours été l’un des domaines d’application favoris de l’IA.

Pour les jeux de plateau et ceux reposant sur des bases mathématiques en général, l’objectif est principalement d’étudier la logique combinatoire du jeu (pour battre un être humain aux échecs, résoudre un Rubik’s Cube, …).

Pour les jeux vidéo, on peut distinguer trois catégories d’IAs :

• Les IAs rendant l’environnement de jeu plus vivant. (Exemple : comportement des PNJs, ennemis dans un jeu…)
• Les IAs facilitant la création de contenu, rendant les jeux plus réalistes et diminuant les coûts de production.
• Les IAs rentrant en compétition avec l’homme, ayant potentiellement pour objectif de le dépasser.

L’IA développée dans le cadre du projet AI-craft fait partie de la troisième catégorie : pour mesurer nos performances sur le jeu, nous les comparerons à celles d’êtres humains. Cependant nous discuterons ici les problématiques propres à chacune de ces trois catégories, afin de faire un rapide état de l’art et définir le contexte.

---

Utiliser l’IA pour améliorer l’environnement du jeu

L’un des principaux objectifs de l’IA dans les jeux vidéos est d’améliorer l’expérience utilisateur, en rendant le jeu aussi immersif, et amusant que possible. Parfois en rajoutant des ennemis, ou en donnant vie à différents éléments du décor.

La tâche était assez aisée sur les premiers jeux vidéos, dont les moteurs de jeux étaient très simples. Prenons l’exemple de Pac-Man :

Sur ce jeu, chaque fantôme possède une stratégie différente pour attraper le joueur :

• Blinky (le fantôme rouge) suit constamment Pac-Man.
• Pinky (le fantôme rose) tente de se positionner devant Pac-Man.
• Inky (le fantôme cyan) est imprévisible, et se comporte parfois comme Blinky, parfois comme Pinky.
• Clyde (le fantôme orange) se comporte bêtement. (Il tente des embuscades avant de s’en aller quand il est sur le point de réussir)

Ces comportements sont très simples à implémenter, puisqu’il s’agit simplement de décider dans quelle direction aller selon l’état du jeu.

Cependant, à mesure que les jeux-vidéos évoluent, de nouvelles difficultés commencent à apparaître : les univers virtuels deviennent de plus en plus grands, et de plus en plus réalistes. En conséquence, les agents sont de plus en plus nombreux, et doivent avoir des comportements de plus en plus complexes.

Une autre contrainte à gérer est celle du temps réel : un personnage dans un jeu vidéo ne peut pas se permettre de réfléchir avant d’agir.

Comment réussir à implémenter des comportements réalistes en un temps record ?

La réponse à cette question peut être synonyme de réussite ou d’échec commerciale pour une licence de jeu.

---

Utiliser l’IA pour créer du contenu

Automatiser la création de contenu est un enjeu crucial de l’industrie vidéoludique, tant il permet de réduire le coût de production des jeux vidéo.

En effet, une grande partie de ce coût provient de la création de l’univers dans lequel le joueur évolue. Prenons l’exemple d’un jeu “open-world”, comme Zelda Breathe of the Wild :

Ce jeu, qui a été développé en cinq ans et dont on estime le coût à environs 100 millions d’euros, offre au joueur la possibilité de se déplacer librement dans un monde qui est extrêmement riche.

Dans ce jeu, il est entre autres possible :

• D’interagir avec son environnement de nombreuses manières (port et destruction d’objets, escalades, …)
• D’interagir avec de très nombreux PNJs qui possèdent chacun une histoire.
• De visiter des lieux variés (lacs, donjons, volcans, aéronefs, …).
• D’utiliser des centaines d’objets différents, ayant chacun leurs caractéristiques propres.

Chacune de ces possibilités est synonyme de nombreuses heures de réflexion scénaristique, de modélisation 3D, et de tests, parfois infructueux. Ce travail est une constante : si 50 heures de travail sont investies pour modéliser un bâtiment, 50 heures de travail seront nécessaires pour en faire un deuxième.

Ainsi, réussir à automatiser une partie du travail d’un artiste est synonyme de gain de temps, et d’argent.

---

Utiliser l’IA pour battre des jeux

Les jeux en général ont un intérêt indéniable pour la recherche en IA. En effet, ils ont plusieurs caractéristiques intéressantes :

• Il est facile d’interagir avec eux.
• On peut mesurer la performance de l’IA en lui faisant affronter des joueurs humains.
• Ce sont des sujets d’études n’ayant pas été biaisés pour favoriser un certain résultat.

Les premiers jeux sur lesquels on a véritablement fait de la recherche sont le jeu d’échecs et le jeu de Go : deux jeux millénaires, compétitifs, dont les enjeux stratégiques sont transmis de génération en génération.

Le jeu d’échecs

Kasparov contre Deep Blue

Le premier ordinateur ayant battu un GM humain au jeu d’échec est Deep Thought, de IBM. Ce super-calculateur était capable d’analyser 720 000 coups par seconde, ce qui lui a permis de remporter la victoire contre le danois Bent Larsen en 1988.

Curieux des capacités de cette IA, un match entre Deep Thought et Kasparov (champion du monde d’échecs) a alors été organisé, en 1989. A cette occasion, Kasparov vainquit facilement Deep Thought, et déclara que jamais un programme n’arriverait à le battre.

Huit ans plus tard (soit en 1997), IBM proposa un match retour à Kasparov. Leur nouveau super-calculateur, Deep Blue, pouvait analyser 200 millions de coups par seconde. Deep Blue remporta la victoire (3,5 - 2,5), et la machine dépassa alors l’homme aux échecs.

Deep Blue n’était pas particulièrement plus intelligent que Deep Thought, c’est sa puissance de calcul qui lui a permis de remporter la victoire.

Ces IAs sont composés de deux éléments :

• Un moteur de calcul, chargé de parcourir les coups possibles à partir d’une position.
• Une fonction d’estimation, définissant la désirabilité de chaque position potentielle.

Autrement dit, à partir d’une position donnée, l’IA va estimer toutes les positions possible plusieurs (entre 6 et 12) coups à l’avance, puis appliquer le coup dont l’issue semble être la meilleure.

La fonction d’évaluation a été partiellement apprise en autonomie, grâce à l’analyse de milliers de parties d’experts. (A quel point est-il important de contrôler le centre ? Quels sont les meilleurs placements du roi ?)

Le jeu de Go

La difficulté de créer une IA au jeu de Go

Les échecs possèdent un “branching factor” entre 31 et 35. Cela signifie qu’en moyenne, il est possible de jouer entre 31 et 35 coups différents à une position donnée.

On peut donc estimer qu’il existe, en moyenne, à peu près 39 millions de façons différentes de jouer cinq coups aux échecs. Pour Deep blue, cela représente à peu près 40 millions de coups à estimer si on considère les états intermédiaires.

En comparaison, le “branching factor” du jeu de Go est de 250.

Cela signifie qu’il existe en moyenne environs :

• 250 manières de jouer un coup
• 62500 manières de jouer deux coups
• 15 millions de manières de jouer trois coups
• 4 milliards de manières de jouer quatre coups
• 1 billion de manières de jouer cinq coups.

C’est là la raison pour laquelle le jeu de Go a été un bien plus grand challenge pour l’IA que le jeu d’échecs.

À titre de comparaison, lorsque Deep Blue a battu Kasparov en 1997, il était possible pour les champions de Go de battre les meilleures IAs avec 25 pierres de handicap (c’est beaucoup, et un tel handicap les mettrait en difficulté face à n’importe quel novice).

Le jeu de Go s’est donc imposé comme le prochain grand challenge pour l’IA, et nombreux pensaient qu’il ne serait pas possible de battre des champions de Go avant 2030 ou 2040.

Les avancées techniques

Jouer au Go à un niveau élevé est une tâche extrêmement complexe en raison du grand nombre de mouvements possibles. Pour relever ce défi, l’intelligence artificielle utilise une combinaison intelligente de deux techniques s’étant développées entre temps : la recherche arborescente de Monte Carlo (MCTS) et des réseaux de neurones profonds.

1. Recherche Arborescente de Monte Carlo (MCTS)

   MCTS est une méthode de recherche qui construit un arbre de décision en explorant les mouvements possibles dans le jeu de Go. Elle procède en simulant des parties et en utilisant les résultats de ces simulations pour évaluer la qualité des mouvements. Toutefois, étant donné l’énorme espace de possibilités dans le jeu de Go, MCTS seule n’est pas suffisamment efficace. Elle a besoin d’être guidée pour se concentrer sur des parties spécifiques de l’arbre.

2. Les Réseaux de Neurones Profonds Comme Guides

   Les réseaux de neurones sont très communs en intelligence artificielle, car ils peuvent apprendre des informations très diverses. Ici, ils sont utilisés pour analyser les positions et guider la MCTS vers des branches plus prometteuses de l’arbre des possibilités. Les réseaux de neurones accomplissent cela en fournissant deux types d’informations cruciales :

   • Estimation de la Valeur : Les réseaux de neurones évaluent la position actuelle du plateau et estiment la probabilité de gagner depuis cette position. Cette information est utilisée par MCTS pour évaluer l’utilité de poursuivre l’exploration le long de certaines branches de l’arbre.

   • Probabilités de Politique : Ils fournissent également des informations sur les mouvements que les joueurs sont susceptibles de faire à partir d’une position donnée. Ces informations permettent à MCTS de se concentrer sur l’exploration de mouvements qui sont plus susceptibles d’être choisis par de bons joueurs.

En combinant la recherche systématique de MCTS avec les analyses précises des réseaux de neurones, l’intelligence artificielle peut parcourir l’arbre des possibilités de manière très efficace. Cela permet de se concentrer sur les parties de l’arbre qui sont plus susceptibles de conduire à de bons résultats, tout en évitant l’exploration inutile de mouvements moins prometteurs.

En résumé, MCTS explore les possibilités, tandis que les réseaux de neurones servent de guides analytiques pour cette exploration. Ensemble, ils ont considérablement amélioré la performance de l’intelligence artificielle dans le jeu de Go, comme démontré par des programmes tels que AlphaGo de DeepMind.

Lee Sedol contre AlphaGo

Grâce à ces deux avancées techniques (Monte Carlo Tree Search et les réseaux de neurones profonds), il a été possible de créer de nouvelles IAs pouvant véritablement rivaliser avec les meilleurs joueurs de Go.

En octobre 2015, DeepMind, organisme de Google, propose au champion d’Europe de Go d’affronter sa nouvelle IA, AlphaGo. Le résultat est sans appel : l’IA remporte la victoire, 5 à 0.

C’est une première grande étape pour l’IA, puisque ces victoires ont été obtenues sans aucun handicap, et les gens commencent à se demander ce qu’AlphaGo est véritablement capable de faire.

En mars 2016, un nouveau match est organisé entre Lee Sedol, 9eme Dan de Go et parmis les meilleurs joueurs du monde, contre AlphaGo.

À cette occasion, AlphaGo s’est imposé 4 à 1, permettant à l’IA de remporter une nouvelle victoire sur l’être humain.

Et depuis ?

Depuis la victoire de AlphaGo sur Lee Sedol, le challenge pour l’IA ne se trouve plus sur les jeux de plateau, mais sur les jeux vidéo.

En effet, ils sont encore plus difficiles à appréhender pour la machine, et sont d’un véritable intérêt pour la recherche.