Sylvain GELLY's Home Page

  Plus d'informations sur MoGo

Rapport de Recherche
Cette page n'est pas à jour, allez plutôt sur (en anglais) : English MoGo web site

  MoGo: un joueur de Go artificiel

The following text is in french. If you don't speak french, please visit English MoGo web site.

Présentation de MoGo, un des tous meilleurs programmes de Go :

Le Go est un jeu avec plus de 4000 ans d'histoire, et est un des derniers jeux pour lequel le niveau des programmes est encore bien plus faible que celui des humains. Ce jeu représente donc un challenge en intelligence artificielle, et bénéficie de l'attention d'une communauté importante. La complexité du Go provient à la fois de la difficulté à évaluer une position donnée, et du grand facteur de branchement de l'arbre de recherche.
MoGo a été développé en attaquant de façon spécifique et efficace ces deux problématiques :
• Evaluation de la position par Monte-Carlo : à partir d'une position, un joueur stochastique et rapide finit la partie en jouant contre lui même. Le score peut alors être calculé. En effectuant cette opération de nombreuses fois, et moyennant les résultats, nous obtenons donc une évaluation de la position. Cette idée est apparue en 1993 dans le Go. MoGo utilise de façon originale des connaissances expertes pour améliorer le joueur stochastique, et ainsi améliorer significativement la précision de l'évaluation.
• Exploration-exploitation dans l'arbre de recherche par l'algorithme UCT : l'algorithme alpha-beta couramment utilisé et très efficace notamment dans les échecs, se révèle peu efficace pour le Go. MoGo est le premier programme a avoir introduit l'algorithme UCT dans le Go. Les avantages sont multiples :
  • croissance asymétrique de l'arbre : les branches plus intéressantes sont explorées plus profondement.
  • gestion efficace de l'imprécision : la fonction calculée varie de la moyenne jusqu'au min-max, suivant la confiance dans les estimations. Ainsi, si après suffisament de simulations, un coup se détache des autres, la valeur renvoyée par UCT va être le max parmis les coups possibles. Si les valeurs estimées de plusieurs coups ne sont pas significativement différentes alors UCT renvoye une moyenne.
  • anytime : l'algorithme peut être arrêté à n'importe quel moment tout en donnant un bon résultat.
  Il est à noter qu'aujourd'hui, la plupart des programmes de premier plan en 9x9 utilisent UCT.

Résultats de MoGo :

(Cette page n'est pas mise à jour, allez voir la page en anglais pour des résultats à jour English MoGo web site)
Il existe différents championnat et tournois dans le "Computer Go". Le but est de faire jouer entre eux les programmes pour estimer leurs niveaux relatifs.

MoGo est depuis début Août 2006 classé 1er programme parmis 142 sur le Computer Go Server.
MoGo a remporté le tournoi international KGS d'Octobre 2006 en 9x9 et 13x13 (résultats).
MoGo a remporté le tournoi international KGS de novembre 2006 en 13x13 et 9x9 (résultats).

Remerciements:

Contributeurs: Yizao Wang, Sylvain Gelly, Rémi Munos, Olivier Teytaud, Pierre-Arnaud Coquelin.