Archive

Articles taggués ‘Monte Carlo’

La méthode Monte-Carlo appliquée au go, pour les nuls

26/03/2010

J’avais découvert le jeu de go en 2004 suite a un article sur les difficultés d’implémentation d’un programme efficace.

J’ai appris les règles a ce moment la, et bricolé un goban en tissus, puis tout laissé tombé en moins d’un mois faute de partenaires.

J’ai repris cet été, et je passe mon temps a jouer sur Internet (KGS, IGS et wBaduk de temps en temps). Je pense que je suis bien accroc ce coup-ci.
Et pour boucler la boucle, je viens d’écrire un petit programme afin de comprendre comment ceux-ci peuvent fonctionner, a partir d’un algorithme de référence (je n’ai rien inventé).

Je vais essayer de le décrire ici.

Le programme de référence

Le programme de référence (jrefgo) utilise la méthode Monte-Carlo avec une évaluation en All Moves As First (AMAF).

Et si vous avez compris cette phrase, vous n’avez pas besoin de lire cette note, puisque c’est précisément ce que je vais tenter d’expliquer.

Ce programme a l’avantage d’être concis : une classe pour GTP (Go Text Protocol), un lanceur, et une classe principale qui gère tout le reste.

Malheureusement, il n’est pas aussi clair qu’il le pourrait, les variables ont des noms abscons, il y a des manipulations de bits qui ne sont pas forcément nécessaires, et beaucoup d’attributs utilisés comme des variables globales. Il reste néanmoins une bonne base, et je me suis plus ou moins contenté de le réarranger a ma sauce, sans en changer le fonctionnement.

Attention: je suis un développeur, pas un statisticien, il est donc possible que j’ai introduit des erreurs ou mal compris un point. N’hésitez pas a me corriger si vous voyez une bourde.

Pourquoi le jeu de go est difficile pour un ordinateur

Pour la plupart des jeux de stratégies de ce type, une intelligence artificielle est composée de deux éléments principaux :

  • un arbre des coups possibles pour chaque joueur
  • une fonction d’évaluation d’une position donnée

A partir de la, on peut évaluer les positions obtenues après X coups, et prendre le coup qui amène a la meilleure de ces positions.

Cette méthode n’est pas applicable au go pour deux raisons :

  • le nombre de coups possibles est gigantesque, il n’est pas possible de générer un arbre d’une profondeur acceptable
  • il est très dur d’évaluer une position (Ce territoire est-il définitif ? Ce groupe est-il vraiment vivant ? Combien vaut cette influence ? Et la pierre en bas, elle est morte, mais a-t-elle encore du potentiel ?)

Il a donc fallu trouver un autre angle d’approche.

La méthode Monte-Carlo

L’idée est assez simple, et je suis moi-même étonné de voir qu’elle fonctionne aussi bien :
puisqu’on n’est capable d’évaluer une position qu’en fin de partie, il suffit de la finir !

Ben oui, mais comment ? En jouant des coups au hasard. C’est ce qu’on appelle un “playout”. Ça fait une fin de partie absolument non réaliste, et peu fiable.
Mais si on joue 10 000 playouts ou plus, on commence a avoir des résultats intéressants. C’est une approche probabiliste.

En divisant le nombre de victoires par le nombre de playouts, on obtient une probabilité de victoire, le winrate. Le score ne compte pas vraiment, gagner de 0.5 ou de 30 points n’a pas d’importance. Si une position a un winrate > 0.5, la position est favorable, et inversement.

Corolaire : le coup qui amène a une position ayant le meilleur winrate est probablement le meilleur coup.

All Moves As First

Reste a savoir comment on mémorise le winrate pour chaque coup ou position. L’approche AMAF, c’est de ne pas tenir compte de l’ordre des coups, et juger toutes les pierres jouées entre la position initiale et la position finale. Par exemple, si 50 coups sont joués entre la position pour laquelle on veut trouver un coup, et la fin d’un playout, on comptabilise une victoire pour chacun des coups qui ont été joués.

