Jeu de go en informatique

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Tableau de jeu de Go 9×9 informatisé

Le jeu de Go - sous forme de programme - est une branche de l'informatique s'attachant à créer des logiciels capables de jouer à ce très ancien jeu de plateau (VIIIe-IVe siècles avant J.-C.).

Après des balbutiements utilisant des algorithmes classiques (Minimax et alpha-bêta), il fait maintenant appel à des techniques issues de l'intelligence artificielle (IA). On le considère comme l'un des problèmes les plus complexes à résoudre en IA. Le premier programme utilisant ces techniques a été écrit en 1968 par Albert Zobrist (en) comme un élément de sa thèse sur la reconnaissance des formes.

Description du problème[modifier | modifier le code]

Comme pour tous les jeux, il faut jouer un coup qui améliore sa situation et détériore celle de son adversaire. Pour estimer une situation aux échecs, une bonne estimation est de compter le nombre de pièces sur l'échiquier, en les pondérant (1 point par pion, 5 par tour...), et en ajustant la valeur trouvée par les libertés, les protections des pièces...

Cela passe par le calcul d'une fonction d'évaluation, associant les scores de chacun des adversaires à chaque nœud.

C'est difficilement réalisable au go : on ne dispose pas de fonction d'évaluation (estimation des valeurs antagonistes d'une position) ne nécessitant pas - entre autres - des capacités humaines de reconnaissance de formes, l'expérience de parties déjà jouées et une très grande profondeur de calcul..

La technique d'exploration des différentes possibilités (pour chaque coup, déterminer la meilleure réponse possible, puis la meilleure réponse à celle-ci, et ainsi de suite…), plus techniquement la méthode dite minimax, échoue au go à cause de l'énorme quantité de coups plausibles, de la durée des parties et de la complexité croissante (Aux échecs, la complexité est - elle - décroissante par diminution du nombre de pièces restantes).

Le nombre de positions légales est estimé à 10170 - sur un Goban 19×19 (contre environ 1040 aux échecs - sur un échiquier 8×8)[1], tandis que l'arbre du jeu couvre 10600 parties plausibles (contre environ 10120 aux échecs).

Histoire[modifier | modifier le code]

Débuts[modifier | modifier le code]

L'augmentation de la puissance des ordinateurs n'a que très peu d'influence sur le niveau des programmes de go, et le problème du jeu de go est souvent considéré comme l'un des prochains défis de l'intelligence artificielle.

Contrairement aux programmes de jeu d'échecs qui ont rivalisé avec les meilleurs professionnels dès les années 1990, les programmes de jeu de go n'ont commencé à atteindre le niveau des joueurs de go professionnels qu'en 2013[2]. Auparavant, sur les petits plateaux de taille 9×9, les meilleurs programmes avaient atteint en 2005 le niveau des joueurs amateurs en dan, mais les techniques qui ont permis cette progression ne donnaient que des résultats mitigés sur la taille normale de plateau 19×19, et le niveau en dan est resté hors d'atteinte jusqu'à l'apparition des programmes basés sur l'algorithme de Monte-Carlo en 2006.

Avant cette date, un joueur moyen était capable de battre les meilleurs programmes et certains joueurs forts entraînés spécifiquement les avaient battu avec des handicaps allant jusqu'à 30 pierres, ce qui serait impossible contre un joueur humain, même très peu expérimenté. Ainsi en 1997, Janice Kim, shodan professionnelle (1er Dan pro.), battait le programme HandTalk malgré un handicap de 25 pierres puis en 1998, Martin Müller, sixième dan amateur, battait Many Faces of Go malgré un handicap de 29 pierres.

Sur des goban de petite taille, les calculs sont plus simple à effectuer. En 2002, le jeu sur un goban 5×5 a été résolu par le programme MIGOS (MIni GO Solver) de Erik van der Werf, fruit de l'examen de 4 472 000 000 positions (environ 4 heures sur un P4 2,0 GHz). Sa thèse[3] développe plus largement la résolution du go 5×5.

Avancées techniques[modifier | modifier le code]

Une des alternatives majeures à l'utilisation de connaissances et de recherches est l'utilisation des méthodes de Monte-Carlo. Pour cela il suffit de lister les coups possibles et pour chaque coup de jouer des milliers de parties au hasard[4]. Le coup qui conduit au meilleur résultat pour le joueur courant est supposé le meilleur coup. L'avantage de cette méthode est qu'elle requiert peu de connaissances spécifiques mais l'inconvénient est qu'elle est coûteuse en termes de mémoire et de temps processeur. De plus, parce que les coups utilisés pour l'évaluation sont choisis au hasard, il est possible qu'un coup qui serait excellent sauf pour une réponse spécifique soit de façon erronée choisi comme un bon coup. Le résultat est un programme qui est fort d'un point de vue stratégique mais faible tactiquement. Ce problème peut être compensé en ajoutant de la connaissance à la génération de coup et une plus grande profondeur de recherche avant l'évaluation de Monte-Carlo. Parmi les programmes qui utilisent les techniques de Monte-Carlo se trouvent MoGo[5], CrazyStone[6], Olga and Gobble.

En 2006, une nouvelle technique, upper confidence bounds applied to trees (UCT[7]), a été développée et utilisée par de nombreux programmes sur 9×9 avec d'excellents résultats. UCT utilise les résultats des play outs joués jusque là pour guider l'exploration tout en autorisant des séquences alternatives à être explorées. UCT et de nombreuses autres optimisations ont conduit MoGo à être l'un des plus forts programmes produits par un chercheur. Parmi les premières applications avec succès de la méthode UCT sur 19×19 on peut trouver MoGo, CrazyStone, et Mango[8]. MoGo a gagné l'édition 2007 des Computer Olympiad et gagné un blitz sur trois contre Guo Juan, 5e dan professionnel, sur le goban 9×9. The Many Faces of Go[9] a gagné l'édition 2008 des Computer Olympiad après avoir ajouté UCT à ses méthodes classiques de recherche.

En 2008, grâce à une parallélisation efficace, MoGo[10] a gagné une partie[11] (sur trois) contre Catalin Taranu, 5e dan professionnel, sur 9×9 avec des temps classiques (30 minutes pour chaque joueur). Mogo tournait sur un cluster fournit par Bull (32 nœuds avec 8 cœurs par nœud, chacun séquencé à 3 GHz). La machine n'était pas disponible durant l'un des matchs perdus. MoGo a également joué une partie sur 19×19 contre Catalin Taranu et a perdu en dépit d'un avantage de 9 pierres de handicap. Cependant Mogo était en bonne position durant cette partie et a perdu à cause d'un mauvais choix lors d'un ko. La machine utilisée pour cet évènement (l'IAGO challenge, organisé par la société « Recitsproque ») était une bonne machine mais loin des meilleurs standards de l'industrie.

