IntellidAma

8/9/2019 IntellidAma

1/22

IntellidAma

Rossinelli Emanuele

10 Aprile 2010

1


2/22

CONTENTS 2

Contents

1 Introduzione 3

2 Dama Italiana 3

2.1 Regole del gioco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.2 Regole rilassate . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

3 Intelligenza Artificiale 5

3.1 Costruzione dellalbero di ricerca . . . . . . . . . . . . . . . . . . . . . . . 53.2 Valutazione dei nodi foglia . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3 Verifica di situazioni non quiescenti . . . . . . . . . . . . . . . . . . . . . . 63.4 Algoritmo MIN-MAX . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

3.4.1 Potatura alfa-beta . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.5 Scelta della mossa migliore . . . . . . . . . . . . . . . . . . . . . . . . . . 10

4 Implementazione 10

4.1 Struttura del programma . . . . . . . . . . . . . . . . . . . . . . . . . . . 104.2 Implementazione della scacchiera . . . . . . . . . . . . . . . . . . . . . . . 104.3 Struttura dati Mossa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.4 Mosse possibili . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124.5 Struttura dellalbero di ricerca . . . . . . . . . . . . . . . . . . . . . . . . 134.6 Classe IDamaEngine . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

4.6.1 Costruzione dellalbero di ricerca . . . . . . . . . . . . . . . . . . . 144.6.2 Funzioni di valutazione . . . . . . . . . . . . . . . . . . . . . . . . 144.6.3 Verifica di quiescenza . . . . . . . . . . . . . . . . . . . . . . . . . 17

4.6.4 Minimax e potatura alfa-beta . . . . . . . . . . . . . . . . . . . . . 184.6.5 Effettuare la mossa . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.7 Grafica e gestione degli eventi . . . . . . . . . . . . . . . . . . . . . . . . . 18

5 Conclusioni 20

5.1 Stato dellarte sui programmi risolutori della dama . . . . . . . . . . . . . 21


3/22


4/22

2 DAMA ITALIANA 4

3. La pedina si muove sempre in diagonale sulle caselle scure di una casella alla volta esoltanto in avanti. Quando una pedina raggiunge una delle caselle dellultima rigaviene promossa, diventa dama e deve essere contraddistinta con la sovrapposizione

di unaltra pedina prelevata tra quelle non in gioco.

4. Ogni pedina puo mangiare quelle avversarie che si trovano in avanti, sulla caselladiagonale accanto alla propria e che abbiano la casella successiva libera. Dopo lapresa, se incontrano in diagonale altre pedine con la successiva casella libera, sideve continuare a mangiare senza togliere la mano dalla pedina stessa. In tal casola presa si chiama multipla. Le pedine prese vanno tolte dalla damiera.

5. La dama si muove anchessa di una casella alla volta, sempre in diagonale, in tuttele direzioni possibili, mangiando sia le pedine che le dame avversarie.

6. In caso di presa e obbligatorio mangiare i pezzi. Lantica regola del soffio, ossia

quella di catturare il pezzo avversario che pur avendone diritto, per distrazione oper scelta non aveva mangiato, e stata abolita dalla Federazione Dama nel 1934.

7. Avendo piu possibilita di presa si debbono rispettare obbligatoriamente nellordinele seguenti priorita:

(a) e obbligatorio mangiare dove ci sono piu pezzi;

(b) a parita di pezzi di presa tra pedina e dama, questultima e obbligata amangiare;

(c) la dama sceglie la presa dove si mangiano piu dame;

(d) a parita di condizioni si mangia dove sincontra prima la dama avversaria.

8. Pezzo toccato = Pezzo mosso: il giocatore che, nel proprio turno di gioco, toccaun proprio pezzo sulla damiera e obbligato a muoverlo. Se si vuole aggiustare unpezzo messo male sulla damiera bisogna prima avvertire lavversario dichiarandoaccomodo o acconcio e attendere lassenso dellavversario.

9. Si vince per abbandono dellavversario, che si trova in palese difficolta, o quandosi catturano o si bloccano tutti i pezzi avversari.

10. Si pareggia in una situazione di evidente equilibrio finale per accordo dei giocatorio per decisione dellarbitro a seguito del conteggio di 40 mosse richiesto da uno deidue giocatori. Il conteggio delle mosse si azzera e riparte da capo tutte le volte che

uno dei due giocatori muove una pedina o effettua una presa.

2.2 Regole rilassate

Il programma e stato scritto considerando un numero ridotto di regole, precisamenteeliminando la regola n. 8 e la n. 10 (il pareggio non e considerato nel nostro gioco).Inoltre, relativamente alla regola n. 7, sono stati rilassati i vincoli b, c, d.


5/22

3 INTELLIGENZA ARTIFICIALE 5

3 Intelligenza Artificiale

