- Jeu de go (informatique)
-
Jeu de go (informatique)
Le jeu de go en informatique est une branche de l'intelligence artificielle qui s'attache à créer des logiciels informatiques capables de jouer au jeu de go, un très ancien jeu de plateau.
Le jeu de go est considéré comme un problème compliqué en intelligence artificielle, qui ne peut pas être résolu aussi facilement que pour les échecs.
Le premier programme a été écrit en 1968 par Albert Zobrist comme un élément de sa thèse sur la reconnaissance des formes.
Sommaire
Performances
Contrairement aux programmes de jeu d'échec qui rivalisent avec les meilleurs professionnels, les programmes de jeu de go n'atteignent pas encore le niveau moyen des joueurs de go amateurs. Sur les petits goban 9x9, les meilleurs programmes ont atteint récemment le niveau des joueurs en dan, mais les techniques qui ont permis cette progression n'ont donné que des résultats mitigés sur la taille normale de goban 19x19. Sur 19x19, le niveau en dan est resté hors d'atteinte jusqu'à l'apparition récente des programmes Monte-Carlo ; avant 2002, 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'à 25 à 30 pierres, ce qui serait impossible contre un joueur humain, même très peu expérimenté. Ainsi en 1997, Janice Kim, shodan professionnelle, 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.
L'augmentation de puissance des ordinateurs n'avait 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.
Méthode de Monte-Carlo
Une des alternatives majeures à l'utilisation de connaissances et de recherche 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. 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 choisie 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, CrazyStone, Olga and Gobble.
En 2006, une nouvelle technique, upper confidence bounds applied to trees (UCT), a été développée et utilisée par de nombreux programme sur 9x9 avec des résultats excellents. 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 conduits 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 19x19 on peut trouver MoGo, CrazyStone, et Mango. MoGo a gagné l'édition 2007 des Computer Olympiad et gagné un blitz sur trois contre Guo Juan, 5ème dan professionnel, sur 9x9 Go. The Many Faces of Go 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 a gagné une partie [1] (sur trois) contre Catalin Taranu, 5ème dan professionnel, sur 9x9 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, séquencé à 3 GHz) La machine n'était pas disponible durant l'un des matchs perdus. MoGo a également joué une partie sur 19x19 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 19x19 face à Kim MyungWan 8ème dan professionnel, avec MoGo ayant un avantage de 9 pierres de handicap. MoGo a gagné (de 1.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). Mr. Kim 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.[2] 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
Notes et références
Voir aussi
Articles connexes
Liens externes
- (en) Cet article est partiellement ou en totalité issu d’une traduction de l’article de Wikipédia en anglais intitulé « Go software ».
- un article sur les progrès de l'intelligence artificielle en 2009
Catégorie : Jeu de go
Wikimedia Foundation. 2010.
