Teoria dei Giochi

Dama Italiana

 3. Implementazione del gioco

Il software preso come base di partenza implementava le regole della dama internazionale mentre, volendo realizzare il gioco utilizzando le regole della dama italiana, è stata necessaria una rivisitazione completa del codice originale. Pertanto, del codice di Victor Hung e di Ha Huh è rimasta solamente in parte l'implementazione dell'applet e la logica di gestione degli eventi di input dell'utente; tutti gli altri metodi sono stati quasi interamente cambiati e adattati alle nuove esigenze. Di seguito verrà riportata un'analisi dell'implementazione della dama, ove verranno indicate le parti innovative e quelle che sono state mantenute del codice originale.

La struttura della nuova versione del gioco riflette quella del codice originale. Sono state mantenute le quattro classi presenti nel vecchio codice e anche le loro funzionalità non sono state cambiate.

  • Checkers: ricopre un ruolo centrale nell'organizzazione del gioco, infatti in questa classe viene realizzata sia la parte grafica, attraverso il costruttore della classe, sia la gestione del gioco, con il metodo switch_toMove. Per quest'ultimo si veda la Sezione 3.1.
  • Board: si occupa della gestione del modulo umano, ossia permette ad un utente umano di giocare ed eseguire la mossa scelta quando è il proprio turno. In questa classe il metodo principale è mouseDown, analizzato in Sezione 3.5.
  • Engine: si occupa della gestione del modulo di intelligenza artificiale. In questa classe vari metodi come MiniMax, con i metodi ausiliari maximize, minimize e quiescent, e le funzioni di valutazione permettono di ricercare la mossa ottima che deve essere eseguita. (Sezione 3.6)
  • Move: permette di calcolare le mosse che sono possibili, con i metodi generate_moves e cattureMultipli, e di eseguirle mediante il metodo eseguiMossa. Move utilizzata da Checkers, ed anche da Board e da Engine. (Sezione 3.4)

Di tali classi sono stati modificati i metodi utilizzati per realizzare le funzionalità, come si potrà osservare nelle successive sezioni. In alcuni casi si è reso necesario eliminare vecchi metodo e aggiungerne di nuovi. In particolare, per quanto riguarda il modulo di intelligenza artificiale, sono stati implementate nuove tecniche di ricerca e nuove funzioni di valutazione.

Accanto alle precedenti classi, ne sono state realizzate due nuove allo scopo di creare un'opportuna struttura dati che gestisse le mosse possibili, facilitando la selezione di quelle permesse dalle regole.

  • InfoMossa: realizza la struttura di una mossa, con le coordinate che la identificano e una etichetta che ne descrive la natura. (Sezione 3.2)
  • MoveScheduler: fornisce i metodi per aggiungere le mosse calcolate alla struttura dati (add) e permettere di ritornare la lista di tutte e sole le mosse possibili (getMossePossibili). (Sezione 3.3)

In Figura 3.1 si nota il diagramma d'uso delle classi.


Figura 3.1: diagramma d'uso delle classi

3.1  La classe Checkers

Come accennato precedentemente, la parte grafica è stata quasi interamente mantenuta. Sono stati cambiati i colori dei pezzi e la disposizione delle finestre dei menu, per la selezione del tipo di giocatore, del livello di profondità dell'albero di ricerca e del tipo di funzione da utilizzare nel caso in cui si utilizzi come giocatore il computer.

Anche la struttura del metodo switch_toMove non è stata cambiata, si sono aggiunte solo le istruzioni che permettessero la gestione della patta, non realizzata nel vecchio codice ed è stata modificata la stuttura dati nella quale viene salvata la mossa da eseguire. La nuova struttura dati creata verrà introdotta in seguito e analizzata in Sezione 3.2, qui verrà spiegato il funzionamento del metodo switch_toMove.

Ogni partita si sviluppa in vari turni che si alternano, nei quali o il giocatore bianco o quello nero devono eseguire la propria mossa. La gestione di tali turni è stata realizzata nel metodo switch_toMove, che pertanto ricopre un ruolo centrale all'interno del gioco. switch_toMove ha il compito di determinare di chi è il turno, se del giocatore bianco o di quello nero e, dopo aver determinato se il giocatore è in modalità computer o umana, di predisporre il gioco in modo da invocare agli opportuni metodi per la gestione di quello specifico turno. Inoltre il metodo deve controllare alla fine di ogni turno lo stato del gioco, ossia se si verifica una situazione nella quale uno dei due giocatori ha vinto, il caso di patta oppure nessuno dei precedenti. Il metodo riesce a determinare lo stato del gioco controllando se per il prossimo giocatore a cui spetta il turno ci sono ancora mosse possibili da eseguire e in tal caso controlla se il contatore per la patta ha raggiunto il numero massimo di mosse possibili prima di verificare la situazione di equilibrio. Se ambedue questi test risultano fallire, allora viene continuato il gioco, altrimenti switch_toMove segnala la vittoria del giocatore o la patta e termina la partita.

Come precedentemente accennato, vi sono due tipologie di giocatore, quella umana e quella del computer. Dato che ognuna ha funzionalità diverse, per gestirle si è reso necessario realizzare due moduli separati e specifici, richiamati opportunamente da switch_toMove. Un modulo si occupa della gestione delle azioni nel caso in cui stia giocando un giocatore umano, discusso in Sezione 3.5, mentre l'altro trova la mossa migliore che il computer deve fare per giocare in modo ottimo, riportato in  Sezione 3.6.

Nel caso in cui stia gestendo il modulo di intelligenza artificiale, switch_toMove utilizza un metodo ausiliario per eseguire la mossa dopo che gli è stata ritornata quella scelta dal computer. Tale metodo chiamato eseguiMossa si trova all'interno della classe Move (si veda la Sezione 3.4.3) ed è stato realizzato in due versioni. Qui viene utilizza quella che permette di eseguire le mosse ritornate dal computer, ricevendo in input la board di partenza e la sequenza con la mossa da eseguire e aggiornando la board con la nuova configurazione di gioco.

