GO: una macchina emula l'uomo (e lo batte)

On January 28, 2016

<<Il software AlphaGo ha battuto il professionista Fan Hui con il risultato di 5-0, giocando alla pari>> una notizia che può facilmente passare inosservata o non essere neppure compresa, eppure è sensazionale perché segna un punto di svolta fondamentale nell’informatica e in particolare nel campo dell’intelligenza artificiale.

 

Qui non si tratta solo dell’ennesimo gioco da tavola (il Go in questo caso) dove la macchina è riuscita grazie alla sua enorme e sempre crescente potenza di calcolo a sopraffare l’uomo, il passo fatto è di gran lunga più significativo di quanto avvenuto ormai venti anni fa quando Kasparov (leggenda degli scacchi) perse contro il computer Deep Blue. Cercheremo di chiarire perché e per farlo c’è bisogno innanzitutto di riassumere alcune regole fondamentali di questo gioco.

Cos'è il GO

Benché quasi sconosciuto alla stragrande maggioranza degli occidentali, il Go è molto giocato in Asia e in particolare in Giappone, Cina e Corea. E’ il gioco da tavola più antico del mondo (risalente forse a 4000 anni fa) e allo stesso tempo però quello più complesso. Eppure le regole del gioco sono di una semplicità disarmante per cui bastano pochi minuti a chiunque per essere in grado di cimentarsi in una partita. Si gioca in due, bianco contro nero, su una scacchiera (detta goban) composta da una griglia di 19 righe orizzontali e 19 verticali, con pedine (in gergo dette pietre). A differenza degli scacchi e della dama le pietre si giocano sulle intersezioni tra righe e non sulle caselle. All’inizio della partita il goban è vuoto. Si gioca a turno, comincia il nero e ogni mossa consiste nel posare una pietra del proprio colore su una qualunque delle intersezioni vuote disponibili. Quando una o più pietre viene circondata da quelle avversarie allora si dice che è stata “catturata” e va rimossa dal goban. Lo scopo del gioco non è catturare le pietre avversarie bensì prendere il controllo di almeno metà delle 361 intersezioni presenti.

Nulla di più semplice e allora da dove nasce la sua complessità? Semplicemente dallo smisurato numero di partite possibili ovvero dalla difficoltà che un giocatore ha nel trovarsi ad ogni turno di fronte ad un numero elevato di possibili alternative tra cui scegliere.

La complessità del gioco

Per avere un’idea di quanto sia complesso il Go è possible confrontarlo con altri giochi. Gli scacchi, che vengono solitamente erroneamente considerati come il non plus ultra della complessità, non sono in grado neanche lontanamente di reggere il confronto con il Go. Per fare un esempio semplice consideriamo la prima mossa. Negli scacchi il bianco ha solo 20 possibili alternative, così come solo 20 sono quelle che ha il nero, per un totale di 400 posizioni dopo il primo turno. Nel go invece il giocatore che inizia (il nero) può scegliere una tra le 19*19=361 intersezioni inizialmente vuote e il bianco, stando a quanto detto prima, una tra le 360 rimanenti, per un totale di 129.960 posizioni! La differenza è abissale. Andando avanti nella partita negli scacchi la media in ogni turno è di 35 mosse possibili tra cui scegliere. Nel Go 200!

Questa differenza diventa una voragine se dopo un conto un poco più elaborato si confronta il numero di posizioni che si possono teoricamente verificare nei due giochi. Negli scacchi possiamo disporre i pezzi (in un modo compatibile con le regole del gioco) in circa 10^{45} modi diversi, un numero davvero enorme. Nel Go però questo numero è stato calcolato con esattezza e supera 10^{170} che è più di quanto oggigiorno si pensa che siano gli atomi presenti nell’universo (10^{80}). Si tratta di un numero talmente grande da aver reso vano ogni tentativo fatto negli ultimi 60 anni di far giocare decentemente i computer attraverso algoritmi utilizzati con successo in altri giochi.

Nella complessità del gioco poi c’è un’altra caratteristica del Go da tenere presente ovvero che questo gioco è stato pensato specificamente per non finire pari. Negli scacchi il risultato di parità, la cosiddetta patta, svolge un ruolo fondamentale. Oggi più di un terzo delle partite giocate da professionisti è destinata a questo risultato, il che vuol dire che spesso un leggero vantaggio negli scacchi non si concretizza. Negli scacchi si possono commettere piccoli errori e non perdere. Nel go invece un solo errore può essere fatale. Per vincere basta controllare alla fine della partita anche una sola intersezione in più del tuo avversario (una delle 361 disponibili). E’ un gioco dove si porta a casa la vittoria anche con un margine minimo. Non devi annientare il tuo avversario catturando il suo re (come negli scacchi) o mangiando tutte le sue pedine (come nella dama), ma devi solo fare un po’ meglio di lui.