Prima di addentrarci nei dettagli implementativi del software, descriviamo come e stato

costruito il modulo di Intelligenza Artificiale, ovvero quali strategie il software usa perscegliere la mossa migliore da effettuare.Ogniqualvolta sia il computer a dover muovere, vengono eseguite le seguenti azioni insequenza:

1. Costruzione dellalbero di ricerca

2. Valutazione dei nodi foglia dellalbero creato

3. Verifica di situazioni non quiescenti

4. Applicazione dellalgoritmo MIN-MAX per la valutazione di tutti i nodi dellalbero

5. Scelta della mossa migliore da eseguire

Vediamole brevemente.

3.1 Costruzione dellalbero di ricerca

La prima cosa da fare e costruire lalbero di ricerca, che ha le seguenti proprieta:

il nodo radice dellalbero rappresenta la situazione attuale (il computer deve muo-vere), tale nodo e a profondita 0 nellalbero

ogni altro nodo dellalbero rappresenta possibili situazioni future

i nodi a profondita dispari sono possibili situazioni di arrivo generate da una mossadel computer

i nodi a profondita pari sono possibili situazioni di arrivo generate da una mossadel player

le foglie dellalbero sono sempre a profondita pari

Lunico nodo noto e proprio il nodo radice. Lalbero poi viene costruito simulando tuttele mosse possibili, nel rispetto delle regole del gioco. La profondita massima dellalbero(ovvero la profondita delle foglie, che chiameremo depth) e definita a priori; piu profondasara la ricerca, migliori risulteranno le mosse del computer, e peggiori saranno i tempi di

risposta. La scelta di terminare la costruzione dellalbero a una certa profondita depth,piuttosto che costruirlo fino ai nodi terminali (vincita o perdita) e necessaria per rendereinterattivo il programma. Tale decisione si chiama taglio della ricerca.

La nozione di situazione riassume lo stato attuale del gioco, ovvero rappresenta lascacchiera e la mossa effettuata per arrivare a tale situazione a partire dalla precedente(il padre del nodo in questione).


6/22


3.2 Valutazione dei nodi foglia

Adesso che lalbero e stato creato, dobbiamo per prima cosa valutare le situazioni di

arrivo, ovvero associare una valutazione ai nodi foglia.Tale valutazione, associata quindi alla scacchiera in un preciso istante, e un numerointero, che deve essere tanto piu grande quanto piu la scacchiera e favorevole dal puntodi vista del computer. Per ottenere questo, si deve utilizzare una funzione di valutazione,chiamata anche euristica, che sintetizzi in un numero la possibilita di vincere da partedel giocatore computer.La scelta di tale funzione e molto importante, in quanto rappresenta la strategia di giocoutilizzata dal computer: possiamo costruire euristiche in modo tale che il computer siadifensivo, e cerchi di proteggere le zone piu sensibili della scacchiera, oppure posiamofare in modo che il computer giochi aggressivo, cercando di andare velocemente a damaed eliminare una ad una le pedine dellavversario.

Creare euristiche valide non e assolutamente semplice; la prima che ci puo venire inmente e la seguente:

V = 100(|pedinecomputer||pedineplayer|)+200(|damecomputer||dameplayer|) (1)

E ovvio che non si tratta di una buona funzione di valutazione: alcune configurazionidella scacchiera potrebbero risultare migliori di altre solo perche presentano una pedinadel giocatore avversario in meno, non considerando il fatto che le posizioni in cui sitrovano le pedine sono fondamentali per lesito del gioco. Chiameremo questa funzione

peso pedine.Come ultima osservazione, ricordiamo che il calcolo della funzione di valutazione nondeve impiegare troppo tempo per non degradare le prestazioni del software; si preferisconoquindi funzioni di valutazioni lineari piuttosto che metodi piu complessi.

3.3 Verifica di situazioni non quiescenti

Per prima cosa, cerchiamo di dare una definizione (o almeno unidea) di situazionequiescente.Una situazione (nel nostro caso, una configurazione della scacchiera) si dice quiescentese e improbabile che nellimmediato futuro manifesti notevoli oscillazioni.

Per esempio, la configurazione rappresentata in fig. 2, e evidentemente non quiescentese il turno e del giocatore verde: la sua prossima mossa sara una cattura doppia con unaconseguente certezza di andare a dama.

Chiaramente si tratta di una verifica strettamente legata alla funzione di valutazionescelta: se abbiamo scelto una funzione che prende in considerazione solo il numero dipedine, possiamo decidere di etichettare una situazione come non quiescente se allaprossima mossa il numero di pedine rimarra invariato. Daltra parte, se avessimo scelto


7/22


Figure 2: Situazione non quiescente

una funzione di valutazione che da importanza anche alle posizioni delle pedine nellascacchiera, allora anche lo spostamento di una pedina verso una posizione strategica-mente buona (per esempio, vicino a dama) renderebbe la situazione non quiescente.