Sia per il giocatore umano che per il computer, si rende necessario calcolare le mosse che possono essere eseguite in modo tale da rispettare tutte le regole elencate e discusse al Capitolo 1. Nel caso in cui si stia considerando il giocatore umano, si devono calcolare le mosse possibili per non permettergli di eseguire quelle che altrimenti infrangerebbero le regole. Queste sono precalcolate in switch_toMove prima di invocare il modulo di gestione del giocatore umano. Nel caso del computer, per ricercare la mossa migliore, si devono prima calcolare tutte le mosse possibili tra le quali poter scegliere. Per permettere il calcolo di tutte e sole le mosse permesse, si è creata una nuova struttura dati, non utilizzata nel codice originale, che permettesse di classificare opportunamente le mosse, e rendesse più facile la ricerca delle sole possibili o obbligate.

L'analisi della struttura è riportata in Sezione 3.2, mentre i metodi principali che si occupano della ricerca delle mosse possibili sono riportati nelle Sezioni 3.3, 3.4.1 e 3.4.2.

3.2  La classe InfoMossa

Nel Capitolo 1 si può notare che vi sono molte regole che determinano quali, fra le mosse considerate legali per un giocatore, sono realmente possibili. Ad esempio fra una mossa semplice ed una in cui si può mangiare è obbligatorio eseguire la seconda, così come fra una cattura singola ed una doppia, si deve dare precedenza a quella che permette di mangiare più pezzi. Inoltre, oltre che in base al numero di pezzi da mangiare, occorre dare diversa priorità anche in base a chi esegue la mossa, se una dama o una pedina, e a quali pezzi e in quale ordine vengono mangiati.

A priori non si può conoscere quali siano le mosse legali e quali fra queste abbiano priorità maggiore, solamente in seguito ad una scansione completa della damiera è possibile ottenere tali informazioni. Per questo motivo si è deciso di creare una struttura dati nella quale salvare tutte le mosse legali, ordinandole in base alla loro priorità e fra queste ritornare tutte quelle con priorità maggiore.

La classe InfoMossa è stata creata per la gestione di una singola mossa, mentre nella classe MoveScheduler si è costruita la struttura per contenere tutte le mosse, come verrà spiegato in Sezione 3.3.

Una singola mossa è stata pensata come un oggetto identificato dalle coordinate che indicano la sequenza di passi per eseguirla e da una etichetta che descrive il tipo di mossa, in base ad una convenzione stabilita a priori. Nel codice, tali variabili prendono il nome rispettivamente di mossa e sequenza.

Per salvare le coordinate, dovendo memorizzare non solo mosse semplici o catture singole, ma anche catture multiple, si è reso necessario salvare tutte le caselle che fisicamente vengono toccate dal pezzo quando si muove sulla damiera. Ad esempio, nel caso in cui si debba eseguire una cattura multipla che si sposti dalla cella di coordinate (5,1) a quella di coordinate (1,5) passando per la (3,3), nella mossa vengono salvate in ordine le tre coppie di coordinate; in base alla convenzione introdotta nella Sezione 1.2 risulta ((5,1), (3,3), (1,5)). Si è utilzzato un vector contente in ogni cella array di dimensione due. In ogni array vengono salvate nell'ordine le coordinate x ed y della casella ed il vettore serve per salvare in ogni posizione una coppia di coordinate relative ad una casella, rappresentando alla fine la mossa.

La necessità di salvare tutti i passi di una mossa è richiesta per eseguire una facile gestione dell'aggiornamento della board in seguito all'esecuzione della mossa. Infatti, specificando solamente le coordinate di partenza e di arrivo di una mossa e tralasciando quelle intermedie, nel caso di catture multiple non si riesce a ricavare con certezza il percorso da seguire e si rischia di non sapere quali pezzi avversari vengono realmente mangiati. Ad esempio, se si desse solo la coppia di coordinate ((6,4),(2,4)) per indicare una mossa, non si saprebbe se si stanno mangiando i pezzi posizionati nelle coordinate (5,3) e (3,3), oppure (5,5) e (2,5).

L'etichetta (stringa) associata ad ogni mossa permette di capire il tipo di mossa cui si riferiscono le coordinate, classificandola in base al numero di catture che vengono eseguite, a chi le esegue, a quali pezzi nell'ordine vengono mangiati e quante dame vengono catturate. L'etichette così costruite permettono di essere ordinare sfruttandone l'ordine lessicografico, e di essere organizzate in base alla priorità di scelta. Di seguito verrà discussa la convenzione utilizzata per creare le stringhe in modo che l'ordine lessicografico che si ottiene rifletta la priorità imposta dalle regole.

Le regole che devono essere rispettate sono: a parità di mangiate, la dama deve avere priorità sulla pedina, pertanto sarà obbligata ad eseguire la mossa; si deve eseguire la mossa ove c'è il maggior numero di dame da mangiare; nell'ordine si devono scegliere le mosse dove si mangia prima una dama. Per realizzare queste tre richieste, si è deciso di utilizzare una stringa del tipo:


sequenza=pezzo+nDamePrese+sequenzaCatture

ove con la notazione precedente si intende:

  • pezzo: indica il tipo di pezzo che deve eseguire la mossa. Viene realizzato con un char, ove d indica che chi si muove è la dama, mentre p per indicare la pedina.
  • nDamePrese: per indicare il numero di dame che devono essere mangiate in quella cattura multipla.
  • sequenzaCatture: una stringa ordinata di caratteri, ove il carattere in posizione i_esima della stringa, indica che il tipo del pezzo i_esimo che deve essere mangiato.

