Intelligence artificielle et StarCraft

Mine de rien j’ai pas mal de chose à dire, alors comme ça risque d’être un petit peu long, pour plus de clarté je divise le post en 3 chapitres : Algo génétique pour build order, Concours d’IA pour Starcraft 1 et Appel à participation (à ne pas rater).

Algorithme génétique pour build order

StarCraft est bourré de termes techniques, et comme je pense que la plupart d’entre vous ne les connaissent pas, je vais les définir au fur et à mesure. Alors, c’est quoi un build order (BO) ? Comme son nom l’indique, c’est une séquence ordonnée de constructions. Rappelez-vous, j’en parle dans le billet précédent : un BO est une séquence d’ouverture dans StarCraft, c’est-à-dire les actions à faire en début de parties afin de pouvoir appliquer le plus rapidement possible la ou les stratégies choisies (je rappelle que SC est un jeu temps réel : être plus rapide que son adversaire est la clé de la victoire).

L’un des lecteurs de ce blog (JIM pour ne pas le nommer), également joueur de SC1 et 2, m’avait envoyé le lien d’un billet très intéressant sur un programme optimisant le BO de la race Zerg (l’une des trois races disponibles) en utilisant un algorithme génétique. En gros un algo génétique, c’est un algorithme d’optimisation qui va reproduire le schéma de sélection naturel. Pour cela, vous prenez une population d’individus (ici des BO satisfaisant le but à atteindre, à savoir une certaine stratégie donnée). Chaque individu est par nature plus ou moins fort (plus un BO se termine tôt, plus il est « fort »), cette force innée étant caractérisée par des propriétés génétiques (la séquence d’actions du BO). On garde les individus les plus forts et qui satisfont le but à atteindre, puis on renouvelle avec eux la population par croisements génétiques (la reproduction) où intervient parfois une modification aléatoire (mutation génétique). On répète l’opération (sélection, croisements, mutations) un certain nombre de fois, et on peut espérer arriver au bout d’un temps t à un super poulain pure race.

Pour info, c’est cet algo génétique qui a découvert le BO optimal pour la stratégie 7-Roaches sur SC2 (je vais pas rentrer dans les détails), l’une des stratégie les plus redoutable lorsque l’on joue Zerg. Et le BO trouvé par cet algo demande d’appliquer des séquences d’actions contre-intuitives (comme produire 2 overlords de suite), qui sont reconnue être en général sous-optimales. Bref, pas sûr qu’un être humain aurait trouvé ce BO par lui-même, ou alors il aurait fallu une bonne dose d’intuition et de créativité.

J’ai moi-même lancé cet algo sur mon PC. C’est un programme en java pas rapide (pléonasme) mais efficace qui a mis 1h30 à trouver le BO optimal 7-Roaches (et même une seconde plus optimal que le BO connu) en testant près de 3 millions de BO différents (555 BO par seconde) sur un dual core 2,66Gh avec 3Go de ram. Pour les curieux, le BO est le suivant :

