# AlphaGo

AlphaGo è un software per il gioco del go sviluppato da Google DeepMind. È stato il primo software in grado di sconfiggere un maestro umano nel gioco senza handicap e su un goban di dimensioni standard (19×19).
Sotto il nome di «AlphaGo» si intendono diverse versioni del software, in particolare:
* la versione che ha sconfitto 5-0 il campione europeo Fan Hui;
* la versione che ha sconfitto 4-1 Lee Se-dol;
* «Master», la versione che ha vinto 60 partite online contro professionisti e ha sconfitto 3-0 Ke Jie;
* «AlphaGo Zero», la versione del software basata completamente sull'auto-apprendimento;
* «AlphaZero», una versione che è in grado di giocare a go, scacchi e shogi.

## Storia

Secondo quanto affermato da David Silver, ricercatore di DeepMind, il progetto AlphaGo venne avviato nel 2014 per studiare quanto le reti neurali profonde potessero essere applicabili al gioco del go.
AlphaGo rappresentò un notevole avanzamento rispetto ai programmi per il gioco del go preesistenti. Su 500 partite disputate contro altri software, tra i quali Crazy Stone e Zen, AlphaGo (in esecuzione su un singolo computer) ha vinto tutte le partite tranne una, ed eseguendo una serie di incontri analoga ma girando su un cluster AlphaGo ha vinto tutte le 500 partite e ha vinto il 77% delle partite contro sé stesso eseguito su una singola macchina. La versione distribuita impiegava 1202 CPU e 176 GPU, circa 25 volte in più rispetto all'hardware del computer singolo.
Una versione preliminare di AlphaGo è stata testata su diverse configurazioni hardware, in modalità asincrona o distribuita, con un tempo di due secondi per mossa, generando i seguenti valori Elo.
| Configurazione | Thread di ricerca | n. CPU | n. GPU | Elo |
| Singola $^{p.10-11}$ | 40 | 48 | 1 | 2,151 |
| Singola | 40 | 48 | 2 | 2738 |
| Singola | 40 | 48 | 4 | 2850 |
| Singola | 40 | 48 | 8 | 2890 |
| Distribuita | 12 | 428 | 64 | 2937 |
| Distribuita | 24 | 764 | 112 | 3079 |
| Distribuita | 40 | 1,202 | 176 | 3140 |
| Distribuita | 64 | 1,920 | 280 | 3168 |

### Incontro con Fan Hui

Nell'ottobre del 2015 AlphaGo sconfisse 5-0 il campione europeo Fan Hui (2 dan), diventando il primo software in grado di sconfiggere un maestro umano nel gioco senza handicap e su un goban di dimensioni standard. L'annuncio pubblico venne fatto solo il 27 gennaio 2016, in coincidenza con la pubblicazione di un articolo su Nature che descrive l'algoritmo impiegato dal software.

### Incontro con Lee Se-dol

Tra il 9 e il 15 marzo 2016 AlphaGo disputò un incontro con il giocatore sudcoreano Lee Se-dol (9-dan), uno tra i più forti giocatori di go al mondo. L'incontro in cinque partite, giocate rispettivamente il 9, 10, 12, 13 e 15 marzo, si tenne al Four Seasons Hotel di Seul e venne trasmesso in diretta in streaming. AlphaGo girava sulla piattaforma cloud di Google, i cui server si trovano negli Stati Uniti, e le mosse elaborate dal software vennero riportate sul goban da Aja Huang, membro del team DeepMind e giocatore amatoriale di go (6-dan). L'incontro adottava le regole cinesi, con un komi di 7,5 punti e un tempo di riflessione di due ore e un byoyomi di 60 secondi. La potenza di calcolo impiegata era simile a quella usata nell'incontro con Fan Hui.
Al tempo dell'incontro, Lee Se-dol deteneva il secondo numero più alto al mondo di vittorie nei campionati internazionali di Go. Pur non esistendo un ranking ufficiale a livello internazionale, alcune fonti consideravano Lee Se-dol come il quarto miglior giocatore al mondo in quel periodo. AlphaGo non era stato configurato in maniera particolare per affrontare lo stile di gioco di Lee.
AlphaGo si è aggiudicato le prime tre partite per abbandono da parte di Lee Se-dol. Questi ha vinto la quarta partita, nella quale AlphaGo ha abbandonato alla centottantesima mossa. Il software ha infine vinto l'ultima partita per abbandono.
Il premio per il vincitore dell'incontro era pari a un milione di USD. Essendo stato aggiudicato da AlphaGo, l'importo è stato devoluto ad organizzazioni per il gioco del go e ad organizzazioni di beneficenza, tra le quali l'UNICEF. Lee Se-dol ha ricevuto un compenso di 150 000 USD per la partecipazione a tutte e cinque le partite e un compenso addizionale di 20 000 USD per la vittoria nella quarta partita.