Associando ad ogni mossa una descrizione del suo tipo, è possibile ordinarle in ordine lessicografico e ritornare solamente tutte le mosse con il numero maggiore di mangiate, che presentano la stessa etichetta. Ad esempio se si hanno tre mosse con le rispettive etichette p0pp, d0pp e d0pp, l'ordine lessicografico è


d0pp = d0pp < p0pp

e pertanto le mosse obbligate tra le quali poter sceglire, che devono essere ritornate, sono quelle associate alle prime due etichette.

Per poter sfruttare l'idea dell'ordine lessicografico si devono fare due considerazioni. In primo luogo, dato che si vogliono privilegiare le mosse che mangiano più dame, in base a quanto scritto, si rischia che la stringa d1dp venga privilegiata rispetto d2dd. Pertanto per riuscire ad utilizzare l'ordine lessicografico è necessario rovesciare tale significato e al posto di nDamePrese porre, 99-nDamePrese. Al posto di 99 si poteva scegliere 12, che indica il numero massimo di dame per ogni giocatore, che possono essere presenti contemporaneamente in una partita. Infatti essendoci 12 pedine iniziali, si può verificare nel caso migliore che tutte divengano dame, ma non di più. Solamente per convenzione si è deciso di prendere 99, il più grande numero a due cifre rappresentabile in base dieci.

La seconda considerazione richiede di rivedere l'etichetta utilizzata per classificare le mosse semplici che si ottiene utilizzando la convenzione precedentemente descritta. La convenzione precedente impone, nel caso in cui vi siano solo mosse semplici che possano essere eseguite sia da pedine che da dame, che possano eseguire delle mosse solamente le dame. Infatti classificando le mosse si avranno etichette del tipo d99, p99, e considerando l'ordine lessicografico, questo impone di ritornare sole le mosse con le dame. In realtà la dama ha priorità sulla pedina solamente nel caso in cui si verifichino delle catture singole o doppie, ma non nel caso di mosse semplici, pertanto in quest'ultimo caso si apporta una modifica all'etichetta non distinguendo il tipo di pezzo che esegue la mossa ma indicando semplicemente p99 per tutti i pezzi.

Dopo aver definito la struttura di base per la memorizzazione di una mossa, la si può utilizzare per creare una opportuna struttura che sia in grado di memorizzare e gestire tutte le mosse possibili di ogni turno. Questo viene realizzato nella classe MoveScheduler descritta nella prossima Sezione 3.3.

3.3  La classe MoveScheduler

La classe MoveScheduler è stata creata per eseguire la memorizzazione e la gestione delle mosse. Tale classe permette di gestire l'ultima regola richiesta: sono obbligatorie le mosse nelle quali si eseguono il massimo numero di catture.

Per implementare tale regola, l'idea utilizzata richiede di classificare le mosse in base al numero di catture che effettuano e di prendere alla fine del raggruppamento il gruppo associato al numero maggiore di catture. Successivamente sfruttando l'etichetta di ogni mossa di tale gruppo, come discusso in Sezione 3.2, si soddisfano anche le altre regole.

Per realizzare tale idea si è utilizzato un array con tredici posizioni: 12+1. 12 perchè è il numero massimo di prese, infatti questo rappresenta il caso estreno nel quale si riescano a mangiare tutti i pezzi dell'avversario;più una entrata che viene utilizzata per salvare le mosse semplici. L'array è stato costruito in modo da contenere all'entrata zero il gruppo delle mosse semplici, alla prima quello delle catture singole,... così fino alla posizione tredicesima, nella quale si salva l'eventuale gruppo con dodici catture. I gruppi di mosse caratterizzati dallo stesso numero di catture, sono realizzati attraverso un vettore ove ogni entrata contiene una mossa. La struttura che ne risulta è un array di tredici posizioni, ove ogni posizione, i può contenere un vettore che a sua volta memorizza le mosse ove vengono eseguite i catture. All'interno della classe, tale struttura viene realizzata nella variabile sequenzePerCattura.

Dopo aver opportunamente popolato la struttura, mediante il metodo add, con tutte le mosse possibili, è facile ricavare quelle obbligate, scorrendo dalla fine all'inizio l'array, fino a quando non si trova un'entrata non vuota. Se questo non accade significa che non ci sono più mosse possibili ed in tal caso il metodo switch_toMove si occuperà della gestione della conclusione della partita. Il metodo getMossePossibili si occupa dell'estrazione delle mosse obbligate dalla struttura. In primo luogo scorre l'array estraendo il gruppo associato al numero maggiore di catture multiple, successivamente ordina tale gruppo e ritorna tutte le mosse che si trovano nelle prime posizioni del vettore e che hanno la stessa etichetta.

Questa la struttura dati alla base della ricerca delle mosse per salvarle e per scegliere le mosse possibili. In Figura 3.2 è riportato uno schema di tale struttura. Viene utilizzata all'interno del metodo generate_moves e cattureMultiple, della classe Move, trattati nelle Sezioni 3.4.13.4.2, per salvare le mosse possibili.

Figure 3.2: Schema della struttura dati utilizzata per salvare e ricercare le mosse permesse dalle regole.

3.4  La classe Move

Questa classe ricopre un ruolo intermedio tra le altre classi; infatti esegue una funzione fondamentale per la realizzazione del gioco, ossia la ricerca di tutte e sole le mosse che sono ammesse, in base alle regole imposte, e la realizzazione di tali nella damiera.

Quando i metodi per il modulo umano devono controllare se la mossa che si desidera fare è permessa, o il modulo di intelligenza artificiale deve scegliere la mossa migliore da eseguire, in ogni caso devono essere prima richiamati i metodi generates_moves e se necessario cattureMultiple, per ricavare tutte e sole le mosse possibili. Successivamente, dopo che la mossa da eseguire è stata scelta, sia per il giocatore umano sia per quello artificiale, si deve eseguire la mossa sulla damiera, aggiornando la configurazione di gioco e questo viene reso possibile mediante l'invocazione dell'opportuna versione del metodo eseguiMossa.

