L’ordinateur champion de Go ?

Avril 2007

Fin Mars, un court message sur fr-go annonce que le journal « Pour la Science » vient de sortir son numéro d’Avril avec en couverture « L’ordinateur maître de Go » en grosses lettres sur un goban électronique reproduisant la partie historique jouée en 1846 entre Gennan et Shûsaku. De plus, il y aurait en début de revue, un bel article avec ce titre provocateur « L’ordinateur champion de Go ? » J’ai d’abord cru à un canular, à un poisson d’Avril légèrement en avance mais quand quelques jours plus tard, je recevais mon numéro personnel, je suis confronté à la réalité : une équipe française vient de mettre au point un programme révolutionnaire baptisé MoGo basé sur la méthode de Monte-Carlo qui s'est imposé sur un goban 9x9 comme champion des ordinateurs sur KGS. Cette équipe est formée notamment d’un doctorant à l’Inria, Sylvain Gelly et d’un ancien joueur de Go du COP, en master au CMAP (centre de Mathématiques appliquées) de l’école Polytechnique Yizao Wang. Dans les tournois entre ordinateurs sur KGS, MoGo a gagné dans toutes les tailles: 9x9, 13x13, 19x19. S'il est vrai que son niveau relatif par rapport aux humains, et aux programmes "classiques" comme GnuGo, diminue avec la taille du Goban, il n'empêche qu'il a remporté les tournois dans toutes les tailles. Par exemple, en 19x19, sur partie en 25 minutes par joueur, MoGo peut donner 4 pierres à GnuGo 3.7.10 et être à 50% de victoires.

Dans un programme de jeu, le principe général est toujours le même. Il consiste à envisager l’arbre des coups possibles jusqu’ à une certaine profondeur.
Arrivé sur une feuille de l’arbre, on évalue la position avec une fonction d’évaluation. On suppose que chacun des joueurs choisira le meilleur coup possible. Imaginons que cela soit à Noir de jouer : compte tenu des différentes valeurs trouvées, on remonte pour chaque feuille la valeur du meilleur coup possible suivant le principe du min-max : la valeur maximum de la fonction d’évaluation si c’est à Noir de jouer, la valeur minimum si c’est à Blanc. Le programme choisira le coup Noir qui a la plus grande valeur.

MoGo apporte deux nouveautés dans ce domaine :

Fonction d’évaluation
Dans les programmes utilisant la méthode de Monte-Carlo, la fonction d’évaluation d’une feuille de l’arbre sera obtenue en faisant jouer au hasard le programme jusqu’au bout de la partie. A ce stade, on calcule le score et on voit si le programme gagne ou pas. L’évaluation sera obtenue en effectuant un grand nombre de fin de parties au hasard et donnant comme évaluation le pourcentage de victoires.

A noter que les échanges de coups vont plus loin que dans une partie entre humains puisqu’on ne comptera la partie que quand tous les territoires ne sont formés que d’œils de 1 point. Il n’y a alors aucune chance de se tromper sur le score.

Dans la version 2 de MoGo, la méthode de Monte-Carlo a été améliorée avec des patterns locales. Au lieu de choisir toujours au hasard, on choisira un coup s’il répond, dans le voisinage du dernier coup joué, à une des patterns 3x3 ou 2x3 sur le bord, qui ont été sélectionnées et qui correspondent à sauver une pierre en atari, couper ou faire un hané. Cette innovation s'est révélée bien fructueuse.

Exploration de l’arbre
MoGo utilise un nouvel algorithme appelé UCT : il consiste à choisir de ré-évaluer un coup avec une probabilité d’autant plus forte que sa valeur évaluée actuellement est grande. Les bons coups seront donc évalués avec plus de tirages au sort que les mauvais. 

Résultats

Le programme MoGo est étonnamment fort sur un 9x9. Que ce soit avec Blanc ou avec Noir, avec un komi de 7,5 points, il parvient à gagner contre des joueurs en Dan et je l’estime à 2 ou 3 Dan.
Dans une série de 100 parties contre Motoki Noguchi 7 Dan français, il parvient quand même à gagner plus d'une partie sur 4. Score actuel (22/87 )

Sur un 13*13, même si le programme se dispute la première place avec Crazy Stone, programme de Rémi Coulom basé également sur l’évaluation à l’aide de la méthode de Monte-Carlo, il semble moins fort.

Enfin sur 19x19, il est 4 kyû KGS mais ne résiste pas à des joueurs solides 4 Dan à 9 pierres de handicap. A titre d'exemple voici une partie que j'ai joué contre lui à 9 pierres de handicap. Il est certainement plus fort à égalité qu’à handicap, du moins quand il le reçoit.

Petite particularité, MoGo gagne la plupart de ces partie de 0,5 points : il se contente d’assurer la partie en jouant dans son territoire quand il considère (à juste titre) que ces coups lui permettent de gagner avec une probabilité de 1, c'est-à-dire à coup sûr.

Deux parties gagnées par MoGo contre Motoki (7d)

• Noir : MoGoBot19

• Blanc : Mtkk

• Komi : 7,5

• Résultat : Blanc abandonne après le coup 51

• Sgf

29 en 26

En fait Blanc perd de 3,5 points.

• Noir : Mtkk

• Blanc : MoGoBot

• Komi : 7,5

• Résultat : Blanc gagne de 0,5

• Sgf

Octobre 2007 : Il est maintenant possible de jouer sur son propre PC avec MoGo qui est téléchargeable sous forme de moteur. On peut ensuite l'interfacer simplement avec par exemple Drago.

Pour le configurer, il suffit de paramétrer les options du moteur de jeu, de cocher le radio bouton custom et d'indiquer la taille du goban et le temps total accordé pour chaque coup. --9 --time 12"

On peut ensuite jouer sur 9*9, 13*13 ou 19*19 avec le komi réglable entre 0 et 7.5.

Ne pas oublier de demander le comptage en règle chinoise (ou française) en sélectionnant "Area scoring".

MoGo reste faible sur 19*19 (6è kyû) ou je l'ai battu facilement à 9 pierres, meilleur sur 13*13 (2è kyû) où j'ai eu du mal à gagner à 4 pierres et coriace sur 9*9 (2 Dan) ou je fais jeu égal sans komi (avec Blanc).

Mars 2009 : Mogo dans le journal Le Monde

Dernière mise à jour 04/07/02023

   Retour Go