## Algoritmo

L'algoritmo impiegato da AlphaGo usa una combinazione di machine learning e tecniche di ricerca su alberi, insieme ad un'estensiva fase di apprendimento da gioco sia umano sia artificiale. Utilizza la ricerca ad albero Monte Carlo (MCTS) per la selezione delle mosse, guidata da due reti neurali profonde (value network e policy network). Prima di essere inviato alle reti neurali, l'input è analizzato in una fase di pre-processing per estrarre alcune feature (ad esempio l'aderenza delle mosse a una serie di pattern comuni).
Nella prima fase del training le reti neurali effettuano un apprendimento supervisionato basato sul gioco umano, tentando di imitarlo usando un database di circa 30 milioni di mosse da partite storiche. Una volta raggiunta una certa forza di gioco, l'apprendimento prosegue per rinforzo giocando contro altre istanze di sé stesso.
Il software è programmato per abbandonare la partita se la probabilità di vittoria scende al di sotto di una certa soglia, che ad esempio nell'incontro del marzo 2016 con Lee Se-dol era fissata al 20%.

## Confronto tra le versioni di AlphaGo

Configurazione e forza :
| Versioni | Punteggio Elo | Partite | Hardware da gioco |
| AlphaGo "Fan" | 3144 | 5:0 contro Fan Hui | 176 GPU, distribuite |
| AlphaGo "Lee" | 3739 | 4:1 contro Lee Se-dol | 48 TPU, distribuite |
| AlphaGo "Master" | 4858 | 60:0 contro giocatori professionisti; Future of Go Summit | 4 TPU, macchina singola |
| AlphaGo Zero (40 giorni) | 5185 | 100:0 contro AlphaGo "Lee" 89:11 contro AlphaGo "Master" | 4 TPU, macchina singola |
| AlphaZero (34 ore) | 4430 (stimato) | 60:40 contro un AlphaGo Zero (3 giorni) | 4 TPU, macchina singola |
Come riferimento, i punteggi Elo di alcuni giocatori umani affrontati da AlphaGo sono:
* Fan Hui (ottobre 2015): 2760
* Lee Se-dol (5 marzo 2016): 3571
* Ke Jie (18 maggio 2017): 3676
Il giocatore umano con punteggio Elo più alto tra quelli registrati è Shin Jin-seo, che ha raggiunto 3827 punti nel 2020.

## Accoglienza

AlphaGo è considerato una pietra miliare nella ricerca sull'intelligenza artificiale, in quanto il go era considerato in precedenza un gioco fuori dalla portata delle tecniche di apprendimento automatico sviluppate all'epoca. Toby Manning (arbitro del match con Fan Hui) e Haijin Lee (segretario generale della International Go Federation) ipotizzano che in futuro i giocatori di go potranno contare sull'aiuto del computer per l'analisi di gioco.
Myungwan Kim (9 dan) ha descritto lo stile di gioco di AlphaGo "come quello di un umano" nell'incontro con Fan Hui. Toby Manning, arbitro dell'incontro, ha descritto lo stile di gioco del software come "conservativo".

## Partita di esempio

AlphaGo (nero) v. Fan Hui, quarto turno (8 ottobre 2015), AlphaGo vince per abbandono.
| Mosse da 1 a 99 | Mosse da 100 a 165 |