MoGo, classé numéro 1 depuis août 2006 parmi 142 sur le Computer Go Server, a été développé au sein du projet TAO en collaboration avec le CMAP de l'Ecole Polytechnique. Mogo est actuellement l'un des tout meilleurs joueurs de GO artificiels. L’efficacité de ce programme de jeu de GO est redoutable, il vient en effet de remporter coup sur coup le tournoi international KGS d’octobre et de novembre 2006 en 9x9 et 13x13.
Un jeu vieux de 4000 ans
Le jeu de Go a plus de 4000 ans d'histoire ; c'est l'un des jeux pour lesquels le niveau des meilleurs joueurs artificiels reste très faible comparé à celui des joueurs humains. La complexité du Go est considérable ; pour donner un ordre d'idée de la taille du problème, le Go est aux échecs ce que les échecs sont au tic-tac-toe.
La construction d'une fonction d'évaluation de la position a pris un tour nouveau en 1993 (approche Monte-Carlo), avec l'utilisation de techniques aléatoires. (prenez une position ; ajoutez aléatoirement des pierres blanches et noires, arrivez à une position finale ; comptez le score ; répétez l'opération de nombreuses fois et moyennez le score obtenu ; de manière surprenante, cette procédure donne une bonne fonction d'évaluation...).
L'efficacité de l'approche a été montrée par le succès de CrazyStone, autre programme informatique de jeu de Go développé à l'INRIA Futurs.
Fondée sur cette fonction d'évaluation, la stratégie de MoGo s'inspire de celle des bandits manchots en théorie des jeux, pour estimer graduellement les branches les plus intéressantes de l'arbre des coups possibles.(Vous êtes face à plusieurs machines à sous - bandits manchots ; vous devez estimer la machine sur laquelle on peut gagner le plus souvent - exploration - et y jouer le plus souvent - exploitation. Comment régler le compromis exploration / exploitation est la clé du problème).
La stratégie de Mogo
Le programme MoGo, inspiré de la stratégie de CrazyStone de Rémi Coulom, chercheur de l'équipe SEQUEL à Lille, 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 renvoit 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.
Le travail actuel consiste à améliorer ces techniques pour permettre à MoGo de progresser en 19x19, taille pour laquelle il est encore en dessous des meilleurs programmes basés sur des connaissances expertes.
Mogo, meilleur joueur de GO artificiel à l'heure actuelle
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 en octobre et novembre 2006 en 9x9 et 13x13 (résultats).
Le "Computer Go Server" est un tournoi où les programmes jouent entre eux en continu et, suivant leurs victoires, un classement ELO leur est attribué (le classement ELO est bien connu dans les échecs, et la probabilité de victoire d'un joueur sur un autre est directement liée à leur différence de point ELO). Les matchs sont tous en 9x9 (taille du Goban).
>> pour en savoir plus
Les tournois sur "KGS" ( Kiseido Go Server) sont mensuels et les tailles sont altérnées. Suivant les participants il y a entre 6 et 9 "rounds" où les programmes jouent entre eux. Ensuite celui qui a gagné le plus de match est déclaré vainqueur.
>> pour en savoir plus
_____________________________________________________________
Le programme Mogo a été réalisé lors du stage d'Yizao Wang (élève à l'Ecole Polytechnique, lauréat du prix du centre de recherche attribué au meilleur stage pour ce travail sur Mogo) en collaboration entre le projet TAO (INRIA) et le CMAP (Ecole Polytechnique). Ce travail a été mené conjointement par Yizao Wang et Sylvain Gelly, doctorant du projet TAO. Olivier Teytaud (INRIA), Rémi Munos (INRIA) et Pierre-Arnaud Coquelin, doctorant au CMAP ont supervisé le projet. Rémi Coulom (INRIA) a appuyé le développement et partagé de nombreuses idées à l'origine du succés de MoGo.
>> pour en savoir plus