![](https://crypto4nerd.com/wp-content/uploads/2024/03/01Fn5ZwFgD_QSpmQI.jpeg)
Hai mai sentito parlare del gioco GO?
Bene,il GO è un gioco da tavola nato in Cina circa 2500 anni fa ed è considerato uno dei giochi più difficili che ci siano, nonostante le regole siano piuttosto semplici.
Il GO si gioca su una griglia, detta “goban”, dove i 2 giocatori schierano le proprie pedine di colore diverso, bianche e nere, con l’obiettivo finale di conquistare il maggior spazio possibile senza essere catturati dall’avversario.
La complessità di questo gioco risiede nell’immenso numero di possibili combinazioni che si possono generare sulla tavola. Giusto per darvi un’idea, il numero di configurazioni supera il numero di atomi nell’universo: Parliamo di circa 2,08×10¹⁷⁰ diverse posizioni possibili. È incredibile!
Probabilmente avrai sentito parlare di DeepMind.
DeepMind può essere considerato il laboratorio in ambito AI di Google. Un’azienda britannica acquisita da Google nel 2014 per promuovere la ricerca sull’intelligenza artificiale. Tutt’oggi è uno dei principali protagonisti del settore.
Ma cosa c’entrano queste due cose tra loro? Nel 2016 DeepMind ha raggiunto un traguardo apparentemente impossibile: ha sviluppato un software in grado di battere i migliori giocatori di GO al mondo… AlphaGO.
AlphaGO è diventato un nome famoso nel settore AI dopo aver sconfitto in una serie di match ufficiali il campione europeo Fan Hui. Eccolo qui!
La vittoria contro il campione Fan Hui ha rappresentato un momento storico per il mondo AI. È stata la prima vittoria di un computer contro un giocatore professionista di GO.
In questo articolo, ci piacerebbe descrivervi brevemente la ricerca pubblicata da DeepMind nel paper “Mastering the game of Go with deep neural networks and tree search”
Sebbene il mondo dell’IA, del Deep Learning e del Machine Learning abbia fatto passi avanti incredibili dalla pubblicazione di questo paper nel 2016, AlphaGO rimane una tappa importante nel percorso che ci ha portato fino ai risultati che vediamo oggi.
Vogliamo quindi, con questo articolo ed altri, ripercorrere alcune delle ricerche che probabilmente sono state più importanti.
Molte delle ricerche di cui parleremo le puoi trovare qui: RicercaMente.
Puoi contribuire anche tu al progetto!
Introduzione ad AlphaGO e il Monte Carlo Tree Search
Da dove partire? Iniziamo dando un maggiore contesto riguardo al problema affrontato.
Giochi come GO e scacchi sono giochi con informazioni perfette (games of perfect information), ovvero giochi sequenziali in cui ogni giocatore è a conoscenza di tutte le informazioni presenti sulla scacchiera.
Per questo tipo di giochi è possibile associare, ad ogni posizione s nella board, una funzione di valore ottimale v(s). Questa funzione restituisce il risultato finale del gioco in base allo stato s, considerando che entrambi i giocatori agiscano in modo “perfetto”.
Per esplorare tutte le le mosse e gli stati possibili che si possono avere durante la partita viene utilizzato un algoritmo chiamato Monte Carlo Tree Search (MCTS).
MCTS
È un’algoritmo di ricerca per problemi di decisione, dove l’obiettivo è trovare la sequenza ottimale di azioni che massimizzano una certa funzione premio.Vi diamo giusto qualche spunto.
L’algoritmo effettua una simulazione (rollout), partendo da un nodo (il nostro stato s), espande l’albero ed esplora ulteriori possibili mosse e stati, sempre basandosi su una certa policy (per il momento definiamola una “strategia”).
Raggiunto lo stato di terminazione, il risultato di questo rollout viene utilizzato per approssimare il valore atteso dello stato di partenza.
Con più rollout, l’approssimazione sarà sempre più accurata.
Il problema nasce dalla grandezza di questo albero di ricerca.
L’obiettivo è quindi quello di esplorare solo un sottoinsieme del Search Tree, attraverso due modi:
- Riducendo la visità in profondità: ovvero utilizzando una funzion v*(s) che approssimi la funzione originale v(s)
- Riducendo l’ampiezza: scegliendo la mossa successiva in base ad una distribuzione di probabilità p(a|s) (la cosidetta“policy” ) e non esplorandole tutte.
I migliori motori di gioco per GO, precedenti ad AlphaGO, erano basati sulla MCTS. Tuttavia non avevano ottenuto risultati eccezionali.
Entra qui in gioco AlphaGO: I ricercatori di DeepMind decisero di unire la MCTS con la potenza delle reti neurali. Arriva il Deep Learning!
Crearono un’ sistema ibrido grazie all’utilizzo di due reti neurali, una per valutare il possibile outcome data una certa posizione nella scacchiera (value network) e l’altra per ottenere una distribuzione di probabilità p(a|s) da cui scegliere la miglior mossa (policy network).
Entriamo ora più nel dettaglio!
Supervised Learning of Policy Network
La prima fase dell’addestramento di AlphaGO prevede l’utilizzo del Supervised Learning per la Policy Network.
Questa rete neurale convoluzionale viene addestrata utilizzando un dataset contenente mosse e posizioni giocate da giocatori esperti (per questo si parla di contesto supervised).
La rete riceve come input una rappresentazione della scacchiera e la mossa giocata (la coppia di input è (s,a), dove s rappresenta lo stato e a la mossa giocata). Produce come output una distribuzione di probabilità considerando tutte le mosse legali in quella posizione, cercando di “predire” la mossa giocata.
In questa fase, viene anche addestrata una Rollout Policy. Ottenuta come una funzione lineare dell’input, diversa quindi dalla rete convoluzionale.
Reinforcement Learning of Policy Network
La seconda fase dell’addestramento di AlphaGO prevede l’utilizzo del Reinforcement Learning per la Policy Network.
Per chi non lo sapesse, il Reinforcement Learning è una tecnica di apprendimento utilizzata nel ML e DL.
Nel RL un agente impara attraverso delle simulazioni. L’agente sceglie quali azioni compiere con l’obiettivo di massimizzare il proprio premio. Più l’agente effettua simulazioni e più imparerà a fare le scelte giuste che lo porteranno alla vittoria!
Partendo dalla rete neurale addestrata nella prima fase, viene addestrata una seconda rete con la stessa struttura, ma utilizzando il Reinforcement Learning. Vengono giocate delle partite (simulazioni) con l’obiettivo della rete di “vincere”, ovvero massimizzare la reward function.
Reinforcement Learning of Value Network
Fino a questo momento ci siamo concentrati sulla policy, ovvero sulla capacità di scegliere la migliore mossa possibile data una certa posizione (stato). Ora ci concentriamo sulla “position evaluation”, ovvero sulla stima di una value function che predica il risultato della partita, sapendo che i due giocatori giocano secondo una stessa policy (nel nostro caso, la policy ottenuta dal Reinforcement Learning). Viene addestrata la value network.
La rete neurale avrà come input delle posizioni e, attraverso la regressione, darà come output un singolo valore: il risultato della partita.
Qui abbiamo un’immagine che riassume le diverse fasi di addestramento di AlphaGO
Ricerca
Ora che abbiamo tutti i pezzi, è necessario unirli.
L’innovazione di AlphaGO è quella di combinare le reti policy e value addestrate con la MCTS. Ecco i punti chiave:
- Ogni arco (s,a) dell’albero conserva un “action value” Q(s,a), il conteggio delle visite in quell’arco N(s,a) e la probabilità P(s,a).
- L’albero viene attraversato durante la simulazione e ad ogni step t, viene scelta l’azione a che massimizza l’action value più un certo bonus
- Raggiunto un nodo foglia (ovverso senza ulteriori nodi figli), Il nodo viene processato: prima dalla policy network che fornisce le probabilità P(s,a). In seguito, dalla value network che darà il valore v(s) e infine dalla rollout policy, ottenendo z. Gli ultimi due valori vengono combinati per ottenere il valore finale della posizione nel nodo considerato
- Alla fine della simulazione, vengono aggiornate le statistiche di ogni arco attraversato in base ai valori calcolati nello step precedente.
Una volta che la ricerca è completata, si ottiene un albero di ricerca e il nostro algoritmo sceglierà, in ogni posizione, l’arco visitato maggiormente per poter proseguire nel gioco.
Conclusioni
La forza di AlphaGo sta nell’avere combinato la MCTS con il Deep Learning. Questo approccio innovativo ha permesso ad AlphaGo di imparare e sviluppare nuove strategie di gioco, mai viste prima, che gli hanno permesso di superare le performance dei migliori motori di gioco esistenti all’epoca.
Anche se per alcuni potrebbe sembrare solo un programma in grado di giocare ad un gioco, rappresenta molto di più. È un esempio concreto di come l’AI possa essere utilizzata per risolvere problemi complessi e raggiungere obiettivi che sembravano impossibili.
Per chi si fosse appassionato a questa storia, consigliamo di visitare il canale youtube di DeepMind. In particolare, vedete questa breve video sulla nascita del progetto … molto ispirazionale secondo noi!
E per i più nerd, il documentario completo 🤓
P.S Speriamo che questo articolo vi sia piaciuto! Molti aspetti non sono stati trattati in modo formale. Voleva essere soltanto un modo per raccontarvi qualcosa in più su questa ricerca.
Se avete dubbi o curiosità andate a guardare la nostra pagina LinkedIn RicercaMente