Abbiamo gia parlato del taglio della ricerca. Proprio a causa di tale taglio entra in giocola ricerca di quiescenza: tagliando la ricerca a una certa profondita depth, andremo a

valutare anche nodi che non sono quiescenti. La situazione rappresentata in fig. 2, peresempio, secondo la funzione di valutazione peso pedine e in leggero vantaggio per ilgiocatore rosso, visto che presenta una pedina in piu. In effetti, pero, scegliendo questamossa, al passo successivo il giocatore verde fara una cattura multipla, passando quindiimmediatamente in vantaggio. Quindi la valutazione che avevamo fatto sul nostro nodonon e affatto affidabile.Per questo motivo e necessario applicare una valutazione solo alle situazioni quiescenti,mentre per quelle situazioni che non lo sono, si preferisce costruire un albero piu pro-fondo, esplorando mosse successive, fino a quando non si arriva a una situazione quies-cente da poter valutare. Scendere in profondita fino a quando non si arriva ad avere solosituazioni quiescenti puo essere molto oneroso: per questo motivo si sceglie di tagliareanche la ricerca di quiescenza.

3.4 Algoritmo MIN-MAX

Lalgoritmo min-max (o minimax) e il vero e proprio modulo di intelligenza artificiale.Una volta che abbiamo le valutazioni dei nodi foglia (che supponiamo essere quiescenti),


8/22


dobbiamo risalire lalbero e valutare tutti i nodi, fino ad arrivare alla radice. Solo inquesto modo possiamo scegliere la mossa migliore da effettuare a partire dalla radice.Lalgoritmo sfrutta le seguenti assunzioni:

Si considerano due giocatori, MIN e MAX

Nel nostro caso, il giocatore MAX e il computer: sceglie ogni volta la mossa chegli consente di massimizzare la valutazione della situazione di arrivo

Dualmente, il giocatore MIN e lavversario, e cerca quindi di minimizzare talevalutazione (ovvero cerca di rendere minime le nostre probabilita di vittoria)

Il turno di gioco passa alternativamente da MIN a MAX e viceversa, e lalgoritmoetichetta i nodi dellalbero in modo da garantire per il computer la mossa migliore,assumendo che lavversario giochera al meglio, minimizzando la valutazione.

Figure 3: Albero di ricerca con le foglie valutate, e applicazione dellalgoritmo minimax

In fig. 3 si vede lapplicazione dellalgoritmo: partendo dalle foglie, sceglie per il padrela valutazione minore (in quanto il turno e dellavversario, e minimizzera le nostre possi-bilita di vincita). Applicandolo ricorsivamente, alla prossima iterazione il turno sara dimax, quindi sceglie la valutazione maggiore (perche e il computer che sceglie la mossa).

Si vede che viene scelta come mossa migliore la seconda, che mi assicura una valutazionefutura di 8, ma potrebbe diventare 10 a causa di un errore dellavversario. Viene invecescartata la mossa n. 3, anche se a causa di un errore dellavversario mi avrebbe portatouna valutazione maggiore, pari a 15. Ma il nostro algoritmo assume che lavversario siapreparato, e giochi bene.


9/22


Per contro, la complessita dellalgoritmo minimax e molto elevata: in termini temporali,e esponenziale e pari a

O(bm) (2)

dove b e il branching factor medio dei nodi (ovvero il numero di figli medio per ogninodo), mentre m e la profondita dellalbero (depth).

Per quanto riguarda la complessita spaziale, essa equivale alla complessita di una ricercain profondita, quindi lineare.

3.4.1 Potatura alfa-beta

Si puo ridurre la complessita dellalgoritmo minimax usando la potatura alfa-beta:sostanzialmente si potano parti dellalbero che non e necessario analizzare, in quantola soluzione finale sara la stessa indifferentemente da tale porzione.

Figure 4: Porzioni dellalbero che e possibile potare

Dalla fig. 4 si puo intuire perche i nodi cancellati sono ininfluenti ai fini del calcolodellalgoritmo minimax, e possono quindi essere potati. Quando si arriva a valutareil nodo foglia con valore 3, abbiamo gi a etichettato un nodo al livello superiore con ilvalore 8. Sappiamo che al turno successivo, ovvero per la valutazione del nodo radice,si scegliera il massimo, quindi nodi con valore minore di 8 non verranno considerati.Daltra parte, valutando il nodo foglia di valore 3, sappiamo che la valutazione del nodopadre sara il minimo dei suoi figli, quindi nel nostro caso sara un valore minore o ugualea 3. Ma siccome 3 e gia un valore piu piccolo di 8, sappiamo subito che questo sottoal-bero non verra certo scelto come mossa migliore. Possiamo quindi tagliarlo ed evitare