Di seguito vengono analizzati i tre metodi prinicipali della classe Move: in Sezione 3.4.1 si trova un'analisi di generate_moves; in Sezione 3.4.2 viene discussa l'implementazione di cattureMultiple e in Sezione 3.4.3 sono riportate le due versioni del metodo eseguiMossa.

3.4.1  Metodo: generate_moves

Il metodo generate_moves viene invocato ogni volta si renda necessario calcolare le mosse possibili, sia per la parte umana che per il modulo di intelligenza artificiale. L'idea della ricerca delle mosse è stata ripresa dal codice originale e sono state apportate solo alcune modifiche dovute al diverso modo di gestire le mosse possibili. Si scorre l'intera damiera e in ogni casella legale, nella quale compare un pezzo del colore del giocatore a cui spetta il turno, si valutano tutte le mosse possibili, salvandole in base al loro tipo nella struttura dati. Per calcolare tutte le mosse che possono essere eseguite da un pezzo, si suppone inizialmente che sia una pedina, controllando se sulle caselle adiacenti che si trovano lungo la diagonale, nel verso corretto, c'è la possibilità di muoversi o mangiare. Quindi successivamente si eseguono le stesse verifiche nel caso in cui sia una dama e possa anche tornare indietro.

Si supponga di aver selezionato un pezzo che si trova alle coordinate (i,j) della damiera e di dover procedere con il calcolo di tutte le mosse che si possono fare con tale pezzo. Muovendosi lungo il verso consentito, che viene chiamato verso e può assumere valori 1 e -1, determinato dal colore del pezzo selezionato, si controlla se da quella casella è possibile eseguire delle catture. Per far questo si guardano le caselle di coordinate (i+2 ·verso, j-2) e (i+2 ·verso, j+2). Per ognuna delle due caselle, si possono verificare tre casi: che la cassella non sia dentro la damiera, oppure che sia piena o che sia vuota. Nei primi due casi si conclude che non ci sono catture e si controlla se si può almeno eseguire una mossa semplice muovendosi nelle caselle (i+verso, j-1) o (i+verso, j+1). Nel terzo caso si deve controllare il contenuto della casella che si trova tra le due considerate: se qui è presente un pezzo del colore opposto e che si può mangiare con il pezzo selezionato, allora si inizia a costruire la cattura e si richiama la funzione cattureMultiple per controllare se eventualmente si tratta di una cattura multipla. Altrimenti se la casella contiene un proprio pezzo, significa che è occupata e non si può eseguire nemmeno una mossa semplice, se è vuota, si salva nella struttura dati come mossa semplice.

Nel caso in cui il pezzo selezionato sia una dama, si esegue quanto sopra descritto, considerando anche il verso opposto.

3.4.2  Metodo: cattureMultiple

Questo metodo non è presente all'interno del codice originale ed è stato implementato per gestire le catture multiple. L'idea utilizzata dal codice originale era di usufruire dei metodi IsMoveLegal e IsWalkLegal per controllare se una mossa era legale, illegale o incopleta, nel caso in cui fosse una cattura multipla. Analizzando tali funzioni si è visto che per determinare il tipo di mossa, non venivano sfruttate le infornazioni già conosciute come la posizione ed il verso, ma veniva scansionata nuovamente tutta la damiera. Per questo motivo e per permettere di utilizare la struttra dati realizzata, si è deciso di eseguire la ricerca delle mosse possibili utilzzando un'altra funzione che fosse in grado di sfruttare le informazioni precedentemente ricavate.

L'idea del metodo cattureMultiple è un'applicazione ricorsiva dei controlli utilizzati nel metodo generate_moves per controllare se si può continuare a mangiare. Non appena si verifica che non è più possibile mangiare, la mossa viene terminata e opportunamente salvata all'interno della struttura dati, e il flusso ritorna alla funzione che l'ha chiamata.

Anche in questo caso si deve fare attenzione al tipo di pezzo che viene passato, infatti nel caso in cui si tratti di una pedina, il controllo delle catture viene eseguito lungo un solo verso, altrimenti se è una dama, si deve controllare anche il verso opposto.

3.4.3  Il metodo eseguiMossa

Vi sono due versioni di tale metodo: quella utilizzata in switch_toMove, che permette di eseguire le mosse ritornate dal computer, ricevendo in input la board di partenza e la sequenza con la mossa da eseguire e aggiornando la board con la nuova configurazione di gioco. L'altra versione viene utilizzata nel modulo umano per realizzare le mosse semplici o le catture singole, ricevendo la board e le coordinate di partenza e di arrivo.

L'esecuzione di una cattura multipla viene gestita dal modulo umano che la spezza in più catture singole e le esegue, invocando per ognuna di queste la seconda versione di eseguiMossa. Tale versione ricorda il metodo move_board del codice originale, ma mentre in quest'ultimo viene richiamato ApplyMove per controllare il tipo di mossa che si sta eseguendo, in eseguiMossa tali informazioni sono già conosciute e si richiede solo di eseguire la mossa sulla board aggiornando la configurazione di gioco.

3.5  La classe Board

Per permettere all'umano di giocare, si è resa necessaria la gestione dell'interazione della dama con l'utente, permettendogli in qualche modo di poter scegliere le azioni da eseguire e non lasciandogli la possibilità di fare una qualsiasi mossa contro le regole del gioco. A questo scopo si sono utilizzate una board virtuale, sotto forma di matrice di interi 8x8, nella quale memorizzare in ogni istante il corrente stato del gioco, ossia la reale posizione delle pedine e una board fisica (grafica) formata anch'essa da 64 caselle, visibile all'utente, nelle quali sono state opportunamente disegnate le pedine rispecchiando le posizioni salvate nella board virtuale. Questa struttura è stata ripresa dal codice originale.

