Kakari

Descrizione del progetto

IL GIOCO DEL GO

Realizzare un’intelligenza artificiale per il gioco del Go (di seguito Go) ha rappresentato e rappresenta tutto'ora un’impresa estrema (se non disperata) nel campo della programmazione: il Go, infatti, è un gioco terribilmente complesso da prevedere mediante un approccio algoritmico deterministico "classico" (quali, ad esempio, quelli impiegati nelle intelligenze artificiali di scacchi), a causa fondamentalmente dell’elevato numero di permutazioni che sono realizzabili sulla scacchiera.

Il gioco si svolge, nella sua forma più completa, su una scacchiera 19x19. In ciascuna intersezione può essere posta una pedina di colore bianco o nero, di conseguenza il numero di permutazioni possibili per il gioco risulta l’impressionante numero di

19 19 1723 1.74 10N

Logicamente, non tutte queste permutazioni rappresentano effettivi schemi possibili di gioco; tale numero resta tuttavia ben oltre la capacità di calcolo di qualunque sistema computerizzato (non fatevi ingannare dal “ben oltre”; sarebbe forse meglio dire “molto molto molto oltre”…)! I giocatori di go professionisti amano affermare che “esistono più permutazioni nel gioco del go, che atomi nell’universo”, e probabilmente visti gli ordini di grandezza in gioco, hanno ragione.

Un'altra caratteristica unica del Go è l’importanza che le mosse iniziali hanno a lungo termine sullo svolgersi della partita: spesse volte una mossa particolarmente brillante si rivela in quanto tale anche quaranta o cinquanta mosse dopo. E' evidente che adottare l'approccio ad albero tipicamente impiegato nelle AI di scacchi è inefficace: esso prevede di considerare a partire dallo stato corrente tutte le possibili mosse, e valutare quale fra le configurazioni conduca con più probabilità alla vittoria (iterando il procedimento per n mosse a seguire si compila un albero di combinazioni di mosse). Nel Go, visto l’enorme numero di permutazioni possibile, è già particolarmente gravoso calcolare l’albero delle mosse per le otto mosse successive, figurarsi quaranta!

E' impensabile perciò costruire un’intelligenza artificiale, per quanto sofisticata, che abbia la pretesa di generare l’albero completo delle mosse possibili e valutare deterministicamente la bontà di ciascuna scelta. Storicamente sono stati tentati diversi approcci per attaccare questo problema, dalla codifica di un set di mosse “standard” (note come joseki, kakari, shimari…) in un database e diminuire notevolmente la complessità del problema. Questi approcci si sono finora rivelati infruttuosi, poiché incapaci di prevedere l’andamento a lungo termine di ciascuna mossa nella visione d’assieme complessiva del gioco.

Il progetto consiste nella realizzazione di un software di intelligenza artificiale per il gioco del Go. Tale software si avvale massicciamente di algoritmi basati su reti neurali artificiali (nello specifico percettroni di Rosenblatt) cercando di imparare progressivamente nel corso delle partite.

Ogni buon programmatore, quando sente parlare di “visione d’assieme” non può fare a meno di preoccuparsi; ciò di cui deficitano maggiormente i calcolatori è quella capacità tipica dei sistemi biologici nota come olismo, cioè la facoltà di cogliere il problema nella sua interezza valutando in contemporanea tutti i collegamenti che ciascuna scelta impone, pur disponendo solamente di un set parziale di parametri che caratterizzano la scelta da compiere.

Per risolvere (o almeno tentare di risolvere) il problema dell’AI di Go (che per i motivi accennati rappresenta un problema profondamente olistico) si rende necessaria una forma diversa di programmazione, decisamente più plastica di un algoritmo classico.

DESCRIZIONE DEL PROGETTO

Il progetto Kakari (dal nome delle sequenze d’attacco standard di inizio partita) si propone di affrontare il problema dell’IA di Go ricorrendo a reti neurali per la stima delle mosse migliori. Le reti vengono preparate (di seguito allenate) su un set di partite già giocate con un apposito algoritmo di learning atto a insegnare, a tutti gli effetti, il gioco alla rete. Una volta allenate, e cambiato il comportamento dell’applicazione mediante file di settings, è possibile interrogare la rete per ottenere i suggerimenti sulle mosse da eseguire.

APPROCCIO REALIZZATIVO