di analizzare gli altri figli.La miglioria portata dalle potature allalgoritmo minimax dipende ovviamente dallordinein cui analizziamo i nodi. Se avessimo analizzato per primo il nodo foglia di valore 8,avremo tagliato anche il sottoalbero con le foglie 2 e 5, senza bisogno di analizzarlo.Non e immediato poter ordinare i nodi senza introdurre ulteriore complessita, e anche ilcomportamento dellalgoritmo minimax con laiuto di alfa-beta risulta scoraggiante: lacomplessita temporale diventa


10/22

4 IMPLEMENTAZIONE 10

O

b

log(b)

m. (3)

3.5 Scelta della mossa migliore

Il lavoro e ormai finito: la scelta della mossa migliore e immediata. Basta infatti anal-izzare i figli del nodo radice, e considerare il figlio con valutazione massima. A questopunto andiamo a vedere quale mossa e stata applicata per generare quel figlio (tale in-formazione deve essere contenuta nel nodo figlio), e semplicemente la applichiamo.

4 Implementazione

Adesso che sono chiare le modalita di funzionamento degli algoritmi usati per lintelligenzaartificiale, vediamo come sono stati implementati nel linguaggio C#.

4.1 Struttura del programma

Il programma segue le regole della programmazione orientata agli oggetti (OOP). Lafigura 5 rappresenta linterconnessione delle varie classi definite nel software.

4.2 Implementazione della scacchiera

La soluzione piu ovvia per limplementazione della scacchiera e usare una matrice. Piuprecisamente, una matrice 8x8 di tipo Casella, quindi ogni elemento della matrice eunistanza della classe Casella. La scacchiera viene costruita settando opportunamentegli attributi delle istanze di Casella, a seconda della posizione dellelemento. Avremoquindi alcune caselle di tipo NERA, alcune di tipo FREE, alcune COMPUTER e altrePLAYER. Questi tipi sono definiti dalla struttura enumerativa casella tipo. Allo stessomodo, la struttura casella peso indica se la casella (in questo caso un pezzo di un gioca-tore) e una PEDINA oppure una DAMA.Questa matrice rappresentante la scacchiera e un attributo della classe Scacchiera; si eritenuto necessario definire una classe che contenesse la scacchiera in quanto durante la

costruzione dellalbero, ogni nodo avra come attributo una diversa istanza della classeScacchiera, ciascuna rappresentante la particolare configurazione di pezzi nella damiera.Alcuni dei metodi piu rilevanti della classe Scacchiera sono:

posizione futura: data una istanza di Casella e una direzione (mossa direction)ritorna la futura posizione della casella, in termini di row e col;


11/22


Figure 5: Ossatura del programma


12/22


mossa possibile multiple: data una istanza di Casella e una direzione, ritorna unalista di tipo Mossa che rappresenta tutte le mosse possibili a partire da quelladirezione. Sara analizzata in dettaglio piu avanti;

muovi multiple: data una istanza di Casella e una Mossa, effettua la mossa sullascacchiera;

n caselle player: ritorna il numero di pezzi del giocatore sulla scacchiera, per capirese il computer ha vinto.

4.3 Struttura dati Mossa

La struttura dati Mossa ha due attributi:

direzioni: una lista concatenata di tipo mossa direction che rappresenta la lista di

mosse semplici consecutive che compongono la mossa completa;

priorita: un intero che rappresenta il numero di pezzi catturati dalla mossa, usatoper decidere se la mossa puo essere effettuata oppure se esistono altre mosse conpriorita maggiore, quindi obbligatorie.

Per mossa semplice si intende uno spostamento di un pezzo (senza catture), o unacattura di un singolo pezzo. Per realizzare le catture multiple (consecutive), e stataquindi implementata una lista di mosse semplici (direzioni, di fatto) consecutive daeseguire. La struttura mossa direction e una struttura enumerativa con i valori NE, NO,SE, SO.

4.4 Mosse possibili

Analizziamo in dettaglio la funzione piu interessante che abbiamo descritto fino ad ora:il metodo mossa possibile multiple della classe Scacchiera. La funzione di costruzionedellalbero, che simula tutte le mosse possibili per tutte le caselle, chiama il presentemetodo per tutte le direzioni: NE, NO, SE, SO. Questo metodo ritorna un valorebooleano, true o false, a seconda che la mossa sia possibile o meno.La prima fase e controllare se con la mossa proposta si esce o meno dalla scacchiera. Incaso positivo, si va a vedere se la mossa e legale: per esempio, le pedine del computernon possono muovere verso Nord, cos come quelle del player non possono muovere verso

