Alors alors…

Alors je sais pas si vous l’avez remarqué, mais c’est un peu la dèche sur ce blog…

C’est vrai j’avoue, je n’ai ni trop le temps ni trop la motivation de le maintenir. J’annonce donc plus ou moins officiellement ce que tout le monde a déjà remarqué : sa mise en stand-by. Ce n’est toutefois pas une fermeture, on sait jamais, je le reprendrai peut être un jour.

Mais je ne suis pas complètement ingrat et je vous donne deux autres moyens de prendre de mes nouvelles : vous pouvez me suivre via google+ (si du moins ce truc survit, et ça semble mal parti) sur mon compte +florianrichoux et via Twitter sur @FloRicx.

Sinon, y’a l’email hein, n’hésitez pas !

Quelques photos (et non, ça ne signifie pas une reprise active de ce blog :-p)

Toujours si peu de temps (et de motivation, faut bien l’avouer) pour entretenir ce blog, alors pour me faire pardonner voici quelques photos du mois de mai :

– Lune de miel en Nouvelle Calédonie : https://picasaweb.google.com/florian.richoux/NouvelleCaledonieLuneDeMielMai2011#

– Enchaînée avec 5 jours (tout seul cette fois, car pour le boulot :-p) à Bangkok : https://picasaweb.google.com/florian.richoux/BangkokMai2011#

À plus les enfants !

Oh mon dieu !

Mais ce blog à un an aujourd’hui ! Ça nous rajeunit pas tout ça…

Pour la peine je changerai la skin bientôt. De toute façon l’actuelle ne me plaisait que moyennement. Et je vais tenter de mettre bientôt quelques photos de l’automne nippon.

À plus alors !

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)

My life for Aiur

Comme vous le savez, j’ai plein de choses en retard dont je dois vous parler. La cérémonie du thé, le petit parc mignon juste à côté de chez nous, les magnifiques couleurs d’automne dont le Japon est en train de se vêtir, les pâtisseries de Mari, …

Je ne vais vous parler de rien de tout ça. Du moins, pas maintenant ni la prochaine fois. Ce post est une première partie d’une chose dont j’aimerai parler et qui est en train de me passionner en ce moment, et ça va au delà du jeu.

Le lecteur averti aura compris de quoi je vais parler grâce au titre. C’est bel et bien de StarCraft, jeu dont j’ai déjà parlé à une occasion (à savoir ici). Aujourd’hui on va se concentrer sur StarCraft 2 (disons SC2). J’ai craqué fin septembre, me suis pris la version US du jeu (il n’est pas vendu au Japon), n’est pas le temps d’y jouer mais apprécie beaucoup de regarder des parties commentées de joueurs renommés, voire de professionnels. Car oui, il y a des professionnels de SC, (essentiellement des Coréens, ce jeu étant un phénomène de société là-bas) s’entraînant quotidiennement comme les sportifs de hauts niveaux, reçoivent un salaire par un sponsor, et deviennent entraîneurs / managers lorsqu’ils ne peuvent assurer le rythme des compétitions.

Je sais que faire d’un jeu vidéo son métier est considéré comme incongru (pour rester soft) par beaucoup de personnes, là où personne ne s’offusque de voir des joueurs professionnels d’échecs par exemple. On me dit : « la comparaison est mal choisie, c’est exagéré ». Ben pas du tout. De mon point de vue, StarCraft est le jeu d’échecs moderne.

Ou plutôt, je trouve SC plus proche du jeu de go (où il existe également des pros principalement au Japon, en Corée et en Chine). Il y a de flagrantes différences entre ces deux jeux, à commencer par le fait que le premier est en temps réel (les deux joueurs jouent simultanément), le second est du tour par tour. Et aussi, SC est un jeu à l’information incomplète (on ne sait pas en permanence ce que fait l’adversaire) alors que chaque joueur d’échecs et de go voit l’intégralité du plateau de jeu. Nous avons donc deux jeux de nature complètement opposée à première vue.

Là où SC rejoint les échecs, et surtout le go, c’est par la stratégie. Comme au go, il y a une notion de gestion locale et de stratégique globale (appelé micro-gestion et macro-gestion pour SC). La première concerne la gestion du combat, à savoir le placement des pierres (des unités) au go (à SC). La seconde, plus complexe, correspond à l’occupation spatiale du plateau (de la carte). Comme au go, les parties dans SC sont divisées en trois différentes phases de stratégie : le début, le milieu et la fin de partie. Comme au go, pour le début de partie il existe des ouvertures, suites d’actions optimales suivant la et les stratégies que l’on pense appliquer.  En général on apprend ces ouvertures (appelées build orders) par cœur. Ces ouvertures existent car, comme au go, ces mouvements optimaux sont plus faciles à étudier en début de partie (situation de départ identique, stratégie à court terme identique), ils sont donc bien connus. Comme au go, StarCraft demande de l’anticipation, de lire dans le jeu de l’adversaire, de l’adaptation, ainsi que de la créativité à partir d’un certain niveau. Une composante supplémentaire dans SC est la réactivité, puisqu’il s’agit d’un jeu en temps réel. Plus je m’intéresse à ce jeu, et plus je constate le potentiel infini qui se cache derrière…