Il Go e l’estetica

Per quanto raffinati siano diventati i programmi di scacchi negli ultimi anni, la potenza di calcolo dei computer odierni è determinante nel gioco perché permette agli stessi di andare tanto in profondità nell’analisi delle posizioni da consentire di prevedere facilmente anche alcune decine di mosse. Nel Go, l’approccio brutale basato su un’analisi più o meno esaustiva delle possibili varianti è per i computer moderni assolutamente proibitiva e non è chiaro neppure se sarà mai praticabile. La sfida giocata dagli informatici negli ultimi decenni è stata quindi quella di trovare un approccio che fosse nuovo e possibilmente emulasse il pensiero umano.

Per cercare di capire come siano riusciti i programmatori del team di Google AlphaGo a rendere competitivo un computer è quindi utile chiarire alcuni dettagli sui processi decisionali che inducono un giocatore di Go a giocare una mossa piuttosto che un’altra. È ovvio che se per i computer non è possibile cercare di prevedere tutte le possibilità, questo per l’uomo è assolutamente fuori discussione. Ebbene, l’uomo, come in altri giochi, pone rimedio a questa sua “incapacità” basandosi sull’esperienza e ragionando per analogie, ovvero costruendo quella che viene comunemente chiamata una “strategia”. Nel processo di apprendimento del gioco, soprattutto nei primi anni di pratica, un giocatore impara a riconoscere un enorme numero di disposizioni delle pietre e le assimila catalogandole come “buone” e “cattive”. Riconoscere, fate bene attenzione, non significa memorizzare. Lo fa attraverso lo studio e la pratica e riesce ad immagazzinare un enorme numero di nozioni non attraverso la logica, ma bensì attraverso l’estetica. È curioso infatti che molto spesso riferendosi ad una certa mossa sentirete dire ad un giocatore di Go che essa è “bella” o “brutta”, e non “buona” o “cattiva”, e questo perché il giudizio si basa su principi di carattere generale non dettati da una certezza matematica. Un professionista durante una partita è in grado all’occorrenza di prevedere un certo numero di mosse e, per restringere il campo delle possibilità e poter andare in profondità nell’analisi, si fa guidare proprio da questo giudizio estetico.

AlphaGo

I programmatori di AlphaGo hanno in pratica costruito una macchina in grado di emulare il pensiero umano. Lo hanno fatto in più fasi. Prima di tutto dotandolo di una imponente rete neurale che fosse in grado di apprendere l’estetica del gioco umano. Attraverso un meccanismo di training, la rete neurale si è esercitata su un database di 30.000.000 di posizioni tratte da partite di professionisti. Un meccanismo che viene comunemente detto “pattern recognition”, alla fine del quale la rete era in grado di indovinare la mossa giocata dall’uomo nel 57% dei casi.

In una seconda fase la rete neurale si è “allenata” giocando contro se stessa. Fino a questo punto il gioco di AlphaGo era interamente basato sull’apprendimento, senza utilizzare alcun meccanismo di previsione delle mosse future.

In un'ultima fase, la rete neurale è stata integrata in un programma che utilizzava il metodo Montecarlo. Senza entrare troppo nei dettagli, il metodo Montecarlo consiste nel giocare, a partire da una determinata posizione, un numero enorme di partite in modo "quasi" casuale, e di valutare la suddetta posizione attraverso il rapporto vittorie/sconfitte che ne risulta.

Il metodo Montecarlo era già stato usato dai programmi di Go, dove aveva già prodotto risultati interessanti, ma è stata la combinazione con la rete neurale a risultare vincente. In un certo senso possiamo sintetizzare la cosa dicendo che AlphaGo usa un metodo Montecarlo “pilotato” dal suo giudizio estetico elaborato durante l’apprendimento.

Durante il suo match con Fan Hui, AlphaGo ha calcolato un numero di posizioni infinitamente inferiore a quanto fatto da Deep Blue nel suo match con Kasparov. Eppure sono passati quasi venti anni e i computer di oggi sono infinitamente più potenti. Ha potuto concedersi questo lusso perché è dotato di un meccanismo di selezione assai più raffinato. Anche Deep Blue era in grado di valutare una posizione, ma l’algoritmo di valutazione era stato costruito artificialmente ed era rigido perché codificato attraverso un algoritmo indotto. Al contrario AlphaGo ha imparato a valutare una posizione attraverso un processo di apprendimento assolutamente autonomo.

AlphaGo sfiderà a marzo il più grande giocatore vivente: Lee Sedol. Non è ancora chiaro cosa accadrà. C’è chi scommette che Lee Sedol sia ancora molto più forte. In fondo Fan Hui era “solo” un 2-dan mentre Lee Sedol è un 9-dan (nel professionismo si distinguono 9 categorie che vanno in ordine crescente di bravura dal 1-dan al 9-dan). Le partite inoltre sono state giocate su un tempo di 60 minuti, piuttosto veloce per un gioco che prevede in media 200 mosse. Ma comunque vada, anche se Lee Sedol dovesse vincere il match, oramai appare chiaro che l’informatica ha tagliato un altro traguardo.