L'utente attraverso il mouse può selezionare una pedina da muovere, cliccando una volta con il tasto sinistro sulla casella desiderata, e successivamente cliccare sulla casella dove finisce la mossa. In questo caso se la mossa è semplice, ossia si muove in una casella libera confinante, o si esegue una sola mangiata si deve semplicemente cliccare il mouse sulla casella di arrivo. Se si deve eseguire una cattura multipla, dopo aver selezionato la propria pedina, con la quale si vuole eseguire la cattura, è necessario cliccare in ordine su tutte le caselle del percorso da seguire per eseguire la mossa.

Il metodo mouseDown si occupa interamente della gestione del gioco per il giocatore umano. Dopo aver eseguito il primo click per selezionare la pedina con la quale si vuole eseguire la mossa, il metodo trasforma le coordinate fisiche ricevute, in coordinate compatibili con la board virtuale. In questo modo si riesce a controllare il reale contenuto della posizione selezionata. Si possono verificare vari casi: l'area selezionata sia al di fuori della damiera, verrà ignorata dal controllo; la cella sia vuota, oppure contenente un pezzo avversario e anche tale selezione verrà ignorata; il pezzo selezionato è del giocatore cui spetta il turno. Solo ques'ultimo caso viene processato e si deve controllare se effettivamente il pezzo selezionato può essere mosso o ci sono delle altre mosse obbligate. Questo controllo è permesso scorrendo all'interno della lista con tutte le mosse obbligate, creata dal metodo switch_toMove prima dell'inizio del turno, se esiste almeno una mossa che presenta come prima coordinata quella selezionata. In caso affermativo la casella verrà colorata di arancione e si permetterà di scegliere dove muovere il pezzo, altrimenti di rosso, indicando che quel pezzo non può essere mosso perchè ve ne sono altri con priorità maggiore. La scelta del colore da assegnare alla casella è lasciata al metodo offscreen_paint, invocato da mouseDown alla fine dei controlli sulla casella selezionata.

Nel caso in cui il pezzo selezionato sia corretto, si può procedere con la mossa gestendo le prossime selezioni dell'utente. Innanzitutto viene settata la variabile highlight per indicare che il pezzo da muovere è stato selezionato, quindi si aggiorna il vettore ove sono memorizzate le mosse possibili, affinchè contenga solo le mosse che hanno come prima posizione quella selezionata. In questo modo, le mosse che vengono mantenute sono solo quelle compatibili con le regole e le scelte dell'utente e si mantiene un contatore con il numero di catture da eseguire con tali mosse. A questo punto l'utente può procedere con la prossima selezione. Se la nuova posizione scelta non appartiene ad una delle mosse possibili rimaste, tale non viene accettata; altrimenti si esegue l'azione, aggiornando il contatore del numero di catture che devono essere eseguite e le mosse che sono ancora disponibili in base alle nuove scelte. Solamente quando si raggiunge l'ultima posizione della mossa, ossia quella d'arrivo per il pezzo, la sequenza di selezioni si considera terminata e viene richiamata la funzione switch_toMove per la gestione del prossimo turno.

Il metodo descritto è stato ripreso dal codice originale e sono state apportate alcune modifiche per permettere di utilizzare la struttura dati studiata per le regole. Il cambiamento riguarda l'aggiunta del vettore con le mosse possibili e la gestione di questa struttura in seguito ad ogni selezione.

3.6  La classe Engine

Nella classe Engine si trovano tutti i metodi utilizzati per la gestione della parte di intelligenza artificiale della dama. Attraverso questi, il computer sceglie quale azione è più conveniente eseguire per avere buone probabilità di arrivare alla vittoria o nel caso peggiore alla patta, cercando di evitare di perdere.

Il codice originale utilizzava la sola funzione MiniMax e una funzione di valutazione Evaluation per realizzare questo modulo. La nuova implementazione crea un codice diverso, nel quale viene realizzata la strategia spiegata al Capitolo 2, e vengono create un certo numero di funzioni di valutazione diverse per simulare strategie di gioco differenti.

Il metodo principale della classe è MiniMax, che si basa sulla ricerca MiniMax discussa al Capitolo 2, come suggerito dal nome. Per poter utilizzare tale funzione in questo gioco, si è reso necessario realizzarne una versione che permetesse di salvare la mossa ritenuta migliore da eseguire; tenendo anche conto della struttura dati utilizzata.

Inizialmente vengono create tutte le mosse possibili invocando l'opportuno metodo della classe Move, ossia generate_moves discusso in Sezione 3.4.1. Nel caso in cui non ci siano mosse possibili, non viene eseguita la ricerca e si ritorna subito al metodo invocante, ossia switch_toMove che, controllando le mosse da eseguire (nessuna), scopre la perdita del giocatore e la segnala terminando la partita. Anche nel caso in cui si incontri una sola mossa possibile non viene eseguita la ricerca e si ritorna al metodo invocante, dato che il computer non può scegliere quella migliore, ma è obbligato nelle sue esecuzioni. Se si verifica questa situazione, prima di uscire viene salvata la mossa da eseguire che verrà applicata da switch_toMove.

Si deve eseguire ricerca della mossa migliore solamente quando si verifica che ci sono almeno due mosse tra le quali scegliere quale eseguire. In questo caso si applicca la ricerca minimax, cercando di ricavare la mossa che massimizza il guadagno del giocatore. Nel realizzare MiniMax si è supposto che il giocatore che deve eseguire la mossa, sia che sia bianco, sia che sia nero, funga il ruolo di Max e l'avversario quello di Min. Pertanto la ricerca è uguale nei due casi e si inizia invocando minimize.

Se il turno è di Min si utilizza il metodo minimize per valutare la mossa che gli permette di essere meno in svantaggio, mentre se il turno è di Max si utilizza il metodo complementare maximize. Tali metodi controllano inzialmente se è verificata la condizione di cutoff, ossia di terminazione che si ha quando la profondità di ricerca raggiunta nell'albero raggiunge il valore della massima profondità selezionata tra le opzioni del gioco. Fino a quando la condizione non è raggiunta si continua ad eseguire alternativamente le chiamate di maximize e minimize.

