Mathématiques appliquées, calcul et simulation

26/02/2009

MoGo mène le jeu !

Le jeu de Go, terrain de technologies pour de nombreux domaines. MoGo, projet coordonné par Olivier Teytaud de l’équipe-projet Tao a été invité au Taiwan Open 2009. Il a battu un nouveau record en réalisant la meilleure performance mondiale à l'heure actuelle en Go 19x19.
Combinant intelligence artificielle novatrice et parallélisation multi-cœurs et à passage de messages, il accumule les victoires contre des joueurs professionnels. Cet algorithme parallélisé est utilisable, au-delà du jeu de Go, pour résoudre une vaste gamme de problèmes.

En 1997, un ordinateur battait, pour la première fois, Garry Kasparov, le champion du monde des échecs. Le jeu de Go, quant à lui, était jusqu’il y a peu un domaine réservé de l’homme. Plus complexe que les échecs avec plus de 10 puissance 600 possibilités de jeu, soit plus que le nombre de particules de l’Univers, le jeu de Go représente une remarquable école de stratégie. Dans ce jeu où la supériorité de l'homme était très large, l’ordinateur a réussi à se hisser au niveau professionnel d’un joueur de Go.
Cependant, comme les programmes actuels sont encore trop faibles pour battre des joueurs de haut niveau, un avantage leur est attribué : ils jouent un certain nombre de coups d’affilée en début de partie, ce qui correspond à des pierres de handicap pour le joueur professionnel. La progression de MoGo au travers de sa succession de victoires se mesure donc principalement à la réduction du nombre de pierres de handicap des joueurs professionnels. Au Taiwan Open 2009 (10-13 février 2009), MoGo a ainsi gagné pour la première fois une partie à
seulement 7 pierres de handicap contre un joueur de tout premier plan, Zhou Junxun, 9ème Dan Pro extrêmement réputé, vainqueur de la LG Cup 2007, ainsi qu'une partie à 6 pierres de handicap contre un joueur professionnel, Li-Chen Chien.

Au cœur de cette compétition internationale, MoGo, issu de la recherche française en informatique démontre ainsi le résultat de trois avancées scientifiques ou technologiques :

  • Tout d’abord, les algorithmes dits de Bandits Manchots ont permis d'explorer (partiellement) l'espace des parties possibles. Ils ont ainsi révolutionné le monde de la planification en univers incertain.
  • D’autre part, l'évaluation des positions est fondée sur des algorithmes de Monte-Carlo, simulant le comportement d'un joueur stochastique, de faible niveau, mais sans aucun préjugé (biais).
  • Enfin, le parallélisme à grande échelle (avec notamment GRID’5000) a permis de disposer de la puissance de calcul nécessaire pour qu'une évaluation Monte-Carlo donne des résultats suffisamment précis.

Ces évolutions ont ainsi permis de nouvelles applications de cet algorithme. Au-delà du jeu de Go, le logiciel employé est basé sur des technologies novatrices, utilisables dans de nombreux domaines, en particulier l'économie de ressources, cruciale pour les problèmes environnementaux.
En effet, le jeu de Go pose des problèmes scientifiques très difficiles à résoudre. Même si en théorie le jeu est déterministe, c’est-à-dire que l’on peut le programmer sans difficultés particulières, il faudrait un temps de calcul astronomique pour obtenir la solution. Or ici les algorithmes parallèles permettent d'utiliser les grilles informatiques et de résoudre des problèmes d'agencement de possibilités, de planification. Les possibilités d’agencement peuvent se compter, par exemple, par milliards de milliards et l’objectif est de trouver l’ordre le plus efficace dans cette foule de possibilités. Le jeu de Go est alors un bon modèle pour développer et expérimenter de nouvelles techniques pour résoudre ce type de problème d’ordonnancement.

Mots-clés : Saclay - Île-de-France Mathématiques appliquées Jeux Intelligence artificielle

Haut de page