Sud, finche non diventano dame. Se la mossa risulta legale, si prova a vedere se la caselladi arrivo e libera. In tal caso, abbiamo trovato una mossa semplice (priorita = 0) e siesce.Se invece la mossa semplice non e possibile, perche la casella di arrivo e occupata, puopresentarsi possibilita di mangiare un pezzo: se la pedina nella posizione di arrivo ap-partiene allavversario, e la casella ancora successiva e libera. In questo caso, dobbiamocontrollare se sono possibili catture consecutive, richiamando ricorsivamente il metodo


13/22


in questione per tutte le direzioni possibili.

Questa funzione ritorna, insieme al valore booleano, una lista di mosse perche nel caso

di catture multiple la pedina potrebbe poter scegliere tra due o piu pedine da mangiareal secondo step, dopo la prima cattura. Queste sono mosse con la stessa priorita e quinditutte legali.

4.5 Struttura dellalbero di ricerca

Lalbero di ricerca e implementato come un albero generico. La classe Tree ha sola-mente la funzione di rappresentare il nodo radice dellalbero. Ogni nodo dellalbero e unelemento di tipo TreeNode, una classe che ha come attributi

n figli: un intero che rappresenta il numero di figli del nodo;

profondita: un intero che rappresenta la profondita del nodo;

padre: link al nodo padre;

fratello dx, fratello sx: link ai nodi fratelli;

primofiglio: link al primo figlio dellalbero (il primo figlio dellalbero e lunico figlioa non avere fratello sinistro);

valutazione: un intero (anche nullo) che rappresenta la valutazione associata alnodo (configurazione della scacchiera);

value: unistanza della classe Scacchiera, ovvero la configurazione della scacchiera

legata al nodo;

casella: unistanza della classe Casella, che rappresenta il pezzo della damiera sulquale si e effettuata la mossa;

mossa: un elemento di tipo Mossa, rappresenta la mossa effettuata sulla casella dicui sopra, a partire dalla configurazione della scacchiera del nodo padre;

Le classi Tree e TreeNode contengono tutte le funzioni, richiamate dalla classe IDamaEngine,necessarie per la costruzione dellalbero, la valutazione dellalbero, la potatura alfa-beta,la scelta della mossa migliore, e la ricerca di quiescenza. Si tratta semplicemente dimetodi in grado di lavorare ricorsivamente sulla struttura ad albero creata. In partico-

lare, per la costruzione dellalbero e stata creata la funzione AddFiglio, per la potatura lafunzione DeleteNode, mentre la ricerca di quiescenza ha richiesto la scrittura del metodoAddSottoAlbero. Sono metodi intuitivi, di cui viene omessa la descrizione dettagliata.Sono inoltre presenti funzioni per il calcolo della profondita dellalbero (TreeNodeDepth),per la valutazione dei nodi a profondita depth (NodeValuta) e la funzione che realizzalalgoritmo minimax, NodeValutaMinMax, lunica che merita una descrizione dettagliata,lasciata al capitolo Minimax e potatura alfa-beta.


14/22


4.6 Classe IDamaEngine

IDamaEngine e la classe che si occupa della strategia di gioco del computer. Di fatto e

la classe che comunica con la parte grafica del programma, come spiegato in dettagliopiu avanti. Essa e definita come partial class, ovvero come classe parziale, dove laltraparte della classe e chiamata Euristiche.Gli attributi sono, ovviamente, una istanza della classe Scacchiera (master), e altre carat-teristiche definite dallutente: la profondita massima dellalbero che verra creato (dMax),la funzione euristica scelta ( funzione euristica), e due variabili booleane (quiescenza equiescenzaricorsiva).

Quando e il turno del computer, la parte grafica del programma invoca la funzionealfabetaPruning che si occupa di costruire lalbero, valutarlo, applicare la verifica di

quiescenza, applicare lalgoritmo minimax ed effettuare la mossa. Vediamo questi passiin dettaglio.

4.6.1 Costruzione dellalbero di ricerca

Per la costruzione dellalbero, viene chiamata la funzione costruisci albero con il parametromaster, ovvero la scacchiera al momento attuale. Tale funzione inizializza lalbero,costruendo il nodo radice proprio con listanza master. Poi chiama la funzione ricor-siva costruisci albero.Inizialmente si cerca la mossa possibile con la priorita maggiore; successivamente, siaggiunge un figlio per ogni mossa legale (quindi si aggiunge un figlio per ogni mossa

possibile di priorita non minore alla priorita massima calcolata). Per ogni figlio creato,si chiama ricorsivamente la stessa funzione, fino a quando non si raggiunge la profonditamassima stabilita.

Lalbero viene poi valutato, applicando alle foglie una funzione di valutazione, tra quelledescritte nel capitolo successivo.

4.6.2 Funzioni di valutazione

Abbiamo gia parlato di funzioni di valutazione in quanto euristiche, e della loro impor-

tanza ai fini della strategia di gioco della macchina. Nel software sono state implementatequattro diverse funzioni di valutazione:

1. Peso Pedine

2. Peso + Posizione

3. Spettacolo


