MoGo & MoGoTW: des algorithmes qui jouent au Go et au-delà

I. Introduction

    Le Go, vieux jeu asiatique,
    résiste toujours aux machines.Il fait partie de ces jeux où la méthodologie usuelle, à base d'algorithme alpha-beta

    et de fonction d'évaluation approchée, ne donne rien de bon.

    Forte combinatoire, pas de fonction d'évaluation
    naturelle. Depuis 2006, une méthodologie appelée MCTS s'impose comme le meilleur
    outil, et s'applique en outre à de nombreux jeux difficiles et à de nombreux
    problèmes de planification dans l'incertain.MoGo(TW) est une implémentation de MCTS pour le

    jeu de Go.

En 2010, MoGoTW a obtenu la certification Dan par l'association Taiwanaise de Go:
           http://mepopedia.com/forum/read.php?160,5537,5537

    En 2010, MoGoTW a gagné la médaille d'or à TAAI 2010 à la fois en Go 9x9, en Go 13x13 et en Go 19x19 !

     Détails sur http://ai.csie.ndhu.edu.tw:9898/eng/

II. Algorithmique

MCTS (dont on présente ici la variante la plus connue, UCT) est un algorithme pour prendre des décisions dans des environnements incertains (par exemple, quand on ignore ce que va jouer l'adversaire; mais des incertitudes de type météorologique ou climatique peuvent être envisagées). Ses principes sont:
- un arbre (sous-arbre, stocké en mémoire, de l'immense arbre des possible) grossissant itérativement;
- des simulations aléatoires pour évaluer les feuilles de cet arbre.

Algorithmiquement, dans le cas du Go (on peut généraliser à d'autres jeux et à d'autres problèmes):

• a. D'abord, on construit en mémoire un arbre avec un seul noeud, qui est le statut actuel du goban.
  
  

Example of UCT tree: each node "knows" its number of simulations

and its number of wins. Thanks to David Silver, original author of this figure.

• b. Alors, démarrez à la racine, et trouvez un chemin jusqu'à une feuille; à chaque noeud, pour choisir un noeud fils, vous choisissez un fils qui a le meilleur compromis exploration/exploitation: le compromis exploitation/exploration dans UCT est la somme:
  
  
  • d'un terme d'exploitation, privilégiant les noeuds qui ont donné de bons résultats au joueur qui doit jouer en ce noeud, égal au taux de victoire des simulations passant par ce fils;
    
    
  • le terme d'exploration: la racine carrée du ratio "log(nombre de simus(noeud père)) / nombre de simus du fils".
  Les motivations pour ce terme proviennent de la littérature dite des "bandits manchots" (Lai Robbins, 1985).
  
  
• c. Une fois arrivée à une feuille, jouez aléatoirement de la feuille jusqu'à une fin de partie.
  
  
• d. Alors, mettez à jour les statistiques dans l'arbre: mettez à jour le nombre de simulations dans chauqe noeud, et le nombre de victoires pour noir et pour blanc.
  
  
• e. S'il reste du temps, retournez en b.
  
  
• f. Sinon, décidez vous pour l'action la plus fréquemment simulée à la racine.

Ceci est le pseudo-code d'UCT, décrit plus formellement dans Kocsis et al, 2006. Le premier MCTS remonte

en fait à Coulom 2006. De nombreuses variations ont été formulées, dont

• le fameux RAVE (rapid action value estimates, qui a son origine dans MoGo) qui utilise des statistiques biaisées mais à variance réduite pour guider l'exploration dans les zones où le nombre de simulations est faible;
• des termes d'exploration différent, utilisant notamment des biais appris hors-ligne (machine learning appliqué aux patterns, implémentation dans MoGo décrite dans Lee et al 2009);
• une parallélisation massive, décrite dans Cazenave et al. 2007, Gelly et al. 2008,
• un apprentissage automatique sur grille pour les livres d'ouvertures, basé sur un niveau "meta" du MCTS (Audouard et al, 2009).

Des extensions au continu (Couetoux et al, 2011), des versions partiellement observables (Auger 2011, Teytaud et al, 2011) ont permis des applications variées (cf section V). MoGo(TW) a obtenu en 2010 le prix de la meilleure contribution aux jeux pour l'année 2009 (chessBase award).

III. Performances contre humains
 Le jeu de Go se joue en 9x9, 13x13, et 19x19. Le handicap mesure l'avance que le joueur
 le plus fort (ici l'humain) accorde à la machine pour compenser la différence de niveau.

   a) Palmarès de MoGo en 9x9: victoires sans handicap
    - première victoire contre un pro en 9x9
    - première victoire contre un top pro en 9x9 en tant que noir (noir est plus dur; à ma
                   connaissance on est toujours les seuls à avoir réussi ce type de perfs)

   b) Palmarès de MoGo en 13x13: victoires avec handicap modéré
    - 2010: première victoire contre un 6D à handicap 2

La première victoire contre un joueur 6D

à handicap 2 en 13x13

    - 2011: première victoire contre un pro à handicap 2.5

   c) Palmarès de MoGo en 19x19: le chemin est encore long - fort handicap!
    - première victoire contre un pro en 19x19 à H9
    - première victoire contre un pro en 19x19 à H6
    - première victoire contre un top pro en 19x19 à H7 (record égalé depuis, mais non battu):

    

La première victoire à H7 contre un top pro

(Performance égalée par Pachi récemment:

le groupe J4 est mort et noir gagne)

Notons qu'il y a quelques années les machines perdaient même à handicap 29,
   un nombre colossal qui ne fait aucun sens pour les joueuers humains et montre l'immense progrès réalisé depuis, loin d'être explicable par le seul essort des machines.

   d) Autres variantes du jeu de Go
   (http://teytaud.over-blog.com/article-blind-go-random-go-13x13-go-rengo-73149193.html, 2010):
        - victoire contre des pros sur un match complet
            (3 parties sur 4) en go 9x9 en aveugle, dont 2/2 contre un top pro.
        - victoire contre un 6D sans handicap sur des positions aléatoires.

IV. Diffusion & importance du logiciel
    - le code MoGo a eu des dizaines de milliers de downloads
        ==> chessBase award en 2009 pour la plus grande avancée de l'année dans les jeux.

    - forte internationalisation (contributeurs sur 3 continents)

    - centre d'un MOU entre deux universités asiatiques http://www.nchc.org.tw/en/news/index.php?NEWS_ID=70

    - son utilisation de patterns dans le Monte-Carlo a influencé tous les codes existants.
    - première utilisation de la technique Monte-Carlo Tree Search sur machine
        massivement parallèle (cumulant multithreading et parallélisation à passage de messages); utilisation régulière sur

        Grid5000 et optimisation de la bibliothèque d'ouvertures sur grille.

  
Un des clusters de Grid5000 (cluster de SMP).

V. Au delà du Go
  Le MCTS s'applique loin au delà du jeu de Go (voir ici une explication des principes du MCTS). Citons:
    - application au power management http://www.lri.fr/~teytaud/iomca.html
    - applications à des problématiques fondamentales d'IA
    - applications à des jeux de cartes partiellement observables (IA au meilleur
       niveau humain à Urban Rivals www.urban-rivals.com , jeu à 11 millions d'utilisateurs
       enregistrés)

Un personnage d'Urban Rivals