Blog

L’esprit du jeu de Go défie la machine (2/2)

Cet article est en deux parties. Retrouvez ici la première partie de cet article .

03-machineamogo

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 ?

04-kimmyungwan

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 :

05-estimationdulac

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:

06-humouretgo

Dernière petite remarque

Une prétérition se cache dans ce mini-dossier, saurez-vous la retrouver ?

admin

Written by

The author didnt add any Information to his profile yet

  • Il me semble avoir entendu parlé de l’utiilsation d’apprentissage par renforcement sur le GO avec des résultats plutôt correct et en tout cas ne nécessitant par de super calculateur. L’intérêt principale étant d’apprendre par l’essai plutôt que de tenter d’explorer l’arbre de possibilités de façon un peu brutale (même en ayant un monte-carlo pas stupide). En gros, pas la peine d’explorer des voies qui de toutes façons ne seront pas choisies… MAlheureusement, je n’ai pas (le temps de) retrouvé de références.

  • Intéressant ça! Je vais rechercher des références.

    J’ai joué GnuGo 3.8 qui intègre du Monte-Carlo, mais je n’ai pas vu de différence de niveau majeur… Si un logiciel existe avec de l’apprentissage, ça me plairait bien de l’essayer.