# AlphaGo

AlphaGo est un programme informatique capable de jouer au jeu de go, développé par l'entreprise britannique DeepMind et racheté en 2014 par Google.
En octobre 2015, il devient le premier programme à battre un joueur professionnel (le Français Fan Hui) sur un goban de taille normale (19×19) sans handicap. Il s'agit d'une étape symboliquement forte puisque le programme joueur de go est alors un défi complexe de l'intelligence artificielle. En mars 2016, il bat Lee Sedol, un des meilleurs joueurs mondiaux (9e dan professionnel)$^,$. Le 27 mai 2017, il bat le champion du monde Ke Jie et le retrait du logiciel est annoncé.
L'algorithme d'AlphaGo combine des techniques d'apprentissage automatique et de parcours de graphe, associées à de nombreux entrainements avec des humains, d'autres ordinateurs, et surtout lui-même.
Cet algorithme sera encore amélioré dans les versions suivantes. AlphaGo Zero en octobre 2017 atteint un niveau supérieur en jouant uniquement contre lui-même. AlphaZero en décembre 2017 surpasse largement, toujours par auto-apprentissage, le niveau de tous les joueurs humains et logiciels, non seulement au go, mais aussi aux échecs et au shōgi.

## Histoire
### Contexte

Programmer un joueur de go est considéré comme un problème bien plus difficile que pour d'autres jeux, comme les échecs, en raison d'un bien plus grand nombre de combinaisons possibles, mais aussi parce que la condition de victoire et les objectifs intermédiaires sont beaucoup moins clairs, ce qui rend extrêmement complexe l'utilisation de méthodes traditionnelles telles que la recherche exhaustive. Quand l'ordinateur d'IBM Deep Blue a battu le champion du monde d'échecs Garry Kasparov en 1997, les ordinateurs étaient alors limités au niveau des joueurs amateurs faibles au jeu de go.
Le monde de la recherche voit en cette difficulté un défi à relever et améliore ses algorithmes, et le niveau des programmes s'accélère dans les années 2010. En 2012, le programme Zen a battu Takemiya Masaki (9e dan) deux fois, avec un handicap de 5 et 4 pierres. En 2013, Crazy Stone a battu Ishida Yoshio (9e dan) avec un handicap de 4 pierres.
Début 2016, Facebook annonce avoir des résultats encourageants à propos d'une intelligence artificielle de go appelée Darkforest développée en interne.

### Développement

AlphaGo a été développé par DeepMind Technologies, une entreprise britannique spécialisée dans l'intelligence artificielle créée par Demis Hassabis, Mustafa Suleyman et Shane Legg en 2010, et rachetée par Google en 2014.
AlphaGo représente une amélioration significative par rapport aux précédents programmes de go. Sur 500 parties jouées contre d'autres programmes, y compris Crazy Stone et Zen, AlphaGo n'en a perdu qu'une.

### Match contre Fan Hui

En octobre 2015, AlphaGo bat le champion européen de go Fan Hui (2e dan), 5-0 en parties lentes et 3-2 en parties rapides. C'est la première fois qu'un programme de go bat un joueur professionnel dans un match avec parties sans handicap sur un goban de taille normale (19×19). La nouvelle n'a été annoncée que le 27 janvier 2016 pour coïncider avec la publication d'un article dans le journal Nature décrivant l'algorithme utilisé.

### Match contre Lee Sedol