15/22


4. Fully Guarded

La prima funzione di valutazione, Peso Pedine, valuta una configurazione della scacchieraignorando le posizioni delle pedine, ma contandone solo il numero. Alle dame e attribuitoun peso doppio rispetto a quelle delle pedine; i pezzi appartenenti al computer vengonosommati, mentre quelli appartenenti al player vengono sottratti dalla valutazione. Gio-cando con questa strategia, ci si accorge che e un po troppo semplicistica; per esempio,il programma ci permettera facilmente di avvicinarci a dama se gli permetteremo di farcicatturare una pedina.

La funzione Peso + Posizione include nel computo anche un valore legato alla posizionedelle pedine. Il peso dei pezzi viene moltiplicato per il quadrato dellindice relativo allariga in cui si trova il pezzo. In questo modo si preferiscono configurazioni in cui le ipezzi del computer vanno verso dama, e allo stesso modo si preferisce che le pedine del

computer non si avvicinino troppo alla nostra base. Inoltre viene attribuita una penalitaalle dame che stanno sui bordi, per incitarle a porsi in mezzo alla damiera, per renderela strategia piu aggressiva. Anche questa funzione di valutazione non ci assicura buonegiocate: tende a scoprire velocemente le sue posizioni di base, per andare verso il centrodella damiera, rendendo cos il player piu facilitato a fare dama.

Per realizzare la terza funzione di valutazione, Spettacolo, sono state utilizzate al-cune considerazioni che sono state documentate in rete. Lidea sfrutta la geometriadella damiera, che presenta delle regioni piu facilmente proteggibili contro gli attacchidellavversario ed altre piu vulnerabili. La damiera puo essere vista come divisa in quat-tro aree: langolo in alto a destra e quello diametralmente opposto in basso a sinistra

vengono definiti cantoni, mentre i due rimanenti sono definiti biscacchi.

Figure 6: Biscacchi e cantoni.


16/22


Un giocatore riesce facilmente a difendere il proprio cantone, infatti lavversario non hamodo di sfondare la base, diversamente la parte del biscacco e piu facilmente sfondabileper un avversario sacrificando una propria pedina e permettendo allaltra di andare a

fare dama. In base alle osservazioni precedentemente fatte, si puo decidere di utilizzarevarie strategie di gioco. In attacco di solito si preferisce dirigere la propria azione versoil biscacco avversario, che presenta piu possilita di sfondare la linea base avversaria edi andare a dama. Per quanto riguarda il gioco in difesa, dato che anche il propriobiscacco puo essere facilemente attaccato dallavversario, lidea e di non far avanzare ipezzi da questa parte e di muovere quelli del cantone. Per implementare tale strategia, siassegna ad ogni area un peso in modo che il secondo ed il terzo quadrante abbiano pesomaggiore mentre il primo ed il quarto peso minore. In questo modo, quando si eseguela valutazione, si obbligano le pedine che sono allinterno di tale area di rimanervici equelle che sono in aree con peso minore di dirigersi verso le altre. Per permettere allepedine di muoversi allinterno delle aree, si e deciso di dare alle caselle dei quadranti dei

pesi crescenti in base allaumetare della distanza.Provando ad implementare la strategia come e stata sopra descritta, ci si accorge chee troppo difensiva e che pertanto, arriva difficilemente a fare dama. Per questo motivosi e pensato di modificare la funzione di valutazione e di suddividerla in due fasi: nellafase iniziale si e implementata la strategia precedentemente descritta, mentre nella fasefinale si promuovono le pedine che vanno a dama. Il test per disinguere la fase inizialeda quella finale controlla se e presente una dama oppure se sono rimaste poche pedine.Inoltre si privilegiano ulteriormente le configurazioni in cui il giocatore ha la mossa, ossiase il numero di coppie di pedine che distano luna dallaltra di un numero pari di casellee dispari allora il giocatore che ha il turno e avvantaggiato.Queste considerazioni, che sembrano assolutamente vincenti, nella pratica si sono ver-

ificate molto banali e facilmente battibili. Un motivo del perche di questa situazione sipuo ritrovare nella difficolta di riuscire ad associare i giusti pesi ai parametri delle fun-zioni di valutazione. Un peso sbagliato rischia o di dar troppo peso ad alcuni parametripenalizzandone altri o viceversa, e si puo verificare che il risultato ottenuto non e quellodesiderato.

Per la realizzazione della quarta funzione di valutazione si e utilizzata la documentazionedi unaltra strategia di gioco che permette di giocare in attacco, mantenendo comunqueuna buona difesa della propria linea di partenza. Questa idea e stata suggerita da unaprima considerazione banale e strategica che spesso viene utilizzata in una partita. Se sitiene la propria linea di base piena, che in termini tecnici si dice avere una fully guarded

