Voilà un petit billet pour se détendre, et sortir un petit peu des sujets technologie.
Confucius disait : «Mieux vaut jouer au Go que de rester oisif».
Ce dossier va donc aborder le jeu de Go, et particulièrement les efforts en cours pour développer une IA de Go correcte.
Et revenir également sur l’événement qui a (un petit peu) secoué le monde du Goen 2008 : La victoire d’un programme sur un joueur professionnel.
Le jeu de Go ? Késako ?
Le jeu de Go est originaire de Chine, il s’agit du plus ancien jeu de stratégie connu.
Des légendes anciennes lui attribuent un âge vénérable d’environ 4000 ans, et lui prêtent des origines diverses. En vérité, les premières références au jeu datent d’environ 722 à 481 av JC.
Il s’agit de l’un des 4 Arts chinois, avec la poésie, la calligraphie, et l’art pictural.
A partir d’un matériel simple (un plateau de jeu appelé Goban, des pierres noires et blanches), les règles du jeu se sont progressivement développées au fil des siècles, pour aboutir aux règles actuelles.
Celles-ci sont très simples et peu nombreuses, il s’agit essentiellement des règles de capture de pierres.
Cependant le go n’est pas un jeu facile. Les stratégies et tactiques possibles sont quasi-infinies, l’apprentissage du jeu est très long.
Certaines mauvaises langues (que je ne citerai pas) affirment que le jeu de go est aux échecs ce que les échecs sont au morpion! No comment. J’ajouterai juste que Bobby Fischer, célèbre champion américain d’échecs affirmait : «Les extra-terrestres ont peut être inventé les échecs, ils ont certainement inventé le jeu de go»
Les règles du jeu en deux mots
Une partie de Go oppose deux joueurs. Il n’y a pas de composante aléatoire.
Sur le plateau de jeu, appelé Goban, est tracée une grille de 19 lignes horizontales par 19 lignes verticales qui déterminent 361 intersections.
Au début d’une partie, le Goban est vide (partie à égalité). Chaque joueur place à tour de rôle une pierre (noire ou blanche) sur une intersection. Noir débute la partie. Pour compenser cet avantage, Blanc se voit attribuer un certain nombre de points d’avance: le Komi.
Le but du jeu est de former des territoires: Ce sont des ensembles d’intersections vides, entourés de pierres de la même couleur.
La partie se termine quand aucun territoire n’est plus attaquable, et qu’il n’y a plus de possibilité d’en construire de nouveaux. Dans ce cas les 2 joueurs passent leur tour et les territoires de chaque joueur sont comptabilisés (en additionnant la taille de chaque territoire). Le joueur ayant le plus de territoires remporte la partie (sans oublier les points de Komi pour le joueur Blanc).
Je ne détaillerai pas plus les règles dans ce billet. Si vous voulez en savoir plus, vous pouvez apprendre les règles ici :
http://fr.wikipedia.org/wiki/Règles_du_jeu_de_go
Ou encore ici (avec Dédé) :
http://jeudego.org/
Informatique et jeu de Go
Malgré un travail aussi important depuis 40 ans sur les programmes de Go que sur ceux d’échecs, les meilleurs programmes atteignent environ le niveau 7 kyu, soit le niveau d’un bon joueur amateur (un joueur amateur débute à 30e kyu et peut progresser jusqu’à 1er kyu. Ensuite, la progression se fait de 1er dan jusqu’à 7ème dan. Un joueur professionnel peut aller jusqu’à 9ème dan).
La première confrontation entre un programme et un joueur humain a eu lieu en 1997, et a opposé Janice Kim (joueuse professionnelle) à HandTalk. Malgré un handicap de 25 pierres, la joueuse s’est imposée…
Seconde confrontation en 1998, entre Martin Müller, un «modeste» sixième dan amateur et le programme Many Faces of Go: Victoire de l’humain sur la machine, malgré un handicap de 29 pierres…!
Certains programmes atteignent cependant des niveaux professionnels, mais uniquement sur des Goban de taille réduite (9×9), ou lorsqu’ils sont spécialisés sur certains aspects du jeu.
Par exemple le programme de Thomas Wolf, spécialisé sur la résolution de tsumegos (prononcer «tsuméguo», problèmes de vie et de mort de groupes de pierres), atteint un niveau quasi professionnel.
Ce n’est pas la seule stratégie. D’autres programmes sont spécialisés sur le calcul de yose (prononcer « yossé », il s’agit de la fin d’une partie, quand il est possible de décomposer la position en petits jeux indépendants).
Mais si ces programmes ont de très bons sur des sous-problèmes, aucun programme n’a encore de bons résultats sur le jeu global,
Du moins jusqu’à il y a peu de temps… Mais nous allons y revenir…
Pourquoi le jeu de Go résiste-t-il encore à l’informatique ?
Les raisons sont multiples.
Contrairement aux échecs où le plateau se vide au cours de la partie, au Go, le plateau est vide au départ. Une partie d’échecs se simplifie petit à petit, une partie de Go se complexifie du début au milieu de partie (du Fuseki au Chuban), puis se simplifie dans les dernières phases de jeu (Yose).
Aux échecs, on commence par choisir parmi 20 coups possibles, puis en moyenne parmi 40 coups.
Au Go, on commence par choisir parmi 361 coups possibles (même si, compte tenu de la symétrie du Goban, et en excluant les coups notoirement mauvais, on peut réduire à 50).
Ensuite nombre de coups possibles décroît lentement au cours du jeu (environ 200 en moyenne).
La taille du Goban (19×19) implique donc une combinatoire gigantesque: la hauteur (très approximative) de l’arbre des possibilités est d’environ 10600, contre 10120 aux échecs, soit plus que le nombre estimé d’atomes dans l’univers…!
De plus, le jeu exige un haut niveau de reconnaissance de forme (il existe des «bonnes» formes et des «mauvaises formes» théoriques, pour les groupes de pierre, même si tout peut dépendre de la situation…), et un sens stratégique global (un groupe de pierres peut avoir une influence sur un autre groupe, même très éloigné sur le plateau. Il est possible d’attaquer des groupes à distance).
Enfin, il est très difficile pour un programme d’évaluer une position de manière statique: Un seul coup peut retourner entièrement une situation, en tuant un grand groupe de pierres par exemple.
Toutes ces difficultés écartent les stratégies de programmation basées sur le min/max.
Mais alors comment procèdent les programmes ?
Fonctionnement de GnuGo
GnuGo est un programme open-source écrit en C. Son niveau est estimé à 7-8 kyu environ (à condition de jouer «à la loyale», c’est-à-dire sans exploiter les faiblesses du programme…).
La dernière version stable est la 3.8.
Son fonctionnement repose sur un certain nombre de modules d’analyse, plus ou moins indépendants les uns des autres, chaque module étant spécialisé sur l’analyse d’un aspect particulier du jeu, par exemple:
Analyse de la vie et mort des groupes (ou plutôt probabilités de vie et de mort)
Analyse des semeai (terme de go désignant 2 groupes de pierres s’attaquant l’un l’autre)
Analyse des coups de coupe possibles (séparation de groupes de pierre adverses)
etc…
Chaque module calcule «son» meilleur coup (avec une fonction d’évaluation propre au module).
Le module principal choisit ensuite l’un des coups selon les estimations faites et un algorithme de priorités.
Jusqu’à présent il s’agit de la stratégie adoptée (peu ou prou) par tous les programmes de Go. Mais cela n’a pas été suffisant pour concurrencer les meilleurs joueurs humains.
Mais en 2008 un petit tremblement de terre a eu lieu…
(à suivre)
Auteur : Mikaël Lester