AlphaGo affronte en mars 2016 le joueur sud-coréen Lee Sedol (9e dan professionnel, niveau maximal), considéré comme le meilleur joueur du monde entre 2000 et 2010. Le match, récompensé par un prix d'un million de dollars, est diffusé et commenté en direct sur internet. Lee Sedol reçoit 150 000 $ pour sa participation, et 20 000 $ pour chaque partie gagnée.
Le match en 5 parties se termine par la victoire 4-1 de l'ordinateur :
* Victoire d'AlphaGo avec les blancs, par abandon après 3 heures et 39 minutes de jeu.
* Victoire d'AlphaGo avec les noirs, par abandon.
* Victoire d'AlphaGo avec les blancs, par abandon.
* Victoire de Lee Sedol avec les blancs (en offrant un jeu de qualité, et découvrant une faille dans le logiciel ; cette faiblesse d'AlphaGo sera réparée dans les versions ultérieures), par abandon.
* Victoire d'AlphaGo avec les blancs. Lee Sedol joue les noirs à sa demande considérant qu'ainsi la partie aurait plus de valeur.
Avant même la dernière partie et assuré de la victoire, AlphaGo est classé 9e dan professionnel de manière honorifique par la Hanguk Kiwon (fédération coréenne de jeu de go). Le prix d'un million de dollars, gagné par l'équipe d'AlphaGo, est donné à des associations caritatives.

### Après le match contre Lee Sedol

Avant même la rencontre, d'autres professionnels avaient manifesté leur désir de s'opposer à AlphaGo, même si Ke Jie estimait, au vu de ses parties contre Fan Hui, que ce n'était pas un adversaire digne de lui. Après le match, Lee Sedol regrettait de ne pas avoir donné toute sa mesure, et souhaitait une revanche. Mais ce n'est qu'au début de juin 2016 que la perspective d'une nouvelle rencontre se précisait ; cependant, le 6 juin, Demis Hassabis refusait de confirmer ces informations$^,$.
Le 18 juillet 2016, AlphaGo devient le meilleur joueur du monde au classement de GoRatings, avec 3612 points Elo (contre 3608 au second, Ke Jie).
En septembre 2016, des commentaires détaillés des parties du match contre Lee Sedol, dus à Gu Li et Zhou Ruiyang (en) et s’appuyant sur les analyses d’AlphaGo, ont été publiés sur le site de DeepMind ; d’après Gu Li, la maîtrise d’AlphaGo et la profondeur de ses analyses dépassent encore ce qu’on en avait déjà dit lors du match.
Le 4 janvier 2017, Demis Hassabis annonce qu’une version améliorée d'AlphaGo vient de disputer une série de 60 parties rapides contre les meilleurs joueurs mondiaux (Ke Jie, Iyama Yuta, Gu Li, Park Jeong-hwan (en)…), parties qu’elle a toutes gagnées, et qu’elle disputera des matchs officiels un peu plus tard dans l’année.
Du 23 au 27 mai 2017, un festival intitulé The Future of Go Summit est organisé par Google et l’association chinoise de weiqi à Wuzhen ; la plus récente version d'AlphaGo y affronte Ke Jie dans un match en trois parties, ainsi que d'autres professionnels chinois jouant en consultation. Là encore, AlphaGo gagne toutes les parties jouées. Après cette rencontre, Google annonce qu'AlphaGo ne jouera plus en compétition, mais qu'ils vont publier des documents techniques décrivant leurs dernières améliorations et un ensemble de parties jouées par la machine contre elle-même ; ils envisagent aussi de développer à l'usage des joueurs un outil d'analyse s'appuyant sur ce logiciel$^,$.
Le 17 octobre 2017, DeepMind annonce un nouveau développement, qu’ils nomment AlphaGo Zero ; ce programme utilise une architecture simplifiée et part d’une connaissance nulle du jeu (uniquement les règles) ; jouant uniquement contre lui-même, il atteint le niveau débutant en trois heures, bat 100 à 0 la version ayant battu Lee Sedol après 72 heures, et après 40 jours, il bat la version de mai 2017 (dite « Master ») 89 parties sur 100$^,$.
Le 5 décembre 2017, une nouvelle version nommée AlphaZero généralise encore cet algorithme, obtenant un programme générique capable d'apprendre à jouer au go, aux échecs ou au shōgi à partir de la simple connaissance des règles ; le programme parvient en quelques heures à battre les meilleurs programmes existants (par exemple, pour les échecs, il obtient après quatre heures d'apprentissage une nette victoire sur Stockfish : sur 100 parties, 25 victoires avec Blanc, 3 avec Noir, et 72 nulles).

## Algorithme

Les premières versions d'AlphaGo utilisent la méthode de Monte-Carlo, guidée par un « value network » et un « policy network » (un réseau de valeur et un réseau d'objectifs), tous deux implémentés en utilisant un réseau de neurones profond.
AlphaGo a initialement été entraîné pour « imiter » les joueurs humains, en retrouvant les coups enregistrés lors de dizaines de milliers de parties menées par des joueurs experts. Une fois un certain niveau atteint, il s'est entraîné à jouer des millions de parties contre d'autres instances de lui-même, utilisant l'apprentissage par renforcement pour s'améliorer.
Cependant, en octobre 2017, DeepMind publie dans Nature une nouvelle étude, décrivant AlphaGo Zero, une architecture simplifiée et n’utilisant plus ni la méthode de Monte-Carlo, ni des connaissances humaines, mais parvenant pourtant très rapidement à des performances supérieures à celles des versions précédentes.

## Projet Leela Zero

L’algorithme d’AlphaGo (ou du moins ses idées essentielles) ayant été rendu public, plusieurs groupes ont essayé de le reproduire, voire de l’améliorer. À partir de 2018 en particulier, un projet collaboratif et open source, Leela Zero, a obtenu en un an des résultats analogues, portables sur des ordinateurs individuels, et même sur des smartphones.