@0:00    M:50    G:0    L:3    S:6/10    BuildDrone
@0:13    M:51    G:0    L:2    S:7/10    BuildDrone
@0:15    Spawned:    Larva+1
@0:17    Spawned:    Drone+1
@0:24    M:52    G:0    L:2    S:8/10    BuildDrone
@0:30    Spawned:    Drone+1
@0:30    Spawned:    Larva+1
@0:34    M:54    G:0    L:2    S:9/10    BuildDrone
@0:41    Spawned:    Drone+1
@0:45    Spawned:    Larva+1
@0:51    Spawned:    Drone+1
@1:00    Spawned:    Larva+1
@1:05    M:204    G:0    L:3    S:10/10    BuildSpawningPool
@1:13    M:55    G:0    L:3    S:9/10    BuildDrone
@1:28    Spawned:    Larva+1
@1:28    M:100    G:0    L:3    S:10/10    BuildOverlord
@1:30    Spawned:    Drone+1
@1:43    Spawned:    Larva+1
@1:43    M:105    G:0    L:3    S:10/10    BuildOverlord
@1:46    M:26    G:0    L:2    S:10/10    BuildExtractor
@1:53    Spawned:    Overlord+1
@1:54    M:52    G:0    L:2    S:9/18    BuildDrone
@1:58    Spawned:    Larva+1
@2:08    Spawned:    Overlord+1
@2:10    Spawned:    Spawning Pool+1
@2:11    Spawned:    Drone+1
@2:13    Spawned:    Larva+1
@2:16    Spawned:    Extractor+1
@2:17    M:152    G:0    L:3    S:10/26    BuildRoachWarren
@2:17    M:2    G:0    L:3    S:9/26    MineGas
@2:17    M:2    G:0    L:3    S:9/26    MineGas
@2:19    Mining:     +1 on gas
@2:19    Mining:     +1 on gas
@2:27    M:51    G:12    L:3    S:9/26    BuildDrone
@2:42    Spawned:    Larva+1
@2:44    Spawned:    Drone+1
@3:12    Spawned:    Roach Warren+1
@3:12    M:241    G:75    L:3    S:10/26    BuildRoach
@3:12    M:166    G:50    L:2    S:12/26    BuildRoach
@3:12    M:91    G:25    L:1    S:14/26    MineGas
@3:12    M:91    G:25    L:1    S:14/26    BuildRoach
@3:14    Mining:     +1 on gas
@3:27    Spawned:    Larva+1
@3:27    M:91    G:28    L:1    S:16/26    BuildRoach
@3:39    Spawned:    Roach+1
@3:39    Spawned:    Roach+1
@3:39    Spawned:    Roach+1
@3:42    Spawned:    Larva+1
@3:42    M:90    G:32    L:1    S:18/26    BuildRoach
@3:54    Spawned:    Roach+1
@3:57    Spawned:    Larva+1
@3:57    M:89    G:35    L:1    S:20/26    BuildRoach
@4:09    Spawned:    Roach+1
@4:12    Spawned:    Larva+1
@4:12    M:88    G:39    L:1    S:22/26    BuildRoach
@4:24    Spawned:    Roach+1
@4:27    Spawned:    Larva+1
@4:39    Spawned:    Roach+1
Satisfied.
Number of actions in build order: 32
—Final Output—
At time: 4:39
Minerals: 147    Gas:      65    Supply:   24/26
Drones: 10
Overlords: 3
Roaches: 7
Hatcheries: 1
Gas Extractors: 1
Spawning Pools: 1
Roach Warrens: 1

Concours d’IA pour Starcraft 1

À la mi-novembre de cette année était organisé un concours d’IA de StarCraft 1, à l’Université de Santa Cruz, Californie, lors de la conférence Artificial Intelligence and Interactive Digital Entertainment (AIIDE 2010). La page du concours est ici. Ce concours ouvert à tout le monde proposait 4 types de tournois : deux de micro-gestion, un de matchs à actions limitées et enfin un tournoi de matchs classiques, ce dernier étant bien entendu le plus intéressant car le plus complet et complexe. Les IA étaient tous différents, certains se focalisant sur la même stratégie (très mauvaise idée, et pourtant…), d’autres cherchant à s’adapter en fonction de la situation à travers de l’analyse et de l’apprentissage automatique. Le vainqueur du tournois est l’IA nommée « Overmind » de l’Université de Berkeley (même si le concours est ouvert à tous, c’est a priori les universitaires travaillant dans l’IA qui sont les mieux placés pour le remporter). Mais franchement, je trouve qu’ils ne méritait pas de gagner. Il y a un gros travail dessus, là c’est clair : il s’agit toute de même d’un projet de 10 personnes, plus un chef de projet épaulé par deux chefs adjoints. Mais leur IA a remporté tous ses matchs en appliquant la même technique qu’aucune IA n’a su contrer (harass mutalisks puis mass muta), sauf lors d’un match qu’il a perdu dû à une close position de son adversaire qui lui a rasé sa base par un run-by zealots avant qu’Overmind n’ait eu le temps de faire sa spire. Bref, rien de bien excitant au final. En plus, leur projet est complètement fermé : pas de code source disponible, ce qui je trouve est un comble pour ce genre de compétition, le but premier étant quand même de faire avancer la recherche en appliquant des résultats d’IA sur un « environnement commercial robuste » qu’offre StarCraft (pour reprendre les termes de la conf.) Pas d’articles ni de pre-print (pré-article si vous préférez) pour exposer à la communauté de chercheurs comment ils ont procédé et choisi les diverses facettes de leur IA. J’ai écris au chef du projet pour lui demandé s’il avait des pre-prints à m’envoyer ; je n’ai reçu aucune réponse. Tout ça sent à plein nez la licence propriétaire pour leur programme. Ils espèrent quoi ? Vendre leur IA à Blizzard ?