J’ai déjà exposé ce point de vue à certains d’entre vous qui m’ont judicieusement demandé « Ok, mais en quoi SC2 est plus le go moderne qu’un autre jeu récent de stratégie, que Civilisation 5 par exemple ? ». Très bonne question. D’un point de vue stratégique, rien en fin de compte. Mais ce qui fait la différence entre SC2  et d’autres jeux comme Civ. 5, c’est la communauté. On a vu se développer  en une dizaine d’année pour SC des tournois nationaux et internationaux, des ligues professionnels, des équipes nationales et internationales dirigées par un manageur et coachées par un entraîneur, ainsi qu’une véritable structure d’e-sport (comme ça s’appelle), animée par des joueurs qui ont préféré se tourner vers l’analyse et se sont imposés comme commentateurs de matchs, à l’instar des journalistes sportifs que nous entendons à la TV pour les matchs de foot, de rugby. Certains de ces commentaires sont tellement  reconnu par Blizzard (l’entreprise qui développe SC) et la communauté qu’on fait appel à eux pour commenter en live des matchs de  grands tournois. Toute cette effervescence au départ d’amateurs commence à se cristalliser vers un professionnalisme cadré. Pour vous dire que ça devient bien au delà d’un simple jeu.

Comme annoncé, le prochain post (lundi prochain) sera sur le même sujet. Mais il devrait être plus long, et surtout croyez-moi, beaucoup plus intéressant. Mais aussi, il débouchera sur un appel à participation pour un projet. :-p

La photo du mois

La photo du mois date d’il y a presque deux semaines maintenant. C’était le jour même où Google m’apprenait ironiquement que c’était le 115ème anniversaire de la découverte des rayons X…

Souriez !

Dimanche 7 novembre, j’avais un tournois de karate. Mon premier tournois. Alors forcement, un peu nerveux, un peu tendu. Et un peu à fond dedans aussi… Je me suis fait ça tous seul, comme un grand : ce n’est un coup que j’ai pris sur ma main droite, mais bien moi qui me suis double-fracturé en tapant dans les côtes d’un gars. Au moins il a eu mal, c’est déjà ça. Note pour plus tard : apprendre à donner des coups de poing…

Alors je vous sors la blague que je sors à tout le monde : « Oui… j’y suis pas allé de main morte ». Oh oh oh. Faut savoir qu’à l’origine, « karate » signifiait « main chinoise ». Dans son sens actuel (pour se débarrasser de toute origine chinoise de cette discipline et souligner que maintenant, c’est bel et bien japonais), « karate » signifie « main vide ». Je peux vous assurer qu’elle le restera un moment. Cinq semaines normalement, si tout va bien. Et encore j’ai de la chance, vu que je me suis également déplacé un os, je devais avoir le droit à une opération pour remettre tout ça en place, mais un scanner de la main a montré que c’était finalement moins grave que prévu. Au passage, bien foutu le scanner qui m’a fait une modélisation complète en 3D de l’ossature de ma main en quelques secondes. Ce sont pas des tocards, mes collègues qui travaillent en imagerie médicale !

Mais qu’est-ce que tu fais maintenant ?

Alors je calme les fausses joies tout de suite : ce billet ne signifie pas une reprise sérieuse de mon blog. Mais je crois quand même important d’au moins vous dire ce que je fais en ce moment, version courte (enfin, pas-trop-longue).

Comme vous le savez, j’ai signé un nouveau contrat début septembre nous permettant de rester deux années supplémentaires sur Tokyo. Je ne vais pas détailler ici comment a fini mon différent avec l’administration du CNRS. Sachez juste que nous avons trouvé un « compromis », où ils sont quand même largement gagnant dans l’affaire. Mais bon, j’avais pas trop le choix, c’était à prendre ou à laisser.

J’ai donc un poste de deux ans en temps que chercheur dans un tout nouveau labo nippo-français en info, toujours à l’Université de Tokyo, la fameuse Todai. J’ai déménagé mes affaires à 400m à peine, et partage maintenant un grand bureau avec actuellement 3/4 autres chercheurs français. Autant vous dire que ça ne parle pas souvent anglais, et encore moins japonais…