Quando si raggiunge la condizione di terminazione, si controlla innanzitutto se la configurazione raggiunta è quiscente, ossia se è stabile. Per il gioco della dama si è deciso di definire una situazione essere stabile quando il giocatore cui tocca il prossimo turno, non ha delle catture da eseguire. Se la configurazione è quiescente, allora si utilizza la funzione di valutazione selezionata tra le opzioni del gioco per valutare la configurazione raggiunta. In questo modo si è raggiunta una foglia dell'albero di ricerca alla quale è possibile associare una valore di valutazione della bontà di tale configurazione. Da questo punto si può iniziare a risalire l'albero massimizzando nei nodi di Max e minimizzando in quelli di Min i valori che vengono associati ai figli.

Se si verifica il caso nel quale la configurazione raggiunta non è quiescente, allora si continua la ricerca, scendendo in profondità nell'albero fino a quando non si raggiunge una configurazione stabile, alla quale poter applicare la funzione di valutazione selezionata e ritornare il valore del nodo.

3.7  Funzione di valutazione

Le funzioni di valutazione sono fondamentali per la ricerca della mossa migliore da eseguire. Infatti è in base al grado di bontà con il quale riescono a valutare le configurazioni raggiunte, che determinano se le mosse che portano a tali configurazioni sono vantaggiose o meno.

Per questo motivo si sono analizzate varie funzioni di valutazione allo scopo di trovare una strategia in grado di comportarsi bene e di essere abbastanza imbattibile da parte di un utente umano. I test e le analisi sono stati eseguiti sia utilizzando un utente umano, sia computer contro computer, ma come verrà discusso e osservato nelle conclusioni riportate nel Capitolo 5, l'essere ottimo contro altre funzioni di valutazione, non sarà indice di giocare in modo ottimo contro un umano. Questo per il fatto che il computer sceglie sicuramente le proprie mosse in modo ottimo, mentre ciò non è detto per il giocatore umano.

Sono state realizzate cinque tipologie di funzioni create sfruttando varie considerazioni che si possono fare sul gioco della dama; alcune di queste sono state prese dal sito ufficiale della Federazione Dama Italiana trovata nella rete [2]. Le funzioni che di seguito verranno analizzate sono: Originale, Spettacolo, SoloPedine, Prima, Funzione2.

Tutte le funzioni si basano su una tecnica spesso usata per la realizzazione di funzioni di valutazione, ossia geralmente viene assegnato un peso ad ogni pezzo e anche un valore in base alla posizione occupata all'interno della damiera.

Per il calcolo del valore di una configurazione, viene utilizzata la notazione di seguito introdotta.

  • score: è il valore ritornato dalla funzione di valutazione, ossia il valore associato alla configurazione della damiera selezionata.
  • pos: indica il peso assegnato alla posizione. Generalemente è posto uguale ad 1.
  • nPedineNere: indica il numero di pedine nere presenti nella damiera nella configurazione valutata;
  • nPedineBianche: indica il numero di pedine bianche presenti nella damiera nella configurazione valutata;
  • nDameNere: indica il numero di dame nere presenti nella damiera nella configurazione valutata;
  • nDameNereBordo: indica il numero di dame nere presenti nel bordo della damiera nella configurazione valutata;
  • nDameBianche: indica il numero di dame bianche presenti nella damiera nella configurazione valutata;
  • nDameBiancheBordo: indica il numero di dame bianche presenti nel bordo della damiera nella configurazione valutata;
  • edge: indica la penalità da attribuire se ci sono dame sulle caselle lungo i bordi della damiera;
  • position[i][j]: corrisponde alla casella della damiera;
  • RANDOM_WEIGHT: valore da attribuire al peso random assegnato ad ogni score;
  • numeroRandom: numero calcolato in modo random;
  • i: coordinata lungo l'asse delle y;

3.7.1  Originale

La funzione di valutazione Originale è quella presa dal codice originale scaricato dalla rete [3].

La funzione di valutazione associa un peso ad ogni pezzo: la dama pesa 200, mentre una pedina pesa 100. La differenza dei pesi è spiegata dalla preferenza di avere più dame che si posono muovere in più direzioni e non possono essere mangiate dalle pedine, rispetto a quest'ultime che sono limitate nelle mosse e possono essere catturate da qualsiasi pezzo.

Ad ogni posizione della damiera viene associato un peso diverso, che per ogni giocatore assume valori crescenti muovendosi nella direzione opposta. Questo permette di promuovere l'avanzata dei pezzi verso dama e di utilizzare una strategia d'attacco. Per valutare il peso di una posizione si utilizza la formula:


peso=i2 ·pos

Inoltre, dato che le dame sono meno vulnerabili, è preferibile seguire una strategia che non cerca di proteggerle facendole muovere lungo i bordi, ma che le promuova a muoversi al centro della damiera. Per fare questo viene associato un peso negativo a tali caselle quando devono essere occupate dalle dame.

La funzione di valutazione viene realizzata sommando il peso di ogni propria pedina e dama che compare all'interno della damiera nella configurazione che si sta valutando. A tale valore si deve sommare il peso che ogni pezzo assume occupando la casella in cui si trova, penalizzando i casi in cui le proprie dame siano lungo i bordi. Lo stesso calcolo deve essere eseguito dal punto di vista dell'avversario e alla fine la funzione di valutazione si ottiene sottraendo al proprio valore, quello dell'avversario. Formalmente lo score si calcola applicando la seguente formula:


score+= ì
ï
ï
ï
ï
ï
ï
ï
í
ï
ï
ï
ï
ï
ï
ï
î
100 ·nPedineNere -100 ·nPedineBianche
200 ·nDameNere -200 ·nDameBianche
pos ·
å
position[i][j]=a  pedina  nera 
(7-i)2   con  i=0,...,8  j=0,...8
pos ·
å
position[i][j] = a  pedina  bianca  
i2     con  i=0,...,8  j=0,...8
edge ·(nPedineBiancheBordi - nPedineNereBordi)
RANDOM_WEIGHT ·numeroRandom

Se si ottiene un valore circa attorno allo zero, significa che i giocatori sono quasi pari e nessuno ha un vantaggio rilevante. Se il valore è tanto più grande dello zero allora vuol dire che in quella situazione si ha un vantaggio sull'avversario, nel caso opposto si sta perdendo. In base a quanto detto, il valore ritornato dalla funzione di valutazione, sembra rispecchiare la reale situazione del gioco.

Nell'implementazione la funzione viene chiamata EvalOriginale.

3.7.2  Spettacolo

Per realizzare la funzione di valutazione Spettacolo si sono utilizzate alcune considerazioni che sono state documentate in rete [2]. L'idea sfrutta la geometria della damiera, che presenta delle regioni più facilmente proteggibili contro gli attacchi dell'avversario ed altre più vunerabili. Nell'implementazione la funzione viene chiamata EvalSpettacolo.

La damiera può essere vista come divisa in quattro aree: l'angolo in alto a sinistra e quello diametralmente opposto in basso a destra vengono definiti cantoni, mentre i due rimanenti sono definiti biscacchi.

Un giocatore riesce facilmente a difendere il proprio cantone, infatti l'avversario non ha modo di sfondare la base, come si può osservare dalla Figura 3.3 .

Figure 3.3: Nella damiera si nota il vantaggio di avere la propria posizione di cantone occupata.

Diversamente la parte del biscacco è più facilmente sfondabile per un avversario sacrificando una propria pedina e permettendo all'altra di andare a fare dama, come si può osservare dalla Figura 3.4 .

Figure 3.4: La figura della damiera indica la posizione di biscacco.

In base alle osservazioni precedentemente fatte, si può decidere di utilizzare varie strategie di gioco. In attacco di solito si preferisce dirigere la propria azione verso il biscacco avversario, che presenta più possilità di sfondare la linea base avversaria e di andare a dama. Per quanto riguarda il gioco in difesa, dato che anche il proprio biscacco può essere facilemente attaccato dall'avversario, l'idea è di non far avanzare i pezzi da questa parte e di muovere quelli del cantone.

Dalle considerazioni si nota come la damiera possa essere immaginata suddivisa in quattro quadranti, Figura 3.5 . Per convenzione ogni quadrante verrà numerato in base alla posizione, seguendo l'ordine da sinistra verso destra, dall'alto verso il basso.

Figure 3.5: Suddivisione della damiera in quattro quadranti.

Si supponga di costruire la strategia dal punto di vista del giocatore nero, per il bianco si ottiene un ragionamento simmetrico. Per voler realizzare l'idea sopra introdotta, il giocatore nero dovrà muovere le proprie pedine verso il secondo quadrante per provare a sfondare e non dirigersi verso il primo, ove può incontrare più difficoltà di fare dama. Volendo anche difendere il proprio lato debole, ossia il proprio biscacco, deve cercare di non muovere le pedine che si trovano nel terzo quadrante. Per implementare tale strategia, si assegna ad ogni area un peso in modo che il secondo ed il terzo quadrante abbiano peso maggiore mentre il primo ed il quarto peso minore. In questo modo, quando si esegue la valutazione, si obbligano le pedine che sono all'interno di tale area di rimanervici e quelle che sono in aree con peso minore di dirigersi verso le altre.

Per permettere alle pedine di muoversi all'interno delle aree, si è deciso di dare alle caselle dei quadranti dei pesi crescenti in base all'aumetare della distanza.

Provando ad implementare la strategia come è stata sopra descritta, ci si accorge che è troppo difensiva e che pertanto, arriva difficilemente a fare dama. Per questo motivo si è pensato di modificare la funzione di valutazione e di suddividerla in due fasi: nella fase iniziale si è implementata la strategia precedentemente descritta, mentre nella fase finale si promuovono le pedine che vanno a dama. Il test per disinguere la fase iniziale da quella finale controlla se è presente una dama oppure se sono rimaste poche pedine applica la seconda fase, altrimenti la prima.

Inoltre si privilegiano ulteriormente le configurazioni in cui il giocatore ha la mossa, ossia se il numero di coppie di pedine che distano l'una dall'altra di un numero pari di caselle è dispari allora il giocatore che ha il turno è avvantaggiato.

Dato che vi sono due fasi, si ottengono due formule da calcolare in base alla situazione.

  • Fase iniziale:


    scorefase iniziale+= ì
    ï
    ï
    ï
    ï
    ï
    ï
    ï
    ï
    í
    ï
    ï
    ï
    ï
    ï
    ï
    ï
    ï
    î
    100 ·
    å
    i: 0 £ (7-i) £ 5 
     (8-j)2 ·(7-i)2
    - 100 ·
    å
    i: 0 £ (7-i) £ 5 
     (8-j)2 ·i2
    100 ·
    å
    i: 5 < (7-i) < 8 
     j2 ·(7-i)2
    - 100 ·
    å
    i: 5 < (7-i) < 8 
     j2 ·i2
    RANDOM_WEIGHT ·numeroRandom
  • Fase finale:


    scorefase finale+= ì
    ï
    ï
    ï
    ï
    ï
    í
    ï
    ï
    ï
    ï
    ï
    î
    200 ·nDameNere - 200 ·nDameBianche
    100 ·
    å
    position[i][j]=a  pedina  nera 
    (7-i)2   con  i=0,...,8  j=0,...8
    - 100 ·
    å
    position[i][j] = a  pedina  bianca  
    i2   con  i=0,...,8  j=0,...8
    RANDOM_WEIGHT ·numeroRandom