Franchement, on peut mieux faire. Et comme disait un autre lecteur de ce blog qui se reconnaitra, « si on peut, on doit ».

Appel à participation

L’année prochaine, la conf AIIDE 2011 sera organisée à l’Université d’Alberta au Canada, et inclura une nouvelle édition du concours d’IA pour SC 1. Je suis sans doute un peu fêlé de m’intéresser de si près à ce concours (celui de type 4, le plus complet) alors que j’ai déjà assez peu de temps libre, mais je me sens vraiment motivé. Question : il y a t-il quelques autres fêlés qui voudraient se lancer dans l’aventure ? On a un an pour faire une « kick-ass AI ».

J’ai quelques idées, notamment pour injecter de l’optimisation à travers des méthodes de recherche locale stochastiques (c’est-à-dire aléatoires), ce sur quoi je travaille. D’où mon projet Aiur (Artificial Intelligence Using Randomness). Avec un nom comme ça, je pense que la race choisie sera Protoss. ^^

Si comme moi vous sentez que ce projet vous enflamme, écrivez-moi un mail (plutôt qu’un commentaire sur ce billet) à l’adresse suivante : florian.richoux_arobase_gmail.com (en remplaçant bien sûr _arobase_ par le fameux symbole). Le projet est ouvert à tout le monde. Si jamais je ne vous connais pas, merci de me préciser en quelques mots vos compétences en IA théorique et/ou en algorithmique et/ou en programmation C++ (car oui, ça sera en C++). Je me réserve tout de fois le droit de rejeter une candidature si j’estime que vous n’avez pas le profil (mais j’accepte tous mes potes, car ça peut être délire de faire ça tous ensemble).

Que l’on soit bien d’accords, j’ai quelques idées de comment faire (et j’ai un plan de bataille pour l’organisation, en fait tout est déjà prêt), mais il reste quasiment tout à définir. Toutes idées sont les bienvenues, alors j’espère vous voir nombreux à répondre à cet appel ! (NB : je suis sur Kyoto aujourd’hui et demain, mais pas d’affolement je répondrai aux mails à partir de mercredi)

And the winner is…

Il y a quelques heures, sont tombés les résultats des lauréats de la Médaille Fields 2010, la plus honorifique distinction en Mathématiques.

Car vous savez qu’il n’y a pas de prix Nobel en Maths. La Médaille Fields est attribuée tous les 4 ans (contre tous les ans pour le Nobel) à des mathématiciens de moins de 40 ans (pas de limite d’âge pour le Nobel). Il y a souvent 4 lauréats une même année, mais ce n’est pas une règle gravée dans le marbre.

Et une fois de plus, la France a pété le score : sur les 4 lauréats 2001, 2 sont Français. Allez, je vais compter les médailles comme pour les J.O. : ça nous en fait 11 (sur 52 depuis 1936), nous mettant à la 2ème place derrière les States (13 médailles). Vu la différence d’investissement dans la recherche entre ces deux pays, c’est un sacré score !