back rank, non si permette allavversario di andare facilmente a dama, a meno che nonsacrifichi qualche pezzo.Mantenendo la base coperta e spostando tutte le pedine verso la dama, si rischia perodi creare una fascia di pedine che alle spalle presentano delle caselle vuote, permettonofacilmente lavversario di attaccare e mangiarle. Per questo motivo si e realizzata unastrategia piu sicura, basata su tale concetto, Federazione Italiana Dama. In questa siafferma che i pezzi devono muoversi in formazione compatta, solidamente piantata alla


17/22


base e con punte avanzate ben appoggiate. Questa frase riassume il punto centrale dellastrategia che e stata realizzata: si e provato a muovere le pedine, facendole avanzare versodama in formazione offensiva, ma cercando nel contempo che tale formazione fosse ben

salda alla base, cos da poter sfondare le linee avversarie, mantenendo le proprie spallecoperte. Per realizzare la strategia, si e costruito una funzione per il calcolo del supporto,ossia delle pedine che si trovano alle spalle di altre. La funzione scansiona la damieracercando se nelle posizioni dietro la pedina selezionata lungo le diagonali, compaionopedine dello stesso colore e se questo accade continua a controllare allindietro ricorsi-vamente fino al raggiungimento della base. Ogni volta che trova una tale situazione peruna propria pedina aumenta il valore della funzione di valutazione, privilegiando i casi incui si presenta una posizione delle proprie pedine che ricorda una forma a piramide conla base ben saldata sulla linea di base. In tal modo si promuovono quelle configurazioniben saldate alla base, penalizzando le altre. Inoltre per ogni pedina si e aggiunto unvalore in base alla posizione occupata allinterno della damiera, privilegiando quelle piu

vicine alla dama, e si sono penalizzate le configurazioni che prevedevano le dame vicinoai bordi laterali della scacchiera, preferendo che ricoprissero ruoli centrali piu offensivi.

In tutte le funzioni si aggiunge una piccola quantita aleatoria, per evitare che il pro-gramma esegua sempre la stessa mossa in caso di mosse con identica valutazione.

4.6.3 Verifica di quiescenza

Una volta valutate le foglie dellalbero, per ogni foglia si fa la verifica di stato quiescente.Se ne occupa la funzione is quiescent, che di fatto, data la foglia da verificare, costruisce

un albero di profondita 2 a partire da quella foglia, usando proprio la stessa funzionecostruisci albero. Per prima cosa, si valutano le foglie di questo albero. A questo punto,viene usato lalgoritmo minimax con potatura alfa-beta (lo stesso di cui parleremo trapoco) per valutare tutti i nodi dellalbero. Se la valutazione del nodo foglia cos calcolata,si discosta molto (negativamente) dalla precedente valutazione associata al nodo fogliadi cui stiamo verificando la quiescenza, si dice che la foglia non e uno stato quiescente.In questo caso, possiamo decidere di richiamare (ricorsivamente) la stessa funzione, peresplorare ancora piu in profondita lalbero creato, nella speranza di arrivare a configu-razioni stabili (quiescenti).Fatto cio, se non abbiamo trovato configurazioni quiescenti, siamo costretti ad appen-dere lalbero creato allalbero di ricerca creato inizialmente (con la funzione AddSot-

toAlbero della classe Tree), aumentandone quindi la profondita totale.La decisione della quiescenza o meno di una configurazione dipende strettamente dallafunzione di valutazione utilizzata. Sono state definite quindi tante funzioni per prenderequesta decisione quante sono le euristiche implementate.

La verifica di quiescenza, e lulteriore seconda verifica sono opzionali, a seconda dellascelta del giocatore.


18/22


4.6.4 Minimax e potatura alfa-beta

Una volta noto lalbero di ricerca, compresa la verifica

La funzione che valuta tutti i nodi dellalbero, a partire dalle foglie fino alla radice, sec-ondo lalgoritmo minimax fa parte della classe Tree: NodeValutaMinMax. Tale funzioneviene invocata con un parametro, esattamente la profondita dei nodi che dobbiamo val-utare. Allinterno del metodo alfabetaPruning della classe IDamaEngine, quindi, vienechiamata questa funzione per ogni valore di depth, partendo dalla profondita delle fogliefino al valore uno, in modo da valutare tutto lalbero.NodeValutaMinMax segue alla lettera la teoria dellalgoritmo minimax e della potaturaalfa beta, gia illustrata allinizio della relazione.

4.6.5 Effettuare la mossa

Adesso che lalbero e totalmente etichettato, basta analizzare tutti i figli del nodo radice(ovvero tutti i nodi a profondita uno). Consideriamo quindi il nodo che ha la valutazionemaggiore; da tale nodo estraiamo la mossa associata ed il gioco e fatto. Basta richia-mare la funzione muovi multiple sulla scacchiera, passando come parametro la mossa inquestione.

