La recherche française à l'assaut des jeux asiatiques.
Image inria Image cnrs Image paris11 TAImage tao Image pascal Image digiteo
Image nutn Image nutn Image nutn Image tuxImage gnu
\epsfig{file=line.eps,width=250mm,height=2mm}

Les ordinateurs concurrencent les humains au jeu de Go.


Les ordinateurs et les jeux.
Certains jeux sont complètement résolus, au sens où une stratégie optimale est connue; par exemple, aux dames, il est prouvé qu'on peut garantir l'ex-aequo. Il existe ainsi un programme qui ne peut pas perdre un match: au mieux, on peut espérer l'ex-aeco. D'autres jeux sont résolus "en pratique", au sens où les humains sont désormais incapables de gagner contre les meilleurs programmes, à moins de bénéficier d'un avantage artificiel au début de la partie; les échecs sont désormais dans cette catégorie.

La première partie gagnée en 19x19 contre un joueur professionnel,
avec 9 pierres de handicap, contre Kim Myungwan (8Dan Pro, gagnant de l'US Open 2008).
La position présentée montre la mise à mort du groupe blanc en bas à
par MoGo (noir, qui encercle le groupe blanc).
Le multimillénaire jeu de Go, encore peu connu en France, est d'une autre catégorie: les jeux où l'humain est encore capable de battre la machine. Des techniques novatrices, pour lesquelles la France est en pointe, ont permis l'émergence de nouvelles familles de programmes dont le niveau est loin au dessus des programmes antérieurs.


Le Go... et le reste.

Un charme particulier de la technique utilisée est son utilisabilité pour de nombreuses applications sans rapport avec les jeux, rappelant l'impact très général des recherches fondamentales. Ainsi, les mêmes chercheurs appliquent cette technologie pour la gestion de production d'énergie, l'optimisation non-linéaire et d'autres domaines fondamentaux d'intelligence artificielle.
MoGo utilise à la fois: Toutes ces méthodes sont employables loin du jeu de Go, pour la recherche fondamentale et pour l'industrie.

Historique du jeu de Go par ordinateur: toujours plus fort.

Ainsi, les techniques développées par des chercheurs et enseignants chercheurs on conduit à une première victoire du programme MoGo contre un joueur professionnel en 9x9, à Amsterdam en 2007, en temps court. Utilisant une parallélisation massive, avec l'aide de Grid5000 et de Bull, lors de l'IAGO Challenge 2008, MoGo a récidivé en gagnant contre un joueur professionnel, 5ème Dan Pro, en temps long; MoGo avait par contre échoué malgré un handicap de 9 pierres sur le plateau 19x19. Ce n'était que partie remise puisque MoGo a gagné contre un joueur 8ème Dan pro avec 9 pierres de handicap lors de l'US Open 2008.
On n'allait pas s'arrêter en si bon chemin. Après des victoires à 8 et 7 pierres par le programme français CrazyStone contre une joueuse 5ème Dan pro, invité au Taiwan Open 2009, MoGo a gagné une partie à 7 pierres de handicap contre un joueur de tout premier plan, Zhou Junxun, 9ème Dan Pro et vainqueur de la LG Cup 2007.


La première partie jamais gagnée à handicap 7 contre un joueur professionnel 9Dan Pro,
avec 7 pierres de handicap, contre Zhou Junxun (9Dan Pro, vainqueur de la LG Cup 2007). La victoire a été
finalisée par la mort du groupe blanc situé autour de H4 (en bas au centre), encerlé par un solide groupe noir. A droite en bas, la machine
fournie par l'université d'Amsterdam pour ce match (640 coeurs, 4.7 GHz, IBM Power6).


Victoire contre un joueur au plus haut niveau mondial.

Zhou Junxun a déclaré à la fin du match remporté par MoGo: "MoGo est apparu comme un joueur de haut rang amateur dans le milieu de match et il a effectué des manoeuvres dignes d'un joueur professionel. MoGo a gagné facilement, pour la première fois (nb: Zhou Junxun avait gagné facilement contre MoGo quelques mois auparavant); ça m'attriste un peu, en même temps que ça m'impressionne." Zhou Junxun a par contre remporté la revanche, sur un Semeai où MoGo a commis une lourde erreur.
MoGo a le lendemain gagné une partie à 6 pierres de handicap contre un joueur de premier Dan professionnel en 19x19, et le surlendemain a gagné une partie sur deux en 9x9 contre un joueur 10ème Dan, établissant un territoire de justesse suffisant pour gagner.


A gauche, la première partie jamais gagnée à handicap 6 contre un joueur professionnel,
contre Li-Chen Chien (1Dan Pro). Le territoire de noir (MoGo) est une longue zone qui serpente
(depuis en bas à gauche jusqu'au centre droit, puis au centre gauche, puis en haut à gauche.
A droite, partie gagnée contre Shih Chin, 2ème Dan Pro (mais vainqueur du tournoi 10Dan);
MoGo (blanc) gagne en bâtissant une solide frontière lui garantissant le territoire de gauche.



Plus d'informations

Qui ?

Les travaux sur le Monte-Carlo Go ont été initiés par Bruno Bouzy (Paris 5), Bernard Helmstetter (Paris 8), Tristan Cazenave (Paris 8), ont été développés par Guillaume Chaslot (univ. Lille, univ. Maastricht), Rémi Coulom (univ. Lille), puis par l'équipe TAO de l'Inria Saclay en collaboration avec le CMAP de l'Ecole Polytechnique (Sylvain Gelly, Yizao Wang, Rémi Munos, Olivier Teytaud) et les universités de Mastricht (Guillaume Chaslot) et Alberta (David Silver). MoGo a ensuite été parallélisé par Jean-Baptiste Hoock, Thomas Hérault, Arpad Rimmel, Olivier Teytaud (Tao, Lri, Univ. Paris-Sud, Inria, Umr Cnrs), puis amélioré par les mêmes et Christophe Fiter, Julien Pérez, Ziqin Yu (Tao, Lri, Univ. Paris-Sud, Inria, Umr Cnrs). Les mêmes techniques sont à l'oeuvre pour de nombreux problèmes industriels ou fondamentaux, loin du domaine du Go: apprentissage actif, optimisation non-linéaire, gestion de production d'énergie.

Plus d'informations sur le programme.

Informations sur l'algorithmique: Tous les programmes du haut du classement des compétitions de Go par ordinateur utilisent l'algorithme de fouille d'arbre par Monte-Carlo, une technologie novatrice d'origine française, montrant le grand succès de cette technique. Cette technique se décompose en deux éléments essentiels: Dans la partie Monte-Carlo, l'ordinateur étudie une position en jouant un très grand nombre de parties aléatoires, cherchant à estimer la probabilité pour chaque joueur de gagner la partie. Le joueur aléatoire étant très médiocre, le résultat est peu fiable, mais il permet de trancher des cas simples où près de 100% des simulations conduisent à une victoire de l'un des joueurs; on peut ainsi, sans coder d'expertise humaine, rapidement avoir une première impression sur une position.

Image de la première victoire d'un ordinateur contre un joueur
professionnel humain en jeu de Go 9x9 (hors blitz), réalisée
par MoGo en 2008.
Presque toutes les parties jouées à partir de cette position
sont gagnantes pour blanc; l'évaluateur par Monte-Carlo, simulant un
grand nombre de parties aléatoires à partir de cette position,
l'identifie immédiatement comme étant une bonne position.
La méthode d'évaluation Monte-Carlo permet de résoudre des cas simples où la victoire est quasi-assurée à l'un des joueurs, mais cet élément seul ne permet pas d'aller à un haut niveau; une construction "d'arbre des possibles" est ajoutée au programme. Elle construit un arbre de représentation des futurs possibles, très développé dans les directions les plus importantes, qui permet alors au programme MoGo d'explorer les coups en amont de ces situations plus simples, et de voir ainsi quels coups joués pour tenter d'arriver à une situation plus simple et qui lui est favorable.

Plus d'infos sur le matériel.
Huygens est un supercalculateur néerlandais conçu par IBM : Power 575 Hydro-Cluster. Doté de 104 noeuds de 32 coeurs = 3328 processeurs POWER6 cadencés à 4,7 GHz et de près de 15 To de mémoire vive, la machine est capable d'atteindre 60 000 milliards d'opérations à virgule flottante par seconde (60 TéraFLOPS), mais seuls 9 TéraFlops étaient disponibles pour le match.