Carlo Nitsch, Università degli studi di Napoli "Federico II"

6 Comments

  1. Delio Mugnolo

    01/02/2016 at 14:33

    Davvero molto interessante, ma qualcosa si deve essere perso nell'articolo, perché il nome "Fan Hui" compare solo verso la fine dell'articolo. Il computer ha giocato con questo/a Fan Hui e cos'è successo? Suppongo abbia vinto, ma quest'informazione non viene data.

  2. Carlo Nitsch

    01/02/2016 at 15:31

    In effetti l'introduzione (che inizialmente era stata inserita correttamemte) per qualche motivo è scomparsa. Al suo posto vedo solo una virgola!
    Andrebbe inserita altrimenti parte del testo risulta incomprensibile.
    Grazie per averlo notato

  3. Roberto Natalini

    01/02/2016 at 15:40

    Ripristinato, scusate... CIao. r

  4. Giuseppe Perelli

    03/02/2016 at 11:28

    Articolo molto interessante.
    Da quel che leggo, rispetto ai metodi usati per progettare motori scacchistici, qui c'è un'opera più complessa che coinvolge elementi di Machine Learning e Reti Neurali, i quali attribuiscono una sorta di "umanità" all'algoritmo che elabora la partita. Mi chiedo: se si progettasse un motore scacchistico adottando la stessa tecnica del team di AlphaGo?
    Attualmente, i migliori motori fanno già uso di database delle aperture e tablebase dei finali, per cui una sorta di machine learning è stata già applicata. Però (se non erro) è noto che programmi come Houdini e Rybka difettano nella valutazione strategica di una posizione. Quale sarebbe l'esito di uno scontro tra Houdini e un ipotetico AlphaChess? La risposta secondo me non è scontata.

    • Carlo Nitsch

      04/02/2016 at 10:35

      Caro Giuseppe,
      la tua è un'osservazione molto interessante. Credo che l'idea del team di Google sia stata proprio quella di mettere insieme una macchina in grado di apprendere allo stesso modo giochi anche molto diversi (diversamente da Deep Blue che era un computer fatto per giocare a scacchi).
      C'è però una differenza fondamentale tra scacchi e go che secondo me ha reso particolarmente fruttuoso nel go l'approccio utilizzato dal team di Google. Negli scacchi i pezzi sono pochi e si muovono nel tempo, nel go invece i pezzi sono tanti e immobili. Nel go colloco le pietre in un certo modo e non le tocco più. Talvolta un gruppo di pietre posizionate in un preciso modo nell'arco dell'intera partita sembra non svolgere alcun ruolo, e poi improvvisamente dopo parecchie decine di mosse acquistano importanza decisiva. L'aspetto "visivo" (saper riconoscere determinate formazioni) è quindi fondamentale. La strategia si basa molto su questo.

      Consentimi anche un aggiornamento. Leggendo alcuni commenti da parte dei top Go player, appare chiaro che AlphaGo sia in grado di emulare molto bene il gioco umano, i professionisti sono tutti molto colpiti dal risultato, ma sono anche convinti (a giudicare da alcuni errori "gravi") che non sia ancora in grado di battere i più forti giocatori al mondo. Inoltre, con un database basato su centinaia di anni di partite (per forza di cose più vecchie che nuove), agli occhi di un top player lo stile di gioco di AlphaGo appare datato. Nulla comunque che un dilettante come me possa apprezzare.
      Il punto fondamentale ora è capire se AlphaGo sia in grado di andare oltre lo stile dell'uomo.

      • Giuseppe Perelli

        04/02/2016 at 16:55

        Caro Carlo,
        grazie per la risposta!
        Parlo da appassionato (dilettantissimo!) di scacchi e la tua osservazione sul dinamismo dei pezzi è interessante. Non a caso tutti i manuali invitano a tener conto delle differenze tra una valutazione statica (conteggio dei pezzi) ed una dinamica (controllo delle case, esposizione del re, minacce generiche).
        Poi forse, da un punto di vista combinatorico, il finale scacchistico è più complesso di un finale del Go, proprio perché nel secondo si va "ad esaurimento case", mentre negli scacchi la scacchiera ha iniziato a svuotarsi e i pezzi si muovono più liberamente, senza che mossa dopo mossa il ventaglio delle possibilità decada esponenzialmente.
        Non so, sto solo buttando lì qualche commento ...

Leave a Reply

Your email address will not be published. Required fields are marked *

this site uses the awesome footnotes Plugin