Le 7 août 2008 Mogo a gagné une partie sur 19×19 face à Kim MyungWan 8e dan professionnel, avec MoGo ayant un avantage de 9 pierres de handicap. MoGo a gagné (de 0,5 pt, mais cette victoire n'est pas si serrée qu'il y parait, le programme jouant la sécurité et perdant des points dès qu'il est certain de gagner). Kim MyungWan a utilisé environ 13 minutes de temps alors que MoGo en a utilisé environ 55, cependant il ne pense pas qu'utiliser plus de temps lui aurait permis de gagner. MoGo fonctionnait depuis les Pays-Bas sur un super ordinateur de 800 nœuds, chacun contenant 4 cœurs tournant à 4,7 GHz pour produire 15 Téraflops[12]. MyungWan et MoGo ont joué un total de 4 parties à handicap et limite de temps variable, chacun en gagnant deux. Les enregistrements des parties sont accessibles sur le serveur de go KGS où Mogo a joué en tant que MogoTitan.

En 2009, d'autres victoires contre des professionnels à des handicaps plus faibles (par des programmes tels que Crazystone) ont eu lieu ; de plus, Zen (programme médaille d'or aux olympiades de 2009) s'est classé de manière consistante entre 1 et 2 dan sur KGS.

Zen, en particulier, a connu ensuite une progression plus lente, mais régulière, l'amenant au début 2012 à un niveau de 4e dan sur KGS, et même de 6e dan en parties rapides ; lors d'un match-exhibition contre Takemiya Masaki, il a gagné successivement une partie à 5 pierres de handicap, puis une partie à 4 pierres[13].

En octobre 2015, un programme développé par Google DeepMind, AlphaGo, utilisant (entre autres) la technique du deep learning, a franchi une nouvelle étape (que les experts pensaient ne pas pouvoir être atteinte avant de nombreuses années[14]) en battant sans handicap Fan Hui, le meilleur joueur européen, professionnel 2 dan, par le score de cinq victoires à zéro en parties lentes et trois à deux en parties rapides[1],[15]. Un match contre Lee Sedol est programmé pour mars 2016[16].

Notes et références[modifier | modifier le code]

  1. a et b « Première défaite d’un professionnel du go contre une intelligence artificielle », sur Le Monde,‎ .
  2. Victoire du programme Crazy Stone sur le 9° dan professionnel Ishida Yoshio le 20 mars 2013 (cf. le site de Crazy Stone et l'article de Go Game Guru « Crazy Stone computer Go program defeats Ishida Yoshio 9 dan with 4 stones »).
  3. (en) AI techniques for the game of Go, Thèse développant la résolution du go sur 5x5.
  4. Le jeu de go et la révolution de Monte Carlo sur le site Interstices.
  5. http://www.lri.fr/~gelly/MoGo.htm
  6. http://remi.coulom.free.fr/CrazyStone/
  7. http://senseis.xmp.net/?UCT
  8. http://www.cs.unimaas.nl/go4go/mango/
  9. http://www.smart-games.com
  10. http://www.lri.fr/~teytaud/mogo.html
  11. http://www.lri.fr/~teytaud/crmogo.en.html.
  12. Sensei's Library: MoGo.
  13. (en) Détails du match sur le site Gogameguru.
  14. (en) A. Levinovitz, The mystery of Go, the ancient game that computers still can’t win. Wired Magazine (2014).
  15. Interview de Fan Hui à ce sujet.
  16. (en) Elisabeth Gibney, « Google masters Go », Nature, vol. 529, no 7587,‎ , p. 445-446.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]