Cette année, les heureux élus sont Villani, un dandy aux goûts vestimentaires bloqués deux siècles en arrière, 36 ans, ENS comme il se doit et directeur de l’Institut Henri Poincaré (IHP pour les intimes). Il fait des Maths pour la physique. On lui a notamment attribué la médaille pour ces travaux sur la théorie cinétique (énergie dépendant de la vitesse de mouvement). Un lecteur de ce blog m’avait dit une fois qu’il détestait les informaticiens théoriciens, c’est-à-dire ma famille scientifique. Je trouve ça dommage ce genre d’attitude fratricide, mais bon, c’est malheureusement assez courant.

L’autre Français est Châu, d’origine Vietnamienne. Il est récompensé par avoir démontré le « lemme fondamental », unifiant la théorie des nombres, la géométrie algébrique et l’analyse (rien que ça). Les deux autres lauréats sont l’Israélien Lindenstrauss et le Russe Smirnov (nasdrovia !), tout deux pour des travaux autour de la statistique. A noter qu’un nom était bien pressenti, le Brésilien Avila, mais il a sans doute été écarté pour son jeune âge (30 ans, putain à peine 3 ans de plus que moi…). Il est donc éligible pour deux fois encore, et il l’aura, c’est quasi-assuré.

On n’oublie pas l’autre prix décerné le même jour, le prix Gauss en Maths appliqués. Cette fois un seul lauréat tous les 4 ans, et c’est aussi un Français qui l’a raflé : Meyer, pour ses études sur les ondelettes et leurs applications dans la compression. L’algorithme de la compression d’image JPEG, c’est notamment à ce Monsieur que nous le devons. Il a développé ça quand il était au CMAP à l’X, au bureau juste au dessus du mieux quand j’étais moi-même à l’X. Le prix ayant été créé en 2006, il n’y a pour l’instant que 2 lauréats : Meyer cette année et le Japonais Ito (en 2006 donc).

De part les contraintes de l’attribution de la Médaille Fields (moins de 40 ans, une fois tous les 4 ans), la très haut distinction en Mathématique qui se rapproche le plus des conditions du prix Nobel (pas de limite d’âge, tous les ans) est le prix Abel créé en 2003. Là encore la France se gave : 3 prix Abel sur 9, deuxième place derrière les States (5 prix). Franchement, y’a de quoi avoir la tête haute, surtout si on prends en compte les conditions de recherche que sont les nôtres en France…

Pensées

Après m’être fait éclater la lèvre supérieure au karate hier soir ; après m’être fait arracher quelques bouts de peau de ma main gauche car j’ai oublié de mettre des gants de protection au practice de baseball tout à l’heure (note pour plus tard : devenir moins con) ; je vais écrire et décrire nos journées au tournoi de sumo et au théâtre noh. Mais avant, j’ai envie de déballer quelques unes de mes pensées du moment.

En ce moment, je réfléchis beaucoup. Je veux dire, plus que d’habitude. Sur mes deux ans en post-doc ici. Sur l’après post-doc. Sous plusieurs angles différents, notamment sous un angle professionnel. Je me lance dans un domaine tout nouveau pour moi, l’IA (l’intelligence artificielle). Je l’aborde avec enthousiasme, j’arrive avec quelques idées personnelles, et surtout avec des yeux neufs, n’ayant jamais été formé à travailler là dedans. J’ai conscience de mon cas : je n’ai pas été formaté aux idées et méthodes actuelles des chercheurs en IA, mais j’ai tout de même un peu de recul par rapport à le recherche et à son univers, chose qu’un jeune doctorant commençant sa thèse n’a pas. Il est donc tentant pour moi de vouloir me lancer dans des directions ayant un grand potentiel novateur mais jugées « dangereuses » car s’annonçant être de la recherche à très long terme et dans l’inconnu le plus total. Ce n’est toute fois pas la meilleure idée de se lancer à corps perdu dans de telles directions car un post-doc est le moment de montrer que l’on est capable d’obtenir de « bonnes » publications rapidement, quitte à taper dans le réchauffé et à faire plus de la soupe que de la Science. Le système de recrutement s’est perverti en ne prenant plus compte qu’une productivité qui n’est possible qu’avec de la recherche à court terme. Et je ne parle même pas des recrutements biaisés par le piston. Mais heureusement les mathématiques et l’informatique sont assez épargnés de ce fléau.