A scorefase finale si deve sommare il peso della mossa, nel caso in cui si abbia la mossa, o sottrarla nel caso in cui l'abbia l'avversario.

3.7.3  SoloPedine

La funzione di valutazione SoloPedine è realizzata, come suggerito dal nome, considerando solamente le pedine. L'idea era di vedere il comportamento di una funzione nella quale si attribuisse un peso solo ai pezzi e alla loro posizione all'interno della damiera. Nel Capitolo  si possono trovare le considerazioni sull'andamento di tale funzione.

Ad ogni pedina è stato associato un peso pari a 100 e ed ogni dama è stata valutata 200. Quindi si è deciso di attribuire un valore solo alla posizione delle pedine all'interno della damiera, non privilegiando o penalizzando alcune configurazioni delle dame rispetto ad altre. Questa idea è stata suggerita dalla decisione di fare una strategia di attacco che favorisse le pedine ad andare a dama.

Per realizzare l'idea precedentemente descritta, si è deciso di attribuire alle caselle un valore che cresce con andamento quadratico nella distanza di queste dal bordo dell'avversario. Pertanto, in base a come si è pensato di ordinare le caselle, per il giocatore nero ogni casella occupata da una sua pedina viene valutata:


peso=pos ·(7-i)2   ,

mentre le pedine del giocatore bianco, verranno valutate con la formula:


peso = pos ·i2

Riassumendo, supponendo di calcolare la funzione di valutazione dal punto di vista del giocatore nero, si ottiene la seguente formula:


score+= ì
ï
ï
ï
ï
ï
í
ï
ï
ï
ï
ï
î
100 ·nPedineNere -100 ·nPedineBianche
200 ·nDameNere -200 ·nDameBianche
pos ·
å
position[i][j]=a  pedina  nera 
(7-i)2   con  i=0,...,8  j=0,...8
pos ·
å
position[i][j] = a  pedina  bianca  
(7-i)2     con  i=0,...,8  j=0,...8

Questa funzione ricorda la funzione Originale, infatti vengono presi in considerazioni gli stessi elementi. Si differenziano solo per il fatto che in questa non si penalizzano le dame nel caso in cui occupino caselle della damiera situate lungo i bordi. Nel codice tale funzione viene chiamata EvalSoloPedine.

3.7.4  Prima

Per la realizzazione di questa funzione di valutazione si è utilizzata la documentazione di un'altra strategia di gioco che permette di giocare in attacco, mantenendo comunque una buona difesa della propria linea di partenza. Questa idea è stata suggerita da una prima considerazione banale e strategica che spesso viene utilizzata in una partita. Se si tiene la propria linea di base piena, che in termini tecnici si dice avere una fully guarded back rank, non si permette all'avversario di andare facilmente a dama, a meno che non sacrifichi qualche pezzo.

Mantenendo la base coperta e spostando tutte le pedine verso la dama, si rischia però di creare una fascia di pedine che alle spalle presentano delle caselle vuote, permettono facilmente l'avversario di attaccare e mangiarle. Per questo motivo si è realizzata una strategia più sicura, basata su tale concetto, suggerita da una osservazione di Sandro Maccagni riportata nel sito della Federazione Italiana Dama [2]. In questa si afferma che: Ï pezzi devono muoversi in formazione compatta, solidamente piantata alla base e con punte avanzate ben appoggiate." Questa frase riassume il punto centrale della strategia che è stata realizzata: si è provato a muovere le pedine, facendole avanzare verso dama 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 spalle coperte.

Per realizzare la strategia, si è costruito una funzione per il calcolo del ßupporto", ossia delle pedine che si trovano alle spalle di altre. La funzione scansiona la damiera cercando se nelle posizioni dietro la pedina selezionata lungo le diagonali, compaiono pedine dello stesso colore e se questo accade continua a controllare all'indietro ricorsivamente fino al raggiungimento della base. Ogni volta che trova una tale situazione per una propria pedina aumenta il valore della funzione di valutazione, privilegiando i casi in cui si presenta una posizione delle proprie pedine che ricorda una forma a piramide con la base ben saldata sulla linea di base. In tal modo si promuovono quelle configurazioni ben saldate alla base, penalizzando le altre.

Questo per quanto riguarda la parte diffensiva della tecnica, mentre per permettere di attaccare, si è dato un peso ad ogni pezzo, differenziandolo nel caso fosse dama o pedina. Per ogni pedina si è aggiunto un valore in base alla posizione occupata all'interno della damiera, privilegiando quelle più vicine alla dama, come si era fatto per la funzione SoloPedine in Sezione 3.7.3. Per le dame, si sono penalizzate le configurazioni che andavano a sistemarle vicino ai bordi laterali della damiera, preferendo che ricoprissero ruoli centrali più offensivi.

All'interno del codice tale funzione è chiamata EvalPrima.

3.7.5  Funzione2

Questa funzione è stata realizzata a partire dalla precedente, cercando di migliorare le considerazioni fatte sul peso delle caselle occupate dalle dame. La parte di strategia diffensiva con il calcolo del supporto e il modo di promuovere le pedine a dama sono state mantenute, in Sezione 3.7.4 è spiegata tale fase, l'unico punto cambiato è stato il modo di considerare le dame.

Con la funzione precedente si era cercato di penalizzare le posizioni nelle quali le dame si rifugiavano lungo i bordi, preferendo che conducessoro un gioco più offensivo per attaccare le pedine avversarie. In questo modo, comunque si era solamtene penalizzato le sole file di caselle lungo il bordo, attribuendo a tutte le altre un valore uguale. L'idea realizzata con questa funzione è stata di promuovere gradualmente le caselle centrali della damiera, con valori crescenti in base alla vicinanza con le quattro caselle centrali, piuttosto di penalizzare solo le altre.

Tale funzione viene chiamata nel codice con il nome Evaluation2