Cet article est en deux parties. Retrouvez ici la première partie de cet article .
Une machine s’impose face à un professionnel
Le 07 Août 2008, Le programme Mogo Titan, développée par l’université de Maastricht et par l’INRIA, a battu Kim MyungWan, un joueur professionnel coréen 8ème dan.
Cependant, quelques bémols:
A l’instar de Deep Blue, le programme tourne sur un supercalculateur, conçu par IBM. La machine, le «Power 575 Hydro-Cluster» est dotée de 3328 processeurs POWER6, cadencés à 4,7 GHz et de près de 15 To de mémoire vive. Elle est capable d’atteindre 60 000 milliards d’opérations à virgule flottante par seconde (60 TéraFLOPS). A titre de compaison, elle est plus de 1000 fois plus puissante que Deep Blue… Ce qui la place cependant assez loin des plus puissants supercalculateurs du monde.
La partie est jouée avec 9 pierres de handicap (à l’avantage de Mogo), ce qui représente environ 120 points d’avance
Kim MyungWan utilise moinsde 6 minutes de temps pour jouer la partie
D’ailleurs, le joueur coréen avait facilement battu Mogo à plusieurs reprises lors des phases de test
Mais au final, la machine gagne….. De 1,5 points!
Cependant, l’événement reste de taille. Mogo reste le programme ayant obtenu le meilleur résultat face à un joueur professionnel.
Quel est son secret ?
Les trois atouts principaux de Mogo
MoGo utilise principalement trois techniques :
Exploration de l’arbre des coups possibles par l’algorithme UCT
Evaluation des positions fondée sur des algorithmes de Monte-Carlo
Parallélisme afin de disposer de la puissance de calcul nécessaire pour qu’une évaluation Monte-Carlo donne des résultats suffisamment précis
L’algorithme UCT – issu de recherche de travaux en IA – est une méthode pour explorer des arbres min/max gigantesques. L’idée étant de se focaliser sur un coup et d’éliminer les autres.
Je ne rentrerai pas en détail là-dessus – surtout que je n’ai pas tout compris…
La partie intéressante est l’algorithme de Monte-Carlo.
Méthode de Monte-Carlo
Une méthode de Monte-Carlo est une technique visant à calculer une valeur numérique en utilisant des procédés aléatoires.
C’est utilisé notamment dans le domaine de la finance pour faire des mesures de risque (du coup on se dit que ça ne marche pas toujours très bien…).
Pour illustrer la méthode, je vais honteusement reprendre l’exemple de Wikipedia,. Il s’agit de faire une estimation de la superficie d’un lac :
Prenez un lac, inclus dans une zone rectangulaire (image de gauche).
Bombardez au hasard N coups de canon dans cette zone (deuxième image).
Comme vous connaissez la superficie du terrain, le nombre total de boulets de canon (X), et le nombre de ceux tombés en dehors du lac (N), vous pouvez estimer la superficie du lac par la formule:
Superficie lac ~= ( ( X – N ) * superficie terrain ) / X
Méthode de Monte-Carlo appliquée au Go
La méthode de Monte Carlo est utilisée par Mogo pour évaluer une position sur le Goban (l’une des principales difficultés du Go).
L’idée est, pour évaluer une position, de jouer des pierres noires et blanches au hasard,
excepté sur les intersections correspondant à des yeux (un «oeil» est une intersection vide unique entouré de pierres de la même couleur, c’est à dire un territoire minimal).
Le but est de terminer aléatoirement la partie, afin d’obtenir une position finale facile à évaluer (on sait qui gagne et de combien, il suffit de compter les territoires).
Puis on répète l’opération à partir de la position initiale.
Plus on répète l’opération, plus l’estimation de la position devient fiable (on fait la moyenne des estimations).
Pour être plus efficace encore, Mogo ne joue pas les coups totalement au hasard, mais essaie de jouer des coups crédibles, selon certains patterns pré-définis.
La combinaison de l’algorithme UCT et des méthodes d’évaluation basées sur Monte-Carlo ont fait de MoGo le meilleur programme de Go à ce jour. Mais il reste encore loin du niveau professionnel.
Pour conclure
Depuis 2006, la programmation du jeu de Go a fait des progrès importants, grâce à la méthode de Monte-Carlo notamment, et à des techniques avancées d’IA.
Le jeu de Go étant un terrain d’étude privilégié pour les sciences cognitives, il est probable que les rencontres entre machine et joueurs professionnels se multiplient dans le futur.
Mais la profondeur du jeu, sa complexité, et les qualités humaines qu’il requiert, font du Go un jeu qui restera encore longtemps l’apanage d’Homo sapiens sapiens! Enfin.. C’est mon avis 🙂
Auteur : Mikaël Lester
Annexe
Ressources diverses sur le Go
gobase.org
goproblems.com
http://igo-kisen.hp.infoseek.co.jp/news.html, pour trouver les parties professionnels des tournois coréens, chinois et japonais.
www.gnu.org pour télécharger le programme GnuGo.
Pour rappel : retrouvez ici la première partie de cet article .
Humour et Go
Voici une petite blague tordante (glacée et sophistiquée) qui prouve bien que l’humour du joueur de Go n’a absolument rien à envier à celui de l’informaticien:
Dernière petite remarque
Une prétérition se cache dans ce mini-dossier, saurez-vous la retrouver ?