Alors que faire ? Se montrer sage pendant mes années de post-doc, montrer que moi aussi je peux faire de la soupe aussi bien que les autres, et si j’ai la chance d’être recruté CNRS commencer à faire de la vraie recherche (car les jeunes maîtres de conférence n’ont pas le temps de vraiment faire de la recherche ; on ne leur en donne pas les moyens en France pour cela) ? Ben ouais, y’a pas vraiment d’autres alternatives…

J’ai dernièrement eu un bref échange d’email avec l’un des grands ponte français de l’IA, et ce dernier est bien pessimiste. Il pense que de réels résultats en IA sont possibles, mais que l’on ne s’en donne pas les moyens (ni financier, ni en organisation), que cela devrait requérir une vraie communauté travaillant dessus avec aucun espoir d’avoir des résultats concrets durant les premières décennies. Mais cela n’est en phase ni avec la structuration de la recherche aujourd’hui ni avec la volonté politique actuelle. Selon lui, la réelle IA est possible, mais on ne la verra jamais…

Bon allez, maintenant j’arrête de me lamenter et j’attaque les articles promis qui seront publiés d’ici quelques jours !

PS : c’était le 50ème article.

Calculer l’incalculable

Peu de gens ont conscience que les ordinateurs ne peuvent pas tout calculer. C’est en effet un résultat bien connu dans mon domaine de recherche : la machine de Turing, modèle théorique des ordinateurs, a des limites bien déterminées en terme de potentiel calculatoire, c’est-à-dire qu’il y a des problèmes que les ordinateurs ne peuvent calculer et ne sauront jamais résoudre.

Par exemple, considérons le problème de décider si une formule arithmétique (donc avec des variables « x, y, z, … »,  les symboles « +, -, *, /, = », les entiers relatifs et les quantifications « pour tout, il existe ») est vraie ou fausse. Plus concrètement si je prends la formule « pour tout x, il existe y tel que y = x+1 », celle-ci est clairement vraie : vous prenez n’importe quel nombre, il existe toujours un nombre un cran au dessus. Par contre la formule « pour tout x et tout y, il existe z tel que x = y * z » est faux, car si vous prenez x=1, y=2 par exemple, il n’existe aucun entier relatif z tel que 1 est égal à 2 fois z. Et bien le problème de décider si une formule arithmétique est vraie ou fausse est un problème indécidable, c’est-à-dire qu’un ordinateur est incapable de trouver une solution à ce problème. Ce n’est pas une question de puissance, c’est une question de faisabilité : il n’existe pas de méthode automatique pour résoudre ce problème en temps fini, donc un ordinateur ne pourra jamais y répondre.

Jamais ? Pas sûr. Des gens bien barrés ont étudié cette question de l’incalculable sous un angle… je dirai… original.

Dans la famille « je-prends-une-dose-de-LSD-à-tuer-un-cheval-et-ensuite-je-fais-de-la-science », je demande Malament, Hogarth, Etesi, Németi et Welch. Ces gens-là ont démontré des résultats ENORMES ! En voici un extrait.

Le temps n’est pas un long fleuve tranquille qui s’écoule uniformément. C’est une dimension non-normée dans le sens où le temps ne s’écoule pas pareil suivant les situations. Cet écoulement est relatif à un repère donné ; c’est ce que nous explique le principe de relativité générale d’Einstein.