L’avantage de cette méthode est le stockage du résultat : un tableau de la taille d’un goban suffit, avec un score pour chaque case. On obtient le meilleur coup après
simulation de toutes les fins de parties en parcourant ce tableau, et en conservant le coup avec le meilleur winrate.

L’inconvénient majeur de cette méthode est que le coup ayant le plus de chance de marcher contre un adversaire jouant au hasard n’est pas forcément le meilleur coup.
Un humain ne rate pas un simple shicho et ne se met pas en auto-atari en espérant que son adversaire l’ignore…

Implémentation

Il nous faut certaines fonction de base que je ne décrirais pas en détail, mais dont vous pouvez voir le source :

Une fois qu’on a ces éléments, on peut rentrer dans le cœur du problème : la génération des playouts, les statistiques, et enfin la sélection du coup a jouer.

Génération d’un playout
CODE: McAmafGenerator.playout

  1. on récupère la liste des intersections libres
  2. tant qu’il reste des intersections libres, on en sélectionne une au hasard qu’on déplace pour ne pas la resélectionner plus tard
  3. si l’intersection est valide, on la joue pour le joueur courant, sinon on recommence la sélection avec un autre coup
  4. si le coup capture des pierres adverses, on récupère a nouveau la liste des intersections libres et on recommence au début, avec la position actuelle
  5. lorsqu’il ne reste plus de coup valide, on passe. Après 2 passes consécutives, la simulation est terminée
  6. on regarde qui gagne la partie dans la position finale, et on sauve les statistiques

Sauvegarde des statistiques après chaque playout
CODE: McAmafGenerator.trackStatistics

Pour chaque coup joué dans le playout par le joueur pour lequel on veut trouver un coup :

  1. vérifier qu’il n’a pas déjà été joué avant depuis la position initiale, par aucun des deux joueurs
  2. s’il n’a pas encore été joué, ajoute 1 ou -1 au score du coup selon le résultat final de la partie, et incrémente le nombre de simulations contenant ce coup.

L’ordre des coups n’a pas d’importance, mais on ne compte chaque coup qu’une seule fois au maximum par playout.

Sélection du coup a jouer
CODE: McAmafGenerator.generateMove

  1. on remet les statistiques a zéro pour ne pas être influencé par les résultats des évaluations précédentes
  2. on joue plein de playouts aléatoires
  3. on récupère la liste de toutes les intersections du goban, qu’on mélange pour ne pas avoir toujours le même ordre de sélection en cas de winrates identiques
  4. on récupère le winrate pour chaque intersection, si elle correspond un coup légal qui ne remplit pas un de ses propres yeux. S’il est meilleur que celui du coup actuellement sélectionné, on sélectionne le coup correspondant
  5. s’il n’y a aucun coup légal restant, on passe
  6. si le winrate de la position de départ est vraiment trop faible, on abandonne.

Pour aller plus loin

Les programmes de ce types évoluent généralement de deux façons :

  • en conservant l’ordre des coups dans un arbre (ex: UCT)
  • en ne faisant pas des playouts totalement aléatoires, mais plus plausibles (heavy playouts), en utilisant des heuristiques basées sur de la reconnaissance de forme.

Liens sur le sujet

Sur Wikipedia :
http://fr.wikipedia.org/wiki/Jeu_de_go_(informatique)

Le programme de référence :
http://cgos.boardspace.net/public/javabot.zip

Un port dans le langage “Google Go” :
http://github.com/skybrian/Gongo

Archives de la liste Computer-Go :
http://groups.google.com/group/computer-go-archive

Mon source :
http://bitbucket.org/vfiack/weiqibot/

Pages sur Sensei’s Library :
http://senseis.xmp.net/?ComputerGoAlgorithms
http://senseis.xmp.net/?MonteCarlo
http://senseis.xmp.net/?UCT

Un PDF sur les valeurs intéressantes :
http://www.fun.ac.jp/~kishi/pdf_file/AAAI06YoshimotoH.pdf

Développement, Jeu de go