Voir la source de Go en informatique

[[Fichier:Territorio.png|thumb|Les programmes sont plus performants sur un [[goban]] de petite taille (ici 9×9).]]
Le développement de [[programme informatique]] capable de jouer au [[Go (jeu)|go]] est un problème de l'[[intelligence artificielle]]. Ce problème est considéré comme l'un des plus complexes à résoudre, les [[Algorithme|algorithmes]] classiques ([[Algorithme minimax|minimax]] et [[Élagage alpha-bêta|alpha-bêta]]) offrant des résultats médiocres. 

Le premier programme a été écrit en [[1968 en informatique|1968]] par {{Lien|trad=Albert Lindsey Zobrist|lang=en|fr=Albert Zobrist}} comme un élément de sa thèse sur la [[reconnaissance des formes]]. Ce n'est qu'en 2015 qu'un programme [[AlphaGo]] bat pour la première fois un [[joueur de go professionnel]], [[Fan Hui]], champion d'Europe de go, avant de battre [[Lee Sedol]], l'un des meilleurs joueurs au monde, en {{date-|mars 2016}} et [[Ke Jie]], le meilleur joueur du monde, en {{date-|mars 2017}}.

== Description du problème ==
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 leur 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é à 10{{exp|170}} - sur un [[goban]] 19×19 (contre environ 10{{exp|40}} aux échecs - sur un [[échiquier]] 8×8)<ref name="Le Monde">{{lien web|url=http://mobile.lemonde.fr/pixels/article/2016/01/27/premiere-defaite-d-un-professionnel-du-go-contre-une-intelligence-artificielle_4854886_4408996.html|titre=Première défaite d’un professionnel du go contre une intelligence artificielle|site=Le Monde|date=27/1/2016}}.</ref>, tandis que l'arbre du jeu couvre 10{{exp|600}} parties plausibles (contre environ 10{{exp|120}} aux échecs)<ref>Ce nombre, le [[nombre de Shannon]], est  lui-même immensément supérieur à celui (10<sup>80</sup>) des particules de l'univers (voir {{Lien web |url=http://www.reseaux-telecoms.net/agenda/lire-l-ordinateur-battra-t-il-l-homme-au-jeu-de-go-5977.html |titre=L'ordinateur battra-t-il l'homme au jeu de go ? |site= reseaux-telecoms.net|consulté le=2 février 2016}}).</ref>.

== Histoire ==

=== Débuts ===
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 go est souvent considéré comme l'un des grands défis de l'[[intelligence artificielle]].

Le premier tournoi entre machines a été organisé en 1984 par l'entreprise ''[[Acorn Computers]]'' et est remporté par le programmeur [[Pologne|polonais]] Bronislaw Przybyla<ref name="jessie31">{{Article|langue = français|année = 1985|mois = février-mars|numéro = 31|périodique = [[Jeux et Stratégie]]|titre = Atari en basic|page = 20-21|auteur=Pierre Aroutcheff|consulté le = 21 mars 2019}}.</ref>. Les huit programmes respectent les règles (à l'exception dans un cas d'une difficulté durant une [[Ko (go)|bataille de ko]]) mais jouent {{citation|affreusement mal}}<ref name="jessie31"/>.

Contrairement aux [[Programme d'échecs|programmes de jeu d'échecs]] qui ont rivalisé avec les meilleurs professionnels dès les années 1990, les programmes de go n'ont commencé à se rapprocher du niveau des joueurs de go professionnels qu'en 2013<ref>Victoire du programme [[Crazy Stone]] sur le {{9e|dan}} professionnel [[Ishida Yoshio]] le 20 mars 2013 (cf. le [http://remi.coulom.free.fr/CrazyStone/ site de Crazy Stone] et l'article de Go Game Guru ''« [http://gogameguru.com/crazy-stone-computer-go-ishida-yoshio-4-stones/ Crazy Stone computer Go program defeats Ishida Yoshio 9 dan with 4 stones] »'').</ref>. Auparavant, sur les petits plateaux de taille 9×9, les meilleurs programmes avaient atteint en 2005 le niveau des joueurs amateurs en [[Grade dan|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 s'appuyant sur l'algorithme de [[Algorithme de Monte-Carlo|Monte-Carlo]] en 2006.

Avant cette date, un joueur moyen était capable de battre les meilleurs programmes et certains bons joueurs, entraînés spécifiquement, les avaient battu avec des [[Handicap (go)|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, {{6e|dan}} amateur, battait ''Many Faces of Go'' malgré un handicap de 29 pierres.

Sur des ''goban'' de petite taille, les calculs sont plus simples à 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 {{formatnum:4472000000}} positions (environ 4 heures sur un P4 {{unité|2.0|GHz}}). Sa thèse<ref>{{en}} [http://erikvanderwerf.tengen.nl/pubdown/thesis_erikvanderwerf.pdf ''{{lang|en|AI techniques for the game of Go}}''], Thèse développant la résolution du go sur 5x5.</ref> développe plus largement la résolution du go 5×5.

=== Avancées techniques ===
[[Fichier:Computer-go-ratings-English.svg|vignette|Progression du [[Rangs et classements au go|niveau]] des ordinateurs sur [[KGS]].]]
Une des alternatives majeures à l'utilisation de connaissances et de recherches est l'utilisation des [[méthode de Monte-Carlo|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<ref>[http://interstices.info/jcms/c_43860/le-jeu-de-go-et-la-revolution-de-monte-carlo?hlText=monte-carlo Le jeu de go et la révolution de Monte Carlo] sur le site [[Interstices]].</ref>. 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<ref>{{lien web |titre=Sylvain GELLY's Home Page |url=https://archive.wikiwix.com/cache/20110224013530/http://www.lri.fr/~gelly/MoGo.htm |site=lri.fr via [[Wikiwix]] |consulté le=09-06-2023}}.</ref>, [[Crazy Stone]], Olga and Gobble.

En 2006, une nouvelle technique, ''upper confidence bounds applied to trees'' (UCT<ref>{{lien web |titre=UCT |url=http://senseis.xmp.net/?UCT |site=xmp.net |consulté le=09-06-2023}}.</ref>), 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<ref>http://www.cs.unimaas.nl/go4go/mango/ {{Lien archive|url=http://www.cs.unimaas.nl/go4go/mango/ |titre=Copie archivée |horodatage archive=20180723025636 }}</ref>. 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<ref>{{lien web |langue=en |titre=Many Faces of Go - Igowin |url=http://www.smart-games.com |site=smart-games.com |consulté le=09-06-2023}}.</ref> 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<ref>https://archive.wikiwix.com/cache/20110224013531/http://www.lri.fr/~teytaud/mogo.html.</ref> a gagné une partie<ref>https://archive.wikiwix.com/cache/20110224013531/http://www.lri.fr/~teytaud/crmogo.en.html.</ref> (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 fourni par [[Bull (entreprise)|Bull]] (32 nœuds avec 8 cœurs par nœud, chacun cadencé à {{unité|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 (go)|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 {{date-|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 point, 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 à {{unité|4.7|GHz}} pour produire 15 [[Téraflops]]<ref>[http://senseis.xmp.net/?MoGo Sensei's Library: MoGo].</ref>. 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é sous le pseudonyme MogoTitan.

En 2009, d'autres victoires contre des professionnels à des handicaps plus faibles (par des programmes tels que [[Crazy Stone]]) ont eu lieu ; de plus, Zen (programme médaille d'or aux olympiades de 2009) s'est [[Rangs et classements au go|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<ref>{{en}} [http://gogameguru.com/zen-computer-go-program-beats-takemiya-masaki-4-stones/ Détails du match sur le site Gogameguru].</ref>.

=== AlphaGo et le ''deep learning''===
{{Article détaillé|Match AlphaGo - Lee Sedol|AlphaGo|AlphaGo Zero|AlphaZero}}
En {{date-|octobre 2015}}, le programme [[AlphaGo]] développé par [[Google DeepMind]], combinant plusieurs techniques notamment du ''[[deep learning]]'', a franchi une nouvelle étape que les experts pensaient ne pas pouvoir être atteinte avant de nombreuses années<ref>{{en}} A. Levinovitz, ''The mystery of Go, the ancient game that computers still can’t win''. Wired Magazine (2014).</ref> : il bat sans handicap [[Fan Hui]], le meilleur joueur européen, professionnel {{2e|dan}}, par le score de cinq victoires à zéro en parties lentes et trois à deux en parties rapides<ref name="Le Monde" />{{,}}<ref>[https://www.lemonde.fr/pixels/article/2016/01/27/fan-hui-champion-europeen-de-go-je-suis-le-premier-joueur-pro-a-perdre-contre-une-machine_4854891_4408996.html Interview de Fan Hui à ce sujet].</ref>. 

En {{date-|mars 2016}}, il bat [[Lee Sedol]], joueur {{9e|dan}}, alors considéré comme un des meilleurs joueurs mondiaux, en remportant successivement les trois premières parties, puis la cinquième d'un [[Match AlphaGo - Lee Sedol|match en cinq parties]]<ref name=":0">{{Article|titre=Jeu de go : victoire finale de l'intelligence artificielle sur le score de 4 à 1|périodique=[[Le Monde|Le Monde.fr]]|date=2016-03-15|lire en ligne=https://www.lemonde.fr/pixels/article/2016/03/15/jeu-de-go-victoire-finale-de-l-intelligence-artificielle-sur-le-score-de-4-a-1_4882998_4408996.html|consulté le=2016-03-15}}</ref>. Ce match est suivi en direct sur internet, et qualifié de moment historique<ref name=":0" />.

Les performances d’AlphaGo amènent de nombreux programmeurs à tenter de développer des systèmes analogues ; ainsi, en {{date-|novembre 2016}}, une version améliorée de Zen, Deep Zen, réussit à gagner une partie sur trois d’un match à égalité contre [[Cho Chikun]]<ref>[https://www.sciencesetavenir.fr/high-tech/intelligence-artificielle/intelligence-artificielle-le-deep-learning-battu-par-l-humain-ouf_108424 La revanche de l’humain], sur [[Science et Avenir]], 11 novembre 2016.</ref>.

Après des améliorations (corrigeant en particulier les faiblesses apparues lors du match contre Lee Sedol),  AlphaGo bat, dans des parties rapides non officielles jouées début {{date-|janvier 2017}} sur des serveurs chinois, quelques-uns des meilleurs joueurs mondiaux ([[Ke Jie]], [[Iyama Yuta]], [[Gu Li]], etc.) sur le score stupéfiant de 60 victoires à zéro<ref>{{de}} [http://www.go-baduk-weiqi.de/masterp-schlaegt-go-profis/ Diagrammes interactifs (mais non commentés) de ces parties].</ref> ; durant ce temps, JueYi, un programme  chinois utilisant les algorithmes d'AlphaGo, parvient, avec des résultats tout de même un peu plus faibles, à atteindre en {{date-|mars 2017}}  [[Rangs et classements au go|le niveau de {{10e|dan}}]] sur le serveur FoxGo<ref>{{en}} [https://xinwengolife.wordpress.com/2017/03/06/chinese-ai-10th-dan-jueyi-alphago-had-slain-top-pros-on-foxgoserver/ Annonce de cette promotion] sur xinwengolife.</ref>.

Développée en  2017 en n'utilisant aucune connaissance humaine mais uniquement à partir des règles du jeu et par [[Apprentissage automatique|auto-apprentissage]], une nouvelle version, [[AlphaGo Zero]], est encore plus compétente que les précédentes<ref name="Nature2017">{{article |prénom1=David |nom1=Silver |lien auteur1=David Silver (programmer) |prénom2=Julian |nom2=Schrittwieser |prénom3=Karen |nom3=Simonyan |prénom4=Ioannis |nom4=Antonoglou |titre=Mastering the game of Go without human knowledge |journal=[[Nature (journal)|Nature]] |volume=550 |numéro=7676 |date=19 octobre 2017 |issn=0028-0836 |doi=10.1038/nature24270 |url=https://www.nature.com/nature/journal/v550/n7676/full/nature24270.html |consulté le=10 décembre 2017 |pages=354–359 |prénom9=Matthew |prénom16=Thore |prénom5=Aja |nom5=Huang |lien auteur5=Aja Huang |prénom6=Arthur |nom6=Guez |prénom7=Thomas |nom7=Hubert |prénom8=Lucas |lien auteur17=Demis Hassabis |nom17=Hassabis |prénom17=Demis |nom16=Graepel |nom15=Driessche |nom9=Lai |prénom15=George van den |nom14=Sifre |prénom14=Laurent |lien auteur13=Fan Hui |nom13=Fan |prénom13=Hui |nom12=Lillicrap |prénom12=Timothy |nom8=Baker |nom11=Chen |prénom11=Yutian |nom10=Bolton |prénom10=Adrian |lien auteur11=Chen Yutian }}</ref> ; en décembre 2017, DeepMind en publie une version plus polyvalente encore, [[AlphaZero]], capable de jouer également aux [[échecs]] et au [[shōgi]] à un niveau supérieur à celui des meilleurs humains ou programmes<ref name="preprint">{{lien arXiv|auteur=David Silver ''et al''|auteur10=Thore Graepel|class=cs.AI|titre=''Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm''|eprint=1712.01815|auteur13=[[Demis Hassabis]]|auteur12=Karen Simonyan|auteur11=Timothy Lillicrap|auteur9=Dharshan Kumaran|auteur1=David Silver|auteur8=Laurent Sifre|auteur7=Marc Lanctot|auteur6=Arthur Guez|auteeur5=Matthew Lai|auteur4=Ioannis Antonoglou|auteur3=Julian Schrittwieser|auteur2=Thomas Hubert|date=5 décembre 2017}}</ref>.

Après 2020, les meilleurs programmes ({{Lien|langue=en|trad=Fine Art (software)|fr=Fine Art}}, Golaxy, etc.), tous développés en s’inspirant des algorithmes d’AlphaGo, rendent de manière consistante deux pierres de handicap aux meilleurs professionnels, ce qui correspondrait à un niveau de {{11e}} dan amateur et de 14 ou {{15e}} dan professionnel{{Note|texte={{article|lang=en|titre=Tencent Fine Art Artificial Intelligence Go program beats top human players after giving two stone handicap|auteur=Brian Wang|date=mars 2018|périodique=nextBIGfuture|url=https://www.nextbigfuture.com/2018/03/tencent-fine-art-artificial-intelligence-go-program-beats-top-human-players-after-giving-two-stone-handicap.html}}}} ; des programmes plus faibles (mais tout de même de la force des meilleurs professionnels), tels que [[Leela Zero]] ou [https://github.com/lightvector/KataGo Katago], développés par la communauté des joueurs, tournent sur des [[Ordinateur personnel|ordinateurs personnels]] et même sur des [[Smartphone|smartphones]], permettant désormais à tous de s’entraîner dans des conditions encore inimaginables en 2018.

== Notes et références ==
{{traduction/Référence|en|Go software|238587545}}

{{Références}}

== Voir aussi ==
=== Articles connexes ===
* [[Jeu vidéo de go]]
* [[Go Text Protocol]] : interface de jeu utilisée par les programmes.
* Exemples de programmes :
** [[GNU Go]]
** [[Crazy Stone]]
** [[AlphaGo]]
* [[Recherche arborescente Monte-Carlo]]

=== Liens externes ===
* {{en}} [http://computer-go.info Diverses ressources sur le go et l'informatique]
* [http://www.inria.fr/saclay/ressources/culture-scientifique/mogo2009/view?set_language=fr Un article sur les progrès de l'intelligence artificielle en 2009]
* {{en}} [http://www.pleinsud.u-psud.fr/specialR2008/en/12_GOthique.pdf Un article détaillant l'algorithme de Mogo]

{{portail|intelligence artificielle|Jeu de go}}

[[Catégorie:Jeu de go et informatique| ]]
[[Catégorie:Intelligence artificielle]]