Malament et Hogarth ont défini ce qui s’appelle maintenant les espaces-temps de Malament-Hogarth. Il s’agit d’espaces-temps où il existe une trajectoire infinie lamba telle qu’il existe un évènement p sur cette trajectoire où tous les évènements de lamba y sont antérieurs (alors que lamba est infini, je le rappelle). Ça veut dire qu’on a une suite infinie d’évènements, mais dans cette suite il y a un évènement qui succède à tous les évènements. Bon, déjà ça, c’est pas un résultat pour les mous du slip.

Hogarth avait déjà démontré en 1994 qu’il existait un espace-temps de Malament-Hogarth dans lequel un ordinateur pouvait calculer la décision de l’arithmétique, mais sans en exhiber d’exemple. C’est ce que font  Etesi et Németi dans cet article de 2002, où ils démontrent qu’un tel espace-temps de Malament-Hogarth est présent autour d’un trou noir en rotation et à charge électrique nulle, appelé trou noir de Kerr. Ainsi, un ordinateur ordinaire en orbite autour d’un tel trou noir, tournant autour tel une bille dans le lavabo sans jamais tomber dans le siphon, pourrai calculer notre problème pendant un temps infini pendant que nous, utilisateur, nous récupérions le résultat de ce calcul infini (le fameux évènement p où tout calcul serait antérieur). Ceci est théoriquement possible puisque l’écoulement du temps autour du trou noir serait nul, comme gelé, aux yeux d’un observateur extérieur, laissant ainsi infiniment de temps pour laisser l’ordinateur finir son calcul. Petit revers de la médaille, si j’ai bien compris pour accéder à cet évènement p dans cet espace-temps de Malament-Hogarth, il faudrait que l’utilisateur tombe dans le trou noir, ce qui risque d’engendrer quelques séquelles. De plus, ce résultat (car c’est pas du flan, ça a été démontré quand même) néglige les phénomènes d’évaporation du trou noir qui voit sa masse diminuer ou augmenter en fonction de la quantité de radiations émises et de rayonnements électromagnétiques absorbés.

Mais Welch va plus loin dans le craquage du slip scientifique : dans cet article de 2006, il présente deux résultats sidérants. Il démontre en effet que 1) pour tout prédicat hyper-arithmétique P  sur les entiers naturels, il existe un espace-temps de Matament-Hogarth dans lequel toute requête du type « n appartient-il à P ? » est calculable, et 2) pour tout espace-temps de Matament-Hogarth, il existe un ordinal dénombrable majorant la compléxité de l’arithmétique dans la hiérarchie de Borel. Autrement dit, dans tout espace-temps de Matament-Hogarth, l’arithmétique dans la hiérarchie de Borel est non seulement décidable, mais elle l’est en temps constant !

Je sais que vous panez rien. Rassurez-vous, moi non plus je ne capte pas grand chose de ces résultats. Mais je trouve ça énorme que des mecs se perdent dans de folles élucubrations et arrivent quand même à y prouver des résultats théoriquement justes ! Y’a pas à dire, la théorie, c’est beau.

Les oreilles de Mickey

Un bail que je n’avais rien écris ici ! Il est grand temps d’y remédier.

Il y a deux mois (ah ouais, déjà quand même), Mari et moi nous sommes allés à Disney Sea, juste à côté de Disneyland Tokyo, parc de la célèbre souris qui a l’eau comme thème principal. Ceux qui me connaissent bien savent que je ne suis pas un grand fan des parcs d’attraction, mais Mari si, donc on y est quand même allé. ^^’ Et puis c’était à 30 minutes en bus de notre ancien logement, donc on (elle) voulait en profiter avant que l’on ne déménage.

On y a donc passé toute une journée, pratiquement de l’ouverture à 10h jusqu’à pratiquement la fermeture à 22h. Et ben je dois avouer que c’était pas mal du tout, et plusieurs choses m’ont impressionné.