In questa sezione intendo spiegare quali sono le idee alla base del progetto, che hanno in seguito condizionato lo sviluppo del codice.

SCELTA DEL GOBAN

Pensare di implementare direttamente una IA che giochi in una scacchiera 19x19 è inefficace, perché il problema è inutilmente complicato. Molto più semplice è invece il gioco nella scacchiera 9x9, che è ampiamente riconosciuta come la scacchiera di Go più piccola in cui il gioco non sia completamente predeterminato (cioè che esista una esatta sequenza di mosse che il giocatore iniziale può svolgere per condurlo sicuramente alla vittoria).

Inoltre, scegliere un goban più piccolo ha il vantaggio che le partite sono mediamente molto più corte che nella scacchiera completa 19x19, rendendo il problema del learning di dimensioni molto più contenute, e permettendo di studiare i meccanismi più efficaci per il design dell’IA.

I DATI DI INPUT

A mia disposizione ho un database di partire nella scacchiera 9x9 scaricato da un server ufficiale di Go contenente oltre 200000 partite in formato .SGF. Considerando che mediamente ciascuna partita contiene una quarantina di mosse, la mole di dati in ingresso per effettuare il learning risulta decisamente convincente.

PREPARAZIONE DEI DATI IN INPUT

Poiché il Go è un gioco in cui la mossa migliore dipende unicamente dallo stato della scacchiera in quel momento (ancor più che negli scacchi, ad esempio), sembra evidente che in input alla rete debba essere presentato lo stato corrente del goban, e che in uscita la rete debba rispondere in qualche maniera fornendo la mossa da effettuare.

L’approccio scelto è stato il seguente: è stata compilata una matrice di dimensioni 9x9 il cui elemento assume i valori

La rete viceversa è stata allenata a rispondere con una matrice delle stesse dimensioni in output (quindi 9x9) riportando i valori secondo la seguente codifica

Si è reso necessario fare imparare alla rete a non giocare ove presenti altre pedine, altrimenti il numero di mosse invalide sarebbe stato decisamente alto.

Perché richiedere alla rete un’intera matrice 9x9 come output, e non solo le coordinate i, j della mossa migliore? Perché la rete, quando applicata ad un contesto reale, risponderà con una matrice i,j di valori intermedi a 1, 0, -2. La giocata migliore è rappresentata dal massimo assoluto di tale grafico, rapidamente calcolabile. Fin qui niente di nuovo. Se però la rete sbaglia? Se asserisce che la miglior mossa sia giocare malauguratamente al di sopra di una casella interdetta da un’altra pedina? Si rende necessario tralasciare il massimo assoluto ed estrarre il secondo massimo dal grafico e verificare che esso non rappresenti una mossa invalida.

Iterando questo procedimento è sempre possibile ottenere una mossa dall’output della rete, qualunque sia la sua risposta: tale accorgimento è necessario per ottenere un algoritmo di gioco stabile e convincente.

CONSIDERAZIONI STRUTTURALI DELL’APPLICAZIONE

Una prima considerazione da fare è la seguente. Le reti neurali sono avide di risorse di calcolo in modo difficilmente immaginabile. Si possono affrontare due strade molto diverse per risolvere il problema: aumentare la scalabilità del codice (e renderlo eseguibile su piattaforme multiprocessore) oppure aumentare l’ottimizzazione degli algoritmi.

Nella realizzazione delle librerie ho compiuto una serie di scelte apparentemente piuttosto forti che permettono in futuro sia di aumentare la scalabilità del codice, sia di aumentarne efficacemente l’ottimizzazione.

La libreria è progettata affinchè l’utilizzatore impieghi unicamente la classe cPerceptron, che tuttavia è una classe puramente virtuale, una façade se così si può dire per un altro tipo di percettrone, che può variare in base al contesto hardware (più processori, più ottimizzazione, presenza di una GPU potente …). Le implementazioni specializzate sono realizzate in sottoclassi di cPerceptron (fra cui spicca cCPUPerceptron) e possono essere istanziate unicamente ricorrendo al singleton globale cPerceptronFactory, che mette a disposizione un metodo Build con argomento una stringa, che istanzia dinamicamente un tipo di percettrone piuttosto che un altro.