Tale funzione si occupera di seguire in dettaglio le direzioni proposte dalla mossa, elim-inando i pezzi catturati e riconfigurando opportunamente le caselle della scacchiera. Inseguito viene richiamata la procedura che si occupa di visualizzare la mossa effettuata,quindi di aggiornare la scacchiera sul video.

4.7 Grafica e gestione degli eventi

La finestra dellapplicazione permette limpostazione di alcuni parametri del softwarein qualsiasi momento del gioco. E possibile scegliere la strategia (di fatto la funzionedi valutazione euristica), la profondita dellalbero di ricerca (ovvero il numero di mossein avanti da prevedere), lattivazione della verifica di quiescenza e lattivazione dellaseconda iterazione della stessa verifica.

La prima mossa e del giocatore. E possibile trascinare solo le pedine che hanno mosselegali, e tale pedina puo essere lasciata su una casella libera (bianca) solo se la mossa coseffettuata e permessa. Questa operazione si chiama drag&drop. E possibile effettuarecatture multiple, semplicemente eseguendo le catture una dopo laltra.

Quando la pedina viene rilasciata sulla casella di arrivo, levento associato chiama unafunzione che si occupa di notificare la mossa alla classe IDamaEngine, che provvede aripercuotere le modifiche sulla matrice che rappresenta la scacchiera. Allo stesso modo,quando il computer effettua una mossa vengono visualizzati degli effetti per rendere


19/22


Figure 7: Impostazioni del programma.

Figure 8: La casella di arrivo viene evidenziata, se la mossa e legale.


20/22

5 CONCLUSIONI 20

Figure 9: Presa multipla effettuata dal computer.

chiara la mossa scelta dal computer.Il software notifica la fine della partita con un semplice messaggio allutente, tramite unoggetto detto MessageBox.

5 Conclusioni

Per ottenere giocate sensate da parte del computer, e necessario attivare la verifica diquiescenza a due livelli, con una profondita dellalbero di ricerca almeno pari a 3 (difatto, lalbero sara in questo caso profondo 6). La strategia che sembra essere la miglioree lultima tra quelle analizzate, Fully Guarded. Con questi parametri, la risposta delprogramma sara molto lenta, non solo a causa delle dimensioni dellalbero da valutare,ma anche a causa dellanalisi delle mosse possibili. Ce da dire che, analizzando le mossepossibili, in molti casi lalbero di ricerca generato e significativamente ridotto, il cheporta la valutazione ad essere estremamente veloce.

Ricordando la regola che in caso di piu mosse possibili si debba scegliere quella chegarantisce il numero massimo di pezzi catturati, si potrebbe pensare che in realt a non e

necessario analizzare la legalita delle mosse prima della costruzione dellalbero, ma sem-plicemente la ricerca dellottimo porterebbe a scegliere la mossa che garantisce il numeromassimo di pezzi catturati. Questo e estremamente falso, in quanto:

1. a causa della profondita dellalbero di ricerca, potrebbe essere conveniente noneseguire una cattura per migliorare la funzione obiettivo nelle mosse successive;

2. potrebbe essere conveniente non eseguire una cattura per mantenere la pedina in


21/22

5 CONCLUSIONI 21

posizione favorevole, nel caso in cui la funzione di valutazione consideri anche laposizione dei pezzi.

5.1 Stato dellarte sui programmi risolutori della dama

La prima grande impresa relativa allintelligenza artificiale associata al gioco della damarisale al 1952, quando Arthur Samuel dellIBM sviluppo un programma per la dama cheapprese la sua funzione di valutazione giocando da solo per migliaia di volte.Nel 1989, allUniversita di Alberta, sotto la coordinazione del prof. Jonathan Schaeffer,un gruppo di studiosi comincia a concentrarsi sul problema della dama. Nasce quindiChinook, che vince gli U.S. Open nel 1992. Il programma usa, tra laltro, una ricercaalfa-beta combinata con un database di soluzioni perfette per tutte le posizioni con seipezzi. Nel 2004 vince il campionato del mondo, e nel 2006 il programma e stato costretto

al ritiro per manifesta superiorita.Nel 2007, finalmente, lequipe di studiosi ha affermato di aver risolto il gioco della dama,con il loro programma: Chinook non puo perdere, quindi qualsiasi umano provi a sfidarlo,puo al massimo pareggiare.


22/22

REFERENCES 22

References

[1] Universita degli Studi di Padova, http://www.math.unipd.it/ mgelain/dama/, .

[2] Federazione Italiana Dama, http://www.federdama.it, .

[3] Russel e Norvig, Intelligenza Artificiale: un approccio moderno, Prentice Hall Inter-national, 1995.

Date post:	30-May-2018
Category:	Documents
Upload:	ciaocrossclub-documents
View:	218 times
Download:	0 times

IntellidAma

Documents