Università degli Studi di Padova
Dipartimento di Matematica
Corso di Laurea in Informatica
Miglioramento del modulo di intelligenza artificiale del gioco "Geister"
Tesi di laurea
Relatore
Prof. Fabio Aiolli
Laureando Stefano Battistella
Anno Accademico 2013-2014
Stefano Battistella: Miglioramento del modulo di intelligenza artificiale del gioco
"Geister",Tesi di laurea, © Ottobre 2014.
“È meglio confessare i propri errori: ci si ritrova più forti.”
— Mahatma Gandhi
Dedicato alla mia famiglia
Sommario
Il presente documento descrive il lavoro svolto durante il periodo di stage, della durata di 320 ore, dal laureando Battistella Stefano presso l’Università degli Studi di Padova.
Gli obbiettivi da raggiungere erano molteplici.
In primo luogo era richiesto di reingegnerizzare il modulo di intelligenza artificiale in modo tale da renderlo facilmente estendibile. In secondo luogo era richiesto di migliorare gli algoritmi di intelligenza artificiale per la determinazione della mossa da eseguire. Terzo ed ultimo obbiettivo era di apportare dei miglioramenti alle tecniche di profile learning per determinare in modo più preciso la tipologia delle pedine avversarie.
“An eye for an eye only ends up making the whole world blind.”
— Mahatma Gandhi
Ringraziamenti
Innanzitutto, vorrei esprimere la mia gratitudine al Prof. Fabio Aiolli, relatore della mia tesi, per l’aiuto e il sostegno fornitomi durante la stesura del lavoro.
Desidero ringraziare con affetto la mia famiglia che non mi ha mai posto degli ostacoli nell’inseguire la mia vita, facendomi comunque capire che la realtà può essere molto diversa dalle aspettative.
In particolar modo vorrei ringraziarie il mio migliore amico Maurizio la cui bontà non sarò mai in grado di ripagare e il cui tempo passato assieme ha sempre un valore inestimabile
Padova, Ottobre 2014 Stefano Battistella
Indice
1 Introduzione 1
1.1 Obbiettivi dello stage . . . 1
1.2 Scopo del documento . . . 2
1.3 Organizzazione del testo . . . 2
1.4 Nota sul codice prodotto . . . 3
2 Il gioco 5 2.1 L’intelligenza artificiale nei giochi . . . 6
2.2 I tipi di apprendimento . . . 8
3 Tecnologie impiegate 11 3.1 Java . . . 11
3.2 IntelliJ IDEA . . . 11
3.3 Neuroph framework . . . 13
3.4 LIBSVM . . . 13
3.5 Git . . . 14
4 Progettazione 15 4.1 Diagrammi delle classi . . . 16
4.1.1 Package euristiche . . . 16
4.1.2 Package operations . . . 17
4.1.3 Package strategie . . . 18
4.1.4 Package IA . . . 18
4.1.5 Package features . . . 19
4.1.6 Package ranker . . . 21
4.1.7 Package learner . . . 22
4.1.8 Package model . . . 23
4.2 Diagrammi di sequenza . . . 25
4.2.1 Richiesta di una mossa . . . 25
4.2.2 Determinazione della mossa . . . 25
4.2.3 Aggiornamento del profilo . . . 26
5 Sviluppo dell’intelligenza artificiale del gioco 27 5.1 Stadio iniziale . . . 27
5.1.1 Buoni Mangiati (BM_AVV) . . . 28
5.1.2 Cattivi Mangiati (CM_AVV) . . . 28
5.1.3 Buoni in Gioco (BG_AI) . . . 29
5.1.4 Cattivi in Gioco (CG_AI) . . . 29
5.1.5 Attacco ai Buoni (AB_AVV) . . . 30
5.1.6 Buoni sotto Minaccia (BMI_AVV) . . . 30
5.1.7 Distanza buoni Uscita (DU_IA) . . . 30
5.1.8 Distanza buoni Uscita avversario (DU_AVV) . . . 31
5.1.9 Confronto contro l’umano . . . 32
5.1.10 Confronto tra euristiche . . . 32
INDICE
5.2 Implementazione della learning heuristic . . . 38
5.3 Incremento della profondità di esplorazione . . . 48
5.4 Transposition tables . . . 51
5.5 Analisi robustezza algoritmi di IA . . . 53
5.6 Miglioramento del profile learning . . . 58
5.7 Impiego delle SVM . . . 60
5.8 Costruzione di un profilo globale . . . 63
6 Considerazioni finali 65 6.1 Consuntivo . . . 65
6.2 Risultati ottenuti . . . 66
6.3 Sviluppi futuri . . . 67
Glossario 69
Bibliografia 71
x
Elenco delle figure
2.1 La scacchiera di “Geister” . . . 5
2.2 I fantasmi di “Geister” . . . 6
2.3 Una parte dell’albero del gioco del tris . . . 7
3.1 Screenshot dell’IDE IntelliJ IDEA v13.1 . . . 12
3.2 Esempio di classificazione nel sito di LIBSVM . . . 14
4.1 Il package euristiche . . . 16
4.2 Il package operations . . . 17
4.3 Il package strategie . . . 18
4.4 Il package IA . . . 19
4.5 Le interazioni del package IA . . . 20
4.6 Il package features . . . 20
4.7 Il package ranker . . . 21
4.8 Il package learner . . . 23
4.9 Il package model . . . 23
4.10 La richiesta della mossa . . . 25
4.11 La determinazione della mossa . . . 26
4.12 L’aggiornamento del profilo . . . 26
5.1 Le vittorie e sconfitte raccolte dal confronto tra euristiche . . . 36
5.2 Le tipologie di vittorie raccolte dal confronto tra euristiche . . . 37
5.3 La prima rete di neuroni progettata . . . 39
5.4 La rete di neuroni progettata . . . 43
5.5 L’andamento della percentuale di vittorie sul totale di partite disputate dalla learning heuristic durante l’allenamento . . . 46
5.6 Il game-tree delle valutazioni eseguite . . . 47
5.7 Percentuale di vittorie contro un umano impiegando la learning heuristic con profondità di esplorazione pari a 4 . . . 50
5.8 Percentuale di vittorie contro un umano impiegando la learning heuristic con profondità di esplorazione pari a 8 . . . 50
5.9 Tipologia di vittorie contro un umano impiegando la learning heuristic con profondità di esplorazione pari a 8 . . . 51
5.10 Stato raggiunto da due stati diversi . . . 51
5.11 Rapporto di vittorie sul totale in relazione al numero di pezzi valutati erroneamente . . . 56
5.12 Fenomeno del positive destructive feedback nel gioco degli scacchi . . . 57
5.13 Il primo metodo di classificazione dei pezzi implementato . . . 59
5.14 Esempio di classificazione errata dei pezzi . . . 60
5.15 Funzionamento delle SVM . . . 61
5.16 Classificazioni errate dei pezzi raccolte durante precedenti stage . . . . 63
6.1 Ore a preventivo e a consuntivo . . . 66
ELENCO DELLE TABELLE
Elenco delle tabelle
5.1 Sigle identificative delle euristiche . . . 28
5.2 Valutazioni dell’euristica buoni mangiati . . . 28
5.3 Valutazioni dell’euristica cattivi mangiati . . . 29
5.4 Valutazioni dell’euristica buoni in gioco . . . 29
5.5 Valutazioni dell’euristica buoni in gioco . . . 30
5.6 Valutazioni dell’euristica distanza buoni uscita . . . 31
5.7 Valutazioni dell’euristica distanza buoni uscita avversario . . . 31
5.8 Partite giocate tra le euristiche e l’umano . . . 32
5.9 Partite giocate per confrontare le euristiche - media esiti . . . 34
5.10 Partite giocate per confrontare le euristiche - n. vittorie . . . 35
5.11 Partite giocate per confrontare le euristiche . . . 35
5.12 Tipologia di vittorie per euristica . . . 36
5.13 Pezzi catturati e persi durante il confronto delle euristiche . . . 38
5.14 Esiti dei test per l’allenamento della learning heuristic - primo tentativo 40 5.15 Esiti dei test per l’allenamento della learning heuristic contro l’umano - primo tentativo . . . 41
5.16 Esiti dei test per l’allenamento della learning heuristic - secondo tentativo 41 5.17 Esiti dei test per l’allenamento della learning heuristic contro l’umano - secondo tentativo . . . 42
5.18 Esiti dei test per l’allenamento della learning heuristic - secondo design 45 5.19 Esiti dei test per l’allenamento della learning heuristic conto l’umano - secondo design . . . 46
5.20 Esiti dei test per l’allenamento della learning heuristic conto l’umano - secondo design e profondità 8 . . . 49
5.21 Pezzi catturati e persi durante le partite contro l’umano . . . 50
5.22 Tempi di individuazione della mossa senza le transposition table . . . 52
5.23 Tempi di individuazione della mossa con le transposition table . . . . 53
5.24 Esiti dei test con un numero di pezzi errati pari a 2 . . . 54
5.25 Esiti dei test con un numero di pezzi errati pari a 4 . . . 55
5.26 Esiti dei test con un numero di pezzi errati pari a 6 . . . 55
5.27 Esiti dei test con un numero di pezzi errati pari a 8 . . . 56
6.1 Ore a preventivo e a consuntivo . . . 65
xii
Capitolo 1
Introduzione
“La disumanità del computer sta nel fatto che, una volta programmato e messo in funzione, si comporta in maniera perfettamente onesta.”
— Isaac Asimov
L’intelligenza artificiale (IA) è lo studio e la progettazione di agenti intelligenti1, ovvero di sistemi che percepiscono l’ambiente circostante, decidendo e agendo per massimizzare le proprie possibilità di successo. Gli obbiettivi primari di questo campo di ricerca trattano gli aspetti più comuni dell’intelligenza umana quali il ragionamento, la conoscenza, la pianificazione e l’apprendimento puntando a sviluppare un’intelligenza artificiale che sia paragonabile, o superiore, a quella di un essere umano, altrimenti detta artificial general intelligence|g|. Il raggiungimento di un tale punto nella ricerca porterebbe ad una rivoluzione tecnologica e sociale liberando l’uomo da qualsiasi sforzo ma mettendolo anche a confronto con le teorie evoluzionistiche. Svariati racconti di fantascienza trattano l’argomento dal punto di vista etico e filosofico domandandosi se una macchina, in grado di riprodurre il comportamento umano, sia effettivamente dotata di pensiero e le possibili conseguenze. Questo influisce molto sull’opinione comune in quanto l’argomento viene trattato in modo troppo semplicistico e non considera minimamente i problemi da affrontare. Sembra sempre che nei laboratori di ricerca si stiano sviluppando macchine in grado di spazzare via l’essere umano per far posto ad una nuova specie dominante ma non si pensa che è l’essere umano stesso a decidere se intraprendere o meno questa strada. Un ambito così problematico dal punto di vista sociale ed evolutivo si scontrerà con l’opinione pubblica molto prima che il problema si presenti realmente ponendo gli scienziati a valutare bene se un eventuale robot, con in mano “L’origine delle specie” di Charles Darwin, in grado di capirne i contenuti, possa decidere che la sua superiorità nella velocità di pensiero debba sopraffare l’umanità. È l’uomo stesso a decidere quindi se l’intelligenza artificiale sarà una piaga o una rivoluzione ma, al momento, lo studio è lungi da tale traguardo.
Non è semplice sviluppare una artificial general intelligence e non si sa nemmeno se effettivamente sia possibile. Il fondo del problema risiede nella scarsa conoscenza di come noi stessi funzioniamo e di come realmente il cervello apprende e solamente quando le scienze cognitive saranno sufficientemente avanzate potremmo stabilire se sia umanamente possibile realizzare una macchina che sia simile a noi per capacità.
1.1 Obbiettivi dello stage
L’obbiettivo dello stage è quello di mettere lo studente davanti a problemi che non hanno una soluzione standard, ma che richiedono di ricercare nuove tecniche e algorit- mi per risolvere le problematiche poste. L’ambito riguarda i campi dell’intelligenza
1Peter Norvi Stuart J. Russell. Artificial Intelligence A Modern Approach. 3rd. New Jersey:
Pearson Education, 2009. Cap. 3, 4, 5, 21, p. 2.
1.2. SCOPO DEL DOCUMENTO
artificiale e di machine learning, che pongono inoltre un’ulteriore difficoltà in quanto tali materie di studi non sono mai state affrontate durante il normale percorso di studi.
Lo stage prevede una prima parte dove lo studente deve effettuare una reingegneriz- zazione del modulo di intelligenza artificiale in modo tale da renderlo estendibile per poter aggiungere, durante il corso dello stage e in futuro, nuovi algoritmi e tecniche in modo semplice e veloce.
La seconda parte dello stage prevede il miglioramento degli algoritmi di intelligenza artificiale applicati in precedenza durante altri stage. Si prevede inizialmente di delinea- re quali siano i problemi da affrontare e di conseguenza individuare le migliori soluzioni da applicare. Per ogni modifica apportata, verranno eseguiti più test possibili per riscontrare il margine di miglioramento e i punti deboli della nuova implementazione.
Verranno disputate partite sia contro altri agenti intelligenti che esseri umani.
Come la seconda parte dello stage, anche la terza prevede il miglioramento degli algoritmi di machine learning secondo le stesse modalità. Lo scopo è quindi di aumentare le capacità del computer di prevedere correttamente la tipologia delle pedine avversarie, riducendo di conseguenza l’errore commesso nel mangiare i pezzi avversari e diminuendo le probabilità di essere ingannati da un comportamento non banale di un pezzo avversario allo scopo di classificarne erroneamente la tipologia.
1.2 Scopo del documento
Il presente documento ha lo scopo di presentare gli esiti delle attività sostenute dallo studente durante il periodo di stage sostenuto presso l’Università degli Studi di Padova
• Nel capitolo 2 verranno presentate le meccaniche e regole del gioco di cui è necessario migliorare il modulo di intelligenza artificiale. Verranno in seguito esposti gli algoritmi di intelligenza artificiale classicamente impiegati in giochi simili.
• Nel capitolo 3 verranno discusse le tecnologie impiegate per lo sviluppo del progetto.
• Nel capitolo 4 verrà presentata la nuova architettura del modulo di intelligenza artificiale. In tale capitolo verranno argomentate tutte le modifiche apportate per sapere cosa è cambiato dalle implementazioni precedenti.
• Nel capitolo 5 saranno esposti tutti gli stati di sviluppo dell’intelligenza artificiale nel gioco, dove verrà eseguita un’analisi dei problemi individuati e si esporranno le soluzioni individuate, implementate e testate per risolverli.
• Nel capitolo 6 verranno presentate le considerazioni finali comprensive del consuntivo delle ore, del soddisfacimento degli obbiettivi e dei possibili sviluppi futuri.
1.3 Organizzazione del testo
Per tutte le parole e le sequenze di parole in italico seguite dalla sequenza di caratteri
“|g|” a pedice, è presente un piccolo approfondimento nel Glossario.
2
1.4. NOTA SUL CODICE PRODOTTO
1.4 Nota sul codice prodotto
Il codice sviluppato è stato pubblicato sulla piattaforma GitHub®sotto licenza GNU GPL v3. L’indirizzo web del codice sorgente lo si può reperire alla sezione 3.5.
Capitolo 2
Il gioco
“Geister” è un gioco da tavolo per due giocatori ideato da Alex Randolph la cui prima produzione risale al 1982. La scacchiera 6x6 è la rappresentazione di un castello infestato e i giocatori hanno otto pedine ciascuno di cui quattro sono considerate buone e identificate da un pallino blu, le restati sono invece cattive e marchiate con un pallino rosso. All’inizio si devono posizionare i pezzi, uno per turno, e il gioco inizia quando entrambi i giocatori hanno posizionato tutte le pedine nelle otto caselle centrali delle due righe più vicine alla propria postazione. Sebbene si sappia nel complesso la tipologia delle pedine, l’informazione di quale pezzo è buono o cattivo non viene fornita finché il pezzo non viene mangiato. Per mangiare un pezzo è necessario semplicemente posizionare uno dei propri fantasmi nella stessa casella di un fantasma avversario. Le mosse considerate legali sono lo spostarsi in una casella adiacente, non in diagonale, libera o al più occupata da un fantasma avversario. Esistono più condizioni di vittoria di seguito elencate:
• mangiare tutte le 4 pedine buone dell’avversario;
• farsi catturare tutti i 4 pezzi cattivi da parte dell’avversario;
• far uscire un proprio fantasma buono dal castello.
Per quanto riguarda i primi due punti non è necessario aggiungere altro. L’ultima condizione di vittoria si verifica quando uno dei propri fantasmi buoni si trova in una delle due caselle, indicate con una freccia come si può notare in figura 2.1, dalla parte
figura 2.1: La scacchiera di “Geister ”
2.1. L’INTELLIGENZA ARTIFICIALE NEI GIOCHI
figura 2.2: I fantasmi di “Geister ”
dell’avversario e con la mossa successiva la pedina fugge dalla scacchiera.
Il gioco viene classificato tra i zero-sum game|g|. Giochi simili sono gli scacchi, la dama o il tris ma si differenzia in quanto non sono disponibili tutte le informazioni sulla tipologia di pedine. Come si può notare in figura 2.2, i fantasmi hanno l’indicazione del tipo solamente nella parte visibile al loro proprietario e non all’avversario. In tal modo, non viene richiesta solamente l’elaborazione di una strategia per arrivare alla vittoria ma è necessario studiare il comportamento dell’avversario per apprendere quale pezzo è buono e quale è cattivo. “Geister” è un gioco ad informazione incompleta rendendolo più simile a “Kriegspiel”, una variante degli scacchi in cui i pezzi possono muoversi ma sono completamente invisibili all’avversario. Questa categoria permette ai giocatori di basarsi sul bluff per complicare l’apprendimento della tipologia dei pezzi mediante movimenti non troppo banali.
2.1 L’intelligenza artificiale nei giochi
Le prime applicazioni di intelligenza artificiale applicata ai videogiochi furono degli avversari del gioco da tavolo archetipo del mondo occidentale, gli scacchi. Negli ultimi 40 anni si è visto un aumento drastico nelle capacità dei computer in tale ambito.
Deep Blue dell’IBM è conosciuto per aver sconfitto il campione e maestro di scacchi Garry Kasparov nel 1997, ma lo sviluppo non si è fermato. Non solo si sono migliorate le architetture dedicate di tali elaboratori, ma anche il progresso degli algoritmi e le tecniche per la ricerca delle strategie migliori hanno avuto un notevole impatto. I successori di Deep Blue, Rybka e Hydra hanno i più grandi Elo|g| mai registrati nella storia degli scacchi e gli incontri più recenti suggeriscono che i migliori computer hanno surclassato tutti i contendenti umani1.
I concetti che stanno alla base degli algoritmi impiegati si basano su quanto già scoperto dalla teoria dei giochi e dello studio degli automi a stati finiti. Infatti, un board-game lo si può vedere come un insieme di stati Q e ogni possibile posizione valida delle pedine è uno stato q ∈ Q. L’insieme di mosse M considerate legali sono le transazioni δ(q, m) → p che portano dallo stato q agli stati p ∈ Q raggiungibili mediante le transazioni. Lo stato iniziale q0∈ Qè individuato dalla posizione iniziale delle pedine (in certi giochi i pezzi hanno una determinata disposizione iniziale come negli scacchi, oppure si inizia con una scacchiera vuota), mentre l’insieme degli stati finali F è formato da tutte le combinazioni raggiungibili mediante mosse legali che dichiarano la vittoria di uno dei giocatori o la patta. Lo stato iniziale, le transazioni e gli stati finali possono essere visti come l’albero del gioco, dove i nodi sono gli stati e gli archi sono le transazioni. Se si attribuisce un valore ai vari stati mediante una funzione
1Peter Norvi Stuart J. Russell. Artificial Intelligence A Modern Approach. 3rd. New Jersey:
Pearson Education, 2009. Cap. 3, 4, 5, 21, p. 186.
6
2.1. L’INTELLIGENZA ARTIFICIALE NEI GIOCHI
figura 2.3: Una parte dell’albero del gioco del tris. Partendo dai nodi finali, viene assegnato +1 per la vittoria, -1 per la sconfitta e 0 per il pareggio. Si procede quindi a propagare il valore negli stati meno profondi dell’albero, livello per livello. Se nello stato che devo valutare è il turno di X, allora tra tutti i possibili stati scelgo quello con valore maggiore, altrimenti minore nel caso in cui debba muovere O.
Se durante una partita ci si ritrovasse nel nodo più in alto, X non sceglierebbe le posizioni più a sinistra perché nel caso peggiore O avrebbe la vittoria. In conclusione, è meglio scegliere la casella a destra poiché, se O gioca all’ottimo, si ha il pareggio.
di valutazione f(q) con q ∈ Q detta Utility e si considera che non tutti gli stati hanno lo stesso valore per i giocatori, il primo giocatore dovrebbe effettuare la mossa che gli procura il maggior vantaggio quindi q0∈ {q ∈ δ(q0, m)|f (q) = maxp∈δ(q0,m)f (p)}. Tuttavia, l’obbiettivo dell’avversario è quello di mettere l’opponente nella situazione più svantaggiosa quindi q00 ∈ {q ∈ δ(q0, m)|f (q) = minp∈δ(q0,m)f (p)}. Applicando questo ragionamento ricorsivamente si deduce che ogni mossa non dipende dalle mosse che sono state effettuate, ma da quelle che verranno scelte considerando sempre che i giocatori hanno obbiettivi opposti. La prima mossa deve mettere il giocatore nella posizione più vantaggiosa tra tutte le possibili posizioni in cui l’avversario lo farebbe ritrovare q0 ∈ {q ∈ δ(q0, m)|f (q) = maxp∈δ(q0,m)minp0∈δ(p,m)f (p0)}. L’albero gene- rato da questa esplorazione ha profondità 2 ma l’ottimo si raggiunge solamente con l’esplorazione dell’intero albero degli stati. Tale algoritmo viene chiamato MiniMax in quanto la scelta delle mosse è un’alternanza tra scegliere lo stato con il valore massimo o minimo.
L’algoritmo preso in considerazione soffre di un difetto con il quale gli attuali calco- latori devono scontrarsi. Il branching factor|g| dell’albero dipende dal numero di mosse definite legali. Nel gioco “Tris”, si hanno 9 possibili mosse iniziali. Successivamente ne sono accettate 8 e così via finché non rimane da posizionare l’ultima croce. Ciò significa che il numero di stati possibili è pari a 9! = 362.8802. Tuttavia, il tris è un gioco estremamente semplice ma il numero di possibili stati è già considerevolmente alto. Gli scacchi hanno un fattore di branching pari a 10 e una partita può concludersi in media dopo 40 mosse. Considerando che il costo computazionale dell’algoritmo MiniMax è pari a O(bm)allora, per quanto riguarda gli scacchi, possono essere generati fino a 1040 stati, impossibili da valutare tutti con i computer attuali. Di conseguenza, si necessita di individuare delle tecniche per evitare di valutare l’intera gamma di stati. Una tecnica è l’alpha-beta pruning che permette di ridurre il valore dell’e-
2Il numero è un upper-bound in quanto molti stati si ripetono e se dopo 5 mosse uno dei giocatori fa tris allora non esistono più mosse legali
2.2. I TIPI DI APPRENDIMENTO
sponente m nella formula. Tale tecnica si basa sull’eliminazione dei rami che non possono sicuramente influire sulla scelta della mossa. Si può considerare, ad esempio, che il primo giocatore possa scegliere di muovere tra tre mosse che portano a tre stati con valore 3, 2, 6 (tali sono scelti tra quelli con valore minore durante il turno dell’avversario). La mossa ottima è quindi quella che porta allo stato con valore 6.
Tuttavia, durante l’esplorazione per la seconda mossa, si è già a conoscenza che il valore dello stato relativo alla prima mossa viene stimato pari a 3. Di conseguenza, se il giocatore avversario può effettuare una mossa che porta ad uno stato con valore peggiore di 3 (in questo caso 2), allora è inutile proseguire con l’esplorazione di quel ramo in quanto il massimo tra 3 e un valore al più uguale a 2 è 3. In tal modo si è evitato di proseguire con un’esplorazione che sicuramente non modificherà la soluzione finale. Di seguito viene esemplificato il caso trattato:
MiniMax(root) = max(min(3, 4, 7), min(2, x, y), min(9, 6, 8))
= max(3, min(2, x, y), 6)
= max(3, z, 6)where z = min(2, x, y) ≤ 2
= 6
Si può quindi considerare che se la mossa che permette di eseguire il taglio è in una posizione random, allora la complessità dell’algoritmo MiniMax scende a O(b3m/4). Tuttavia, anche se la complessità algoritmica è inferiore, non è ancora sufficiente per fornire una risposta in tempo reale. Di conseguenza è necessario sacrificare l’ottimo per l’efficienza, sfruttando tecniche che permettono di interrompere la ricerca ad una determinata profondità di esplorazione. Si possono quindi impiegare delle euristiche|g|
che forniscono una valutazione degli stati che si trovano al livello più profondo, senza necessariamente esplorare l’albero in tutta la sua profondità. Ciò solleva numerosi problemi in quanto si necessita di determinare la profondità giusta in cui interrompere l’esplorazione, come progettare l’euristica e testare se il comportamento previsto corrisponde con quello reale.
2.2 I tipi di apprendimento
La necessità di valutare la tipologia delle pedine non può essere soddisfatta dalla stessa intelligenza artificiale per determinare una strategia. Bisogna quindi adottare un approccio diverso, sfruttando le tecniche offerte dal campo dell’apprendimento auto- matico per acquisire delle informazioni mediante l’accumulazione di dati e osservazioni.
La categorizzazione, l’individuazione di correlazioni tra dati o la generalizzazione sono problemi a cui l’apprendimento automatico fornisce un approccio per risolverli. La trasformazione di concetti astratti in dati può risultare molto complessa in quanto il linguaggio umano non è basato sulla matematica come quello dei computer. Affermare che la buccia di un frutto è liscia oppure rugosa, saper scegliere tra andare a lavoro in macchina o con i mezzi pubblici o capire il perché di un fenomeno sono problemi estremamente complessi in quanto si rifanno a concetti astratti o coinvolgono un numero troppo elevato di variabili. Ciò nonostante, se si riesce a dare un valore oggettivo anche a delle parti di un fenomeno, si possono utilizzare delle tecniche per apprendere da tali dati, lasciando al computer scoprire l’eventuale correlazione tra essi. Esistono tre categorie di apprendimento:
• supervisionato: è un tipo di apprendimento dove i dati di allenamento consi- stono in un insieme di esempi, dove ogni esempio è una coppia consistente di un oggetto in input (tipicamente un vettore) e un desiderato valore in output.
Un algoritmo di apprendimento supervisionato analizza i dati di allenamento e produce una funzione che associ l’input all’output e che può essere usata per mappare nuovi esempi. Questo particolare tipo di apprendimento richiede di
8
2.2. I TIPI DI APPRENDIMENTO generalizzare dai dati di allenamento per permettere di classificare correttamente nuove istanze che non sono state fornite.
• non supervisionato: lo scopo di questo apprendimento è di classificare ed individuare una struttura nascosta da dati che non sono già categorizzati. Non è possibile quindi fornire una stima dell’errore per valutare la bontà della potenziale soluzione.
• con rinforzo: tale apprendimento si ispira ai concetti di comportamento e adattamento, determinando come scegliere le azioni in un ambiente con lo scopo di massimizzare un determinato risultato. Tuttavia, non vengono fornite delle coppie di input/output e non viene indicata la presenza di azioni sub-ottimali, ma si preferisce l’utilizzo di algoritmi online per individuare un bilanciamento tra esplorazione dell’ambiente e lo sfruttamento della memoria accumulata mediante l’esperienza.
Capitolo 3
Tecnologie impiegate
In questo capitolo saranno descritte tutte le tecnologie e gli strumenti di ci si è reso necessario l’utilizzo durante lo stage. Il software impiegava già numerose tecnologie per permettere di essere eseguito su di un’architettura client-server, ma gli algoritmi di intelligenza artificiale erano stati sviluppati nuovamente da zero. L’impiego di tecniche più sofisticate ha richiesto l’utilizzo di librerie per velocizzare lo sviluppo del progetto.
3.1 Java
Java è un linguaggio di programmazione concorrente, class-based e object-oriented.
È stato specificatamente progettato per avere il minimo numero di dipendenze di implementazioni possibili in modo tale per cui il codice che viene eseguito su una piattaforma non necessita di essere ricompilato e avviato su un’altra. Le applicazioni in Java sono tipicamente compilate in bytecode|g| che può essere eseguito su di una qualsiasi JVM|g| indipendentemente dall’architettura del computer. Java fu origina- riamente sviluppato da James Gosling presso la Sun Microsystems e rilasciato nel 1995 come componente centrale della piattaforma Java della Sun Microsystems. Il linguaggio trae molta della sua sintassi dal C e C++, ma ha meno funzionalità di baso livello rispetto a tali linguaggi.
Il codice già presente era scritto in Java, si è stati costretti quindi a continuare con questo linguaggio. Tuttavia, tale scelta influisce direttamente sulle potenzialità dell’intelligenza artificiale. L’utilizzo di tecniche più sofisticate che implicano quindi un maggior costo computazionale impattano su quanto tempo è necessario all’intelligenza artificiale per determinare la mossa. Così come le tecniche, anche l’adozione di un linguaggio, come Java, può aumentare il tempo di esecuzione richiesto a causa di come sono processate le istruzioni o anche delle ottimizzazioni che vengono apportate dal compilatore stesso. Probabilmente un linguaggio che garantisce prestazioni più elevate potrebbe rendere più profonda l’esplorazione del game-tree, con conseguente aumento nella precisione di valutazione delle mosse.
Non potendo adottare un linguaggio diverso si è proceduto ad individuare gli strumenti che fossero adatti a svolgere il lavoro pianificato. Conseguentemente le librerie impiegate sono state scelte tra quelle che fornivano una versione in linguaggio Java.
3.2 IntelliJ IDEA
IntelliJ IDEA è un IDE progettato appositamente per lo sviluppo di applicazioni Java realizzato da JetBrains. È disponibile sia la versione community edition che la
3.2. INTELLIJ IDEA
commercial edition ed è rilasciato sotto licenza Apache 2. Il software è reperibile al seguente indirizzohttp://www.jetbrains.com/idea/
La scelta di IntelliJ IDEA v13.1 rispetto ad altri presenti in commercio (ad esempio Eclipse) è dovuta alle numerose funzionalità offerte durante la stesura del codice, per effettuare il refactoring e l’analisi statica del software. Tale si è rivelato essere fondamentale per la prima parte del progetto, ossia durante la reingegnerizzazione del codice in quanto ha permesso di individuare tutte le istruzioni che non sarebbero state mai raggiunte (altrimenti dette unreachable code|g|) e altre che venivano eseguite ma il cui risultato non sarebbe stato più utilizzato (ossia dead code|g|), rinominare tutte le classi, la cui denominazione non era rappresentativa del funzionamento interno, in ogni istruzione dove venissero utilizzate. Sono stati risolti, grazie ad esso, anche numerosi problemi relativi a codice obsoleto o nell’attuale versione di compilazione (è stato scelto Java SE 7) ed è stato migliorato lo stile del codice adottando convenzioni comuni (ad esempio scrivere un ciclo con for piuttosto che con while se il funzionamento è
identico).
Grazie a tale strumento la stesura del codice è stata agevolata notevolmente. La funzionalità di completamento del codice permette allo sviluppatore di avere dei suggerimenti in tempo reale di quali istruzioni possono concludere la parte di comando già scritta. Come si può notare in figura 3.1 viene suggerito quale metodo si sta scrivendo e viene inoltre fornita tutta la lista dei vari tipi di parametri che vengono accettati da tale metodo. Ciò permette di individuare immediatamente se un metodo che dovrebbe essere presente in una classe è ancora da realizzare. In tal caso l’IDE si presta a realizzare un metodo fittizio nella classe corretta, marchiandolo con TODO per poter essere poi velocemente reperibile nella lista dei TODO dove sono presenti tutti quei punti dove il codice deve ancora essere scritto. Grazie ai suggerimento forniti è stato inoltre possibile ridurre la complessità ciclomatica del codice per aumentarne la testabilità.
figura 3.1: Screenshot dell’IDE IntelliJ IDEA v13.1
12
3.3. NEUROPH FRAMEWORK
3.3 Neuroph framework
Neuroph è un framework per lo sviluppo di reti neurali in un’ottica object-oriented scritto in Java. Può essere impiegato per creare e allenare reti di neuroni in pro- grammi sviluppati in Java. Neuroph fornisce una libreria di classi così come un tool dotato di interfaccia grafica detto easyNeurons per creare e allenare reti di neuroni. Tale framework open source è ospitato presso SourceForge al seguente indirizzo http://neuroph.sourceforge.net/ed dalla versione 2.7 è rilasciato sot- to Apache License. Le versioni precedenti erano rilasciate sotto LGPL. La ver- sione adottata per il progetto è la 2.8 e la si può ritrovare al seguente indirizzo http://neuroph.sourceforge.net/download.html
L’utilizzo di tale framework si è rivelato essere essenziale per poter implementare la learning heuristic1. La realizzazione delle classi necessarie per lo sviluppo di una rete neurale e relativo allenamento avrebbe richiesto troppo tempo e necessitava di test per determinare se il funzionamento corrispondeva con quello previsto.
La scelta di tale framework è dovuta a due fattori. Il primo è il numero di critiche positive reperibili in internet che sono state scritte in merito a tale framework e che hanno fatto emergere i punti di forza rispetto ad altre soluzioni. Il secondo fattore, che è stato cruciale, è la presenza di una documentazione chiara e approfondita sia di come è la struttura interna del framework (ossia di tutte le classi presenti) e di come impiegarla in un’applicazione. Ciò ha permesso in poco tempo di apprendere quali dovessero essere le classi da utilizzare e come eseguire l’allenamento della rete neurale.
3.4 LIBSVM
LIBSVM è una libreria open source per algoritmi di machine learning, sviluppata presso la National Taiwan University e scritta in C++. LIBSVM implementa l’algo- ritmo SMO per le kernelized support vector machines (SVMs), supportando quindi la classificazione e la regressione. Il codice per l’apprendimento delle SVM è spesso riusato in altri toolkit open source per gli algoritmi di machine learning. Esistono inoltre vari adattamenti per altri linguaggi di programmazione quali Java, Matlab e R.
La librerira è software libero rislasciata sotto la 3-clause BSD license. La libreria è reperibile al seguente indirizzohttp://www.csie.ntu.edu.tw/~cjlin/libsvm/ed è stata utilizzata la versione 3.18
L’utilizzo di tale libreria è stato importante per sfruttare la potenzialità delle SVM nel progetto 2. La realizzazione di tutte le classi necessarie per implementare gli algoritmi delle SVM avrebbe richiesto troppo tempo che non era disponibile. Inoltre era necessario rendere le classi estendibili in modo tale da poter modificare velocemente il particolare tipo di algoritmo e di conseguenza l’utilizzo di codice già realizzato era essenziale.
L’adozione di questa libreria rispetto ad altre è dovuta alle numerose critiche positive rivolte ad essa. Il reperimento di una documentazione chiara che indicasse esplicitamente come includere LIBSVM nel progetto è stato più complicato in quanto è presente molta documentazione su come utilizzarla mediante linea di comando ma come includerla in un progetto. Di seguito viene presentato un esempio di categorizzazione realizzato impiegando la libreria. Il software lo si può ritrovare al seguente sito web http://www.csie.ntu.edu.tw/~cjlin/libsvm/index.html?js=1#svm-toy-js.
1L’implementazione di tale euristica la si può ritrovare in 5.2
2Nella sezione 5.6 viene spiegato come sono state impiegate nel progetto
3.5. GIT
figura 3.2: Esempio di classificazione nel sito di LIBSVM
3.5 Git
Git è un sistema di controllo versione distribuito e di gestione del codice sorgente con un’enfasi alla velocità, all’integrità dei dati e il supporto ad un flusso di lavoro distribuito e non lineare. Git è stato inizialmente disegnato e sviluppato da Linus Torvalds per lo sviluppo del kernel Linux nel 2005, e da allora è diventato il sistema di controllo versione maggiormente adottato per lo sviluppo di software. Come la maggior parte di sistemi di controllo versione distribuiti, e non come i sistemi client-server, ogni working directory di Git è un repository a tutti gli effetti con una storia completa e una piena funzionalità di tracciamento di versione, indipendente dall’accesso in rete o dal server centrale. Git è un software libero distribuito sotto i termini della GNU General Public License version 2.
Lo sviluppo del progetto ha utilizzato tale strumento per poter mantenere in contemporanea più branch dello stesso software. Infatti, era necessario innanzitutto mantenere la copia originale del codice fornito all’inizio dello stage, per determinare se eventuali errori erano già presenti oppure sono stati inseriti successivamente. Dopodiché era necessario poter effettuare diverse modifiche in contemporanea agli algoritmi di intelligenza artificiale per provare varie soluzioni ed eventualmente combinare varie versioni degli algoritmi scartando quelle che non funzionano. Perciò era necessario poter avere una separazione del codice per provare in parallelo varie versioni senza che si sovrapponessero dovendo poi scorporare le parti che costituivano la versione finale.
Sono stati quindi realizzati più branch per ogni implementazione diversa che doveva essere poi testata separatamente. Il codice sorgente del progetto può essere reperito al seguente indirizzohttps://github.com/Bishop92/Geister. Inoltre, l’utilizzo di un IDE quale IntelliJ IDEA che fornisce le interfacce necessarie per inviare tutte le modifiche effettuate al server e anche al branch corretto, senza dover utilizzare uno strumento a parte per inviare i cambiamenti apportati.
14
Capitolo 4
Progettazione
La progettazione del software non ha richiesto la realizzazione dell’intera architettura in quanto questa era già disponibile. Tuttavia, il modulo di intelligenza artificiale non soddisfaceva vari principi quali la modularità o l’estendibilità. Infatti, non era prevista alcuna gerarchia che permettesse di aggiungere agevolmente nuove euristiche, così come per gli algoritmi di apprendimento della tipologia dei pezzi e per gli algoritmi di scelta della mossa da effettuare.
La struttura complessiva del modulo è costituita da tre componenti fondamentali:
• Strategia: è la parte che determina come viene scelta la mossa da eseguire tra tutte quelle considerate legali per un determinato tavolo. Data la complessità nella determinazione della mossa, una strategia può utilizzare delle euristiche per valutare un tavolo sulla semplice disposizione dei pezzi. Non esistono molti algoritmi diversi per scegliere quale pezzo muovere e come in quanto normalmente viene utilizzato l’algoritmo MiniMax. Tuttavia, può variare considerevolmente la strategia di esplorazione dell’albero del gioco e per determinare quale algoritmo risulta essere il più efficacie ed efficiente è necessario dover cambiare velocemente la strategia adottata per vederne i risultati.
• Ranker: si occupa di determinare se il pezzo che sta valutando è cattivo oppure buono. Il ranker si basa sui profili registrati dei giocatori per predire, in base al comportamento che questi hanno adottato durante gli incontri precedenti, se l’atteggiamento della pedina corrisponde ad un particolare pattern che permetta di classificarla. Gli algoritmi possono inoltre gestire, o meno, i bluff dell’avversario, ossia adottare comportamenti diversi e non banali per non far capire l’effettivo tipo dei pezzi. Ciò comporta che questa componente deve gestire un numero vario di ranker e che permetta di cambiarli agevolmente per poter effettuare vari test.
• Learner: il suo scopo è di stilare un profilo per il giocatore al termine della partita. Il learner è strettamente associato al ranker in quanto ogni ranker avrà il proprio modo di valutare il profilo e questo dipende da come il learner lo ha memorizzato. Si sfrutta il log della partita per ottenere le feature e determinare quindi il profilo. Anche in questo caso è necessario dover aggiungere velocemente varie tecniche per l’individuazione del profilo.
Nel seguito vengono proposte le varie modifiche che sono state apportate, package per package.
4.1. DIAGRAMMI DELLE CLASSI
4.1 Diagrammi delle classi
4.1.1 Package euristiche
Questo package, non presente nella precedente versione del software, contiene tutte le classi necessarie alla gestione delle varie euristiche.
figura 4.1: Il package euristiche
In figura 4.1 sono presenti le varie classe contenute nel package. Ogni euristica, per poter essere utilizzata, deve implementare l’interfaccia Euristica in quanto non è necessario che la classe, che effettivamente utilizza l’euristica, ne conosca il tipo. Per ottenere l’euristica desiderata è necessario richiederla alla classe EuristicheFactory che fornirà l’oggetto relativo. Il funzionamento complessivo del package permette di mantenere un’unica istanza di ogni algoritmo che implementa l’euristica in quanto ogni oggetto è effettivamente indipendente dal tavolo che si richiede di valutare.
Classe astratta Euristica
Tale classe astratta fornisce un contratto a tutte le classi che implementano gli algoritmi per la valutazione delle euristiche. Viene esposto il metodo valuta(Tavolo, byte) che richiede il tavolo da valutare e il giocatore a cui spetta la mossa. Viene quindi ritornato il valore della valutazione.
16
4.1. DIAGRAMMI DELLE CLASSI Classe astratta LearningHeuristic
La necessità di sviluppare euristiche che fossero in grado di apprendere da altre euristiche a fornire una valutazione del tavolo più precisa è stata soddisfatta me- diante tale classe. Infatti, un’euristica che apprende deve poter essere allenata indicando quali tavoli valutare e successivamente se la valutazione eseguita corri- spondeva alla situazione del tavolo. Vengono di conseguenza aggiunti i metodi addValutazioneAlTrainingSet(String, byte, Tavolo) che inserisce il tavolo e la valutazione nel training set, e learn(String, double) che esegue l’allenamento dell’euristica sulle valutazioni raccolte nel corso della partita.
Classe EuristicheFactory
Questa classe, implementata secondo il pattern Singleton, fornisce l’euristica in base ad un tipo enum EURISTICHE, definito all’interno della stessa classe e ricevuto alla chiamata del metodo getEuristica(EURISTICHE). Tale classe permette di mantenere un’unica copia di tutte le euristiche implementate senza doverle istanziare più volte ad ogni richiesta di valutazione di un tavolo.
4.1.2 Package operations
La richiesta di aggiungere nuovi tipi di euristiche, che fossero in grado di apprendere oltre a valutare, portava a dover eseguire parti di codice separate in base al tipo di euristica. Per aumentare l’estendibilità si è ricorsi al design pattern Visitors. Tale package rappresenta la gerarchia delle operazioni che le euristiche possono eseguire, dove l’interfaccia HeuristicOperation rappresenta un’operazione generica che può essere eseguita su classi di tipo Euristica oppure di tipo LearningHeuristic. La separazione tra queste due gerarchie permette di non dover eseguire cast per control- lare il tipo di euristica. Inoltre, aumenta sensibilmente la manutenibilità in quanto l’aggiunta di nuovi tipi modifica solamente le gerarchie delle euristiche e delle relative operazioni, non comportando l’aggiunta di nuovi controlli per l’esecuzione di operazioni in base al tipo. Infine, mantiene la gerarchia delle euristiche pulita in quanto i metodi delle sottoclassi non vengono propagati alle superclassi per sollevare il client dai cast.
figura 4.2: Il package operations
Interfaccia HeuristicOperation
L’interfaccia fornisce un contratto standard per tutte le operazioni che la realizzano.
Per ogni tipo di euristica viene fornito un metodo che implementerà l’operazione rela- tiva. Attualmente vengono esposti i metodi doHeuristicOperation(Euristica) e doLearningHeuristicOperation(LearningHeuristic)che eseguono rispettivamen- te le operazioni per oggetti di tipo Euristica e di tipo LearningHeuristic.
4.1. DIAGRAMMI DELLE CLASSI
4.1.3 Package strategie
Questo package, non presente nella precedente versione del software, contiene tutte le classi necessarie alla gestione dei vari algoritmi che forniscono la mossa da eseguire da parte dell’intelligenza artificiale.
figura 4.3: Il package strategie
In figura 4.3 sono presenti le varie classi contenute nel package. Ogni nuovo algoritmo per determinare la mossa da eseguire deve necessariamente implementare l’interfaccia Strategia, disaccoppiandosi così dall’intelligenza artificiale che ottiene semplicemente la mossa senza conoscere il particolare algoritmo. Essendo che l’oggetto istanziato non è strettamente legato alla partita o al giocatore e che questi dati possono essere passati come parametri si è scelto di mantenere un unico oggetto per ogni strategia, mantenuto dalla classe StrategieFactory che ne controllerà l’accesso.
Classe Strategia
Tale classe fornisce un contratto a tutte le classi che implementano gli algoritmi per la scelta delle mosse. Viene esposto il metodo getMossa(Tavolo, Giocatore, EURISTICHE)che richiede il tavolo da valutare, il giocatore a cui spetta la mossa e l’euristica da utilizzare. Permette quindi fornita la mossa da effettuare. Non è stata pensata come interfaccia perché il viene fornito un algoritmo standard che ritorna una mossa a caso tra tutte quelle possibili.
Classe StrategieFactory
Questa classe, implementata secondo il pattern Singleton, fornisce la strategia in base ad un tipo enum STRATEGIE, definito all’interno della stessa classe e ricevuto alla chiamata del metodo getStrategia(STRATEGIA). Tale classe permette di mantenere un’unica copia di tutte le strategie implementate senza doverle istanziare più volte ogni qual volta venga richiesta la mossa da eseguire.
4.1.4 Package IA
Il package rappresenta il modulo di intelligenza artificiale con il quale il resto del gioco interagisce per ottenere le mosse e le valutazioni dei pezzi. Si prevede che l’intelligenza artificiale venga istanziata ogni volta che viene richiesto di giocare contro un avversario
18
4.1. DIAGRAMMI DELLE CLASSI non umano. In precedenza, veniva creato un oggetto ogni volta che si richiedeva al computer di eseguire una mossa, comportando a cascata la creazione ripetuta di tutte le varie classi necessarie al soddisfacimento di tale requisito. Si aveva quindi un overhead non giustificato. Si è proceduto di conseguenza a rimuovere tale problematica istanziando un oggetto solamente quando si richiede la prima mossa di una nuova partita. Tale verrà quindi acceduto ogni turno ed eliminato al termine della partita.
Il package si occupa inoltre di mantenere aggiornata la valutazione dei pezzi del- l’avversario ad ogni turno, raccogliendo le varie feature ed analizzandole per ottenere il profilo delle varie pedine e predirne la tipologia.
Come si nota dalla figura 4.4, il package contiene anche i package euristiche e strategie. Oltre a questi sono presenti le classi IntelligenzaArtificiale e IAFactory.
figura 4.4: Il package IA
Classe IntelligenzaArtificiale
Questa classe permette di ottenere la mossa, mediante il metodo getMossa() da eseguire quando il turno spetta al computer. Per istanziare un oggetto di questa classe è necessario fornire il tavolo relativo alla partita, i due giocatori, il livello di difficoltà richiesto e, soprattutto, l’euristica, la strategia e il ranker. Ciò permette di cambiare velocemente il comportamento dell’intelligenza artificiale.
Classe IAFactory
La classe garantisce di accedere all’intelligenza artificiale associata ad una determinata partita senza dover necessariamente istanziare in modo non controllato. Ogni qual volta viene richiesto l’intervento dell’intelligenza artificiale viene infatti controllato se questa non esista già per la partita attualmente in corso. Se è già stato istanziato un oggetto allora si procederà a fornirlo, evitando quindi un’inutile proliferazione di oggetti, altrimenti lo crea nuovo. Tale meccanismo si basa sull’univocità dell’identificativo della partita e viene implementato dal metodo getIA(...) al quale bisogna fornire tutti i parametri necessari all’eventuale creazione dell’oggetto. Il metodo deleteIA(String) richiede invece l’identificativo della partita per eliminare l’oggetto associato. Al termine della partita non viene più richiesto di eseguire mosse e di conseguenza l’oggetto relativo non viene più utilizzato, rendendo quindi necessaria la sua rimozione.
4.1.5 Package features
Il package, già presente nella precedente versione, contiene tutte le classi necessarie per la raccolta delle feature.
4.1. DIAGRAMMI DELLE CLASSI
figura 4.5: Le interazioni del package IA
figura 4.6: Il package features
In figura 4.6 sono presenti le varie classi contenute nel package. Ogni nuova feature deve necessariamente implementare l’interfaccia Feature permettendo di memorizzare velocemente la feature per ogni pezzo senza dover conoscere come viene calcolata. La classe FeatureCollector immagazzina tutte le feature per ogni pezzo e si occupa di fornire all’esterno il profilo dei pezzi memorizzato turno per turno. La classe Controllorefornisce delle semplici funzionalità di utility necessarie alle feature per determinare se la mossa eseguita soddisfa qualche caratteristica da rilevare.
20
4.1. DIAGRAMMI DELLE CLASSI Interfaccia Feature
Questa interfaccia fornisce un contratto per interfacciarsi in modo univoco con tutte le varie feature. Tramite il metodo resolve(int, String, int, int) si delega alla feature l’operazione di registrare la caratteristica individuata. È necessario fornire il turno in cui si esegue la mossa, la mossa, il pezzo e il giocatore che ha effettuato la mossa. Si fornisce anche il metodo getFeature(int) per ottenere il profilo del pezzo richiesto.
Classe FeatureCollector
Questa classe ha il compito di eseguire l’analisi delle feature per ogni turno e per ogni pezzo che è presente all’inizio del turno mediante il metodo analizzaMosse(int, LogPartita, int)che richiede il giocatore di cui bisogna analizzare i pezzi, il log della partita di cui si vuole produrre il profilo e il turno limite al quale l’analisi deve terminare. Gli altri metodi sono privati e pertanto vengono utilizzati solo per ridurre la complessità del metodo analizzaMosse(...). Il profilo complessivo dei pezzi viene fornito mediante una classe interna FeaturePezzi che mantiene un array di tutti i profili dei pezzi per ogni turno.
4.1.6 Package ranker
Il package, non presente nella precedente versione, fornisce le classi che implementano gli algoritmi per la valutazione della tipologia delle pedine. Nell’architettura precedente non esisteva la separazione tra l’algoritmo che forniva la stima dei pezzi e le classi che fungevano da interfaccia per ottenere la valutazione. La necessità di realizzare tecniche diverse per l’analisi dei profili porta a dover necessariamente separare i due compiti.
Nella vecchia versione la valutazione veniva effettuata dalle classi Ranker, che ora è stata rinominata in ValutaPezzi per indicarne il cambiamento nelle funzionalità, e PezzoNascostoche a cui è stato rimosso tale compito.
figura 4.7: Il package ranker
In figura 4.7 sono presenti le varie classi contenute nel package. Ogni nuovo ranker deve necessariamente implementare l’interfaccia Ranker che permette di disaccoppiare l’algoritmo effettivo dal generico contenitore che deve fornire la valutazione. Essendo la valutazione dei pezzi dipendente solo dal profilo registrato per il giocatore, allora è sufficiente fornire tali dati come parametri garantendo così la presenza di un’unica istanza per ogni algoritmo di ranker. La classe RankerFactory controlla l’accesso a tali algoritmi permettendo di evitare la proliferazione di oggetti inutili. La valutazione del pezzo viene memorizzata automaticamente all’interno della classe PezzoNascosto in modo tale da mantenere il tavolo costantemente aggiornato.
4.1. DIAGRAMMI DELLE CLASSI Interfaccia Ranker
L’interfaccia fornisce un contratto standard per tutte le classi che implementano un nuovo algoritmo di apprendimento. Viene infatti richiesto dall’algoritmo di fornire la bontà del pezzo secondo il profilo memorizzato. Il metodo getBonta(PezzoNascosto, Model, double)richiede il pezzo che si desidera valutare, il modello rappresentante che permette la classificazione dei pezzi in base al profilo dell’utente e il livello di difficoltà della partita, in modo tale da determinare il livello di rumore da adottare durante la valutazione.
Classe RankerFactory
Questa classe, implementata secondo il pattern Singleton, fornisce il ranker in base ad un tipo enum RANKERS, definito all’interno della stessa classe e ricevuto alla chiamata del metodo getRanker(RANKERS). Tale classe permette di mantenere un’unica copia di tutti i ranker implementati senza doverle istanziare più volte ad ogni richiesta di valutazione delle pedine.
Classe ValutaPezzi
La classe, nella vecchia versione chiamata Ranker non ha subito cambiamenti impor- tanti. Lo scopo principale, implementato dal metodo aggiornaProfilo() è quello di invocare il ranker indicato durante la costruzione dell’oggetto e, per ogni pezzo, ottenere la valutazione da attribuire agli oggetti PezzoNascosto.
Classe PezzoNascosto
Tale classe, già presente nella precedente versione, memorizza le informazioni che iden- tificano un pezzo dell’avversario di cui non si sa la tipologia. Inizialmente l’algoritmo che valutava il tipo della pedina era implementato in questa classe. Ora la classe si occupa solamente di mantenere le feature del pezzo e il presunto tipo, lasciando alle varie classi che realizzano l’interfaccia Ranker l’implementazione dell’algoritmo.
4.1.7 Package learner
Il package contiene le classi che implementano gli algoritmi per la valutazione dei profili offline. Nell’architettura precedente era già presente questo pacchetto che è effettivamente rimasto quasi identico. È stata effettuata una pulizia del codice per rimuovere metodi e classi necessari esclusivamente a scopo di test ed è stata aggiunta la classe LearnerFactory per controllare l’accesso ai vari algoritmi garantendo l’esistenza di un’unica copia.
Classe Learner
Ogni algoritmo che fornisce un modello che permetta di classificare i pezzi deve necessariamente derivare da questa classe. Infatti, sono presenti metodi comuni a qualsiasi algoritmo come getProfilo(Vector<LogPartita>) che restituisce il profilo ottenuto dalle partite indicate. Per ogni learner è necessario indicare il relativo nome salvato nell’attributo privato nome. Tale nome è necessario per gli algoritmi di ranking che hanno una corrispondenza con gli algoritmi di learning in quanto una volta costruito il profilo di un giocatore, è necessario utilizzare tale per fornire delle previsioni durante le partite andando a recuperare tali informazioni dal database.
Classe LearnerFactory
Questa classe, implementata secondo il pattern Singleton, fornisce il learner in base ad un tipo enum LEARNERS, definito all’interno della stessa classe e ricevuto alla chiamata
22
4.1. DIAGRAMMI DELLE CLASSI
figura 4.8: Il package learner
del metodo getLearner(LEARNERS). Tale classe permette di mantenere un’unica copia di tutti i learner implementati senza doverle istanziare più volte ad ogni richiesta di valutazione delle pedine.
4.1.8 Package model
Il package fornisce una rappresentazione generica del modello dei dati che si ottiene durante la creazione dei profili. Ogni particolare algoritmo necessiterà di rappresentare il modello dei dati, su cui si baserà poi la valutazione, in modo appropriato, non è quindi possibile determinare ne il numero di attributi, ne le funzioni per accedere ad essi. Tuttavia, si vuole comunque non essere a conoscenza del particolare modello da costruire. La gerarchia quindi presenta un’interfaccia Model vuota che non fornisce attributi e metodi ma rappresenta un generico modello di dati. Per costruire l’oggetto corretto è stata realizzata la classe BuildModel che, in base al learner indicato, costruisce l’oggetto rappresentante il modello associato al learner. Ad ogni classe che implementa l’interfaccia Model viene passato un parametro di tipo stringa che è stato memorizzato per ricostruire il modello immagazzinato in qualsiasi sistema di archiviazione (file, database, ...). In figura 4.9 è rappresentata la struttura del package.
figura 4.9: Il package model
4.1. DIAGRAMMI DELLE CLASSI Classe BuildModel
Data la necessità di costruire un determinato tipo di modello in relazione all’algoritmo di learning, si è provveduto a creare tale classe per costruire l’oggetto esatto, senza necessariamente dover replicare il codice ogniqualvolta si debba richieda il modello dei dati rappresentante il profilo. La classe sfrutta il pattern Singleton garantendo quindi un’unica istanza in tutto il sistema ed espone il metodo buildModel(String, String)che richiede il learner e il profilo immagazzinato da fornire al modello che si occuperà di effettuare il parsing corretto per ricostruire i dati per poterli usare agevolmente.
24
4.2. DIAGRAMMI DI SEQUENZA
4.2 Diagrammi di sequenza
Di seguito vengono presentati i diagrammi di sequenza rappresentanti le interazioni con l’intelligenza artificiale per l’ottenimento di una mossa.
4.2.1 Richiesta di una mossa
figura 4.10: La richiesta della mossa
Come si evince dalla figura 4.10, ogni volta che a un oggetto di tipo MySkeleton viene richiesto che mossa l’intelligenza artificiale esegue, questo invoca il metodo getIA()alla IAFactory per ottenere l’oggetto di tipo IntelligenzaArtificiale. A questo punto richiederà all’intelligenza artificiale la mossa da eseguire. Tale interazione viene approfondita successivamente.
Una volta terminata la partita, mediante l’invocazione del metodo modificaTipo() il cui scopo è di cambiare lo stato della partita, l’oggetto MySkeleton si occuperà di chiamare il metodo deleteIA() per deallocare l’oggetto associato all’intelligenza artificiale per la partita desiderata.
4.2.2 Determinazione della mossa
Come si nota dalla figura 4.11, il calcolo della mossa richiede due invocazioni di metodi fondamentali.
Prima di iniziare con la valutazione del tavolo per sapere quale mossa scegliere, è fondamentale aggiornare il profilo delle pedine mediante il metodo aggiornaProfilo().
Verrà successivamente indicato il funzionamento di tale metodo. La determinazione
4.2. DIAGRAMMI DI SEQUENZA
figura 4.11: La determinazione della mossa
del profilo aggiorna il tavolo di gioco permettendo quindi alla strategia di operare come se il gioco fosse a conoscenza completa.
Viene poi richiesto al particolare oggetto derivato da Strategia di fornire la mossa da eseguire. La tecnica algoritmica viene lasciata alla precisa implementazione della classe scelta secondo quanto impostato nella classe IntelligenzaArtificiale. In ogni caso, la classe interfaccerà con l’oggetto di tipo EuristicheFactory per ottenere l’euristica per la valutazione del tavolo. Mediante il metodo valuta() ottiene il punteggio da assegnare al tavolo e scegliere quindi quale e come pezzo muovere.
4.2.3 Aggiornamento del profilo
figura 4.12: L’aggiornamento del profilo
L’aggiornamento del profilo viene eseguito dalla classe ValutaPezzi. Inizialmente richiede ad un oggetto RankerFactory il ranker da impiegare per la classificazione delle pedine. Si procede quindi, per ogni pezzo ad ottenerne la tipologia che verrà poi impostata mediante il metodo setBonta() nel relativo oggetto PezzoNascosto.
Ciò comporta l’aggiornamento diretto del tavolo da gioco in quanto gli oggetti di tipo PezzoNascosto sono riferiti anche dall’oggetto Tavolo associato alla partita da esaminare.
26
Capitolo 5
Sviluppo dell’intelligenza artificiale del gioco
L’IA che è stata progettata appositamente per il gioco ha seguito vari passi ed evoluzioni che hanno risolto le problematiche che si presentavano ad ogni nuovo stadio. Nei capitoli iniziali è già stato presentato l’algoritmo che sta alla base, ma sono possibili varie personalizzazioni che si possono apportare in base al tipo di gioco, certe che possono migliorare l’intelligenza artificiale e altre che potrebbero essere irrilevanti o addirittura peggiorare le prestazioni. Durante lo stage sono emerse varie idee e proposte per rendere più “intelligente” il computer e, mentre certe hanno contribuito ad aumentare il numero di vittorie, altre sono state scartate poiché non erano propriamente adatte al tipo di gioco. Nelle successive sezioni vengono spiegati i vari passaggi che sono stati percorsi individuando i problemi emersi e le modifiche apportate.
5.1 Stadio iniziale
Lo stadio iniziale coincide con l’analisi della precedente intelligenza artificiale realizzata durante gli stage degli anni passati. La sua implementazione comprendeva innanzitutto l’algoritmo MiniMax con l’aggiunta dell’alpha-beta pruning1. Di conseguenza le basi erano già state realizzate e potevano essere riusate senza problemi. Erano state sviluppate varie euristiche e di seguito viene fornita un’analisi per ognuna di esse.
Vengono qui riportate le abbreviazioni delle euristiche che verranno impiegate durante i test.
Euristica Abbreviazione
Buoni mangiati BM_AVV
Cattivi mangiati CM_AVV
Buoni in gioco BG_AI
Cattivi in gioco CG_AI
Attacco ai buoni AB_AVV
Buoni sotto minaccia BMI_AVV
Distanza buoni uscita DU_AI
1Il funzionamento di questi algoritmi lo si può ritrovare alla sezione 2.1
5.1. STADIO INIZIALE
Distanza buoni uscita avversario DU_AVV
tabella 5.1: Sigle identificative delle euristiche - Le sigle sono state costruite secondo le seguenti convenzioni:
• B: pezzi buoni
• C: pezzi cattivi
• M: vengono considerati i pezzi che sono stati mangiati
• G: vengono considerati i pezzi che sono ancora in gioco
• A: viene considerato il numero di pezzi cattivi che minacciano quelli dell’avversario
• MI: viene considerato il numero di pezzi che minacciano quelli dell’avversario
• DU: distanza dei pezzi buoni dai cancelli dell’avversario
• AI: i pezzi che vengono valutati sono quelli dell’intelligenza artificiale
• AVV: i pezzi che vengono valutati sono quelli del giocatore avversario dell’intelligenza artificiale
5.1.1 Buoni Mangiati (BM_AVV)
L’euristica buoni mangiati fornisce un punteggio crescente in base al numero di pezzi buoni che l’intelligenza artificiale ha mangiato all’avversario.
Pezzi buoni Valutazione
0 0
1 0.5
2 0.6
3 0.8
4 1000
tabella 5.2: Valutazioni dell’euristica buoni mangiati
L’euristica attribuisce un valore crescente all’aumentare del numero di pezzi buoni che sono stati mangiati all’avversario. Tale euristica persegue direttamente una condizione di vittoria in quanto tenta di minimizzare la distanza da un obbiettivo. Il comportamento si desume essere aggressivo proprio per tale caratteristica.
5.1.2 Cattivi Mangiati (CM_AVV)
L’euristica cattivi mangiati fornisce un punteggio decrescente in base al numero di pezzi cattivi che l’intelligenza artificiale ha mangiato all’avversario.
Pezzi cattivi Valutazione
0 0
1 -0.05
28
5.1. STADIO INIZIALE
2 -0.1
3 -0.15
4 -1000
tabella 5.3: Valutazioni dell’euristica cattivi mangiati
L’euristica attribuisce un valore decrescente all’aumentare del numero di pezzi cattivi che sono stati mangiati all’avversario. Tale euristica non persegue direttamente una condizione di vittoria in quanto tenta di massimizzare la distanza da una situazione di sconfitta, ossia catturare tutti i pezzi cattivi dell’avversario. Il comportamento si desume essere difensivo proprio per tale caratteristica.
5.1.3 Buoni in Gioco (BG_AI)
L’euristica buoni in gioco fornisce un punteggio decrescente in base al numero di pezzi buoni che rimangono all’intelligenza artificiale.
Pezzi buoni Valutazione
0 -1000
1 -0.8
2 -0.6
3 -0.5
4 0.2
tabella 5.4: Valutazioni dell’euristica buoni in gioco
L’euristica attribuisce un valore decrescente all’aumentare del numero di pezzi buoni che l’intelligenza artificiale si fa catturare. Tale euristica non persegue direttamente una condizione di vittoria in quanto tenta di massimizzare la distanza da una situazione di sconfitta, ossia perdere tutti i pezzi buoni. Il comportamento si desume essere difensivo proprio per tale caratteristica.
5.1.4 Cattivi in Gioco (CG_AI)
L’euristica cattivi in gioco fornisce un punteggio crescente in base al numero di pezzi cattivi che rimangono all’intelligenza artificiale
Pezzi buoni Valutazione
0 1000
1 0.3
5.1. STADIO INIZIALE
2 0.2
3 0.1
4 -0.1
tabella 5.5: Valutazioni dell’euristica buoni in gioco
L’euristica attribuisce un valore crescente al diminuire del numero di pezzi cattivi che l’intelligenza artificiale si fa catturare. Tale euristica persegue direttamente una condizione di vittoria in quanto tenta di minimizzare la distanza da un obbiettivo. Il comportamento si desume essere aggressivo proprio per tale caratteristica.
5.1.5 Attacco ai Buoni (AB_AVV)
L’euristica attacco ai buoni fornisce un punteggio crescente in base al numero di pezzi buoni avversari che vengono minacciati da pezzi cattivi dell’intelligenza artificiale.
x = 0.5 · n
Dove n è il numero di pezzi buoni avversari sotto minaccia da pedine cattive dell’intelligenza artificiale. L’euristica attribuisce un valore crescente all’aumentare del numero di pezzi buoni che vengono posti sotto minaccia da pezzi cattivi dell’intelligenza artificiale. Tale euristica non persegue direttamente una condizione di vittoria e non tenta di massimizzare la distanza da una sconfitta. Da notare che l’intelligenza artificiale preferisce aumentare il numero di pezzi buoni avversari sotto minaccia e di conseguenza mangiarli fa diminuire quasi sicuramente il valore fornito (a meno che mangiando un pezzo buono non si mettano sotto minaccia almeno lo stesso numero di pezzi buoni).
5.1.6 Buoni sotto Minaccia (BMI_AVV)
L’euristica buoni sotto minaccia fornisce un punteggio crescente in base al numero di pezzi buoni avversari che vengono minacciati da pezzi dell’intelligenza artificiale.
x = 0.5 · n
Dove n è il numero di pezzi buoni avversari sotto minaccia da pedine dell’intelligenza artificiale. L’euristica attribuisce un valore crescente all’aumentare del numero di pezzi buoni che vengono posti sotto minaccia da pezzi dell’intelligenza artificiale (si differenzia dalla precedente euristica in quanto non si considera la tipologia di pedina che minaccia). Tale euristica non persegue direttamente una condizione di vittoria e non tenta di massimizzare la distanza da una di sconfitta. Da notare che l’intelligenza artificiale preferisce aumentare il numero di pezzi buoni avversari sotto minaccia e di conseguenza mangiarli fa diminuire quasi sicuramente il valore fornito (a meno che mangiando un pezzo buono non si mettano sotto minaccia almeno lo stesso numero di pezzi buoni).
5.1.7 Distanza buoni Uscita (DU_IA)
L’euristica distanza buoni uscita fornisce un punteggio crescente al diminuire della distanza dei pezzi buoni dai cancelli avversari.
30
5.1. STADIO INIZIALE Distanza uscita Valutazione
0 0.8
1 0.4
2 0.2
3 0.1
4 -0.1
5 -0.2
6 -0.3
7 -0.4
tabella 5.6: Valutazioni dell’euristica distanza buoni uscita
L’euristica attribuisce un valore crescente al diminuire della distanza del pezzo buono dell’intelligenza artificiale più vicino ad uno dei cancelli avversari. Tale euristica persegue direttamente una condizione di vittoria in quanto tenta di minimizzare la distanza da un obbiettivo. Il comportamento si desume essere aggressivo proprio per tale caratteristica.
5.1.8 Distanza buoni Uscita avversario (DU_AVV)
L’euristica distanza buoni uscita avversario fornisce un punteggio decrescente al diminuire della distanza dei pezzi buoni dai cancelli dell’intelligenza artificiale.
Distanza uscita Valutazione
0 -0.8
1 -0.4
2 -0.2
3 -0.1
4 0.1
5 0.2
6 0.3
7 0.4
tabella 5.7: Valutazioni dell’euristica distanza buoni uscita avversario
L’euristica attribuisce un valore decrescente al diminuire della distanza del pezzo buono dell’avversario più vicino ad uno dei cancelli dell’intelligenza artificiale. Tale