Et mon boulot, il s’agit de quoi ? Pour ce nouveau poste, j’ai dû changer légèrement de thématique, ce qui n’était pas pour me déplaire car bien que j’ai beaucoup aimé ce que j’ai fais en thèse, je voulais voir un peu autre chose. Ce n’est pas non plus un changement complètement brutal. Avant, j’étudiais la difficulté intrinsèque de certains problèmes de contraintes. Ces derniers, appelés CSP, permettent par exemple de modéliser des problèmes comme le sudoku, l’emploi du temps d’un lycée, mais également les stratégies logistiques d’une compagnie de transport ou encore la décision d’un chemin à emprunter dans un environnement en 3D. Les CSP  sont des modèles couramment utilisés en intelligence artificielle, que l’on abrège par IA. Avant d’aller plus loin, je me suis rendu compte qu’il y avait une grande confusion dans l’esprit des gens. Pour M. Tout-le-monde, IA = robot. C’est faux ; on peut dire merci aux blockbusters américains. Je vais tenter de donner une explication simple, peut être un peu simplificatrice mais efficace. Si on voit le robot comme étant un corps artificiel, l’IA serait l’esprit. L’IA a comme application possible la définition du comportement d’un robot, mais porte également sur un champs beaucoup plus large. Il y a de l’IA dans votre voiture, dans vos jeux vidéos bien sûr, mais aussi dans votre micro-onde, votre ipod et dans la ligne de métro automatique qui vous emmène, peut être, tous les jours au boulot. L’IA est tellement disparate qu’il n’est pas facile d’en donner une définition en quelques mots (sans compter les différentes approches des chercheurs sur ce qu’ils appellent « IA »), mais en gros, je dirais que l’IA est l’étude et la reproduction automatisée des comportements.

Et c’est dans quoi je bosse maintenant. Avant j’étudiais de manière très théorique les CSP. Maintenant, j’essaye de trouver de manière automatisée une solution à ces problèmes le plus rapidement possible. En bref, dans mon labo nous concevons des algorithmes de résolution de CSP. Là où ça devient original, c’est que nous faisons cela sur l’un des supercalculateurs du Japon, ainsi qu’une grille de calcul basé en France (et peut être bientôt sur le supercalculateur du CEA en France). La conception d’algorithmes pour ces problèmes sur de telles machines est un domaine encore largement ouvert, très peu exploré. Et pourtant d’une importance de taille, car avec l’augmentation actuelle des cores CPU dans les ordinateurs, les supercalculateur d’aujourd’hui seront vos PC portables dans 10 ans !

L’une des raison pour laquelle je n’ai plus beaucoup de temps à consacrer à ce blog est la suivante. Travailler dans ce nouveau domaine me demande d’ingurgiter une grande quantité d’articles de recherche sur le sujet auquel je ne connaissais pas grand chose, mais également d’apprendre la programmation parallèle et de lire et comprendre le code existant qui a été écrit par mes collègues (l’une des partie les plus dures ; c’est l’horreur de lire le code source de quelqu’un d’autre, surtout quand c’est peu commenté T_T). C’est pour ça que je pense que d’ici quelques semaines, ça devrait déjà aller mieux une fois après avoir digéré toutes ces nouvelles choses.

Alors soyez encore un peu patient svp. ^_^ La reprise du blog ne devrait pas trop tarder !

Pour patienter…

Comme il se peut que je n’écrive rien pendant un ch’tit moment, je vous propose une interlude en regardant quelques photos que j’ai pris lors de mes précédents voyages comme le Japon l’été dernier, mais également l’Inde, Vienne, Prague, …

C’est ici : picasa powaaa !!!

Petite pause

Salut à vous, surfeurs du web.

Je pense que je vais prendre une petite pause dans mon blog. J’ai commencé mon nouveau poste de chercheur CNRS le 1er septembre et je vois bien que je n’arrive pas à trouver le temps d’alimenter ce blog (bien que les choses à écrire s’accumulent méchamment !). Et comme les mois d’octobre et novembre s’annoncent aussi bourrin que celui de septembre, c’est peut être le temps de prendre un peu de recul. Si jamais je trouve un petit moment et une petite motivation pour écrire, je le ferai, à commencer par la rapide description de mon nouveau poste (et la visite du petit parc à côté de chez nous, tout mignon, sans oublier de parler des cours de pâtisseries japonaises et européennes que prend Mari en ce moment).

J’espère à très bientôt les jeunes !

Erratum

J’ai toujours des trucs à dire ; j’ai juste la flemme d’écrire en ce moment. Ça viendra. :-)

Mais ayant reçu plusieurs messages alarmés au sujet de mon nouveau financement, je tiens à faire une correction car visiblement je me suis bien mal exprimé. Plusieurs d’entre vous ont pensé que nous allions Mari et moi traverser une difficile période financièrement dû à cette réduction subite de salaire (par rapport à qui m’avait été promis). En fait, vous n’avez aucune inquiétude à avoir de ce côté : jamais je n’aurais été aussi bien payé, et en France on ne m’aurait jamais proposé un tel salaire. C’est juste qu’au lieu d’être très très bien payé, je vais « simplement » être  très bien payé. ^^

La précision étant faite, j’espère avoir la gniak pour écrire bientôt à nouveau. J’ai plein de choses à dire !