Universit` a degli Studi di Bologna
FACOLT ` A DI SCIENZE MATEMATICHE FISICHE E NATURALI Corso di Laurea Magistrale in Informatica
Tesi di laurea magistrale
Planning in giochi ad informazione parziale
Candidato:
Andrea Gasparro
Matricola 0000540558
Relatore:
Paolo Ciancarini
Anno Accademico 2010-2011
I giochi ad informazione parziale, specialmente quelli in cui si abbia un ele-
vato branching factor, rappresentano un interessante dominio applicativo per
sperimentare approcci basati sul planning: l’idea di sviluppare una strategia
legata all’approfondimento di un sottoinsieme circoscritto dei percorsi possi-
bili, in qualche modo identificato come promettente, appare ragionevole in un
ambito in cui l’esplorazione esaustiva dell’albero di gioco, tradizionalmente
associata alla forza bruta, risulta estremamente difficoltosa. In questo elabo-
rato è proposta una tecnica di planning legata per la costruzione di piani su
differenti livelli di priorità, al fine di sviluppare una strategia che, se da un lato
deve includere piani tradizionali per gestire il breve periodo, dall’altro neces-
sita di un sistema per sfruttare piani che siano linee guida nel lungo periodo,
sopperendo così alla cecità dell’agente. Dopo una prima fase di studio del
dominio, tale tecnica viene prima presentata in astratto e quindi sperimentata
sul programma campione del mondo di Kriegspiel, Darkboard, con risultati
incoraggianti.
Un Grazie sincero a coloro che mi hanno accompagnato fin qui, a chi mi ha dato fiducia ed affetto, siete stati il mio motore, a chi con me ha percorso solo parte del cammino, restandomi comunque nel cuore, a chi ha saputo insegnarmi ad imparare, ed a chi con me ha imparato.
Inoltre e nuovamente un sentito ringraziamento al mio relatore, il Prof. Paolo
Ciancarini, per essere stato un punto di riferimento durante questo mio primo
vero periodo di ricerca.
Indice
1 Introduzione 7
1.1 Struttura dell’elaborato . . . . 9
2 Stato dell’arte 11 2.1 Planning . . . 11
2.2 Planning in contesti ad informazione imperfetta . . . 13
2.2.1 Planner Markoviani . . . 14
2.2.2 Planner gerarchici . . . 15
2.2.3 Priority planning . . . 17
2.3 Pattern recognition in giochi ad informazione imperfetta . . . 17
2.3.1 Chunks . . . 18
2.3.2 Machine learning e reti neurali . . . 20
2.3.3 Opponent modelling . . . 20
2.4 Riepilogo . . . 22
3 Descrizione del dominio 23 3.1 Kriegspiel . . . 23
3.1.1 Regole di gioco . . . 24
3.1.2 Il Kriegspiel da un punto di vista computazionale . . . 26
3.2 Darkboard . . . 27
3.2.1 Apertura . . . 27
3.2.2 Mediogioco . . . 28
3.2.3 Finale . . . 32
3.3 Riepilogo . . . 33
5
4 Planning su livelli di priorità 35
4.1 Modellare il dominio applicativo . . . 35
4.1.1 Contesti ad informazione imperfetta e riflessi sulla tipologia di piani . . . 36
4.2 Planning su livelli di priorità . . . 37
4.2.1 Algoritmo . . . 40
4.2.2 Progresso . . . 43
4.2.3 Classi di problemi interessanti . . . 45
4.2.4 Complessità Computazionale . . . 46
4.2.5 Planning su livelli di priorità e forza bruta . . . 47
5 Planning su livelli di priorità in Darkboard 49 5.1 Planning su livelli nel Kriegspiel . . . 49
5.2 Il Mediogioco in Darkboard 2.0 . . . 50
5.3 Definizione dei Livelli di Priorità in Darkboard . . . 52
5.3.1 Definizione del goal set dei piani affidabili . . . 53
5.4 Lo sviluppo di un piano in Darkboard . . . 55
5.4.1 Progresso . . . 59
5.5 Costo Computazionale . . . 60
5.6 Risultati sperimentali ed altre considerazioni . . . 61
6 Goals in giochi strategici 65 6.1 Goals come Strategie . . . 65
6.2 Chunks come Goals . . . 66
6.3 Chunks come contenitori di Goals . . . 68
6.4 Conclusioni . . . 69
7 Conclusioni e sviluppi futuri 71 7.1 Risultati . . . 72
7.2 Sviluppi futuri . . . 73
A Glossario 75
B Una partita dal punto di vista dell’agente 79
C Listato 85
Capitolo 1 Introduzione
Un problema di Scacchi non è altro che un esercizio di matematica pura.
G.H.Hardy A Mathematician’s Apology
Un problema estremamente complesso nella proposta o nella verifica di algo- ritmi, non necessariamente connessi al solo mondo dell’informatica, è quel- lo di individuare domini pratici in cui sperimentare quanto è oggetto di stu- dio, mantenendo un sufficiente livello di generalità ed astrazione da permet- tere una verifica ed una sperimentazione, che non siano vincolati ad ipotesi specifiche connesse al contesto.
Sin dalla nascita, o meglio ancora prima che il termine Intelligenza Artificiale fosse coniato, i giochi sono stati un ambito d’ elezione per tale scopo: si pensi al contesto dal quale è nato il teorema di Zermelo, all’algoritmo di Turing per giocare a Scacchi, o all’intera teoria dei giochi che tanto impatto ha avuto su informatica ed economia, fra le altre.
Di fatto è vero anche l’inverso: le origini dei giochi strategici vengono fat- te risalire alla simbolizzazione di modelli concreti e sono riproposizioni in astratto di problematiche reali, ritualizzate attraverso i secoli, le cui strategie sono però ancora riconducibili all’ambito originario. Un esempio su tutti è rappresentato dal gioco degli scacchi.
L’ argomento centrale di questa tesi è lo studio del planning in contesti ad informazione parziale. Sin da quando Shannon, negli anni ’50, divise i possi-
7
bili approcci a disposizione di un agente razionale in forza bruta e planning, queste due strategie hanno goduto di fortune alterne: ad oggi si può dire che la forza bruta abbia relegato il planning ad ambiti specifici, ed in particolare Minimax domini la scena.
L’idea dalla quale prende le mosse questa tesi, è che una discriminante fra il successo dell’uno o dell’altro approccio, possa essere proprio la presenza di informazione imperfetta, congiunta a dei fattori di rischio relativi alla pre- senza di un avversario. Se è vero infatti che Minimax ha ucciso molti giochi con avversari (si pensi alla dama, o ai risultati eccellenti ottenuti nell’ambito degli Scacchi), è altrettanto vero che domini ad informazione imperfetta co- me Go, Kriegspiel e Bridge si sono dimostrati più adatti ad altre strategie che privilegiano un’ analisi parziale delle azioni disponibili, a favore di una qual- che valutazione sugli stati futuri di un insieme ristretto di nodi: questo tipo di strategia è lo stesso che guida a grandi linee il planning, che per definizio- ne preferisce ad un’analisi esaustiva, la selezione di percorsi che presentino determinate caratteristiche considerate desiderabili.
La tecnica proposta, che abbiamo chiamato planning su livelli di priorità, si indirizza proprio a questa classe di problemi. L’idea alla base è che per elaborare piani in domini caratterizzati da repentini cambi di scenario, dovuti alla presenza di un avversario, in cui non vale il teorema di Zermelo, che è il vero garante dell’esistenza di un unico percorso oggettivamente migliore, sia necessario catturare la nozione di piano a breve termine ed a lungo termine, che naturalmente un giocatore umano applica in questa tipologia di giochi.
I piani a breve termine sono necessari per la gestione di situazioni specifiche, connesse a minacce o a guadagni entro l’orizzonte dell’agente e sono definiti come piani prioritari, mentre l’elaborazione di un piano visto come una linea guida, che permette di selezionare un sottoinsieme dei percorsi disponibili, in assenza di informazioni sufficienti a puntare ad un obiettivo preciso, è definito come piano affidabile.
Questa seconda categoria di piani è la soluzione proposta per aumentare l’o-
rizzonte di un agente in situazioni di incertezza, offrendo così un criterio di
selezione più profondo di quello a cui è condannata un’analisi con la forza
bruta, in giochi ad informazione imperfetta in cui vi sia un branching factor
elevato.
1.1. STRUTTURA DELL’ELABORATO 9 Dopo una fase di studio preminiare, la tecnica proposta viene sperimentata integrandola in Darkboard, il programma campione del mondo di Kriegspiel.
La scelta del Kriegspiel come ambito per la sperimentazione, è dovuta ad un insieme di fattori: sebbene il Kriegspiel sia un dominio ancora poco studiato, molti dei padri della teoria dei giochi si sono interessati allo studio dei gio- chi ad informazione imperfetta in generale, si pensi a Von Neumann e Mor- genstern in Neumann e Morgenstern [1944] fra gli altri, ed in particolare, le caratteristiche del Kriegspiel che rappresenta una concretizzazione eccellente di dominio ad informazione parziale con un avversario aggressivo, abbinato ad una complessità computazionale elevatissima, hanno attirato l’interesse di molti studiosi, sia in ambito scientifico che in quello scacchistico: vale la pena di menzionare John Nash, Steve Jobs e Aleksandr A. Alekhine fra gli altri.
Avere l’opportunità di contribuire allo sviluppo di uno strumento eccezionale quale è Darkboard, è stato un ulteriore motivo di interesse personale.
1.1 Struttura dell’elaborato
Questa tesi è suddivisa in sette capitoli, strutturati come segue:
• Capitolo 2: Stato dell’arte Sono presentate alcune teniche di plan- ning promettenti nell’ambito dei giochi ad informazione imperfetta, per poi concludere trattando un insieme ristretto di tecniche appartenenti al ramo del machine learning.
• Capitolo 3: Descrizione del Dominio Viene brevemente descritto Dar- kboard, concentrandoci sugli aspetti più rilevanti dal nostro punto di vista, dopo una breve introduzione alle caratteristiche del Kriegspiel.
• Capitolo 4: Planning su livelli di priorità È presentata una prima trattazione teorica dell’algoritmo proposto in questa tesi, analizzandone le caratteristiche e studiando i contesti in cui è applicabile.
• Capitolo 5: Planning su livelli di priorità in Darkboard Viene de-
scritta la realizzazione di un planner su livelli di priorità sviluppato
al fine di essere integrato in Darkboard e sono presentati i risultati
sperimentali ottenuti in questo contesto.
• Capitolo 6: Goals in giochi strategici Vengono ripresi alcuni concetti introdotti nel secondo capitolo, al fine di discutere alcune tecniche in- teressanti per la costruzione di un goal set sfruttabile dalla tipologia di planner proposta
• Capitolo 7: Conclusioni e sviluppi futuri Sono riassunti i punti di
interesse identificati nel corso dell’elaborato, discutendo quanto dimo-
strato e presentando plausibili ulteriori sviluppi della testi sostenuta
Capitolo 2
Stato dell’arte
In questo capitolo saranno presentate brevemente alcune tecniche di planning promettenti nell’ambito dei giochi ad informazione imperfetta, soffermandoci in particolare su quelle che hanno ottenuto risultati interessanti in contesti simili a quello studiato.
Sarà quindi esaminato un insieme ristretto di tecniche appartenenti al- l’area del machine learning, ipotizzando possibili connessioni con sviluppi relativi alle tipologie di planner appena discusse.
2.1 Planning
Il Planning è giustamente considerato l’approccio più simile a quello adope- rato dagli esseri umani, fra quelli a disposizione di un giocatore artificiale;
essenzialmente vi è una rinuncia ad analizzare completamente (o nel modo più esaustivo possibile) l’albero di gioco, a favore della ricerca di una stra- tegia che valorizzi elementi specifici della configurazione corrente, la quale cosa viene spesso effettuata ricongiungendosi direttamente o indirettamente a configurazioni conosciute in quanto analizzate precedentemente.
Fu Shannon negli anni ’50 in Shannon [1950], prima ancora che fosse mai stato realizzato un giocatore artificiale di Scacchi 1 , a dividere i possi- bili approcci per la ricerca in giochi con avversari in piano A e piano B: A corrispondeva al planning, B alla ricerca sullo spazio degli stati con la forza bruta.
1
Non considerando tale l’algoritmo eseguito by hand da Turing nel 1948
11
Storicamente, a partire dagli anni ’80 il planning, nell’ambito di giochi ad informazione perfetta, è passato in secondo piano rispetto a soluzioni basate sul piano B, cedendo il passo agli algoritmi incentrati sull’uso della forza bru- ta: la ragione di ciò è da ricercarsi essenzialmente nel fatto che con la crescita della potenza di calcolo a disposizione è cresciuto il numero di stati visita- bili dai giocatori artificiali e di conseguenza, unendo una strategia di gioco ottima 2 ad una visita dell’albero molto approfondita, un giocatore artificiale non fa altro che scegliere la mossa oggettivamente migliore, la cui esistenza è assicurata dal teorema di Zermelo, fra quelle entro l’orizzonte dell’agente:
un esempio significativo per comprendere quanto detto è pensare che fino al 1998 programmi basati su Minimax non erano in grado di battere i miglio- ri Grandi Maestri di Scacchi, mentre al contrario da quella data in poi “le macchine hanno inevitabilmente superato gli umani“, come ebbe a dichiarare Garry Kasparov, continuando ad utilizzare lo stesso paradigma.
Il passo più naturale nell’approccio ai giochi ad informazione imperfetta, è stato tentare di riproporre un approccio basato su Minimax, a dispetto di una significativa differenza: in questi contesti il teorema di Zermelo non vale e di conseguenza non esiste una mossa oggettivamente ottima, solo mosse probabilmente buone 3 , ed in particolare nel Kriegspiel, che è come vedremo in seguito uno degli esempi più interessanti fra queste tipologie di problemi, la conoscenza acquisita sulla posizione al momento corrente, invecchia molto in fretta.
In questo contesto, considerare la possibilità di rinunciare ad una visita approfondita dell’albero ( che sarà fuori dalle possibilità dell’hardware per molte decadi, in casi complessi come Go e Kriegspiel) a favore della ricer- ca di configurazioni su cui abbiamo indicazioni positive, acquisisce un nuovo significato: guardando da questo punto di vista anche algoritmi basati sul- la forza bruta, è in effetti evidente che la ricerca con avversari in giochi ad informazione imperfetta si sta evolvendo in questa direzione: un esempio si- gnificativo è il successo con cui è stato applicato l’algoritmo Monte Carlo al Go ed al Kriegspiel.
2
si pensi a Minimax
3
esclusi casi in cui il branching dell’albero sia ristretto abbastanza da permettere un
calcolo esaustivo di tutte le possibilità
2.2. PLANNING IN CONTESTI AD INFORMAZIONE IMPERFETTA 13 Alla luce di quanto detto, presentiamo due approcci impiegati nella costru- zione di strategie che non si basino su una valutazione esaustiva dell’albero di gioco: Planning e Machine Learning.
2.2 Planning in contesti ad informazione imper- fetta
Definiamo il dominio in cui opera un planner, come una tripla:
D = ( S, Act, G)
Dove S sono gli stati validi, Act l’insieme delle azioni consentite, G i goal cioè gli obiettivi da raggiungere.
Il Planning è considerato NP-Hard Smith e Nau [1993] e sono note una serie di condizioni restrittive poste sul dominio, nella teoria classica:
• Il sistema in cui si opera deve essere Finito, cioè composto da un nu- mero finito di azioni, stati ed eventi.
• Il Controller conosce sempre lo stato della configurazione corrente S.
• Deterministico: ogni azione ha sempre un solo riusultato.
• Statico: non si verificano cambiamenti a meno di azioni da pare del controller.
• Deve esistere un insieme di Goals, che sono stati in S.
• Un piano è una sequenza ordinata di azioni.
Altro fatto noto è che l’interruzione della visita degli stati ad una profon- dità limite fissata, che nella ricerca di un goal è assolutamente inevitabile in contesti complessi, può portare un planner a non fornire nessuna risposta e dunque a fallire nel compito assegnatogli.
Tradizionalmente i planner vengono divisi in domain specific, domain in-
dipendent e configurabili: le prime due definizioni rispecchiano il fatto che
essi dipendano o meno da una conoscenza specifica del dominio applicativo
ed abbiano subito un conseguente adattamento(o restrizione) allo stesso.
Intuitivamente, i domain specific planner non funzionano in domini diffe- renti da quelli per cui sono stati programmati e questo li rende meno versatili e inadatti a problemi che richiedano una certa flessibilità, ciò non di meno restano la tipologia maggiormente utilizzata in applicazioni reali.
I domain independent planner al contrario, sono pensati per funzionare bene in qualunque dominio 4 e presentano vantaggi e svantaggi: in un con- testo differente rispetto a quello per cui sono stati progettati non richiedono una modifica al loro approccio ma al contempo, tendono ad avere prestazioni inferiori in compiti in cui alla flessibilità sia preferibile l’elaborazione di piani specifici, rispetto a pianificatori pensati appositamente per quel determinato compito.
Alla luce di queste analisi preliminari, è facile intuire che molte tipologie di planner sono inadatte per il problema in analisi: ci concentreremo dunque su quelle più promettenti.
2.2.1 Planner Markoviani
Questa tipologia di planner ben si presta a rappresentare una realtà in cui frequentemente non si conosce lo stato corrente nella sua interezza, ma solo la probabilità del verificarsi di determinate condizioni.
La realtà in esame viene rappresentata come una tripla T= (S, A, P, G), dove:
S := insieme degli stati S1,...,Sn A := insieme delle azioni possibili
P := Probabilita’di transitare da Sn ad Sm G := Goals in S
Il piano elaborato non è dunque un piano classico, ovvero una sequen- za di azioni, perché non abbiamo la garanzia assoluta che ci troveremo in uno stato da cui potremo applicare una determinata azione, si tratta invece di una sequenza di coppie che mappa degli stati appartenenti ad S in determi- nate azioni appartenenti ad A, da compiere nel caso in cui tali stati vengano effettivamente raggiunti.
4
conforme alle condizioni restrittive specificate in precedenze
2.2. PLANNING IN CONTESTI AD INFORMAZIONE IMPERFETTA 15
a root
c
d 0, 3 0, 3
0 ,4
0, 6 0, 4
1
1
Figura 2.1: Grafo rappresentante il flusso di un planner Markoviano in cui l’insieme degli stati è composto da (root,a,d,c) mentre le etichette in corri- spondenza degli archi descrivono le probabilità di transitare da uno stato all’altro.
Purtroppo questo tipo di approccio è chiaramente inapplicabile in ambiti complessi come il Go od il Kriegspiel, che presentano alberi di gioco con un branching factor nell’ordine di 250 per il go e di più di 30! per il Kriegspiel 5 . Anche restringendo il campo di ricerca ad un limitato set di mosse po- tenzialmente interessanti come può avvenire nel finale di tali giochi, questa tipologia di planner appare inadeguata.
2.2.2 Planner gerarchici
Un’altra categoria interessante da considerare sono i planner gerarchici in considerazione dei risultati ottenuti dalla loro applicazione in un gioco ad informazione imperfetta, il Bridge.
Il dominio viene rappresentato per mezzo di Task, che possono essere di tre tipologie:
Primitivi := Corrispondono ad azioni atomiche Compositi := Aggregati di Task Primitivi
Goals := Anch’essi sequenze di azioni primitive,
ma sono rappresentati come un insieme di condizioni che devono essere verificate.
Vincoli fra Tasks sono rappresentati tramite reti, dette Reti di Task (da qui la definizione HTN, Hierarchical Task Networks): ciascuna rete può a
5
questo aspetto viene trattato in Ciancarini [2004]
Task: getPlane (money,destination)
packSuitcase ( ) findPlane (destination,money)
buyTicket (money,destination) choseChair ( )
Figura 2.2: Esempio di Hierarchical Task Network, acquisto di un biglietto aereo
sua volta essere utilizzata come la precondizione di un’altra rete o di un goal, la quale cosa permette di esprimere gerarchie fra vincoli e quindi modella- re realtà in cui bisogna pianificare di verificare preliminarmente determinate precondizioni per il raggiungimento di un Goal.
In questo contesto si segnalano i risultati ottenuti da Bridge Baron de- scritti in Smith et al. [1998] applicando una versione modificata di planning HTN al bridge. Osservando che nel bridge anzichè considerare l’insieme de- gli stati l’insieme delle possibili configurazioni di carte, la scelta è stata di considerare uno stato come una strategia applicata da un giocatore: se in ogni nodo di un albero minimax-like si inserisce uno dei possibili piani, si ha una sorta di ibrido fra planning e forza bruta; il concetto fra l’altro non è molto dissimile da quanto descritto da Favini in G.P.Favini [2010] dove Darkboard essenzialmente associa all’algoritmo Monte Carlo una valutazione in termini di possibili messaggi di risposta da parte dell’arbitro.
Un altro approccio interessante in questo senso si ha in Chung [2005], dove per definire il procedimento decisionale in uno gioco strategico-real time è utilizzata una soluzione simile a quella appena descritta, ma al posto di minimax viene utilizzato Monte Carlo.
Riassumendo, il planning HTN è stato sperimentato con successo domini
(quali ad esempio il Bridge) in cui si possa identificare un insieme di piani
ristretto e in qualche modo prevedibile; in definitiva si riconduce l’incertezza
fra un grande numero di stati ( che descrivono combinazioni di carte) ad un
ristretto numero di piani, assumendo che sia possibile prevedere quali tipolo-
2.3. PATTERN RECOGNITION IN GIOCHI AD INFORMAZIONE IMPERFETTA17 gie di piano adotterà l’avversario. In ambiti in cui la nozione di piano appare
più indefinita, o potrebbe addirittura essere assente a favore di un algoritmo che calcola con la forza bruta, come nel Kriegspiel e nel Go ad esempio, non si ha notizia di tentativi in questo senso.
2.2.3 Priority planning
L’ argomento non è ancora molto studiato e non si dispone di una descrizione di un paradigma standardizzato, come scarseggiano i dati sperimentali.
Questo approccio appare concettualmente non molto dissimile rispetto a quello proposto da Nau e Smith: l’idea è essenzialmente quella di de- finire una coda di priorità fra le azioni possibili, la cui importanza varierà dinamicamente in risposta alla percezione degli agenti coinvolti.
In questo contesto, sono da segnalare gli esperimenti di Bennewitza, Bur- garda e Thrun in Bennewitza [2002] nell’ambito della coordinazione di team di automi.
2.3 Pattern recognition in giochi ad informazione imperfetta
Rispetto al Bridge, altri giochi computazionalmente più complessi e privi di fattori di casualità nel determinarsi delle configurazioni correnti, come il Kriegspiel e gli Scacchi, presentano una maggiore ambiguità nell’identifica- zione di cosa sia un piano: se la definizione data da Dana Nau di un insieme di azioni che portano al raggiungimento di un Goal resta valida, è in effet- ti la definizione di Goal che non è chiara; se come Goal considerassimo lo scacco matto (o equivalentemente in altri contesti, la vittoria della partita) ri- sulterebbe impossibile definire un insieme di azioni tale da raggiungerlo nella maggior parte dei casi.
Dobbiamo dunque definire delle configurazioni auspicabili da utilizzare come Goals quando non vi siano possibilità immediate di vittoria.
Con pattern tecognition in questo ambito si intende il riconoscimento di
schemi ricorrenti all’interno di insiemi di dati grezzi: se come dati grezzi con-
sideriamo un insieme di partite giocate e come schemi i piani adottati all’in-
terno di queste partite, appare evidente come questa disciplina sia strettamente connessa alla possibilità di ricavare piani da partite giocate.
2.3.1 Chunks
È la tecnica a cui probabilmente è stato dedicato più interesse nell’ambito del pattern recognition negli Scacchi ed è stato in genere molto studiato negli an- ni ’90 nel machine learning come in numerosi altri ambiti (dalla psicologia cognitiva alla medicina) eppure una sua definizione univoca di cosa sia un chunk non esiste. Ci limiteremo a dire che nell’ambito dei giochi può essere considerata come la fotografia di una determinata configurazione: negli Scac- chi ad esempio, strutturalmente può essere assimilata alla configurazione di un insieme di pezzi in una posizione.
8 rZbZ0skS
7 Z0Z0a0o0
6 0ZpZpZ0Z
5 lpO0ZpO0
4 pZ0OQZ0Z
3 Z0M0ONZ0
2 PO0Z0O0Z
1 Z0J0Z0S0
a b c d e f g h
Figura 2.3: Esempio di chunk contenuto in una posizione scacchistica
Le caratteristiche che rendono un chunk rilevante sono:
• Occorrere con una frequenza maggiore di una soglia fissata f ∈ R, all’interno del database in analisi.
• Essere significativo per la funzione di valutazione: non necessariamen-
te questo significa discostarsi dalla media degli stati valutati, piuttosto
trovarsi entro un certo arco di mosse precedenti ad una discontinuità
2.3. PATTERN RECOGNITION IN GIOCHI AD INFORMAZIONE IMPERFETTA19 maggiore di una certa soglia V per la funzione di valutazione: intuitiva-
mente questo vuol dire che stiamo cercando l’origine fattori che hanno causato questa discontinuità.
• Gli elementi che compongono un chunk hanno associazioni particolar- mente significative fra loro: in particolare negli scacchi, ed in generale in molte classi di giochi strategici, le relazioni fra i pezzi dipendono dalla dinamica degli stessi.
• In contesti in cui lo spazio è rilevante ( ed è ragionevole affermare che lo è in quasi tutti i giochi strategici, alla luce del fatto che la quasi totalità fu originata da simulazioni di conquista o di protezione di un territorio) un chunk è una posizione assoluta 6 .
Un tentativo di sviluppare un giocatore artificiale basato su chunk fu Clamp (Ericsson and Harris’s, 1990) che portò alla creazione di un giocatore di livel- lo discreto, ma sopratutto a interessanti risultati dal punto di vista didattico.
Il motivo per il quale questo approccio non è stato approfondito ulterior- mente è da ricercarsi principalmente in due fattori: la quantità di configu- razioni diverse che possono verificarsi in una partita di scacchi, Shannon in Shannon [1950] ha calcolato sia nell’ordine delle 10 42 , ed il fatto che pic- cole differenze in una posizione possono mutare radicalmente il significa- to della stessa, rendendo dunque impossibile comprendere chunk anche solo lievemente differenti in un’unica analisi.
In particolare riguardo al Kriegspiel, c’è da segnalare che la visione par- ziale della scacchiera rende l’approccio ancora più difficoltoso: non cono- scendo lo stato dei pezzi dell’avversario, non è nemmeno possibile essere sicuri che due chunk analoghi dal nostro punto di vista siano effettivamente lo stesso chunk in senso assoluto!
A discapito di quanto detto, il concetto di chunk rimane un punto focale nello studio di goal in giochi strategici, argomento particolarmente interessan- te ai fini di questa tesi ed in generale nella ricerca con avversari in giochi ad informazione imperfetta, dunque nel sesto capitolo di questa tesi torneremo su alcuni utilizzi possibili di collection di chunks.
6
Per posizionamento assoluto si intende che la configurazione non è soggetta a traslazioni
o altre trasformazioni: è una configurazione che può essere ritrovata esattamente come viene
proposta.
2.3.2 Machine learning e reti neurali
Implementazioni basate su reti neurali sono divenute una delle principali al- ternative a minimax nell’ambito dei giochi ad informazione imperfetta dopo il successo ottenuto da Tesauro in G.Tesauro [1994] che le ha impiegate per l’addestramento di un giocatore artificiale nel backgammon: TD-Gammon.
TD-Gammon addestrandosi contro se stesso è stato in grado di sviluppare strategie di gioco che lo hanno portato ai livelli dei migliori giocatori uma- ni, sfruttando una strategia che richiama da lontano il simulated annealing:
dopo aver tarato la propria funzione di valutazione attraverso autoaddestra- mento (altro fatto molto raro) TD-Gammon sceglie frequentemente la mossa dalla quale si aspetta i risultati migliori, ma talvolta testa anche alcune strade considerate promettenti ed aggiorna la sua valutazione in base all’esito.
È stato evidenziato come alcuni fattori determinanti negli incredibili risul- tati di TD-Gammon, risiedano nella particolarità del backgammon di scioglie- re la configurazione corrente da quelle passate, in cui le uniche informazioni importanti sono quelle sulla situazione corrente, quelle passate sono quasi prive di interesse: è un gioco non Markoviano che si sposa alla perfezione con l’uso di reti neurali, anzichè con procedimenti che rendono necessaria la costruzione di un albero di gioco; indipendentemente da ciò, le reti neurali restano l’approccio principale per il machine learning di strategie complesse.
2.3.3 Opponent modelling
Questa tecnica dopo essere stata accantonata ha trovato recentemente nuo- ve applicazioni nell’ambito dei giochi ad informazione imperfetta, proprio in Darkboard, come descritto da Favini in G.P.Favini [2010]; tradizionalmente questo approccio è stato trascurato negli Scacchi ed in altri ambiti di ricerca con avversari ad informazione perfetta; nonostante ciò, alcuni tentativi sono stati fatti più o meno recentemente.
A. Jansen, D. Dowe, E.Farr in Jansen [2000] associano a partire da un
DataBase di partite di Grandi Maestri di Scacchi una funzione di distribuzione
di probabilità che in una posizione l’avversario compia una certa mossa, per
tarare attraverso di essa la funzione di valutazione in modo che, nella scelta
2.3. PATTERN RECOGNITION IN GIOCHI AD INFORMAZIONE IMPERFETTA21 delle mosse assegni priorità simili a quelle che stimerebbe un Grande Maestro
nella stessa situazione.
Nell’ambito dei giochi ad informazione imperfetta Del Giudice, P. Gmy- trasiewicz, J. Bryan in Giudice [2009] sperimentano l’opponent modelling basato su probabilità Bayesiane in una variante semplificata del Kriegspiel giocata su una scacchiera 4x4.
Come anticipato ad ogni modo, in analogia rispetto a quanto avvenuto per il planning, questo approccio per anni è stato ritenuto poco promettente per il semplice fatto che mal si sposa con l’utilizzo della forza bruta, che come detto domina in questa categoria di problemi.
Recentemente, risultati interessanti in questa direzione sono stati ottenuti da Darkboard, il quale ha proposto un approccio in un certo senso simile a quello di Jansen e Dowe: a partire da un DataBase di 12000 partite di Krieg- spiel giocate da giocatori umani o da Darkboard contro giocatori umani, vie- ne calcolata la probabilità che alla mossa m, con m ∈ N, su una matrice 8x8 rappresentante la scacchiera, un giocatore specifico (del quale quindi si pos- siedono file .pgn di partite giocate in precedenza) o un opponente generico effettuino una determinata mossa.
L’idea alla base di questa strategia è l’ipotesi che in contesti in cui si possiedono scarse informazioni, un giocatore tenda a riproporre mosse che gioca abitualmente, la quale cosa renderebbe prevedibile il suo comporta- mento, fornendo quindi una sorta di indicatore statistico sullo stato dei pezzi dell’avversario.
In conclusione si può dire che in ambiti in cui si disponga di scarse in- formazioni, il profiling può risultare una risorsa preziosa per ricostruire il comportamento del proprio avversario: essenzialmente è un’ottima (vitale, citando Favini) arma difensiva.
Per quanto riguarda la pianificazione in senso tradizionale come l’elabora- zione di un tradizionale piano offensivo però , l’approccio appare restrittivo:
il meccanismo si sposa perfettamente con l’idea di descrivere la pericolosi-
tà di occupare alcune case della scacchiera in un certo momento di gioco ad
esempio, ma utilizzarlo per sviluppare un piano stimando che obiettivi strate-
gici si trovino in un settore specifico appare ancora abbastanza azzardato, se
non in condizioni particolari (ad esempio, in apertura).
2.4 Riepilogo
Gli approcci legati al Planning in giochi ad informazione parziale ed in parti- colare quelli legati al Kriegspiel presentano delle difficoltà aggiuntive rispetto al Planning classico, già un problema complesso di per se: la definizione di cosa sia un piano è in se ambigua in questi ambiti, mentre le azioni possibili dipendono non più da valutazioni certe ma da stime di probabilità sull’effetti- va situazione dello stato corrente, che può in alcuni casi essere completamente erronea.
In questo contesto è utile tenere presente alcune buone performances ot-
tenute da algoritmi basati su reti gerarchiche e reti neurali, come anche il
successo di alcuni approcci basati sull’estrazione di indicazioni statistiche sul
comportamento di giocatori umani, a partire da database di partite giocate.
Capitolo 3
Descrizione del dominio
In questo capitolo viene descritto Darkboard, lo strumento di sviluppo scelto e presentato nell’introduzione di questo elaborato, dopo aver proceduto ad una relativamente breve introduzione al dominio applicativo per il quale è stato progettato: il Kriegspiel.
3.1 Kriegspiel
Il Kriegspiel o Scacchi Ciechi è una variante degli Scacchi (per una trattazione più estesa di quella offerta in questo capitolo, rimandiamo ad Wiki [2012]) ed è un gioco con avversari, ad informazione imperfetta a somma zero.
Storicamente la nascita del Kriegspiel viene fatta risalire al 1899, per ope- ra di Henry Michael Temple in Inghilterra, più precisamente a Londra (allora considerata la Capitale Mondiale degli Scacchi) 1 nel Club The Gambit: le pri- me regole di cui si abbia notizia sono dette “all’inglese, in memoria del loro luogo di origine.
Il Kriegspiel prende le mosse dal war game detto Kriegsspiele, probabil- mente inventato da Georg von Rassewitz nel 1812 e già allora utilizzato dal- l’esercito tedesco, come simulazione di situazioni di guerra su cui addestrare i propri ufficiali.
1
G.Kasparov, I miei più Grandi Predecessori, Vol 1
23
3.1.1 Regole di gioco
In ciascuna partita di Scacchi Ciechi sono coinvolti tre attori, due giocatori ed un arbitro, ciascuno dei quali ha a disposizione una scacchiera, ed un totale di due set di scacchi: un colore a ciascun giocatore ed un set completo per l’arbitro.
L’obiettivo del gioco è come negli Scacchi catturare il re avversario e le regole per il movimento dei pezzi restano invariate, con la differenza che ciascun giocatore vede solo i propri pezzi e dunque può inconsapevolmente proporre mosse illegali che saranno rifiutate dall’arbitro.
Il compito dell’arbitro, unico attore a conoscere lo stato complessivo del gioco, è quello di monitorare l’andamento del gioco controllando che i gio- catori effettuino solo mosse valide, notificando in caso contrario uno dei se- guenti messaggi:
• illegale: se la mossa è illegale a causa di impedimenti non visibili dal giocatore.
• nonsense: se la mossa viola le regole sulla mobilità dei pezzi proprie degli scacchi
L’arbitro comunica inoltre il verificarsi di determinate situazioni di gioco regolamentari con i seguenti messaggi:
• pezzo catturato: se l’ultima mossa porta alla cattura un pezzo, l’arbitro informa entrambi i giocatori.
• scacco: se il re del giocatore che ha il tratto si trova sotto scacco ( cosa che può avvenire anche a seguito di una mossa tentata dal gioca- tore stesso, che sarà quindi rifiutata) l’arbitro lo comunica con uno dei messaggi che vedremo in seguito.
• scacco matto: se un giocatore è sotto scacco e non puo muovere il proprio re, nè proteggerlo con un altro pezzo, l’arbitro informa i due giocatori che la partita è terminata.
Ogni messaggio dell’arbitro è pubblico: le comunicazioni sono dirette ad
entrambi i giocatori, mentre ogni messaggio inviato da un giocatore all’arbitro
viene notificato esclusivamente a quest’ultimo.
3.1. KRIEGSPIEL 25 È opportuno sottolineare che i messaggi dell’arbitro giocano un ruolo fon- damentale nelle deduzioni (potenzialmente anche erronee) effettuate dai gio- catori sullo stato della scacchiera e dunque, tentare di massimizzare il numero di comunicazioni che si ricevono per ogni mossa è una strategia sensata, per poter sviluppare delle ipotesi più accurate sullo stato complessivo del gioco da parte di ciascun giocatore, ma non solo; questo pone l’accento su un aspetto trasversale nei giochi ad informazione imperfetta: le informazioni in questo contesto sono preziose.
Come già detto in precedenza, il Kriegspiel non è popolare quanto gli Scacchi e la mancanza di una standardizzazione nelle regole di gioco ha porta- to alla nascita di differenti dialetti; quelle scelte per implementare Darkboard e qui presentate sono le più largamente condivise, giocate dalla maggioranza dei giocatori ed adottate da ICC 2 ed alle Olimpiadi di Informatica tenutesi nel 2006.
In questa variante, a seguito di ogni mossa le comunicazioni dell’arbitro possono essere:
• White move: la mossa è al bianco.
• Black move: la mossa è al nero.
• Pawn at <square> captured: l’ultima mossa effettuata ha portato alla cattura di un pedone nella casella corrispondente
• Piece at <square> captured: l’ultima mossa effettuata ha portato alla cattura di un pedone nella casella corrispondente
• Rank check: Scacco sulla Traversa: notare che in tale caso non viene comunicato se lo scacco arrivi dal lato corto o lungo.
• File check. Scacco sulla Colonna: notare che in tale caso non viene comunicato se lo scacco arrivi dal lato corto o lungo.
• Long-diagonal check: Scacco sulla diagonale lunga (rispetto al re og- getto dello scacco)
2
Internet Chess Club Server, la più grande comunità di Kriegspiel attiva
(a)
8 0Z0Z0Z0Z
7 Z0Z0Z0Z0
6 0Z0Z0Z0Z
5 ZBZ0Z0Z0
4 0Z0ZPZ0Z
3 Z0Z0ZNZ0
2 POPO0OPO
1 SNAQJ0ZR
a b c d e f g h
(b)
8 rZblkans
7 opopZpop
6 0ZnZ0Z0Z
5 Z0Z0o0Z0
4 0Z0Z0Z0Z
3 Z0Z0Z0Z0
2 0Z0Z0Z0Z
1 Z0Z0Z0Z0
a b c d e f g h
8 rZblkans
7 opopZpop
6 0ZnZ0Z0Z
5 ZBZ0o0Z0
4 0Z0ZPZ0Z
3 Z0Z0ZNZ0
2 POPO0OPO
1 SNAQJ0ZR
a b c d e f g h
Figura 3.1: Esempio di configurazione in una partita di Kriegspiel, raffi- gurante la visuale del giocatore bianco(a), del giocatore nero (b) e quella dell’arbitro
• Short-diagonal check: Scacco sulla diagonale corta (rispetto al re og- getto dello scacco)
• Knight check: Scacco di Cavallo.
• «INT> pawn tries: Il giocatore che ha il tratto ha a disposizione INT catture di pedone.
3.1.2 Il Kriegspiel da un punto di vista computazionale
Il Kriegspiel, sebbene abbia regole simili al gioco degli scacchi, appartiene
alla classe di giochi che come Go, Phantom Go etc, risultano estremamente
complessi per un giocatore artificiale a causa del loro branching factor: è
significativo considerare che se negli Scacchi il branching è nell’intorno delle
35 mosse, in Kriegspiel questo potrebbe essere approssimativamente intorno
a 35!
3.2. DARKBOARD 27 Per avere un’idea di come sia possibile calcolare questo dato, fra le di- verse scuole di pensiero a riguardo ci appoggeremo al metodo utilizzato in Ciancarini [2004]: al contrario di quanto avviene negli scacchi, in Kriegspiel bisogna considerare anche i possibili tentativi rifiutati e dunque le possibili sequenze di tentativi: questo è rilevante in quanto, una diversa sequenza di tentativi porta ad avere diverse informazioni da parte dell’arbitro, quindi una diversa visione dello stato corrente.
Quello che contiamo in questo caso è dunque il numero di semimosse possibili in una posizione: se le mosse possibili sono N, le sequenze possibili sono N*(N-1)*(N-2)...*2.
L’insieme degli stati invece è esattamente lo stesso degli scacchi, quindi come detto pari a 10 42
3.2 Darkboard
Darkboard è il programma attualmente campione del mondo, detentore del- la medaglia d’oro assegnatagli alle Olimpiadi di Informatica del 2006 e del 2009 come miglior giocatore artificiale di Kriegspiel, sviluppato da G.Favini sotto la supervisione del Prof. P.Ciancarini, presso il Dipartimento di Scienze dell’Informazione dell’Alma Mater Studiorum di Bologna.
Per una trattazione estesa sul funzionamento di Darkboard si rimanda a G.P.Favini [2010]; l’obiettivo di questo paragrafo è descriverne la struttura, in modo da contestualizzare l’ambito nel quale testeremo la tecnica di planning proposta in questo elaborato di tesi.
La gestione di una partita da parte di Darkboard è suddivisa in tre mo- menti distinti, affrontati con approcci distinti e che dunque saranno presentati separatamente.
3.2.1 Apertura
I giocatori artificiali di Scacchi ormai convergono sul gestire questa prima fa-
se attraverso la creazione di Libri di Aperture, cioè sequenze di mosse ormai
consolidatesi nel tempo e che la teoria scacchistica ha nei secoli individua-
to come le varianti migliori di determinate mosse iniziali: essenzialmente si
tratta di sequenze, abitualmente comprese fra le 5 e 10 mosse, che permet- tono al giocatore artificiale di risparmiare tempo e potenza di calcolo, nel caso in cui le aperture si svolgano secondo schemi consueti, oltre ad avere la fondamentale funzione di evitare le numerose trappole studiate in avvio di partita.
La difficoltà più significativa incontrata nel trasporre questo approccio al Kriegspiel è che in questo ambito non è presente una teoria ben studiata come per gli scacchi, ma questa via resta percorribile: Darkboard ha infatti creato libri di aperture appoggiandosi alle sequenze di mosse iniziali messe in pratica dai migliori giocatori umani su un database di 12.000 partite raccolte su ICC 3 . Al momento della ricezione del primo messaggio dell’arbitro che riporti informazioni sul gioco avversario, la fase di apertura è considerata conclusa e si passa al Mediogioco.
3.2.2 Mediogioco
Il mediogioco è il momento più creativo e ricco di incertezza dell’intera partita sia negli Scacchi che nel Kriegspiel, il che equivale a dire che è la fase in cui il branching factor dell’albero di gioco è più ampio: in questa fase non si hanno pattern noti da seguire o semplificazioni a disposizione: è il momento in cui pesa maggiormente la capacità di pianificare e calcolare sequenze di mosse dinamicamente, cioè su situazioni potenzialmente nuove, ed altresì la fase in cui maggiormente emerge l’aspetto computazionale in astratto rispetto a quello legato alle specifiche regole del gioco.
In questo momento di gioco si inquadrano molte delle innovazioni ap- portate da Darkboard allo studio del Kriegspiel ed in generale ai giochi ad informazione imperfetta:
Monte carlo tree search
Un’evoluzione del metodo Monte Carlo standard, proposto da E.Fermi, J. von Neumann e S.M. Ulam negli anni ’40 che appartiene alla famiglia dei metodi statistici non parametrici, in cui essenzialmente il computer simula un ampio numero di partite che potrebbero seguire alla scelta delle mosse disponibili
3
Internet Chess Club
3.2. DARKBOARD 29 nella configurazione corrente, per ricavarne indicazioni statistiche sulla bontà di tali mosse.
Nella versione tree search, l’algoritmo si basa sulla ripetizione, fino all’e- saurimento del tempo disponibile, dei seguenti quattro passi:
Scelta viene scelta una foglia dell’albero basandosi sul numero di visite e dei i risultati medi ottenuti.
Espansione in questa fase é possibile aggiungere nuovi nodi all’albero di gioco.
Simulazione il punto di maggior rilievo: secondo differenti metodologie che dipendendono dal contesto in cui il metodo è impiegato, viene simulato il proseguimento della partita sin dallo stato corrente e la media dei risultati prodotti è restituita in output ed associata alla foglia.
Backpropagation Il valore associato a ciascun nodo è propagato verso l’al- to a ciascun padre fino alla radice ed i valori di ciascun nodo sono ricalcolati.
Al termine di questo ciclo l’algoritmo sceglie il nodo che ha ricevuto il maggior numero di visite e non quello con il valore statistico più alto, che è sperimentalmente risultato essere un indicatore inaffidabile, là dove il nodo da visitare viene scelto in base alla formula:
U i = V i + c ∗ r lnN n i
(3.1) Dove V i è il valore del nodo i, N è il numero di volte in cui il nodo padre di i è stato visitato, n i è il numero di volte in cui i stato visitato e c è una costante che può essere modificata verso il basso nel caso in cui si voglia favorire l’exploitation, verso l’alto nel caso in cui si voglia favorire l’esplorazione.
Monte carlo tree search in Darkboard
Il problema principale nell’applicare Monte Carlo al Kriegspiel è che simula-
re per intero una partita dallo stato corrente non fornisce indicatori statistica-
mente rilevanti: il branching nel mediogioco è talmente ampio che simulare
per un tempo ridotto i possibili sviluppi risultava in un comportamento non distinguibile dal giocatore casuale, come descritto in G.P.Favini [2010].
La scelta implementativa è stata quella di utilizzare una versione del MC- TS in cui non viene simulata la scacchiera dell’avversario, una volta consta- tata l’inefficenza che ne derivava, bensì i messaggi che è possibile ricevere da parte dell’arbitro in seguito ad ogni azione.
In aggiunta, ad ogni istante una matrice 8x8 rappresentante la scacchiera descrive la probabilità che un pezzo appartente ai tre gruppi Pedoni, Pezzi, Re si trovi sulla casa i,j e tali indicatori sono utilizzati per meglio modellare la scelta dei messaggi che verranno restituiti dall’arbitro durante la simulazione.
La probabilità che un pezzo occupi una casa sulla matrice è calcolata in base alle regole sulla mobilità dei pezzi, in base ai messaggi ricevuti dall’ar- bitro negli ultimi n turni(messaggi ricevuti prima di un certo lasso di tempo sono considerati inattendibili in quanto come detto, nel Kriegspiel la cono- scenza attuale invecchia e diviene inservibile in modo molto rapido, a causa della grande mobilità dei pezzi e della scarsità di informazione) ed ultimo ma forse più importante, basandosi sul meccanismo di profiling anticipato nel secondo capitolo, che vedremo in dettaglio nel prossimo paragrafo.
Un ulteriore discostarsi di Darkboard dall’algoritmo Monte Carlo standard si ha per quanto riguarda la lunghezza delle simulazioni effettuate; sperimen- talmente è emerso che più sono profonde le simulazioni, minore è la precisio- ne nell’approssimare lo stato della scacchiera e di conseguenza l’affidabilità del risultato: i tentativi che hanno dato risultati migliori sono le simulazioni ad un passo ed a 4 passi, al termine delle quali l’indicatore sulla bontà del- la posizione ottenuta è ricavato in base al calcolo del materiale residuo per Darkboard e per l’avversario.
Attualmente, la versione più performante di Darkboard è quella che effet- tua simulazioni ad un passo, esemplificata in figura:
Current State
3.2. DARKBOARD 31
Figura 3.2: Esempio di visita Monte Carlo ad un passo: questa è in realtà una semplificazione in quanto ciascuno stato è una coppia di metaposizioni in Darkboard, ma ai fini della nostra trattazione abbiamo preferito astrarre su questo meccanismo, che non giocherà un ruolo determinante nella gestione del planner
Un’ultima considerazione, interessante anche ai fini dell’algoritmo che presenteremo, è che l’utilizzo del metodo Monte Carlo riduce significativa- mente la conoscenza specifica del dominio necessaria al programma, renden- do l’approccio al mediogioco di Darkboard interessante non solo dal punto di vista del Kriegspiel.
Per una trattazione più approfondita sull’uso del metodo Monte Carlo nel caso specifico del Kriegspiel si rimanda a Ciancarini e Favini [2009a].
Profiling
L’opponent modelling in ambito di giochi strategicamente complessi come gli Scacchi è stato per molto tempo e con alcune valide ragioni 4 considerato un approccio scarsamente attrattivo, ma parlando di giochi ad informazione parziale è significativo soffermarsi su alcuni aspetti.
Durante il mediogioco il goal ricercato sia da giocatori artificiali che da giocatori umani è contingente alle situazioni che si verificano sulla scacchiera;
salvo eccezioni non è più direttamente correlato allo scopo finale del gioco(lo scacco matto in questo caso), bensì ad obiettivi che si possono considerare locali, cioè a quello che scacchisticamente viene definito come miglioramento della posizione.
Una previsione che si basi su abitudini di gioco in questo contesto rischia per tanto di trascurare parametri oggettivi rilevanti, che dovrebbero incidere nella scelta delle strategie da impiegare.
L’ intuizione che ha portato all’approccio usato in Darkboard è che in un certo senso, i parametri oggettivi nel Kriegspiel sono effettivamente poco oggettivi: si ha una scarsa conoscenza della situazione reale di gioco ed anche eventi, che in un contesto ad informazione perfetta devierebbero l’attenzione
4
di cui abbiamo discusso nel capitolo precedente, nel paragrafo relativo all’Opponent
Modelling
di un giocatore dai suoi consueti schemi di gioco verso considerazioni relative alla situazione contigente, in questo caso spesso non forniscono informazioni abbastanza significative per elaborare altri schemi di gioco. L’importanza, anche in termini psicologici dei pattern ricorrentemente messi in atto da un giocatore, è drasticamente maggiore a fronte della scarsità di informazioni disponibili.
Essenzialmente l’ipotesi è che in contesti in cui si possiedono scarse infor- mazioni, un giocatore tenda a riproporre mosse e schemi che gioca abitual- mente e dunque se tali schemi sono opportunamente identificati è possibile ricavare altri preziosi indicatori sullo stato del gioco.
Il modello sviluppato da Darkboard è originato da un Database di 12000 partite in cui semplicemente si effettua, in corrispondenza dell’istante di gio- co corrente, una ricerca statistica sulla probabilità che l’avversario occupi determinate case della scacchiera.
Questo semplice meccanismo viene raffinato con alcune ottimizzazioni contingenti alle situazioni specifiche della partita: in base al colore scelto dal giocatore il modello cambia, viene applicata una sorta di neighboring col procedere del gioco, in considerazione della già menzionata tendenza insita nello stesso ad una volatilità delle informazioni che erano valide anche solo poche mosse addietro.
Si ha inoltre la suddivisione dei modelli in due differenti tipologie: mo- delli specifici per uno specifico avversario noto ed un modello generico per un avversario sconosciuto.
3.2.3 Finale
I risultati sul finale ottenuti sono forse l’apporto più significativo fornito da Darkboard al Kriegspiel, dal punto di vista del gioco in se.
Per mezzo di un approccio che richiama quello delle tavole per i finali at-
tualmente utilizzate nei programmi di Scacchi professionali (essenzialmente
costruite attraverso un’analisi brute force retrograda a partire dalle foglie di
un albero in cui vengono inizialmente memorizzate delle metaposizioni rap-
presentanti finali vinti) il programma è in grado di offrire gioco perfetto nel
caso pessimo, in situazioni cui si sia effettivamente in presenza di un finale
3.3. RIEPILOGO 33 vinto, riconducendo la trattazione dello stesso ad un caso particolare di gioco ad informazione perfetta.
Segnalazione necessaria é che questi risultati non hanno precedenti nel- l’ambito del Kriegspiel e sono dunque di assoluto interesse, ma vista la com- plessità dell’argomento ed il fatto che esula dall’interesse di questo elaborato, per una trattazione esaustiva si rimanda a G.P.Favini [2010] ed a Ciancarini e Favini [2010a].
3.3 Riepilogo
Riepilogando quanto visto, il Kriegspiel è un gioco ad informazione parziale con avversari ed a somma zero, molto complesso per un giocatore artificiale:
le informazioni sono scarse, invecchiano in fretta e l’incertezza è non mono- tona, il branching factor è nell’intorno del fattoriale di 30 e lo spazio degli stati secondo quanto calcolato da Shannon in Shannon [1950] è pari a 10 42 .
Darkboard, il programma campione del mondo di Kriegspiel, è in grado di giocare perfettamente finali semplici ed ha a disposizione quello che è pro- babilmente il miglior repertorio di aperture che sia stato sviluppato in questo ambito.
Da un punto di vista difensivo, specie nelle fasi iniziali del gioco, il mec- canismo del profiling e la creazioni di matrici associate a pezzi con differente mobilità, forniscono un eccellente strumento di previsione riguardo alla peri- colosità di ciascuna casa sulla scacchiera, il che viene ulteriormente rafforzato dall’innovativo sfruttamento di un algoritmo Monte Carlo-like che è il cuore del programma nel medio gioco, da un punto di vista computazionale.
Anche alla luce di quanto visto, si deve però rilevare che Darkboard, pur essendo il programma campione del mondo di Kriegspiel, non è ancora al livello dei migliori giocartori umani; un parametro oggettivo per misurare la distanza che separa giocatori artificiali da quelli umani è l’Elo 5 che questi hanno su ICC: quello ottenuto da Darkboard varia intorno ai 1700 punti, non avvicinandosi agli Elo oltre i 2000 punti dei migliori umani.
5