Sebbene le specificità e le differenze dei percettroni siano profonde variando l’implementazione, una serie di “punti fissi” permangono, fra cui le routine Run, Learn, Evolve, Build che sono fondamentalmente standard per tutti i casi: è proprio questa uniformità che rende particolarmente efficace questa catena di eredità per implementazione.

In futuro progetto di estendere l’implementazione a più processori mediante la classe cMultiCPUPerceptron ed eventualmente al calcolo in scheda video attraverso CUDA o direttamente lavorando in DirectX e scrivendo uno shader in HLSL apposito per avere la compatibilità su schede video anche vecchie, e non solo su GPU nVidia GeForce di ultima generazioni CUDA-compatibili.

A fronte di tutte queste considerazioni di ottimizzazione e scalabilità, ho scelto in fase di disegno della classe cCPUPerceptron di vincolare la dimensione dei layer del percettrone ad una potenza di due, in modo che il problema sia facilmente divisibile in unità di calcolo indipendenti.

SCELTA DELLA SIGMOIDE

La prima cosa da fare quando si costruisce una rete neurale è scegliere la funzione sigmoide da impiegare negli algoritmi di learning. Solitamente la sigmoide che si impiega è la curva logistica

I problemi che ho riscontrato con questa sigmoide, tuttavia, sono molteplici. Il principale è che la sigmoide ha valori unicamente positivi, di conseguenza non si presta per imparare pattern in cui la distribuzione dei campioni negativi eguaglia quelli negativi. Inoltre, da considerazioni del tutto sperimentali (letteralmente, provando e valutando i tempi di convergenza con una sigmoide piuttosto che un’altra) ho deciso di utilizzare come sigmoide la funzione

Essa ha caratteristiche simili alla logistica vista prima: ha tutte le derivate continue, è integrabile su intervallo, ma ha codominio [-1, 1]. Ho osservato sperimentalmente che questa sigmoide dà risultati più convincenti qualora il pattern da imparare contenga molti numeri

negativi o sia fortemente variabile (ad esempio un pattern del tipo che ha infiniti

minimi per x piccolo).

DEFINIZIONE DELL'ALGORITMO DI LEARNING

Durante la realizzazione del progetto ho implementato e provato un’infinità di sistemi di learning diversi per cercare di capire quale potesse essere il più efficace per imparare un problema tanto complesso.

L'algoritmo che sopra tutti ha dato i risultati migliori è il seguente (è una versione migliorata degli algoritmi genetici)

Costruzione di due popolazioni eguali di percettroni (popolazione di partenza e di arrivo)

o Inizializzazione a caso dei pesi e delle soglie sulla base di un riferimento (la rete caricata da file) della popolazione di partenza

o Inizializzazione di tutte le variabili temporanee

Ciclo sul numero di generazioni

o Calcolo del chi-quadro di ciascun individuo della popolazione di partenza facendolo giocare un intero set di partite

o Ricerca del minimo e del massimo chi quadro fra tutti i percettroni della popolazione di partenza

o Normalizzazione fra 0 e 1 del fitness di ciascun percettrone sfruttando il valore massimo e minimo estratti prima

o Backup del percettrone con il massimo fitness per ragioni di convergenza

o Calcolo delle probabilità di sopravvivenza, accoppiamento e accoppiamento doppio di ciascun percettrone della popolazione di partenza

o Rescaling degli array di sopravvivenza e accoppiamento doppio per ricoprire tutta la popolazione di arrivo

o Accoppiamento dei percettroni salvando i figli sulla popolazione di arrivo

o Doppio accoppiamento dei percettroni, sempre scrivendo sulla popolazione di arrivo e sovrascrivendo i percettroni non sopravvisuti.

o Esecuzione di 10 step di backpropagation unicamente sui figli del doppio accoppiamento (che a rigore dovrebbero essere coloro che fittano meglio nell'ambiente) per aumentare (e di molto) la convergenza verso i minimi

o Mutazione casuale degli elementi appartenenti alla poplazione di arrivo

o Sovrascrittura del percettrone con il fitting minore con il percettrone con il fit maggiore estratto lo step precedente (per garantire una convergenza monotona non crescente verso il minimo)

o Scambio delle due popolazioni

Copia dei pesi e delle soglie dal miglior percettrone selezionato nel percettrone corrente

Calcolo dell'errore finale e ritorno del valore

TESTING DELL'ALGORITMO DI LEARNING

Gli algoritmi di learning, prima di essere impiegati nel problema corrente, sono stati testati a fondo sottoponendo a percettroni di tipo diverso problemi più semplici da imparare e di facile controllo.

LEARNING DI PERCETTRONI A SINGOLO INPUT ED OUTPUT

Come primo controllo dell'algoritmo di backpropagation sono state sottoposte una serie di funzioni ad un percettrone dotato di 8 layer interni ciascuno costituito da 16 neuroni (per semplificare la notazione, di seguito si adotterà la scrittura 16 8 con l'ovvia convenzione neuroni layern n ). Il training è effettuato fornendo alla rete punto per punto la

