Skip to content. | Skip to navigation

Emergences

Lettre d'information n° 30

Image emergences pour impression
Personal tools
You are here: Home 2014 Lettre d'information n° 30 L'intelligence artificielle progresse à StarCraft
Document Actions

L'intelligence artificielle progresse à StarCraft

Dès 1997, l'ordinateur Deep Blue battait le champion d'échecs Garry Kasparov. Mais il reste encore du chemin avant que l'intelligence artificielle puisse rivaliser avec un être humain dans un jeu de stratégie en temps réel (RTS) comme StarCraft. Ces dernières années, un tournoi s'est mis en place pour donner aux scientifiques l'occasion d'évaluer les progrès dans le domaine et de comparer leurs IA respectives. Lors de la dernière rencontre en date, la médaille de bronze a été attribuée à AIUR 2.1, une création de Florian Richoux, chercheur de l'équipe projet Tasc* au Lina, à Nantes.

Dès 1997, l'ordinateur Deep Blue battait le champion d'échecs Garry Kasparov. Mais il reste encore du chemin avant que l'intelligence artificielle puisse rivaliser avec un être humain dans un jeu de stratégie en temps réel (RTS) comme StarCraft. Ces dernières années, un tournoi s'est mis en place pour donner aux scientifiques l'occasion d'évaluer les progrès dans le domaine et de comparer leurs IA respectives. Lors de la dernière rencontre en date, la médaille de bronze a été attribuée à AIUR 2.1, une création de Florian Richoux, chercheur de l'équipe projet Tasc* au Lina, à Nantes.

Le Secteur Kropulu ? Un recoin sombre de la Voie Lactée où Protoss, Terrans et Zergs se livrent une guerre aux proportions cosmiques. Apparu en 1998, StarCraft incarne le jeu de stratégie en temps réel par excellence. Avec onze millions d'exemplaires vendus sur la planète Terre, il reste à ce jour indétrôné.

Le jeu propose trois races très différentes et conserve un excellent équilibre entre elles, explique Florian Richoux (1). Aucune n'a le dessus sur les autres. De plus, il existe des professionnels, des tournois télévisés, quantités d'informations et beaucoup de matchs à analyser. On peut ainsi toucher une grande communauté de joueurs, de sponsors et de spectateurs. Rien de tel pour promouvoir la recherche en Intelligence Artificielle.

De fil en aiguille, StarCraft est devenu l'étalon à l'aune duquel se mesurent les avancées scientifiques dans le domaine. Chaque année, en Amérique du Nord, un tournoi machine contre machine se déroule durant la conférence AIIDE (Artificial Intelligence and Interactive Digital Entertainment). “Je m'y suis intéressé à partir de 2010, se souvient Florian Richoux. Cette année-là, Overmind, l'IA de l'Université de Berkeley, avait remporté le tournoi. Au vu des matchs, elle semblait complètement scriptée. Elle appliquait systématiquement la même stratégie —certes efficace— quelque soit l'adversaire. Je me suis dit que je pouvais faire mieux. Et c'est comme ça que je me suis lancé.

Une dose d'aléatoire


Le chercheur a donc développé AIUR (Artificial Intelligence Using Randomness). Cette AI a remporté la médaille de bronze au tournoi organisé durant AIIDE 2013. “L'idée de base c'est de laisser certains choix stochastiques afin de la rendre plus difficilement prédictible. Surtout ne pas toujours appliquer la même stratégie. Toutes les IA, y compris la mienne, demeurent bien trop scriptées. Cependant, AIUR comporte une touche d'aléatoire à deux niveaux. Premièrement, et c'est le plus important, elle dispose de 5 stratégies très différentes.” On les appelle aussi des ‘humeurs’. Durant les premiers matches contre un joueur, l'IA les essaye chacune tour à tour et observe laquelle marche le mieux. “De cette phase initiale d'apprentissage, AIUR déduit une distribution de probabilité de sélection de stratégies contre cet adversaire. Elle favorise les stratégies gagnantes sans s'interdire des stratégies moins efficaces mais qui peuvent porter leurs fruits de temps en temps. Deuxièmement, certaines actions sont pondérées par de l’aléatoire : timing de la première attaque, nombre d'unités affectées à la prochaine offensive...”

Comme dans la réalité, le fameux brouillard de guerre théorisé par Clausevitz s'invite sur le champ de bataille. “Et c'est là que réside tout l'intérêt. Ce brouillard recouvre toute la carte. Il ne se dissipe qu'à proximité de vos unités. Au-delà, vous ignorez ce que trame l'adversaire. Que ce soient des humains ou des machines, les joueurs doivent deviner et anticiper les coups adverses à partir des quelques bribes d'informations qu'ils ont pu collecter.

L'humain meilleur décideur


Quand il s'agit de spéculer à partir d'une information aussi fragmentaire, l'être humain reste inégalé. “On ne connaît pas encore de bons algorithmes pour prendre des décisions efficaces dans les jeux de stratégie en temps réel. Toutes les techniques appliquées jusque là pour les échecs ou le go... échouent.” Et aucune solution n'est à espérer du côté de la puissance de calcul. “Pour StarCraft, une estimation optimiste du nombre d'états de jeu possibles et valides par minute avoisine 2.10690. Mener des simulations classiques de Monte Carlo est pratiquement sans espoir. Même sur les meilleurs super-calculateurs. Aussi puissante soit-elle, aucune machine ne peut explorer efficacement le gigantesque espace de recherche des choix menant à autant d'états du jeu. Il faut en quelque sorte lire entre les lignes. Or, l'ordinateur n'est pas très doué pour cela.

D'où le besoin de nouvelles techniques aptes à contourner cet obstacle. Actuellement, à StarCraft, les meilleurs IA perdent face à de bons débutants. "Mais au jeu de go, nous commençons à avoir des IA qui battent des joueurs professionnels partant avec seulement 4 pierres de handicap. Je suis certain que d'ici 2 ou 3 ans, même sans handicap, les pros devront s'incliner.

Cela dit, l'intelligence artificielle en RTS demeure un domaine de recherche relativement nouveau. “Tout reste à construire. Ce qui est passionnant.” La discipline va-t-elle contribuer à lever des verrous scientifiques ? “J'en suis convaincu, répond Florian Richoux.  Devant un problème qu'on ne sait pas résoudre, la démarche scientifique habituelle consiste à simplifier ce problème. Je vois StarCraft comme une simplification du monde réel qui, à l'instar du jeu, est lui aussi un environnement dynamique à information incomplète. Des algorithmes efficaces de prise de décisions pour StarCraft devraient pouvoir s'appliquer avec succès à des problématiques plus ambitieuses comme la robotique, la gestion automatique du trafic aérien, la finance...


------
Note:
(1) Florian Richoux est membre de Tasc, une équipe-projet Inria, Ecole des Mines de Nantes, Université de Nantes, CNRS, Laboratoire d'Informatique de Nantes Atlantique (LINA) (UMR6241). Tasc travaille sur la programmation par contraintes.

Lire aussi : “A Survey of Real-Time Strategy Game AI Research and Competition in StarCraft” (pre-print disponible ici).