Vous êtes ici
L'intelligence artificielle devient stratège
Derrière sa simplicité trompeuse, le jeu de go offre des choix tactiques si variés que les intelligences artificielles, ou IA, semblaient devoir éternellement s’y casser les dents. En mars 2016, la forteresse est pourtant tombée quand AlphaGo a battu 4 à 1 Lee Sedol, un des meilleurs joueurs du monde. Le logiciel s’est depuis encore amélioré et a pulvérisé, début janvier 2017, un panel de champions par cinquante victoires d’affilée. Au même moment, l’IA Libratus de l’université Carnegie-Mellon plumait quatre requins à une variante du poker, le Texas Hold’em.
La stratégie en temps réel : un défi inédit
AlphaGo a été développé par DeepMind, une entreprise d’intelligence artificielle rachetée en 2014 par Google. La firme est résolue à ne pas en rester là et a annoncé, en novembre 2016, qu’elle allait désormais s’attaquer à Starcraft II. Dans ce jeu vidéo de stratégie extrêmement populaire, les joueurs s’affrontent « à mort » en récoltant des ressources qui permettent de construire des bases et des unités. Il est possible de jouer à plusieurs en même temps, avec ou sans équipe, mais les compétitions officielles se déroulent en un contre un. Comme bon nombre de jeux vidéo, Starcraft II donne lieu à des tournois avec des cagnottes pouvant atteindre 500 000 dollars. Ces compétitions suscitent une concurrence féroce, et DeepMind compte bien y piocher ses adversaires.
Comparé aux échecs et au go, Starcraft II pose toutefois des défis inédits. D’abord, il se déroule en temps réel et non au tour par tour : tout le monde joue en même temps. Les différentes cartes officielles qui servent de plateau ne sont pas divisées en une centaine de cases, mais offrent une quasi-infinité de positions différentes. Les joueurs sont confrontés au « brouillard de guerre » qui limite la connaissance des actions et des positions de l’adversaire au champ de vision de ses unités. Enfin, les joueurs peuvent incarner trois « races » complètement différentes, comme si les noirs et les blancs ne disposaient pas des mêmes pièces aux échecs.
Comment le go fut vaincu
Pour défaire les joueurs de go, l’entreprise s’était appuyée sur la recherche arborescente Monte-Carlo et l’apprentissage profond. « La technique de la recherche arborescente Monte-Carlo repose sur la construction d’un arbre des états d’un problème proches de l'état à évaluer et sur des statistiques de parties aléatoires. On utilise les résultats des parties aléatoires précédentes pour choisir les prochains coups à essayer », explique Tristan Cazenave, professeur à l’université Paris-Dauphine et membre du Laboratoire d’analyse et modélisation de systèmes pour l’aide à la décision (Lamsade)1.
L’apprentissage profond passe par des réseaux d’algorithmes, inspirés des neurones, qui décomposent successivement les tâches. Les premières couches vont repérer des fragments de situations très simples, tandis que les dernières aboutissent à une interprétation de l’ensemble. L’IA étudie d'abord les parties de compétiteurs de haut niveau puis joue contre elle-même partiellement au hasard. En répétant l’opération des millions de fois, l’IA finit par disposer de statistiques solides qu’elle est en mesure d’utiliser pour s’adapter et combattre correctement. Les chercheurs ne lui suggèrent ainsi aucune stratégie, mais lui donnent les moyens de trouver par elle-même les meilleures.
« Ces intelligences artificielles ont énormément d’applications, poursuit Tristan Cazenave. Les algorithmes employés pour le go sont par exemple les mêmes que ceux de reconnaissance d’images. L’augmentation de la puissance des machines et l’amélioration des algorithmes expliquent les forts progrès réalisés récemment. »
De l’apprentissage profond aux heuristiques
Reste que si la méthode a vaincu le go, qui offre 361 points pour poser un jeton, le format des cartes de Starcraft II tourne autour de 150 x 150. Le nombre de positions avoisine donc les 22 500 possibilités pour chaque soldat, sachant que chaque joueur peut en amasser jusqu’à un maximum de 200. L’échelle des options explose complètement et représente le principal défi pour les IA.
La saga Starcraft sert en fait depuis longtemps de terrain de recherche, même sans intention de battre les humains. La « AIIDE Starcraft AI Competition » permet depuis 2010 à des chercheurs et des passionnés de faire s’affronter leurs intelligences artificielles sur Brood War, une version antérieure à Starcraft II. « Pour l’instant, personne n’utilise d’apprentissage profond dans ces compétitions, détaille David Churchill, professeur adjoint d’informatique à l’Université Memorial de Terre-Neuve et organisateur de l’événement depuis 2011. Je me focalise sur la recherche heuristique, plus adaptée au temps réel. »
Face à un problème, les fonctions heuristiques fournissent des approximations du coût de chaque solution possible et éliminent progressivement les moins efficaces. L’accumulation de ces règles fixées par le programmeur permet de ne garder que les choix, a priori, les plus intéressants. La méthode perd la puissance de l’apprentissage profond, mais évite les longs entraînements que celui-ci réclame. Les éditeurs de jeux vidéo ne s’en servent d’ailleurs pas non plus dans les créations.
Rester réaliste et laisser sa chance au joueur
« Nous cherchons à divertir les joueurs, à leur donner l’impression d’affronter les généraux d’autres pays, précise Carl Carenvall, programmeur d’IA sur Hearts of Iron IV, la référence des jeux de stratégie sur la Seconde Guerre mondiale. Notre IA doit prendre des décisions qui ont du sens par rapport à l’histoire et ne pas faire se comporter le Japon impérial de la même manière que la France libre. Nous n’utilisons ainsi pas d’apprentissage profond, nous préférons garder la main sur l’IA pour lui donner de la personnalité. »
Un objectif similaire aux projets de DeepMind. Carl Carenvall estime ainsi que Google et Facebook s’intéressent aux RTS non seulement pour améliorer l’efficacité de leurs algorithmes, mais aussi pour que leurs résultats et interactions semblent moins froids et déshumanisés aux utilisateurs.
Mais qu’en pensent les joueurs ? PtitDrogo, pseudonyme de Théo Freydière, est le seul Français à avoir remporté un premier tournoi de Starcraft II en 2016, la catégorie la plus prestigieuse. Il estime que la victoire d’une IA sur l’homme à son jeu préféré n’a rien d’impossible. En revanche, comme Starcraft II se joue en temps réel, PtitDrogo pense qu’il faut impérativement brider le nombre d’actions par minute (APM) que peut réaliser l’IA. « Un joueur pro réalise 300 APM, un ordinateur n’a aucun souci à dépasser les 3 000, explique-t-il. S’il peut contrôler individuellement 50 unités en même temps, il nous battra très facilement juste en abusant de ça. » DeepMind a annoncé que les APM de son IA seraient en effet bridées.
Florian Richoux, maître de conférences à l’université de Nantes et membre du Laboratoire des sciences du numérique à Nantes (LS2N)2, pense aussi qu'il faut avant tout améliorer les algorithmes. Il a d’ailleurs participé à TorchCraft, un frameworkFermerUn framework est un cadre applicatif servant de fondation à des logiciels. Dans le cas présent, il permet aux programmeurs qui s’intéressent au sujet de ne pas partir de zéro qui permet de lier l’interface de Brood War et la bibliothèque d’apprentissage profond Torch. Open source, le projet a été soutenu par Facebook. « Il n’y a pas encore d’IA capable de jouer une partie entière de Starcraft grâce à l’apprentissage profond, reconnaît-il. Torchcraft sert pour l’instant à des sous-problèmes, comme la gestion de petits groupes d’unités sans stratégie précise. »
Florian Richoux n’écarte pas pour autant la possibilité que DeepMind réserve quelques surprises, alors que l’entreprise a promis de premiers résultats pour début 2017. Quant à l’intérêt de Facebook et Google, qui ne produisent pas de jeux vidéo : « Seule une toute petite fraction de la communauté des chercheurs étudie l’IA pour améliorer les jeux, conclut-il. Pour l’écrasante majorité, c’est juste un cadre très pratique et médiatique pour les tests. »
Mots-clés
Partager cet article
Auteur
Diplômé de l’École supérieure de journalisme de Lille, Martin Koppe a notamment travaillé pour les Dossiers d’archéologie, Science et Vie Junior et La Recherche, ainsi que pour le site Maxisciences.com. Il est également diplômé en histoire de l’art, en archéométrie et en épistémologie.
Voir aussi
Commentaires
Connectez-vous, rejoignez la communauté
du journal CNRS