funzione in un intervallo delle x fissato (con campionamento fissato a 100 punti in tutto l'intervallo). I risultati ottenuti sono i seguenti (in rosso la funzione di riferimento, in blu la stima della rete dopo il learning una volta valutata.

Figura 1: Learning di una funzione caratteristica 1,3 dopo 8 sec di esecuzione e dopo 20 sec.

Figura 2: Learning di un dente di sega dopo 8 sec, 12 sec, 17 sec

Figura 3: Learning del seno di una rampa dopo 13 sec e 60 sec

Figura 4: Learning dell'esponenziale di una rampa dopo 49 sec e 150 sec

La rete si comporta in modo molto soddisfacente quando alle prese con un problema con, fondamentalmente, un solo minimo assoluto sul grafico multidimensionale di chi2: il learning delle funzioni è molto rapido e convincente. Ciò che appare chiaro è che la gran parte del learning è svolta nei primi 20 secondi di esecuzione; prolungando per molto tempo si ottengono correzioni minime, che non giustificano molto un investimento di risorse di calcolo. Questo giustifica la scelta di usare poche iterazioni di backpropagation per migliorare la stima degli algoritmi genetici (come asserito sopra).

Appare inoltre evidente che più le funzioni divengono complicate, più fatica compie la rete ad impararle: il caso dell'esponenziale della rampa è il più emblematico, in quanto dotato di brusche cadute e cuspidi. Alla rete sono occorsi quasi 50 secondi per convergere ad un chi2 complessivo inferiore a 0.1.

Che cosa accade se si mette alla prova la rete su una funzione veramente complicata, magari dotata di un infinito numero di massimi e minimi?

Figura 5: Learning di 1

sinx

dopo 30 sec

Sebbene la convergenza sui valori superiori a 1 sia piuttosto valida, chiaramente per valori piccoli di x la rete non riesce a imparare le infinite oscillazioni della funzione (complice il fatto che il campionamento a punti non è perfetto in quell'intervallo). Quello che si osserva è una buona approssimazione dei primi due massimi e minimi dopo 1, e poi un sostanziale appiattimento intorno allo 0 (una sorta di risposta media alle sollecitazioni).

L'esito di questo test è tutt'altro che malvagio, visto che la rete è stata in grado anche in situazioni di dubbio di trovare una soluzione di compromesso tutto sommato valida e che non esula dai termini del problema.

LEARNING DI PERCETTRONI A MOLTI INPUT

Riporto una rapida analisi del caso di percettroni a numero superiore di input (il caso da noi trattato per il go). Il training questa volta è eseguito sempre su funzioni elementari, ma con un set di dati in ingresso che contiene tutti i valori dell'asse delle ascisse campionati e un set di dati attesi contenente tutti i valori valutati dalla funzione voluta. Il percettrone scelto ha 100 input, 100 output e 8 livelli da 16 neuroni ciascuno. L'apprendimento ottenuto è il seguente

Figura 6: Learning della funzione caratteristica dopo 5 min

La convergenza in questo caso è pressocchè perfetta, con chi2 minimo di quasi 3 ordini di grandezza inferiore rispetto al caso precedente (per quantificare nell'ordine di 10-6). Tuttavia si paga il prezzo di un tempo di computazione sostanzialmente più alto, nell'ordine dei 5 minuti.

Non sono rappresentati altri casi poiché i risultati ottenuti con altre funzioni sono pressoché identici, con tempi leggermente variabili anche se di poco (in questo caso non conta la complessità della funzione in gioco, poiché la rete è sempre stimolata con gli stessi input! Ciò che varia è unicamente l'array dei valori attesi).

STRUTTURA DEL SOFTWARE

Il software è costituito da un main core del programma e da due librerie separate a loro volta articolate in sottoparti. Ciascuna libreria è logicamente indipendente ed è stata separata rispetto al programma originale per specificità del codice e possibilità di riutilizzo. Riporto un elenco delle componenti del software con una descrizione rapida del loro funzionamento. A ciascuna componente corrisponde quasi perfettamente un file di codice del progetto.

Libreria di oggetti globali

o Libreria di matematica veloce

FastFunction: Cached-functions per evitare le valutazioni di funzioni matematiche lente, valutate solo all’avvio del programma e memorizzate in un buffer

FastMatrix: Matrici a dimensione generica

FastVector: Vettori a dimensione generica (con estensioni di calcolo parallelo SSE)

o Libreria multithreading: basata sulla libreria pthreads permette di creare facilmente nuovi threads (sia con l’approccio a oggetti, sia con l’approccio sequenziale) e fornisce i più semplici modi di gestione della memoria (spinlock, mutex).

o Libreria CUDA: in fase di sviluppo, permette di interfacciarsi con i dispositivi CUDA compatibili presenti nel sistema.

o Libreria OpenGL: in fase di sviluppo, basata sull'engine grafico ScialloEngine3, permette di interfacciarsi con i dispositivi grafici (GPU) presenti nel sistema ed eseguire calcolo in shader a basso livello.

o Improved String: stringa di caratteri con funzionalità avanzate di ricerca

o Settings: gestione automatica dei settings dai file

o Timer: misuratore del tempo di precisione per benchmarking

Libreria neural networks

o Percettroni

PerceptronFactory: la fabbrica dei percettroni in tempo reale (rispetta il design pattern della Factory)

CPUPerceptron: attualmente l’unico funzionante, è un percettrone con algoritmi spiegati e molto semplici, con qualche rapida ottimizzazione

FastCPUPerceptron: in fase di sviluppo, dovrebbe essere una versione di CPUPerceptron modificata e fortemente ottimizzata

MultiCPUPerceptron: in fase di sviluppo, versione di CPUPerceptron ottimizzata per il calcolo su macchine a multiprocessore

o Strategie di learning

Chi-Squared: strategia di learning basata su backpropagation e minimizzazione di chi quadrato

Validation: strategia di learning basata su backpropagation con il controllo del set di validazione

Kakari: l’intelligenza artificiale di go

o BatchLoader: componente che gestisce il caricamento da disco delle partite di go per effettuare il learning; il componente è eseguito su thread separato per non rallentare eccessivamente

o GoGame: oggetto contenente una partita di Go al completo dalla prima all’ultima mossa, e calcola automaticamente lo stato del Goban ad una certa mossa

o GTPInterface: tentativo (non ancora riuscito) di interfacciare l’applicazione con il Go Text Protocol e permettere il gioco direttamente da client standard (i.e. PandaGO)

o GoNetwork: è un’interfaccia al di sopra di un percettrone e si occupa delle strategie di learning per il Go, fra cui la preparazione degli input per la rete e l’interpretazione degli output

o AI: il cuore dell’applicazione, è la componente che contiene il codice dell’applicazione vera e propria e si occupa dell’integrazione di tutte le componenti

o Test: banco di prova degli algoritmi usato per non sporcare il codice di AI.

Prendiamo ora in esame con più dettaglio le componenti di particolare interesse per il progetto

GONETWORK

La classe cGoNetwork costituisce probabilmente il perno centrale del progetto. Essa implementa tre metodi di fondamentale importanza: LearnGameSet, CalculateErrors e SuggestMove. Come suggeriscono i nomi, i tre metodi si occupano rispettivamente di

1. LearnGameSet: imparare un set di partite di go fra un intervallo di mosse selezionato, e controllare i risultati mediante un set di validazione

2. CalculateError: Calcolare gli errori mediamente commessi dalla rete una volta chiamata a giocare le mosse di un set intero di partite

3. SuggestMove: Fissato lo stato di un goban, suggerire la miglior mossa successiva

Prenderemo in esame successivamente i dettagli dell’algoritmo impiegato per effettuare il learning, per preparare gli input e interpretare gli output della rete. Questi metodi, infatti, non si occupano direttamente di implementare le strategie di learning, ma si appoggiano su componenti esterni intercambiabili (secondo la specifica del design pattern noto come Strategy). Essi realizzano quell’importante interfaccia necessaria per il passaggio da un elenco di mosse (la partita di go) a un pattern di input-output che la rete possa fisicamente imparare secondo i suoi canoni.

CPUPERCEPTRON

La classe cCPUPerceptron è l’implementazione più semplice di un percettrone di Rosenblatt-Minsky-Papert, con qualche piccola accortezza all’ottimizzazione, tuttavia non tale da rendere il codice di difficile lettura. I metodi di principale importanza sono i seguenti

1. Run: metodo di esecuzione della rete. Fissato un array di input esegue la propagazione in avanti (feed-forward propagation) e calcola gli output sulla base dei coefficienti della rete. È il metodo che si impiega per fare eseguire la rete una volta allenata

2. Learn: metodo che esegue il learning con algoritmo backpropagation di minimizzazione dell’errore. Fissati un set di input e output attesi, allena la rete ad associare ad un dato input il suo relativo output. Poiché ciascun elemento del set è un array, ciascun set è di fatto una matrice (per essere precisi, un array di array).

3. Evolve: qualora il backpropagation non sia efficace (condizioni di learning con molti minimi locali) può essere preferibile sfruttare un sistema puramente statistico. Questo metodo implementa l’evoluzione con algoritmi genetici, costruendo una popolazione di percettroni ed evolvendoli per un numero fissato di generazioni. Il percettrone allenato sarà alla fine delle generazioni quello più selezionato dall’ambiente.

4. LoadFromFile – SaveToFile: routine di caricamento e salvataggio da file veloci (binarie)

5. Build: metodo che si occupa di costruire il percettrone sulla base dei dettagli di configurazione passati a parametro, che specificano le caratteristiche fisiche del percettrone (numero di layer, dimensione del layer) e i parametri degli algoritmi di allenamento.

La classe CPUPerceptron è fortemente commentata per rendere il codice il più leggibile possibile, e gli algoritmi sono implementati in maniera il più simile possibile agli algoritmi teorici.

RISULTATI

Si tratta ora di effettuare la prova del software realizzato secondo lo schema illustrato e discutere se l'approccio con reti neurali ha portato a qualche beneficio.

Per i seguenti test costruiamo un percettrone 16 4 . Il learning viene svolto mediante algoritmi genetici (popolazione 5000 individui, tasso di mutazione 0.03) su set consecutivi di 16 partite. La rete viene allenata mossa per mossa, a partire dalla mossa 10 fino alla mossa 30.

TEST A SINGOLA MOSSA

Riportiamo in seguito una serie di test di semplici mosse. Facendo riferimento alle immagini seguenti, sottoponiamo alla rete gli schemi nella colonna di sinistra, chiedendo di suggerire la mossa per il giocatore nero. Nella seconda colonna sono riportate le mosse della rete non allenata; nella terza sono riportate le mosse della rete allenata.

Figura 7: Risultato di un learning di 10 minuti. Le colonne rappresentano 1. Il pattern di input 2. L'output della rete non allenata 3. L'output della rete allenata

Il primo problema è un classico problema di Go noto come atari; la mossa corretta (senza dubbio) sarebbe completare l'occhio in G5 e mangiare la pedina bianca in F5. E' evidente la casualità della mossa della rete non allenata, mentre la rete allenata 10 minuti risponde in modo decisamente meno casuale, sebbene la risposta non sia quella che ci fossimo aspettati (è molto difficile asserire, nel Go, che una mossa è definitivamente sbagliata, poichè dipende molto dalla strategia che il giocatore vuole intraprendere!).

Decisamente sbagliata è, invece, la risposta al problema seguente. La mossa corretta è mangiare in E3 in modo da non venire a sua volta mangiata in D4 alla mossa successiva. Questo problema è leggermente più complicato del precedente, e la rete non si comporta in modo soddisfacente.

Il terzo test è una prova della rete in un contesto in cui non è stata allenata. Ricordiamo che l'allenamento è stato svolto dalla mossa 10 alla mossa 30, mentre qui le si chiede di giocare la terza mossa della partita. E' evidente che la rete non gioca una mossa strategicamente corretta (le risposte tipiche sono E6 o F6).

Questi test suggeriscono di aumentare drasticamente il tempo di learning, nella speranza che un numero maggiore di partite osservate possa aiutare la rete a separare il problema. Se il l'aumentato tempo di learning non dovesse portare benefici, la probabile causa si dovrebbe ricercare nelle dimensioni della rete, troppo esigue per imparare efficacemente.

Figura 8: Risultato di un learning di 90 minuti. Le colonne rappresentano 1. Il pattern di input 2. L'output della rete non allenata 3. L'output della rete allenata 10 min 4. L'output della rete allenata 90

min

Quello che si può dire subito osservando i risultati del learning è che la rete ha imparato. La risposta al primo test (sebbene non sia esattamente quella che ci si aspetta) è valida e probabilmente porta alla vittoria, perché la giocata in D4 stabilisce un vantaggio deciso su una parte piuttosto ampia di territorio.

Il secondo test è stato superato in pieno: la rete ha risposto esattamente nel punto in cui ci si aspettava, mangiando le pedine bianche e stabilendo un vantaggio preponderante.

Il terzo test continua a non essere superato, e mette in mostra le grandi difficoltà delle reti a giocare in contesti in cui non sono state allenate. Inoltre, appena si esce da questi test molto semplici e si iniziano a sottoporre problemi reali, la rete fallisce nella maggioranza dei casi.

Si è dimostrato che il tempo di learning influisce in modo sostanziale sull'apprendimento della rete. Non si è ancora indagato quanto influiscano le dimensioni della rete. Ricostruiamo il percettrone come 128 4 (si è scelto un numero di neuroni maggiore del numero di input) e rieseguiamo il learning (questa volta il tempo impiegato è decisamente superiore, e la popolazione è stata ridotta a 1000 unità per limitare la memoria impiegata dal processo).

Figura 9: Risultato di un learning di 6 ore. Le colonne rappresentano 1. Il pattern di input 2. L'output della rete non allenata 3. L'output della rete allenata 90 min 4. L'output della rete allenata 6 ore

Non c'è molto da aggiungere a quanto detto prima soltanto guardando questi test; l'unica (decisa) differenza rispetto al caso precedente è la risposta al primo test, più efficace per la rete allenata 6 ore (probabilmente, è la risposta che avrebbero dato molti giocatori esperti di Go). Nel secondo test la rete - fortunatamente - continua a rispondere correttamente. Nessun sostanziale miglioramento nel terzo test, cosa che tuttavia non ci si aspettava.

CONTESTI REALI

Quale miglior banco di prova di una intelligenza artificiale che provare a giocarci contro? Abbiamo sottoposto alla rete più allenata (128 4 allenata sei ore), una serie di problemi reali di fronte a cui ci si può effettivamente trovare durante una partita di medio livello di Go in una scacchiera 9x9. Di seguito riporto una serie di pattern proposti affiancati dalla sua risposta e dalla discussione sull'efficacia di tale mossa.

Figura 10: Prima prova in un contesto reale contro giocatore umano

La mossa suggerita dalla rete non è particolarmente efficace, pur non essendo sbagliata. Qualunque giocatore giocando con il nero avrebbe probabilmente giocato in E7, sebbene esistano moltissime sfumature al gioco. Sicuramente però il proseguimento di partita risulta più complicato

Figura 11: Seconda prova in contesto reale contro giocatore umano

Questa volta alla rete è stato chiesto di giocare con il bianco. La risposta questa volta non è per nulla convincente, poichè la rete non si è difesa dall'atari in E4 perdendo una porzione sostanziale di fronte e regalando la partita all'avversario.

Figura 12: Terza prova in contesto reale contro giocatore umano

Fra le mosse viste finora, questa tutto sommato risulta la meno peggio, visto che la rete ha preferito consolidare il suo territorio piuttosto che attaccare. Sicuramente però giocare in C4 sarebbe decisamente meglio.

Figura 13: Quarta prova in contesto reale contro GnuGo

Finalmente una risposta corretta da parte della rete, che si accorge correttamente della debolezza in E8 e provvede a proteggersi. Nella terza immagine è riportata infatti la successiva mossa che avrebbe operato GnuGo se la mossa ipoteticamente fosse stata H2.

Figura 14: Quinta prova in contesto reale contro GnuGo

In questa situazione, la rete ignora completamente il rischio di atari in C4 e decide di giocare in G2. Se da una parte è corretto ignorare l'atari (la pedina in C4 è disgraziatamente persa in partenza), è abbastanza discutibile la mossa in G2, visto che un tentativo di attacco sarebbe comunque decisamente difficile. Probabilmente avrei protetto in 4E.

CONCLUSIONI

Tirando le fila, è indiscutibile che la rete abbia imparato dalle partite, e anche più di quello che ci si aspettava, visto che talvolta sorprende lo stesso osservatore con delle mosse senza dubbio corrette.

Quello che tuttavia le manca completamente è la capacità di sviluppare una strategia e portarla avanti nella partita: si dimostra valida a rispondere a situazioni molto precise e determinate, ma inefficace a portare avanti la partita nel suo complesso.

I test che sono qui illustrati infatti sono indicativi; in situazioni di non minaccia immediata (come gli atari) spesso la rete compie mosse del tutto irragionevoli, dettate fondamentalmente da una indecisione nella scelta del luogo dove giocare.

Il problema quindi è che la rete gioca male. Dove può risiedere il problema?

Si possono dare molte risposte a questa domanda. La prima causa è la dimensione del percettrone coinvolto, probabilmente esiguo per separare un problema complesso come il Go. Si rende probabilmente necessario impiegare un percettrone di dimensioni superiori. Dopo una serie di test con percettroni molto grandi (anche 128 128) ciò che appare evidente è una

difficoltà sostanziale a convergere ad un minimo di chi2 soddisfacente in un tempo umanamente compatibile. Una soluzione che si è pensata a questo problema è ingrandire per gradi il percettrone: partire inizialmente da un percettrone allenato abbastanza piccolo, ed estenderlo progressivamente senza modificare l'output ottenuto dopo l'ingrandimento. Questo approccio non è ancora stato tentato.

Un'altro possibile motivo della scarsa abilità della rete è il processo di learning che si è scelto. Mettendosi nei panni della rete per un momento, si supponga di voler imparare a giocare a Go senza averlo mai visto, e che venga proposto di impararlo anzichè leggendo un libro o sotto l'assistenza di un giocatore esperto, unicamente guardando una gran quantità di partite e cercando di desumere le regole dal gioco. Il 99% degli esseri umani del pianeta non sarebbe in grado di imparare decentemente in questo modo, se non dopo un tempo davvero lunghissimo di analisi delle partite, estrapolazione dei pattern di gioco ricorrenti e delle regole! Inoltre, poichè le partite non sono in alcun modo classificate, non si sa quali siano state effettivamente giocate da giocatori esperti e quali da perfetti ignoranti, per cui si rischia di prendere per buone delle mosse effettivamente molto discutibili (problema di cui molto probabilmente il corrente algoritmo di learning soffre moltissimo) .

In conclusione del ragionamento, se dovessi reimpostare il progetto in vista di una nuova implementazione, tenterei di costruire delle piccole "retine" ciascuna dedicata ad imparare una regola o un processo singolo del gioco (rispondere a un certo joseki, imparare come attaccare un territorio, imparare ad risolvere situazioni di vita o morte ...), un po' come farei se stessi cercando di insegnare il Go ad una persona, guidandola progressivamente attraverso le regole del gioco e poi unificando il tutto in un unico processo di gioco.

BIBLIOGRAFIA

C. M. Bishop, Neural Networks for Pattern Recognition, Oxford University Press (1995).

J. Rojo, Slides delle lezioni, Corso di Metodi Computazionali della Fisica 2, Università degli Studi di Milano (a.a. 2009-2010). Avail. at http://wwwteor.mi.infn.it/~rojo/teaching- neuralnet.html

A. Alexandrescu, Modern C++ Design: Generic Programming and Design Patterns Applied, Addison-Wesley (2001)

E. Gamma, R. Helm, R. Johnson, J. Vlissides, Design Patterns. Elements of Reusable Object- Oriented Software, Addison-Wesley (1994)

Intel, IA-32 Intel Architecture Software Developer's Manual. Volume 3: System Programming Guide, Intel Corporation (2005)

Intel, IA-32 Intel Architecture Software Developer's Manual. Optimization Manual, Intel Corporation (2005)

nVidia, CUDA 3.0 SDK Code Programming Samples, nVidia Corporation (2010). Avail. at http://developer.nvidia.com/object/cuda_3_0_downloads.html