Tesi Specialistica - Bruno Tagliapietra

Università degli Studi di Trieste

Tesi di Laurea Specialistica

PROGETTAZIONE E

REALIZZAZIONE DI UNA APPLICAZIONE PER IL

LAUREANDO:

Bruno TAGLIAPIETRA

Anno Accademico 200

Università degli Studi di TriesteFacoltà di Ingegneria

Tesi di Laurea Specialistica in

Ingegneria Informatica

PROGETTAZIONE E


GIOCO DEGLI

"SCACCHI 3D"

LAUREANDO: RELATORE:

Bruno TAGLIAPIETRA Chiar.mo Prof.

Maurizio FERMEGLIA

Anno Accademico 2008/09

Università degli Studi di Trieste

PROGETTAZIONE E


Maurizio FERMEGLIA

3

Indice Introduzione 5

Motivazione 5

Analisi 7

Descrizione del gioco preso in esame 7

Raumschach 7

Pezzi 9

Scopo del gioco e relativo regolamento 16

Notazione delle mosse 16

Requisiti funzionali 17

Requisiti non funzionali 18

Progettazione 19

Considerazioni preliminari 19

Architettura del sistema 20

Interfaccia – Motore VS Model – View - Controller 20

Progettazione del Motore 21

Rappresentazione della scacchiera e generazione mosse 23

Tecniche di ricerca 32

Valutazione di una posizione 41

Progettazione dell’Interfaccia 50

Scacchiera Tridimensionale 50

Comunicazione Interfaccia-Motore 56

Realizzazione 57

Tecnologie utilizzate 57

Realizzazione del Motore 60

Header files 60

C Files 62

Realizzazione dei modelli 3D 75

Realizzazione dell’Interfaccia 77

Premessa: XNA Application Model 77

Librerie di terze parti 79

Gameplay 81

4

Videocamere Virtuali 81

Gestione dei modelli 90

Logiche di gioco 92

Conclusioni 93

Raggiungimento degli obiettivi 93

Sviluppi futuri 93

Bibliografia 94

Letteratura 94

Web 94

Ringraziamenti 96

Appendice 97

Fast, Minimum Storage Ray/Triangle Intersection 97

5

Introduzione

Motivazione

Il gioco degli scacchi è considerato un problema molto interessante dal punto di vista della sua risoluzione e gioco da parte di un elaboratore: nel corso degli anni, fin dagli albori dell’informatica, gli appassionati e i professionisti di scacchi e di computer hanno perfezionato algoritmi sempre più sofisticati, fino a riuscire recentemente a far vincere il computer contro i più grandi maestri. Vale la pena ricordare che gli scacchi, a differenza ad esempio della dama, sono ancora un problema aperto: cioè, mentre nella dama ormai si conosce la mossa “migliore” in ogni situazione, dall’inizio della partita fino alla fine, Vi sono competizioni mondiali che consistono in un gran numero di partite fra i cosiddetti “motori” per il gioco degli scacchi, ovvero software molto perfezionati e specifici il cui unico obiettivo è vincere una partita di scacchi. Alcuni fra i motori migliori sono stati poi inseriti nei programmi di scacchi commerciali, il più famoso di tutti è sicuramente “Chessmaster 10”: presenta innumerevoli funzionalità quali interfaccia grafica user friendly, possibilità di selezionare le abilità dell’avversario computerizzato (fino ad arrivare ad un’abilità stimata con punteggio FIDE 2966), un breve corso di scacchi integrato... Sarebbe stato quindi presuntuoso e difficilmente fattibile per un singolo scrivere qualcosa che sia competitivo sia dal punto di vista del motore, cioè dell’intelligenza del programma, sia dal punto di vista delle funzionalità offerte all’utente, rimanendo nel campo degli scacchi classici. Un’alternativa sarebbe stata inventare un gioco del tutto nuovo. Tuttavia spesso i giochi complessi difficilmente risultano equilibrati, interessanti e umanamente giocabili alla prima versione. Per questi motivi si è deciso di “riesumare” e computerizzare una fra le versioni più interessanti di questo gioco, che sono indubbiamente quelle che si svolgono su una scacchiera tridimensionale. Le tre principali alternative erano: Raumschach (in tedesco “scacchi nello spazio”), inventata nei primi del ‘900, Asimov Chess (versione ideata da Isaac Asimov in uno dei suoi racconti, ma mai sufficientemente giocata), Star Trek 3D Chess (versione giocata nell’omonima saga).

6

Si sono scelti i Raumschach fra i tre perché essi sono stati indubbiamente i più giocati e i più sperimentati; inoltre non esiste alcuna implementazione sotto forma di videogame che sia fedele all’originale di questo gioco, ideato e giocato in alcuni club tedeschi nel periodo tra la prima e la seconda guerra mondiale.

7

Analisi

Descrizione del gioco preso in esame

La versione scelta è, fra le versioni tridimensionali esistenti del gioco degli scacchi, la più documentata e la più giocata in assoluto. Le versioni tridimensionali del gioco degli scacchi, abbreviabili in 3D chess, fanno parte delle innumerevoli varianti di questo famosissimo gioco. Le più antiche risalgono alla fine del 1800. Una delle più famose versioni tridimensionali degli scacchi è appunto quella analizzata in questo documento. Essa è detta Raumschach, ovvero “scacchi spaziali” in lingua tedesca. Inventata nel 1907 da Ferdinand Maack, è stata giocata prevalentemente in Germania. Nel 1919 Maack fondò anche un club di Raumschach ad Amburgo, rimasto attivo fino all’inizio del secondo conflitto mondiale. Inizialmente giocata in un cubo 8x8x8, la versione del 1907 vide la luce su una scacchiera cubica con cinque caselle per ognuna delle tre dimensioni.

Raumschach

Come negli scacchi classici l’obiettivo è catturare il re avversario. Questo può avvenire solo tramite lo “scacco matto”, ossia una posizione in cui non vi è mossa in grado di impedire la cattura del re nella mossa immediatamente successiva. I contendenti muovono uno dei propri pezzi alla volta, a turno, alternandosi. I movimenti, descritti più avanti in dettaglio, sono simili a quelli degli scacchi classici. Ognuna delle 125 caselle è identificata da tre coordinate: “livello” di appartenenza, “riga” e “colonna”, in quest’ordine.

• Livelli: identificati dalle lettere

maiuscole A,B,C,D,E

• Righe: identificate dalle cifre 1,2,3,4,5

• Colonne: identificate dalle lettere minuscole a,b,c,d,e

Seguendo la disposizione di fig.2 si inizia, per convenzione, la numerazione delle caselle da quella posta sul livello più basso, sulla colonna più a sinistra e sulla riga più vicina al giocatore con i pezzi di colore bianco. Perciò, nella casella Aa1 vi sarà all’inizio partita una torre “bianca”, e in Ba1 nel medesimo istante un alfiere “bianco”, con il re posto nel piano più basso. Sempre da fig.2 è facile ed importante notare che la disposizione dei pezzi

Fig. 1 Schema della scacchiera

8

neri risulta speculare a quella dei pezzi bianchi, quindi con il re polivello più alto. Quindi in Ee5 vi sarà una torre “nera” e in Ed5 un unicorno “nero”.

Fig. 2 - La disposizione iniziale della scacchiera, dal piano più alto (E) al piano più basso (A)

neri risulta speculare a quella dei pezzi bianchi, quindi con il re posto sul livello più alto. Quindi in Ee5 vi sarà una torre “nera” e in Ed5 un unicorno

iniziale della scacchiera, dal piano più alto (E) al piano più basso (A)

sto sul livello più alto. Quindi in Ee5 vi sarà una torre “nera” e in Ed5 un unicorno

iniziale della scacchiera, dal piano più alto (E) al piano più basso (A)

Pezzi

I pezzi sono, come negli scaccPedoni, con l’aggiunta degli Unicorni. Ogni giocatore ha a disposizione 10 pedoni, 2 torri, 2 cavalli, 2 alfieri, 2 unicorni, 1 regina e naturalmente 1 re.Come negli scacchi classici su ciascuna casella pe l’unico in grado di “saltare”, cioè di non subire l’ostruzione degli altri pezzi presenti sulla scacchiera, è il cavallo. Qualsiasi pezzo di un certo colore può occupare una casella contenente un pezzo avversario, catturando imodo quest’ultimo, il quale verrà rimosso dalla scacchiera. Pedone: come negli scacchi classici il suoi movimenti cambiano a seconda

che esso catturi o meno un pezzo. Senza cattura esso deve muovere di un

passo di torre verso il campo avversario;

verso l’alto o verso avanti rispetto al giocatore che lo controlla. In caso di

cattura a questo movimento dovrà essere aggiunto un cambio di colonna verso destra o verso sinistra, risultante in un passo d’alfiere sullo ste

piano o sul piano immediatamente successivo nel viaggio verso il campo

avversario. A differenza degli scacchi classici non c’è differenza di possibilità

di movimento fra la prima mossa e le successive.

Lettera identificativa:

I pezzi sono, come negli scacchi classici, Re, Regina, Torri, Alfieri, Cavalli e Pedoni, con l’aggiunta degli Unicorni. Ogni giocatore ha a disposizione 10 pedoni, 2 torri, 2 cavalli, 2 alfieri, 2 unicorni, 1 regina e naturalmente 1 re.Come negli scacchi classici su ciascuna casella può stazionare un solo pezzo e l’unico in grado di “saltare”, cioè di non subire l’ostruzione degli altri pezzi presenti sulla scacchiera, è il cavallo. Qualsiasi pezzo di un certo colore può occupare una casella contenente un pezzo avversario, catturando imodo quest’ultimo, il quale verrà rimosso dalla scacchiera.

come negli scacchi classici il suoi movimenti cambiano a seconda


passo di torre verso il campo avversario; se “bianco”, quindi, può muovere


cattura a questo movimento dovrà essere aggiunto un cambio di colonna verso destra o verso sinistra, risultante in un passo d’alfiere sullo ste



di movimento fra la prima mossa e le successive. Non c’è mossa

Lettera identificativa: P

9

hi classici, Re, Regina, Torri, Alfieri, Cavalli e Pedoni, con l’aggiunta degli Unicorni. Ogni giocatore ha a disposizione 10 pedoni, 2 torri, 2 cavalli, 2 alfieri, 2 unicorni, 1 regina e naturalmente 1 re.

uò stazionare un solo pezzo e l’unico in grado di “saltare”, cioè di non subire l’ostruzione degli altri pezzi presenti sulla scacchiera, è il cavallo. Qualsiasi pezzo di un certo colore può occupare una casella contenente un pezzo avversario, catturando in questo

come negli scacchi classici il suoi movimenti cambiano a seconda


se “bianco”, quindi, può muovere


cattura a questo movimento dovrà essere aggiunto un cambio di colonna verso destra o verso sinistra, risultante in un passo d’alfiere sullo stesso



mossa en-passant.

10

Torre:

può muovere in linea retta di quante caselle si vuole in un solo turno. Può

muoversi in sei versi; è utile immaginare che essa per muoversi esca da una

delle sei facce del cubo di partenza.

Es: una torre posta al centro di una scacchiera vuotmuovere in

o Cc1, Cc2,Cc4, Cc5 (Varia la riga)

o Ca3, Cb3, Cd3, Ce3 (Varia la colonna)

o Ac3, Bc3, Dc3, Ec3 (Varia il livello)

Lettera identificativa: R (dall’inglese “rook”)



delle sei facce del cubo di partenza.

: una torre posta al centro di una scacchiera vuota, quindi in Cc3, si può

Cc1, Cc2,Cc4, Cc5 (Varia la riga)

Ca3, Cb3, Cd3, Ce3 (Varia la colonna)

Ac3, Bc3, Dc3, Ec3 (Varia il livello)

Lettera identificativa: R (dall’inglese “rook”)



a, quindi in Cc3, si può

Alfiere: anch’esso muove in linea retta per quante casellturno. A differenza della torre però esso esce dagli spigoli del cubo, perciò

può muoversi in otto versi.

Es: Un alfiere posizionato nella casella Dc4 in una scacchiera vuota può muoversi in

• Da2, Db3, Dd5, De2, Dd3, Db5 (nello ste

• Eb4, Ed4, Cb4, cd4, Ba4, Be4 (nel piano posto frontalmente al giocatore)

• Ec3, Ec5, Cc3, Cc5, Bc2, Ac1

(nel piano posto lateralmente al giocatore)

Lettera identificativa: B (dall’ingelse “bishop”)

anch’esso muove in linea retta per quante caselle si vuole in un solo turno. A differenza della torre però esso esce dagli spigoli del cubo, perciò

può muoversi in otto versi.

: Un alfiere posizionato nella casella Dc4 in una scacchiera vuota può

Da2, Db3, Dd5, De2, Dd3, Db5 (nello stesso livello, come negli scacchi classici)

Eb4, Ed4, Cb4, cd4, Ba4, Be4 (nel piano posto frontalmente al giocatore)

Ec3, Ec5, Cc3, Cc5, Bc2, Ac1

(nel piano posto lateralmente al giocatore)

Lettera identificativa: B (dall’ingelse “bishop”)

11

e si vuole in un solo turno. A differenza della torre però esso esce dagli spigoli del cubo, perciò

: Un alfiere posizionato nella casella Dc4 in una scacchiera vuota può

12

Unicorno: anch’esso in linea retta per quante caselle si vuole in un solo turno, ma uscendo dai vertici del cubo. Perciò si muove in quattro versi.

Es: un unicorno posizionato al centro di una scacchiera vuota (Cc3) può essere posto in:

Dd4, Ee5, Bb2, Aa1, Db2, Ea1, Bd4, Ae5, Ee1, Dd2, Bb4, Aa5, Ea5, Db4, Bd2,

Ae1

Lettera identificativa: U

nch’esso in linea retta per quante caselle si vuole in un solo turno, ma uscendo dai vertici del cubo. Perciò si muove in quattro versi.

: un unicorno posizionato al centro di una scacchiera vuota (Cc3) può

, Bd4, Ae5, Ee1, Dd2, Bb4, Aa5, Ea5, Db4, Bd2,

nch’esso in linea retta per quante caselle si vuole in un solo turno, ma uscendo dai vertici del cubo. Perciò si muove in quattro versi.

: un unicorno posizionato al centro di una scacchiera vuota (Cc3) può

, Bd4, Ae5, Ee1, Dd2, Bb4, Aa5, Ea5, Db4, Bd2,

Regina: essa può muovere sia come una torre, sia come un alfiere, sia come un unicorno.

Lettera identificativa: Q

essa può muovere sia come una torre, sia come un alfiere, sia come

Lettera identificativa: Q (dall’inglese “queen”)

13

essa può muovere sia come una torre, sia come un alfiere, sia come

14

Re: esso si sposta come la regincasella di arrivo deve essere adiacente alla casella di partenza cioè avere in

comune con essa una faccia, uno spigolo o alla peggio un solo vertice. In altre parole un re può muovere in ciascuna delle otto cas

casella di partenza. A differenza degli scacchi classici non vi sono manovre

di arrocco.

Lettera identificativa: K (dall’inglese “king”)

esso si sposta come la regina però di un solo passo per turno. Ovvero, la casella di arrivo deve essere adiacente alla casella di partenza cioè avere in

comune con essa una faccia, uno spigolo o alla peggio un solo vertice. In altre parole un re può muovere in ciascuna delle otto caselle più vicine alla


Lettera identificativa: K (dall’inglese “king”)

a però di un solo passo per turno. Ovvero, la casella di arrivo deve essere adiacente alla casella di partenza cioè avere in

comune con essa una faccia, uno spigolo o alla peggio un solo vertice. In elle più vicine alla


Cavallo: E’ l’unico pezzo in grado di muovere di un solo passo di torre più un solo passo di alfiere. In altre

parole, date le coordinate della casella di partenza, una di esse deve restare invariata, una deve variare di 1 e la terza deve variare di 2.

Es: in questi esempi indichiamo il variare delle coordi

parentesi l’entità della variazione di livello, riga e colonna, in quest’ordine.

Perciò ad esempio la tripla (0,1,2) indicherà un insieme di caselle poste contemporaneamente nello stesso livello di quella di partenza, su righe

distanti 1 e colonne distanti 2.

Un cavallo posto al centro di una scacchiera, nella casella Cc3, può essere

posto in ciascuna delle 24 caselle sottostanti, purché libere da pezzi dello stesso colore:

Cb1, Cb5, Cd1, Cd5

Bc1, Bc5, Dc1, Dc5Ab3, Eb3, Ad3, Ed3

Lettera identificativa: N (dall’inglese “knight”)

E’ l’unico pezzo in grado di saltare oltre gli altri pezzi.olo passo di torre più un solo passo di alfiere. In altre

parole, date le coordinate della casella di partenza, una di esse deve restare invariata, una deve variare di 1 e la terza deve variare di 2.

: in questi esempi indichiamo il variare delle coordinate racchiudendo tra



i 1 e colonne distanti 2.


posto in ciascuna delle 24 caselle sottostanti, purché libere da pezzi dello

Cb1, Cb5, Cd1, Cd5 (0,1,2) --------- Ca2, Ca4, Ce2, Ce4

Bc1, Bc5, Dc1, Dc5 (1,0,2) --------- Ba3, Be3, Da3, De3Ab3, Eb3, Ad3, Ed3 (2,1,0) --------- Ac2, Ec4, Ac4, Ac2

Lettera identificativa: N (dall’inglese “knight”)

15

oltre gli altri pezzi. Si deve olo passo di torre più un solo passo di alfiere. In altre

parole, date le coordinate della casella di partenza, una di esse deve restare

nate racchiudendo tra




posto in ciascuna delle 24 caselle sottostanti, purché libere da pezzi dello

Ca2, Ca4, Ce2, Ce4 (0,2,1)

Ba3, Be3, Da3, De3 (1,2,0) Ac2, Ec4, Ac4, Ac2 (2,0,1)

16

Scopo del gioco e relativo regolamento

Come negli scacchi classici, lo scopo del gioco consiste nel dare "scacco matto" (dal persiano Shah Màt = il re è morto) al re avversario; si ha "scacco matto" quando il Re, trovandosi sotto la minaccia diretta dei pezzi avversari, non ha la possibilità di sottrarsi ad essa (cioè sarebbe sicuramente catturato alla mossa successiva, se non si trattasse del Re). Lo "scacco" invece è l'attacco (evitabile) che un pezzo avversario porta al Re. L'avversario non può eseguire alcuna mossa che metta o lasci il proprio re sotto "scacco". La partita può terminare anche per abbandono da parte di un contendente, ovviamente con la vittoria dell'altro.

Il gioco termina obbligatoriamente in parità (patta) nei seguenti casi:

1. se restano sulla scacchiera soltanto i due re; 2. se il giocatore che ha il tratto non può muovere alcun pezzo, ma il suo re non è sotto scacco (stallo). 3. se per cinquanta mosse consecutive (cinquanta mosse per ciascun giocatore) non viene catturato alcun pezzo e non viene mosso alcun pedone.

Notazione delle mosse

Durante il corso della storia sono state ideate innumerevoli notazioni per gli scacchi classici. Senza dubbio la più utilizzata, per le sue caratteristiche di intuitività e brevità, è la cosiddetta “notazione algebrica”, descritta nel regolamento internazionale degli scacchi. Risulterebbe però problematico, e con tutta probabilità controproducente: infatti in essa si preferisce, per identificare una mossa, annotare la lettera iniziale del nome del pezzo che la esegue seguita dalle coordinate della casella di arrivo.

Es: Cf3 (cavallo mosso in f3, non si sa da quale punto di partenza).

E’ evidente che tale notazione necessita di complesse regole per evitare equivoci nel caso in cui, ad esempio, i cavalli che possono muovere in f3 siano più di uno.

Per questo motivo, la notazione adottata nel nostro caso consisterà in:

casella di partenza – casella di arrivo – iniziale di eventuale pezzo “di promozione”

es: Aa1Ca1 (il pezzo presente in Aa1 va in Ca1), Ec4Ec5Q (il pezzo, pedone, presente in Ec4 va Ec5 e viene promosso in regina);

17

Requisiti funzionali

Di seguito sono riportati i requisiti funzionali raggruppati in macrofunzionalità. Ciascuna macrofunzionalità è raggiunta nel momento in cui vengono soddisfatti tutti i requisiti in esso contenuti.

Requisiti giocabilità 2 giocatori su stessa postazione

• Il software deve presentare una scacchiera cubica 5x5x5, conforme al

regolamento indicato precedentemente. Detta scacchiera deve essere inizialmente configurata come da Fig.2 e contenere tutti e soli i pezzi indicati in Fig.2.

• Si vuole inoltre che i movimenti consentiti sui pezzi siano conformi al regolamento precedentemente indicato.

• Essendo la visualizzazione di una scacchiera 3D ostica all’essere

umano, si vuole che vi siano più modalità di visualizzazione della stessa (lontano-vicino).

• Per selezionare il pezzo da muovere e conseguentemente la casella in cui muoverlo si vuole poter usare il mouse: un primo click sul pezzo lo deve evidenziare, un secondo click fuori dal pezzo deve:

o Spostare il pezzo se il click è stato effettuato su una casella dove il pezzo stesso possa muovere.

o Selezionare un pezzo diverso se il click è stato effettuato su un altro pezzo selezionabile.

o Deselezionare il pezzo selezionato altrimenti.

18

Requisiti giocabilità giocatore umano vs giocatore

computerizzato

• Si vuole che vi sia la possibilità di giocare contro un avversario

computerizzato.

• Si vuole che l’abilità di detto avversario sia regolabile. Per la precisione:

o Deve essere possibile regolare il tempo massimo concesso per eseguire una mossa.

o Deve essere possibile fissare la profondità di analisi massima del software.

Requisiti giocabilità 2 giocatori umani su postazioni diverse

• Si vuole che vi sia possibilità di giocare via internet con un avversario

umano.

Requisiti non funzionali

• Portabilità: si vuole che il gioco sia cross platform il più possibile.

19

Progettazione

Considerazioni preliminari

Dallo studio dei requisiti emerge come prima peculiarità il fatto che si tratti di arrivare alla realizzazione di un videogame. Già questa semplice particolarità presenta non poche implicazioni progettuali: Restringendo il campo e riassumendo, dal punto di vista informatico si tratta di un gioco da tavolo (board videogame) dotato di “intelligenza artificiale” (AI), che deve quindi essere in grado di tener testa ad un giocatore umano. Si delina quindi una prima suddivisione in “motore”, ossia la parte pensante del gioco, e “interfaccia utente”, cioè tutto ciò che è percepito sensorialmente dal giocatore umano. Dovendo essere intelligente, il motore deve avere come caratteristiche peculiari rapidità di calcolo, efficienza, ed un certo grado di “regolabilità della difficoltà”. L’interfaccia, per contro, dovrà soddisfare i requisiti richiesti; inoltre, non avendo particolari requisiti di efficienza, sarà facile progettarla in modo che sia il più manutenibile possibile. Altro punto fondamentale, si tratta di un software che fa uso di grafica 3D. Sarà quindi necessaria la scelta di tecnologie adatte a coprire le necessità emerse da queste prime considerazioni iniziali. In particolare si avrà bisogno di:

• Un game engine con supporto 3D (OpenGL, Direct3D o entrambi).

E’ un software che serve a sviluppare video game. Le funzionalità principali fornite da un game engine comprendono un renderer per grafica 2D e/o 3D, animazioni, networking, gestione della memoria, threading. In più quello da noi scelto dovrà facilitare la portabilità, come da requisito.

• Un software di 3D modeling per la realizzazione dei modelli (i pezzi, la scacchiera).

20

Architettura del sistema

Nella primissima fase della definizione architetturale è opportuno mantenersi ad alti livelli di astrazione, scendendo nei dettagli il meno possibile. Via via che l’architettura prende forma, la definizione delle singole parti sarà sempre più dettagliata.

Interfaccia – Motore VS Model

In accordo alle considerazioni preliminari, in prima approssimazione viene molto naturale suddividere il progetto in due macroparti, come segue:

• Interfaccia Utente Si occupa di raccogliere input dall’utenfare) e di visualizzare a video la scacchiera.

• Motore In esso sono implementate le regole del giocola logica di gioco computerizzato.

In questo modo, ad ogni input dell’utente l’Interfaccia Utent

1. Compiere un’operazione di traduzione dell’input.2. Passare al Motore la suddetta traduzione.3. Attendere risposta del Motore.4. Aggiornare la visualizzazione basandosi sullo stato del Motore.

Ad ogni input ricevuto, il Motore dovrà:

1. Porre a confronto l’input ricevuto con le regole.2. Se l’input ricevuto corrisponde ad una mossa permessa, modificare lo

stato e generare un messaggio di conferma.Altrimenti, generare un messaggio di errore.

3. Rispondere con il messaggio generato all’Intefaccia Utente

Fig. 3 Model

del sistema

Nella primissima fase della definizione architetturale è opportuno mantenersi ad alti livelli di astrazione, scendendo nei dettagli il meno possibile. Via via che l’architettura prende forma, la definizione delle singole parti sarà sempre più dettagliata.

Motore VS Model – View - Controller

In accordo alle considerazioni preliminari, in prima approssimazione viene molto naturale suddividere il progetto in due macroparti, come segue:

Si occupa di raccogliere input dall’utente (le mosse che egli intende fare) e di visualizzare a video la scacchiera.

esso sono implementate le regole del gioco, lo stato della partitala logica di gioco computerizzato.

In questo modo, ad ogni input dell’utente l’Interfaccia Utente dovrà:

Compiere un’operazione di traduzione dell’input. Passare al Motore la suddetta traduzione. Attendere risposta del Motore. Aggiornare la visualizzazione basandosi sullo stato del Motore.

Ad ogni input ricevuto, il Motore dovrà:

l’input ricevuto con le regole. Se l’input ricevuto corrisponde ad una mossa permessa, modificare lo stato e generare un messaggio di conferma. Altrimenti, generare un messaggio di errore. Rispondere con il messaggio generato all’Intefaccia Utente

Model - View - Controller

Nella primissima fase della definizione architetturale è opportuno mantenersi ad alti livelli di astrazione, scendendo nei dettagli il meno possibile. Via via che l’architettura prende forma, la definizione delle

In accordo alle considerazioni preliminari, in prima approssimazione viene

te (le mosse che egli intende

, lo stato della partita e

Se l’input ricevuto corrisponde ad una mossa permessa, modificare lo

21

L’architettura così descritta richiama il pattern archietturale Model View Controller. Il comportamento del sistema viene normalmente così illustrato:

1. L’utente interagisce in qualche modo con l’interfaccia (View) 2. Il Controller reagisce all’input, ad esempio tramite una callback. 3. Il Controller propaga sul Modello il risultato dell’azione dell’utente;

solitamente modifica lo stato del Modello. 4. Una View utilizza il modello indirettamente per generare

un’interfaccia utente appropriata, o per modificare quella già esistente. Il Controller e il Modello non “sanno” che la View esiste.

Nel nostro caso Model e Controller farebbero entrambi parte del Motore.

Questa è infatti l’architettura più conveniente; tutto lo stato è contenuto nel Motore, che viene interrogato dall’Interfaccia ogniqualvolta ve ne sia bisogno.

Progettazione del Motore

Per essere in grado di assolvere alla sua funzione in base ai requisiti descritti, il Motore di 3D Chess deve innanzitutto possedere un sistema di strutture dati atte a descrivere lo stato della partita in corso. Lo stato sarà formato da:

• Stato della scacchiera, ovvero stato di ciascuna delle 125 caselle. Ciascuna di esse può essere vuota oppure contenere uno dei 7 tipi di pezzi disponibili, che possono essere a loro volta “bianchi” o “neri. Perciò ogni casella ha 7 ∗ 2 + 1 = 15 stati possibili.

• Numero di mosse consecutive dall’ultima cattura di pezzo o mossa di pedone (essenziale per soddisfare la regola di partita patta in caso di 50 mosse consecutive senza catture o mosse di pedoni).

• Giocatore che ha il tratto (cioè: tocca muovere al bianco o al nero?)

• Inoltre, volendo dare la possibilità di “takeback”, ovvero di poter annullare un certo numero di mosse, sarebbe opportuno mantenere uno stack delle mosse fatte fino a quel momento. In alternativa, per semplificare il calcolo, si potrebbero memorizzare direttamente le posizioni della scacchiera.

22

A questo punto, basandosi sullo stato così descritto, il Motore deve essere in grado di:

• Esprimere una valutazione quantitativa sulla posizione

• Per un certo numero di “livelli”, si esso n:

o Generare tutte le mosse possibili o Valutare tutte le posizioni o Per ciascuna posizione, generare tutte le mosse possibili

o Fermarsi quando ha raggiunto il tempo limite

In questo modo si sarà in grado di fissare il “livello” di difficoltà sia basandosi sulla massima profondità di esplorazione dell’albero delle mosse, sia fissando un tempo limite massimo oltre il quale il Motore dovrà selezionare la mossa ritenuta fino a quel momento la migliore. Naturalmente, tutto questo deve essere fatto nel modo più efficiente possibile, in quanto questo è il requisito fondamentale che deve avere il nostro Motore. Da queste considerazioni iniziali si può facilmente concludere che tre sono i problemi fondamentali da risolvere:

• Rappresentazione della scacchiera: quali strutture dati utilizzare per rappresentare una posizione?

• Tecniche di ricerca: come identificare le mosse possibili e selezionare quelle che sembrano essere più “promettenti” in modo che vengano esplorate per prime?

• Valutazione di una posizione: come valutare quantitativamente una posizione?

Descriviamo ora i punti presi in considerazione nella progettazione della soluzione a questi tre principali problemi.

23

Rappresentazione della scacchiera e generazione mosse

Nei motori per il gioco degli scacchi classici vengono utilizzati da molti anni delle strutture dati ormai considerate standard per la rappresentazione di una scacchiera. E’ nostro intento adottare la più consona ai nostri scopi, fornendo dapprima una descrizione delle possibili alternative.

Alternative progettuali

1. Lista di pezzi

Era utilizzata dai primi programmi di scacchi, i quali avevano a disposizione pochissima memoria. Perciò anziché riferirsi prima alla cella e da essa ottenere il pezzo, mantenevano una lista dei pezzi in gioco e relative coordinate. E’ utilizzata ancora oggi in congiunzione ad altre tecniche nel caso serva scoprire rapidamente la posizione di un certo pezzo.

2. Array based Una fra le alternative più intuitive, ovvero creare un array di tante caselle quante sono quelle della scacchiera che trattiamo. Ciascun elemento dell’array identificherà il contenuto della casella: ad esempio assegnando un valore convenzionale a ciascuna delle 15 possibili combinazioni (vuota, uno dei 7 tipi di pezzi bianchi o uno dei 7 tipi di pezzi neri). Diventa lento durante la generazione delle mosse in quanto per ogni mossa generata bisogna controllare se essa è dentro o fuori dalla scacchiera, rallentando in questo modo il processo di generazione.

3. Codifica Huffman Ispirato alla nota codifica di Huffman, le posizioni vengono descritte con configurazioni di bit di lunghezza inversamente proporzionale alla probabilità che esse compaiono. Ecco un esempio che farebbe al caso nostro: Casella vuota = 0 Pedone = 10c Unicorno = 1100c Alfiere = 1101c Cavallo = 1110c Torre = 1111c Regina = 11110c Re = 11111c

dove ‘c’ rappresenta il colore (ad esempio 1 per bianco e 0 per nero).

24

Servono ancora 1 bit per identificare chi ha il tratto e 7 bit per la regola delle 50 mosse. Questa strategia risulta molto onerosa dal punto di vista della complessità di calcolo, mentre è conveniente per le ridotte dimensioni in memoria.

4. Metodo 0x88: Questo metodo funziona negli scacchi classici perché le 64 caselle sono in numero una potenza di 2, come pure le due dimensioni 8x8. Non può essere utilizzato nel nostro caso (la scacchiera è composta da 125 caselle, con tre dimensioni 5x5x5, e non vi sono potenze di 2 fra questi numeri), ma lo citiamo, senza spiegarlo, per completezza.

5. Bitboard: Anche questo metodo non funziona per noi. Consiste nello sfruttare la parallelizzabilità del calcolo in caso di processori a 64 bit quando le caselle sono 64, come negli scacchi normali. Anche questo è citato solo per completezza

6. Notazione Forsyth–Edwards (FEN)

Basata su un sistema ideato dal giornalista scozzese David Forsyth, è stata estesa da Steven J. Edwards per utilizzi informatici. Un “record” FEN definisce una particolare posizione di gioco; si tratta di una stringa di caratteri ASCII tutti sulla stessa riga, contenente sei campi, separati da uno spazio. I campi sono: (NB: la sguente descrizione si riferisce al regolamento degli scacchi classici. E’ qui riportata per confronto con la variante FEN elaborata per il caso nostro e descritta in seguito)

a. Posizionamento dei pezzi (dalla prospettiva del bianco) Ciascuna delle 8 righe è descritta come segue, ed è separata dalle altre utilizzando il carattere “/”. Seguendo la notazione algebrica standard (stessa iniziale dei pezzi descritta in questo documento nella parte di analisi), i pezzi bianchi sono designati usando lettere maiuscole (“PNBRQK”) mentre quelli neri con lettere minuscole (“pnbrqk”). Le caselle vuote consecutive vengono raggruppate e indicate con cifre da 1 a 8.

b. Colore di chi ha il tratto “w” per bianco (white), “b” per nero (black).

25

c. Arrocco Se non si può più arroccare si segnerà “-“. Altrimenti il vocabolario è il seguente: “K” (il bianco può arroccare dal lato di re), “Q” (il bianco può arroccare dal lato di regina), “k” (il nero può arroccare dal lato di re), “q” (il nero può arroccare dal lato di regina).

d. En Passant Se un pedone può essere mangiato “en passant” si segneranno le coordinate della casella sulla quale finirà un eventuale pedone avversario che effettuerà la mangiata. Altrimenti si segna “-“.

e. Halfmove clock Così si definisce il numero di mezze mosse passate da quando è stato mosso un pedone o mangiato un pezzo. Se raggiunge 100 la partita è pari.

f. Fullmove number: Il numero di mosse complete eseguite fino al momento della scrittura della posizione. Comincia da 1 e viene incrementato ogniqualvolta muove il nero.

Esempio di record FEN per scacchi classici (appena descritto) nella posizione iniziale: rnbqkbnr/pppppppp/8/8/8/8/PPPPPPPP/RNBQKBNR w KQkq - 0 1

Ispirandoci a questa notazione possiamo derivarne con poco sforzo

una rappresentazione appropriata ed intuitiva per il caso preso in esame da questa tesi. Notazione Forsyth–Edwards-Raumschach (FENR) Non contemplando il regolamento del gioco da noi preso in esame la presa “en passant” né tantomeno alcun tipo di arrocco, i campi che compongono un record FENR saranno soltanto 4, separati da spazi. Gli ultimi 3, ovvero “Colore di chi ha il tratto”, “Halfmove clock” e “Fullmove number”, rimarranno fedeli all’originale. Il primo, riguardante la descrizione del posizionamento dei pezzi, sarà annotato come segue. Come nell’originale la scacchiera verrà rappresentata dal punto di vista del bianco. I piani saranno scritti dal più alto al più basso. La rappresentazione delle caselle vuote e le lettere rappresentanti i pezzi seguiranno le regole dell’originale, con l’aggiunta della “u” e “U” per gli unicorni rispettivamente neri e bianchi.

26

Come nell’originale le righe saranno separate da “/”. I piani, invece, saranno separati da “-“. Esempio di record FENR per 3D Chess nella posizione iniziale: rnknr/ppppp/5/5/5-buqbu/ppppp/5/5/5-5/5/5/5/5-5/5/5/PPPPP/BUQBU-5/5/5/PPPPP/RNKNR w 0 0

(cfr. con fig. 2).

7. Mailbox Array E’ una variante della struttura dati Array Based (descritta al punto 2), mantiene i suoi vantaggi ed abbatte la difficoltà di determinare, durante la generazione delle mosse, se la mossa generata finisca dentro o fuori dalla scacchiera. Descriviamo dapprima il metodo utilizzato negli scacchi classici, più semplice in quanto riferito ad una scacchiera bidimensionale. Per rappresentare la scacchiera si utilizzano 2 array monodimensionali di interi. Uno formato da 8 ∗ 8 = 64 caselle, denominato “addresser”. L’altro formato da 12 ∗ 12 = 144 caselle, denominato “mailbox”. Mailbox sarà così composto:

-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 0 1 2 3 4 5 6 7 -1 -1 -1 -1 8 9 10 11 12 13 14 15 -1 -1 -1 -1 16 17 18 19 20 21 22 23 -1 -1 -1 -1 24 25 26 27 28 29 30 31 -1 -1 -1 -1 32 33 34 35 36 37 38 39 -1 -1 -1 -1 40 41 42 43 44 45 46 47 -1 -1 -1 -1 48 49 50 51 52 53 54 55 -1 -1 -1 -1 56 57 58 59 60 61 62 63 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1

27

Addresser sarà invece composto come segue:

26 27 28 29 30 31 32 33 38 39 40 41 42 43 44 45 50 51 52 53 54 55 56 57 62 63 64 65 66 67 68 69 74 75 76 77 78 79 80 81 86 87 88 89 90 91 92 93 98 99 100 101 102 103 104 105 110 111 112 113 114 115 116 117

Ovvero addresser conterrà tutti e soli, nell’ordine, gli indici delle caselle di Mailbox che non contengono −1. A questi due array si aggiunge la scacchiera Array Based, sia esso ℎ�� , costituita da un array monodimensionale di interi composto da 64 caselle. I pezzi vengono rappresentati in esso con valori convenzionali. Esempio: 0: casella vuota 1: pedone bianco , -1 pedone nero 2: unicorno bianco , -2 pedone nero 3: cavallo bianco , -3 cavallo nero 4: alfiere bianco , -4 alfiere nero 5: torre bianca , -5 torre nera 6: regina bianca , -6 regina nera 7: re bianco , -7 re nero

Ora, per ogni verso in cui ciascun pezzo può muoversi si definisce un offset. Aggiungendo questo offset all’indice della casella in cui esso si trova si otterrà la successiva casella nella direzione di movimento di quell’offset. Ad esempio, per l’alfiere gli offset saranno 4, uno per ogni direzione, e saranno −13, −11, 11, 13. Infatti, un ipotetico alfiere in posizione 115, ovvero la posizione di partenza dell’alfiere di re bianco, potrebbe muoversi ad esempio nelle caselle 115 − 13 = 102 e 115 − 11 = 104 (prendendo come riferimento l’array Addresser). E infatti:

mailbox[102] contiene 52

e mailbox[104] contiene 54

Infatti 52 e 54 sono le nuove coordinate dell’alfiere nella scacchiera Array Based.

28

Si vede subito che tentando di far muovere l’alfiere in questione fuori dalla scacchiera si ottiene −1. Infatti 115 + 11 = 126 e 115 + 13 = 128. E

mailbox[126] contiene -1

e mailbox[128] contiene -1

Vediamo l’algoritmo in linguaggio naturale: con questo sistema, per ogni casella !�" 0 ≤ ≤ 63 sarà necessario e sufficiente:

• Se la casella non è vuota, fare riferimento agli offset del pezzo in essa contenuto.

• Per ogni offset:

1. Sommare il primo offset ad $��[ ]. Sia �� l’intero così ottenuto.

2. Se '�()�� [��] contiene −1 fermarsi e passare all’offset successivo. Se sono finiti gli offset, passare alla casella successiva.

3. Altrimenti significa che il pezzo può muoversi in

ℎ��['�()�� [��]] , a meno che questa casella non sia occupata da un altro pezzo dello stesso colore o che a seguito di questa mossa il re non venga messo sotto scacco.

4. Se il pezzo può muoversi di più caselle in una direzione

(alfiere, torre o regina) ripetere il punto 1. Altrimenti passare all’offset successivo. Se sono finiti gli offset, passare alla casella successiva.

NOTA: Le colonne e le righe contenenti −1 sono due per ogni lato dell’array. Ne basterebbero soltanto una per lato se non fosse per il cavallo, il quale nel caso in cui si trovasse sul bordo di uno dei lati potrebbe essere spinto appunto di due colonne, o righe, fuori dalla scacchiera da uno dei suoi offset. A questo punto si può immaginare un’implementazione di questo algoritmo in C. Avendo già descritto l’algoritmo in linguaggio naturale sembra superfluo utilizzare lo pseudocodice, e più appropriato il C, anche per sottolineare la semplicità di calcolo ottenuta con la struttura dati “Mailbox Array” Siano:

29

• “mailbox” l’array da 144 caselle. • “addresser” l’array da 64 caselle. • “chessboard” la scacchiera Array Based (supponiamo che il

valore convenzionale per “casella vuota” sia zero), quindi da 64 caselle.

• “color” un array da 64 caselle contenente −1, 1 o 0 a seconda che una casella sia occupata da un pezzo nero, bianco o vuota, rispettivamente.

• “offset” un array bidimensionale contenente in ogni colonna tutti gli offset per muovere ciascun pezzo (zero per i pezzi che hanno meno direzioni).

• “slide” un array di boolean che contiene “vero” nelle celle destinate ad alfiere, torre e regina, “falso” nelle altre.

L’algoritmo necessario a determinare tutte le caselle in cui il pezzo contenuto nella casella “i” (da zero a 64) può essere mosso è il seguente: // *** ALGORITMO DI GENERAZIONE MOSSE

BOOL is_moveable = FALSE; int n; for (j = 0; j < offsets[piece[i]]; ++j)

//il tipo di pezzo contenuto in piece[i] //ha offsets[piece[i]] offset diversi

for (n = i;;) {

//inizializzazione e ciclo infinito //”n” è la casella da esaminare n = mailbox[addresser[n] + offset[piece[i]][j]]; //utilizzando le schematizzazioni di mailbox e //addresser sopra indicate è facile capire che //con questa operazione “n” diventa -1 nel caso //in cui il movimento usando l’offset //individuato nel modo descritto porti fuori //dalla scacchiera

if (n == -1)

break; //se siamo usciti dalla scacchiera ci fermiamo //e passiamo all’offset successivo if (color[n] != 0) { //se la casella non è vuota...

if (color[n] == not_my_side) is_moveable = TRUE;

//se è occupata da un pezzo avversario allora

30

//è possibile occuparla (catturando il pezzo)

break;

} is_moveable = TRUE;

if (!slide[piece[i]])

break; //se si tratta di alfiere, torre o regina //esaminiamo un ulteriore spostamento nella //direzione dell’offset preso in esame }

E’ chiaro che questo algoritmo risolve il problema della generazione delle mosse Passando tutte le 64 caselle in questo modo si ha rapidamente la situazione della scacchiera in una determinata posizione. A questo punto si tratta di portare questo metodo alla nostra situazione di scacchiera cubica. A tal proposito, sarà sufficiente:

1. Modificare l’array “Mailbox” in un array con 9x9x9 = 729

caselle, in modo da avere in ogni direzione sufficiente spazio per eventuali pezzi “caduti” fuori dalla scacchiera. Per ogni dimensione, infatti, avremo le 5 caselle utili più 2 caselle per lato (necessarie a mantenere i movimenti dei cavalli)

2. Modificare l’array “addresser” trasformandolo in un array di 125 caselle. Anch’esse, come nell’esempio degli scacchi classici, dovranno contenere gli indirizzi delle caselle di Mailbox che non contengono “-1”.

3. Costruire opportunamente l’array degli offset basandosi

sulle dimensioni di “mailbox”.

4. Modificare gli array “chessboard” e “color” in array da 125 caselle.

5. Modificare l’array “slide” aggiungendo ad esso l’unicorno.

L’algoritmo resterà invariato e il metodo sarà applicabile al caso nostro.

31

Soluzione adottata

La soluzione più adatta al caso nostro è sicuramente “Mailbox Array”, unendo essa la praticità della scacchiera “Array Based” senza però gli handicap di inefficienza di cui quest’ultima soffre. Anche la facilità di adattabilità della metodologia al nostro tipo di problema la rende la miglior candidata fra le proposte elencate. Esso però è difficilmente applicabile al caso del pedone: il movimento del pedone è condizionato in modo particolare dai pezzi avversari che lo circondano; esso infatti può muovere in diagonale soltanto se vi sono presenti pezzi avversari nelle caselle di destinazione (per un’accurata descrizione del movimento del pedone v. Analisi). Basterà utilizzare l’algoritmo di generazione precedentemente individuato solo per i pezzi che non siano pedoni, anteponendo ad esso un controllo condizionale. Per i pedoni sarà sufficiente controllare lo stato delle 6 caselle interessate dal movimento di ciascuno di loro, a seconda che sia nero o sia bianco, in modo da massimizzare l’efficienza pur scrivendo codice ridondante. In pseudocodice: foreach (casella c della scacchiera) { if (color[c] == colore di turno) { if (piece[c] == pedone) { if(color[c] == bianco) { //controllo dello stato delle 6 caselle //corrispondenti al movimento pedone bianco } else { //controllo dello stato delle 6 caselle //corrispondenti al movimento pedone nero } } else { //esegui algoritmo di generazione mosse

} } }

I dettagli sulla effettiva implementazione sono riportati nella sezione dedicata alla realizzazione.

32

Tecniche di ricerca

La ricerca di una mossa in un gioco a turni si risolve, in generale, sotto forma di ricerca in un albero. La prima idea che viene in mente è impostare una massima profondità, generare tutto l’albero fino a quella profondità e valutare le “foglie”, ovvero le posizioni definite terminali. E’ ovvio che in ogni caso la “visibilità” che l’algoritmo consente è limitata dalla profondità impostata. Questo fenomeno è chiamato “horizon effect”: il numero dei possibili stati, o posizioni, è molto grande e I computer possono cercare soltanto fra una piccola parte di essi. Perciò potrebbe capitare ad esempio che la mossa ritenuta migliore guardando soltanto 5 mosse più avanti risulti disastrosa, al punto di essere determinante per la perdita della partita (pensiamo ai famosi “sacrifici”: ne è un esempio lampante la famosa partita a scacchi detta “L’immortale”, nella quale il bianco vince pur essendo in schiacciante inferiorità numerica). Per questo motivo negli anni si è tentato di ottimizzare la ricerca della mossa migliore facendo in modo di selezionare i “rami” nei quali cercare con profondità maggiore o nei quali cercare prima. Perciò il problema della ricerca viene a sua volta scomposto in tre problemi:

1. Algoritmo di ricerca da utilizzare 2. Come ottenere una differenza efficace di profondità nella ricerca 3. In quale ordine effettuare la ricerca nei vari livelli dell’albero

Algoritmo di ricerca

Di seguito si elencano brevemente alcune fra le procedure di ricerca più utilizzate:

• Minimax Così cita il teorema del minimax (dalla teoria dei giochi): per ogni gioco a somma zero con strategie finite che interessa due giocatori, esiste un valore V ed una strategia mista per ciascun giocatore tale che:

a. Data la strategia del giocatore 2, il miglior risultato per il giocatore 1 è V.

b. Data la strategia del giocatore 1, il miglior risultato per il giocatore 2 è –V.

Senza entrare neapprofondimento va al di là dello scopo di questa tesi, possiamo applicare questo teorema agli scacchi, ed anche ai nostri scacchi 3D. Infatti, dall’applicazione dell’algoritmo minigeneralmente a cercare la miglior mossa successiva in un gioco di n giocatori. Viene associate un valore a ciascuna posizione o stagioco; questo valore indica quanto buono è per un giocatore raggiungere qmassimizza il minimo valore della posizione risultante dalle possibili mosse successive dell’avversario. Il valore dei nodi viene valutato con una funzione euristica discussa e descritta più avanti. Di seguito un’implementazione in maximin.

function minimax(node, depth, if ((node è un nodo terminale return else

α := - foreach

α := max(α, return α

Alla prima chiamata si smuovere e la profondità massima da raggiungere.

Senza entrare nel merito della teoria dei giochi, il cui approfondimento va al di là dello scopo di questa tesi, possiamo applicare questo teorema agli scacchi, ed anche ai nostri scacchi 3D.

l’applicazione del teorema del minimax scaturisce l’algoritmo minimax. Esso è un algoritmo ricorsivo che serve generalmente a cercare la miglior mossa successiva in un gioco di n

Viene associate un valore a ciascuna posizione o stagioco; questo valore indica quanto buono è per un giocatore raggiungere quella posizione. Il giocatore poi farà la mossa che massimizza il minimo valore della posizione risultante dalle possibili mosse successive dell’avversario.

Il valore dei nodi viene valutato con una funzione euristica discussa e a più avanti.

Di seguito un’implementazione in pseudocodice dell’algortimo

minimax(node, depth, color) node è un nodo terminale) or (depth == 0

return color * (valore euristico del nodo

-∞ foreach child of node α := max(α,-minimax(child, depth-1), -color)

α

Alla prima chiamata si setta il nodo di partenza, il colore che deve muovere e la profondità massima da raggiungere.

Fig. 4 Esempio di albero minimax con valori calcolati

Min

33

approfondimento va al di là dello scopo di questa tesi, possiamo applicare questo teorema agli scacchi, ed anche ai nostri scacchi 3D.

minimax scaturisce max. Esso è un algoritmo ricorsivo che serve

generalmente a cercare la miglior mossa successiva in un gioco di n Viene associate un valore a ciascuna posizione o stato del

gioco; questo valore indica quanto buono è per un giocatore la mossa che

massimizza il minimo valore della posizione risultante dalle possibili

Il valore dei nodi viene valutato con una funzione euristica discussa e

pseudocodice dell’algortimo

depth == 0)) valore euristico del nodo)

color)

etta il nodo di partenza, il colore che deve

Min

34

• Alfa-Beta pruning

È un algortimo di ricerca il cui obiettivo è ridurre il numero di nodi da valutare rispetto all’algoritmo minimax: esso infatti smette di valutare una mossa quando è stata trovata almeno una possibilità in grado di provare che la mossa in questione è peggiore di una precedentemente esaminata. Questo farà sì che tale mossa non necessiti di ulteriore valutazione. E’ un’ottimizzazione che non cambia il risultato dell’algoritmo, quindi sicuramente da adottare. I benefici dell’alfa-beta pruning consistono nel fatto che utilizzandolo si riescono ad eliminare rami dell’albero di ricerca: in questo modo il tempo di ricerca può essere limitato ai rami “più promettenti”, permettendo così una più profonda ricerca. L’ottimizzazione riduce la profondità effettiva a poco più della metà rispetto al minimax se i nodi sono valutati in ordine ottimale o quasi ottimale. La dimostrazione di tale affermazione esula dagli obiettivi di questa tesi. L’algoritmo funziona mantenendo due valori, alfa e beta, che rappresentano il minimo punteggio ottenibile dal giocatore massimizzante e il massimo punteggio ottenibile dal giocatore minimizzante, rispettivamente. Alfa è inizialmente infinitamente negativo, beta infinitamente positivo. La loro distanza decresce al progredire della ricorsione. Nel momento in cui beta diventa minore di alfa significa che la posizione corrente non può essere il risultato del gioco ottimale di entrambi i giocatori, perciò diventa inutile esplorarla ulteriormente: è infatti inutile esplorare eventualità di gioco non ottimali nella speranza che esse si verifichino; questo, negli scacchi ma non solo, è uno dei più gravi e comuni errori dei giocatori principianti: sperare in un grossolano errore dell’avversario per assicurarsi la vittoria.

Fig. 5 - Una illustrazione di migliora la soluzione (nell'esplorazione da sinistra a destra). "min" e "max"

rappresentano i turni del giocatore e dell'avversario rispettivamente.

Pseudocodice dell’algori function alfa //β rappresenta la miglior scelta della mossa preecedente (e quindi dell’altro giocatore) if ((node return foreach α := ma // uso if return

//chiamata inizialealfabeta(origin, depth,

NOTA: Dalla fig. 5 si nota che se i sottorami di terzo livello, figli del nodo di secondo livello marcato con valore 3, fossero scambiati di posto, uno di loro non verrebbe nemmeno analizzato perché verrebbe tagliato fuori dal pruning. Infatti la tecnica di putilizzando metodi di ordinamento euristici per alberi che probabilmente potrebbero causare tagli se analizzate per prime. Idealmente, sarebbe necessario che fossero esaminate per prime le mos Una delle tecniche più diffuse in questo senso, per la sua efficacia e basso costo di calcolo, è la cosiddetta

Una illustrazione di alfa-beta pruning. Esplorare i sottoalberi in grigio non

migliora la soluzione (nell'esplorazione da sinistra a destra). "min" e "max" rappresentano i turni del giocatore e dell'avversario rispettivamente.

Pseudocodice dell’algoritmo:

alfabeta(node, depth, α, β) rappresenta la miglior scelta della mossa

preecedente (e quindi dell’altro giocatore) node è un nodo terminale) or (depth =

return (valore euristico del nodo) foreach child of node

α := max(α, -alfabeta(child, depth-1,// uso della simmetria, -β diventa α if β≤α

break // Beta cut-off return α

//chiamata iniziale beta(origin, depth, -infinity, +infinity)

i nota che se i sottorami di terzo livello, figli del nodo di secondo livello marcato con valore 3, fossero scambiati di posto, uno di loro non verrebbe nemmeno analizzato perché verrebbe tagliato fuori dal pruning.

Infatti la tecnica di pruning può venire ulteriormente migliorata utilizzando metodi di ordinamento euristici per individuare parti di alberi che probabilmente potrebbero causare tagli se analizzate per prime. Idealmente, sarebbe necessario che fossero esaminate per prime le mosse “migliori”.

Una delle tecniche più diffuse in questo senso, per la sua efficacia e basso costo di calcolo, è la cosiddetta killer heuristic.

35

beta pruning. Esplorare i sottoalberi in grigio non migliora la soluzione (nell'esplorazione da sinistra a destra). "min" e "max"

rappresentano i turni del giocatore e dell'avversario rispettivamente.

) rappresenta la miglior scelta della mossa

depth == 0))

1,-β,-α))

infinity, +infinity)

i nota che se i sottorami di terzo livello, figli del nodo di secondo livello marcato con valore 3, fossero scambiati di posto, uno di loro non verrebbe nemmeno analizzato perché verrebbe tagliato

può venire ulteriormente migliorata individuare parti di

alberi che probabilmente potrebbero causare tagli se analizzate per prime. Idealmente, sarebbe necessario che fossero esaminate per

Una delle tecniche più diffuse in questo senso, per la sua efficacia e

36

• Killer Heuristic Si tratta di una tecnica di ordinamento di alberi in supporto all’algoritmo di alfa-beta pruning. Si tenta di produrre un cutoff sperando che una mossa che ha prodotto un cutoff in un altro ramo dell’albero alla stessa profondità produca un cutoff nella posizione in cui ci si trova al momento. Particolarmente efficace negli scacchi, dove spesso una mossa buona si rivela tale anche in posizioni di poco diverse. Perciò, esplorando la mossa killer prima di altre mosse spesso si riesce a creare un taglio, il cui beneficio sarà tanto maggiore quanto minore sarà la profondità in cui lo si esegue. History Heuristic Ulteriore evoluzione, di comprovata efficacia negli scacchi classici, è la cosiddetta history heuristic. Si costruisce una tabella di mosse, indicizzandole in qualche modo, ad esempio tramite il pezzo che muove e la casella di destinazione. Al verificarsi di un taglio l’elemento appropriato della tabella viene incrementato, ad esempio aggiungendo ad esso la profondità rimanente (quindi mosse meno profonde risulteranno avere punteggio più alto). In questo modo si tenderà a privilegiare, fra le mosse che hanno causato tagli, quelle avvenute in rami meno profondi dell’albero, quindi in grado di produrre tagli più cospicui. Qualunque sia l’algoritmo di ordinamento utilizzato, questo dovrà avvenire prima della ricerca sull’albero.

• Quiescenza

Questo metodo di ricerca si è provato funzionale sperimentalmente, e deriva da un’imitazione di comportamento umano: un giocatore infatti tende istintivamente ad analizzare più in profondità situazioni “agitate”, ovvero mosse attraverso le quali la posizione viene profondamente alterata; tipicamente, mosse di cattura. Il metodo consiste semplicemente nel dedicare maggiore profondità all’analisi di mosse di cattura.

• Principal Variation + Iterative Deepening Il termine variazione si riferisce ad una specifica sequenza di mosse in un gioco a turni generico; spesso è utilizzato per identificare un ipotetico stato futuro del gioco.

37

La variazione principale (principal variation) è quella particolare variazione che è la più vantaggiosa per il giocatore corrente, assumendo che il giocatore avversario risponda con le mosse per lui di volta in volta migliori. In altre parole essa è la “migliore” o “corretta” linea di gioco. Nel contesto qui preso in esame si indica con variazione principale la sequenza che il giocatore computerizzato crede essere la migliore; questo assunto non è garantito a causa dell’euristicità dell’algoritmo di valutazione e dell’horizon effect.

Fig. 6 In blu la variazione principale di un ipotetico albero minimax

Estendendo ancora il significato del termine, si può pensare di avere una variazione principale per ciascun grado di profondità dell’albero: ciascuna di esse sarebbe lunga quanto la profondità esaminata. Utilizzare un array bidimensionale quadrato (avente come “lato” la massima profondità che si decide di analizzare), unito ad uno schema iniziale di iterative deepening, ovvero un ciclo che richiama l’algoritmo di alfa-beta pruning con limite di profondità inizialmente pari a 1 e ad ogni iterazione incrementato fino ad un certo massimo, permette di mantenere la “storia” delle soluzioni trovate e l’evoluzione della soluzione migliore trovata verso l’ottimalità attraverso i vari passaggi all’interno dell’albero.

38

Soluzione adottata

Per la sua comprovata capacità di migliorare l’efficienza rispetto al Minimax, l’algoritmo che si utilizzerà sarà l’alfa-beta pruning, corredato da ricerca di quiescenza a profondità maggiore. Inoltre, si utilizzerà una tabella per l’implementazione dell’algoritmo “History Heuristics”. In questo modo si potrà efficientemente compiere ricerche in profondità nell’albero, potendo così supplire alle carenze (inevitabili) della funzione di valutazione della posizione. Si è desciso di utilizzare una ricerca a tre livelli. Riferendosi alla figura 7: una prima funzione, think, richiama l’algoritmo alfa-beta pruning, chiamato search, dando ad esso profondità limite inizialmente pari ad 1 e ad ogni iterazione incrementata di 1. Questo è necessario per soddisfare il requisito della limitazione temporale nella nostra ricerca: alfa-beta pruning è un algoritmo di tipo depth-first; questo significa che non si ha soluzione fino a che non è stato esplorato tutto l’albero alla massima profondità desiderata. Invece, impostando la profondità massima di volta in volta maggiore, ed utilizzando un array per contenere tutte le variazioni principali ottenute nelle varie iterazioni, l’algoritmo di ricerca potrà essere interrotto anche dopo brevissimo tempo: in caso di interruzione verrà utilizzata la miglior soluzione trovata fino a quel momento, indipendentemente da quanto in profondità si sia riusciti ad andare. Ad ogni iterazione viene chiamata la search, che implementa alfa-beta pruning. Essa genera tutte le mosse possibili nella posizione corrente e, iterando sull’elenco che le contiene, ne esegue la i-esima, richiama sé stessa (invertendo alfa e beta perché il punteggio del giocatore nero è opposto a quello del giocatore bianco) riducendo la profondità rimanente (depth), annulla la mossa i-esima. Poi controlla il valore restituito dalla chiamata ricorsiva, e, se è avvenuto un cut-off, aggiorna la tabella per history heuristics, aggiorna l’array delle variazioni principali, e aggiorna il valore di alfa. Proseguendo con la ricorsione, la profondità rimanente (depth) descresce fino ad arrivare a zero. A quel punto viene richiamata un’altra funzione che implementa l’alfa-beta pruning, chiamata quiesce. Essa, a differenza di search, genera soltanto mosse di cattura; così facendo si è implementata la ricerca estesa per situazioni dove il punteggio della posizione può variare di molto (per l’appunto nel caso di catture di pezzi). In essa avviene anche la chiamata alla funzione di valutazione della posizione.

39

Con il sistema così progettato si può ottenere grande profondità di calcolo nell’esplorazione della posizione nel caso il tempo concesso al computer sia elevato e contemporaneamente una risposta in breve tempo nel caso si volesse dare al software soltanto pochi secondi per decidere.

40

Fig. 7 -Algoritmo semplificato di ricerca della mossa migliore

41

Valutazione di una posizione

Questo, dei tre problemi è sicuramente il più arduo: come valutare la bontà di una posizione? Molte sono le strategie di calcolo utilizzate negli scacchi normali. In ogni caso, la valutazione avviene con un algoritmo molto specifico, che funziona soltanto per lo speciale gioco degli scacchi classici. Tuttavia, alcuni fattori di cui si tiene conto negli scacchi possono essere utilizzati anche nel nostro caso. Sicuramente saranno sufficienti a giungere ad una soluzione iniziale soddisfacente, in modo che l’utente percepisca un certo grado di intelligenza nella scelta delle mosse da parte del computer, in quanto sono le più influenti anche nelle scacchi classici. In ogni caso si tratta sempre di algoritmi euristici, per i quali non riusciamo nemmeno a stimare il grado di ottimalità della soluzione trovata. Vediamo gli accorgimenti applicabili.

Alternative progettuali

• Bilanciamento degli schieramenti

Il modo più intuitivo per assegnare un punteggio ad una posizione è contare quanto “materiale”, nel senso di pezzi, è ancora disponibile al bianco e quanto al nero. Inizialmente, entrambi dispongono di dieci pedoni, due unicorni, due cavalli, due alfieri, due torri, una regina, e naturalmente un re. La “potenza” di un pezzo è determinata unicamente dal suo grado di mobilità. La mobilità dipende sia da come esso può intrinsecamente muoversi (per regolamento) sia dalla sua posizione sulla scacchiera.

42

Vediamo in una tabella le “potenzialità” di ciascun pezzo:

Pezzo

Direzioni Caselle

Slide Note Al

centro

Sui

vertici

Al

centro

Sui

vertici

Unicorno 8 1 8 4 Sì Può muoversi in un ristretto numero di caselle

rispetto le 125 totali (vedi fig.8)

Cavallo 24 8 24 8 No

La sua mobilità è ostacolata soltanto da pezzi

presenti sulle caselle di destinazione e non da

quelli sul tragitto (“salta” oltre i pezzi).

Alfiere 12 3 32 12 Sì Può muoversi su metà delle caselle totali

(quelle del colore della sua casa di partenza)

Torre 6 3 12 12 Sì Può muoversi sempre al massimo in 12 caselle,

a meno che non vi siano ostacoli sul tragitto.

Regina 26 7 52 28 Sì Ad ogni mossa possiede le mobilità addizionate

di un alfiere, di una torre e di un unicorno.

Re 26 7 26 7 No

Come tutti i pezzi è molto mobile al centro

della scacchiera. Tuttavia è opportuno tenerlo

“in salvo” in quanto la sua perdita comporta la

sconfitta. Il suo valore sarà quindi infinito.

Il pedone non è qui trattato, essendo un pezzo “speciale” sotto molti punti di vista. Alcuni chiarimenti sulla tabella: con “slide” stiamo ad indicare se un pezzo può “scivolare” di più caselle in una direzione, nel modo in cui lo fanno appunto l’alfiere, la torre, la regina e l’unicorno. Nella tabella si è tentato di quantificare intuitivamente in prima approssimazione la mobilità dei pezzi, confrontando il numero di direzioni e il numero di caselle in cui ciascun pezzo può muoversi nel caso esso si trovi su una scacchiera vuota in un vertice oppure al centro. Risulta immediatamente chiaro che alcuni pezzi sono sempre più mobili di altri, e tutti traggono beneficio quando sono spostati verso il centro della scacchiera. Ad esempio, è chiaro che l’unicorno è sicuramente il pezzo di minor valore fra quelli segnati in tabella: non solo non è molto mobile, ma non può nemmeno viaggiare su tutta la scacchiera, bensì solo su una minima parte di essa (circa ¼ delle caselle). Per contro, la regina è sicuramente il pezzo che vale di più (ricordiamo che il re ha valore idealmente infinito, quindi non conta), in quanto essa è il pezzo più mobile di tutti.

43

Fig. 8 - I 4 “tipi” di unicorno diversi e il dettaglio delle loro mobilità.

La cosa più difficile nella valutazione del materiale a disposizione è quantificare il valore dei singoli pezzi; negli scacchi classici si sono fissati, nei secoli di esperienza, alcuni valori di riferimento:

o Pedone: 1

o Cavallo: 3

o Alfiere: 3 o Torre: 5 o Regina: 9

In realtà vi sono opinioni discordanti, spesso all’alfiere viene attribuito un valore maggiore che al cavallo. Poi verso il finale, ovvero quando ad un certo punto i pezzi in gioco cominciano ad essere “pochi”, i valori cambiano. Inoltre, il valore dei pedoni negli scacchi classici varia fortemente a seconda della posizione del pedone: se infatti esso può facilmente essere portato in zona di promozione varrà la pena difenderlo anche a costo di perdere ad esempio una torre ed un alfiere, per guadagnare una regina.

44

Indipendentemente da tutto ciò, analizzando la nostra variante 3D, ci si accorge che i valori non vi si adattano: la torre, ad esempio, non è così “potente” come negli scacchi, perde infatti nella terza dimensione la sua funzione di “muro”; inoltre non è più così efficace nel sostegno dei pedoni. Lungi dagli obiettivi di questa tesi eseguire un approfondito studio sul punteggio base da assegnare ai pezzi, si è immaginata una sorta di “traduzione” dagli scacchi classici agli scacchi 3D, successivamente spiegata.

• Sviluppo Il valore di un pezzo è tanto maggiore quanto maggiore è la sua influenza sulla scacchiera. Ad esempio una torre nella sua posizione originale non “controlla” nessuna casella, ovvero non può muoversi perché bloccata da altri pezzi del suo stesso schieramento. I pezzi hanno massima influenza quando sono mossi verso il centro della scacchiera. Per questi motivi, negli scacchi classici si costruiscono array di interi di dimensioni della scacchiera, i cui valori corrispondono a piccoli incrementi o decrementi di punteggio da applicare ai pezzi a seconda della loro posizione. In questo modo una scacchiera con pezzi sviluppati varrà di più rispetto ad una con i pezzi bloccati nelle posizioni originali. Nel caso nostro sarà semplice adattare una simile tecnica, non essendo obiettivo di questa tesi individuare i numeri ottimali per ottenere la valutazione più precisa: sarà sufficiente un array con somma zero e valori tanto cospicui da fare la differenza rispetto ad un metodo di valutazione privo di questo accorgimento.

• Struttura dei pedoni Negli scacchi classici, in due dimensioni, risulta abbastanza semplice e intuitivo modificare il valore dei pedoni in funzione delle loro posizioni reciproche. Ad esempio, se in una colonna vi sono due o più pedoni dello stesso colore è naturale pensare che essi si ostacoleranno. Al comparire della terza dimensione tuttavia questo fenomeno tende praticamente a scomparire, muovendosi essi non solo lungo le colonne ma anche attraverso i piani.

45

Omettiamo quindi di descrivere le varie strategie utilizzate per il calcolo del valore della struttura dei pedoni negli scacchi classici, perché esse non sarebbero adottabili per nostri scacchi 3D.

• Posizione del re

Negli scacchi classici, durante l’apertura (inizio della partita) e il mediogioco (parte del gioco difficilmente definibile, in essa i pezzi sono sviluppati e sono ancora “tanti”), il re è bene che stia dove si trova all’inizio, o ancora meglio “arroccato” ad uno dei due lati. Negli scacchi 3D non vi è manovra di arrocco, quindi è consigliabile che all’inizio esso rimanga nei pressi della casella iniziale, anche perché sarebbe inutile sprecare preziose mosse di sviluppo per spostare il lento re e portarlo alla mercé dell’esercito avversario. Nel finale della partita, quando i pezzi sono “pochi”, è essenziale, negli scacchi classici, che il re partecipi attivamente al combattimento. Infatti, in tutti i finali fondamentali (re e regina contro re, re e torre contro re, re e pedone contro re, ...) esso gioca un ruolo fondamentale. Di uguale importanza, se non maggiore, sarà negli scacchi 3D, nei quali è ancora più arduo, a causa della tridimensionalità, dare lo scacco matto. E’ quindi utile individuare un momento della partita oltre il quale il re “vale” di più se portato verso il centro dela scacchiera. La metodologia più semplice da utilizzare è valutare il materiale a disposizione dell’avversario: nel momento in cui i pezzi sono troppo pochi per nuocere seriamente, allora il re potrà essere portato allo scoperto.

46

Soluzione adottata

Bilanciamento degli schieramenti

Anzitutto è opportuno fissare dei valori di base a ciascun tipo di pezzo. Ciò può essere fatto nel seguente modo: si possono definire i suddetti valori rapportando i gradi di mobilità dei pezzi negli scacchi classici con quelli degli stessi nel 3D, e variare il loro valore proporzionalmente. Nella tabella seguente si compara la mobilità di cavallo, alfiere, torre e regina negli scacchi 3D e negli scacchi classici.

Pezzo

3D Chess Scacchi Classici

Direzioni Caselle visitabili Direzioni Caselle visitabili

Al centro Sui vertici Al centro Sui vertici Al centro Sui vertici Al centro Sui vertici

Cavallo 24 8 24 8 8 2 8 2

Alfiere 12 3 32 12 4 1 13 7

Torre 6 3 12 12 4 2 14 14

Regina 26 7 52 28 8 3 27 21

Nella prossima tabella si riportano soltanto le caselle visitabili, rapportate però al numero di caselle totali della scacchiera (125 nel 3D, 64 negli scacchi classici).

Pezzo

Caselle visitabili / Caselle totali

3D Chess Scacchi Classici

Al centro Sui vertici Al centro Sui vertici

Cavallo 0.192 0.064 0.125 0.031

Alfiere 0.256 0.096 0.203 0.109

Torre 0.096 0.096 0.219 0.219

Regina 0.416 0.224 0.422 0.328

Si nota subito che il cavallo 3D risulta molto più mobile di quello classico. Al contrario, la torre è sensibilmente meno mobile, come ci si aspettava.

47

Si osservi ora nella tabella seguente l’aumento di mobilità in prossimità dei vertici e in posizione centrale di ciascun pezzo dagli scacchi classici agli scacchi 3D:

Pezzo

Fattore di incremento di mobilità nel 3D

Direzioni Caselle visitabili Caselle visitabili/Caselle totali

Al centro Sui vertici Al centro Sui vertici Al centro Sui vertici

Cavallo 3 4 3 4 1.536 2.064

Alfiere 3 3 2.286 1.714 1.261 0.881

Torre 1.5 1.5 0.857 0.857 0.438 0.438

Regina 3.25 2.333 1.857 1.333 0.986 0.683

A questo punto, applicando a questi fattori di incremento e ai valori negli scacchi classici un’opportuna funzione, sarà possibile ottenere dei valori da sperimentare nel motore per questi pezzi. Sicuramente il fattore di peso maggiore sarà il rapporto tra caselle visitabili e caselle totali, esso esprime la differenza di mobilità meglio rispetto agli altri fattori, essendo relativo. Un buon esempio potrebbe essere dare 10% di peso agli incrementi di direzioni, 14% di peso agli incrementi assoluti di caselle visitabili e 26% a quelli relativi. Perciò, definiti con +, e +. gli incrementi assoluti di direzione rispettivamente al centro e ai vertici , e . gli incrementi assoluti di caselle rispettivamente al centro e ai vertici ,; e .; gli incrementi relativi di caselle rispettivamente al centro e ai vertici il fattore selezionato è:

< = [10 ∗ (+, + +. ) + 14 ∗ ( , + .) + 28 ∗ ( ,; + .;) ]/100 Esso andrà poi moltiplicato per il valore convenzionale del pezzo negli scacchi classici. Sostituendo i valori numerici si ottiene:

o Cavallo: < = 2.616 segue punteggio: 2.616 ∗ 3 = 7.848 o Alfiere: < = 1.717 segue punteggio: 1.717 ∗ 3 = 5.151 o Torre: < = 0.768 segue punteggio: 0.768 ∗ 5 = 3.839 o Regina: < = 1.439 segue punteggio: 1.439 ∗ 9 = 12.95

48

I valori così ottenuti saranno utilizzati come punteggio base dei pezzi. Mancano ancora tuttavia Unicorno e Pedone. Per quanto riguarda l’Unicorno, esso ha una mobilità che oscilla tra

circa @

A (sui vertici) e circa

@

B (al centro) rispetto a quello della regina

(in base alle tabelle stilate). Inoltre, può muoversi al massimo su circa ¼ della scacchiera; questo fa di esso un pezzo estremamente debole e poco prezioso.

Fissiamo il valore dell’unicorno a @

C rispetto a quello della regina, cioè

2.16. Per i pedoni non si hanno parametri di valutazione da cui partire, se non il fatto che negli scacchi classici essi valgono 1 punto. Fissiamo il loro valore a 1 anche negli scacchi 3D. Si riassume nella tabella a fianco i valori di base che si è deciso di adottare, arrotondati ad una cifra decimale: sarebbe inutile essere molto precisi in quanto si tratta di valori praticamente arbitrari.

Sviluppo

I pezzi aumentano di valore quando vengono sviluppati, cioè sostanzialmente portati verso il centro della scacchiera. Questo vale quasi per tutti, a parte per i pedoni. Essi infatti valgono tanto quanto più si avvicinano alla zona di promozione. Il modo più semplice ed efficiente per ottenere questo effetto è utilizzare un array di interi grande quanto la scacchiera, inserendo un numero negativo nelle caselle “cattive” (vertici e bordi) e un numero positivo nelle caselle “buone” (centrali). Per ogni pezzo mosso si sommerà al suo valore il numero corrispondente alla casella in cui lo si vuole muovere. Questi accorgimenti si rivelano utili specialmente nella fase iniziale del gioco.

Posizione del re

Al re assegneremo in fase di realizzazione un valore incommensurabilmente alto rispetto a quello degli altri pezzi, naturalmente, perché perderlo equivale a perdere la partita.

Pezzo valore

Pedone 1

Unicorno 2.2

Cavallo 7.8

Alfiere 5.1

Torre 3.8

Regina 12.9

49

Il re necessita anche di due array di interi grandi come la scacchiera: uno per l’inizio della partita, per fare in modo che esso tenda a rimanere nella posizione iniziale, e uno per il finale. Si entrerà nel “finale” quando il valore dei pezzi avversari sarà uguale o inferiore a 1300, re escluso.

Riepilogo funzionamento globale

Fig. 9 - comportamento macroscopico del motore

In figura 9 è illustrato il comportamento del motore dal punto di vista macroscopico: la UI comunica al motore la posizione della scacchiera, intesa come stato della partita. Se valida, si generano le mosse possibili. Se ne esistono, si ricerca la mossa migliore, e la si comunica alla UI.

50

Progettazione dell’Interfaccia

Scacchiera Tridimensionale

Essa è la componente principale dell’interfaccia utente. Vale la pena stendere una breve introduzione sull’argomento grafica tridimensionale.

La grafica tridimensionale

La computer grafica 3D è un ramo della computer grafica che si basa sull'elaborazione di modelli virtuali in 3D da parte di un computer. Essa viene utilizzata insieme alla computer animation nella realizzazione di immagini visuali per cinema o televisione, videogiochi, ingegneria, usi commerciali o scientifici. Il termine può anche essere riferito ad immagini prodotte con lo stesso metodo. La grafica computerizzata tridimensionale è basilarmente la scienza, lo studio e il metodo di proiezione della rappresentazione matematica di oggetti tridimensionali tramite un'immagine bidimensionale attraverso l'uso di tecniche come la prospettiva e l'ombreggiatura (shading) per simulare la percezione di questi oggetti da parte dell'occhio umano. Ogni sistema 3D deve fornire due elementi: un metodo di descrizione del sistema 3D stesso ("scena"), composto di rappresentazioni matematiche di oggetti tridimensionali, detti "modelli", e un meccanismo di produzione di un'immagine 2D dalla scena, detto "renderer".

Modelli 3D

Oggetti tridimensionali semplici possono essere rappresentati con equazioni operanti su un sistema di riferimento cartesiano tridimensionale: per esempio, l'equazione x²+y²+z²=r² è perfetta per una sfera di raggio r. Anche se equazioni così semplici possono sembrare limitative, l'insieme degli oggetti realizzabili viene ampliato con una tecnica chiamata geometria solida costruttiva (CSG, constructive solid geometry), la quale combina oggetti solidi (come cubi, sfere, cilindri, ecc.) per formare oggetti più complessi attraverso le operazioni booleane (unione, sottrazione e intersezione): un tubo può ad esempio essere rappresentato come la differenza tra due cilindri aventi diametro differente. L'impiego di equazioni matematiche pure come queste richiede l'utilizzo di una gran quantità di potenza di calcolo, e non sono quindi pratiche per le applicazioni in tempo reale come videogiochi e simulazioni. Una tecnica più efficiente, ma che permette un minore livello di dettaglio, per modellare oggetti consiste nel rilevare solo alcuni punti dell'oggetto, senza informazioni sulla curva compresa tra di essi. Il risultato è chiamato

modello poligonale. Questo presenta "faccette" piuttosto che curve, ma sono state sviluppate tecniche ddati. Delle superfici poligonali di un modello senza informazioni sulla curvatura possono essere comunque raffinate per via algoritmica in superfici perfettamente curve: questa tecnica è chiamata "superfici di su(subsurfing), perché la superficie viene suddivisa con un processo iterativo in più superfici, sempre più piccole, fedeli alla curva interpolata e che vanno a comporre un'unica superficie sempre più liscia.

Creazione della scena

Una scena si compone di "primitive" (modelli tridimensionali che non possono essere ulteriormente scomposti).Le primitive sono generalmente descritte all'interno del proprio sistema di riferimento locale, e vengono posizionate sulla scena attraverso opportune trasformazioni. Le trasformazioni affini più impiegate, come omotetia, rotazione e traslazione, possono essere descritte in uno spazio proiettivo con una matrice 4x4: esse si applicano moltiplicando la matrice per il vettore a quattro componenti che rappresenta ogncurva. La quarta dimensione è denominata coordinata omogenea.

Rendering

Il rendering è il processo di produzione dell'immagine finale a partire dal modello matematico del soggetto (scena). rendering, ma tutti implicano la 2D. Gli oggetti tridimensionali devono essere proiettati idealmente sulla superficie bidimensionale del monitor. Il tipo di proiezione psistemi CAD e CAM si utilizza la proiezione La differenza fra le due è che nella visualizzati di dimensioni misoftware rendono la prospettiva moltiplicandelevata all’opposto della distanza dall’osservatore. prospettiva. All’aumentare di k aumenta la distorsione prospettica.

Un punto di fuga

Una trattazione dettagliata della matematica riguardande la proiezione prospettica esula dagli scopi di questo testo.

modello poligonale. Questo presenta "faccette" piuttosto che curve, ma sono state sviluppate tecniche di rendering per ovviare a questa perdita di

Delle superfici poligonali di un modello senza informazioni sulla curvatura possono essere comunque raffinate per via algoritmica in superfici perfettamente curve: questa tecnica è chiamata "superfici di su

, perché la superficie viene suddivisa con un processo iterativo in più superfici, sempre più piccole, fedeli alla curva interpolata e che vanno a comporre un'unica superficie sempre più liscia.

Creazione della scena

ompone di "primitive" (modelli tridimensionali che non essere ulteriormente scomposti).

Le primitive sono generalmente descritte all'interno del proprio sistema di riferimento locale, e vengono posizionate sulla scena attraverso opportune

zioni. Le trasformazioni affini più impiegate, come omotetia, rotazione e traslazione, possono essere descritte in uno spazio proiettivo con una matrice 4x4: esse si applicano moltiplicando la matrice per il vettore a quattro componenti che rappresenta ogni punto di controllo delle

La quarta dimensione è denominata coordinata omogenea.

è il processo di produzione dell'immagine finale a partire dal modello matematico del soggetto (scena). Esistono molti algoritmi di

ma tutti implicano la proiezione dei modelli 3D su una superficie

Gli oggetti tridimensionali devono essere proiettati idealmente sulla superficie bidimensionale del monitor. Il tipo di proiezione più usato è la prospettica, anche se ad esempio nei

stemi CAD e CAM si utilizza la proiezione ortogonale. La differenza fra le due è che nella prospettica gli oggetti più lontani sono visualizzati di dimensioni minori rispetto a quelli più vicini all’ “occhio”. software rendono la prospettiva moltiplicando una costante di dilatazione elevata all’opposto della distanza dall’osservatore. Se k = 1 non vi è prospettiva. All’aumentare di k aumenta la distorsione prospettica.

Fig. 10

Un punto di fuga - Due punti di fuga - Tre punti di fuga

Una trattazione dettagliata della matematica riguardande la proiezione prospettica esula dagli scopi di questo testo.

51

modello poligonale. Questo presenta "faccette" piuttosto che curve, ma per ovviare a questa perdita di

Delle superfici poligonali di un modello senza informazioni sulla curvatura possono essere comunque raffinate per via algoritmica in superfici perfettamente curve: questa tecnica è chiamata "superfici di suddivisione"

, perché la superficie viene suddivisa con un processo iterativo in più superfici, sempre più piccole, fedeli alla curva interpolata e che vanno

ompone di "primitive" (modelli tridimensionali che non

Le primitive sono generalmente descritte all'interno del proprio sistema di riferimento locale, e vengono posizionate sulla scena attraverso opportune

zioni. Le trasformazioni affini più impiegate, come omotetia, rotazione e traslazione, possono essere descritte in uno spazio proiettivo con una matrice 4x4: esse si applicano moltiplicando la matrice per il

i punto di controllo delle La quarta dimensione è denominata coordinata omogenea.

è il processo di produzione dell'immagine finale a partire dal Esistono molti algoritmi di

dei modelli 3D su una superficie

Gli oggetti tridimensionali devono essere proiettati idealmente sulla

, anche se ad esempio nei

gli oggetti più lontani sono nori rispetto a quelli più vicini all’ “occhio”. I

o una costante di dilatazione k Se k = 1 non vi è

prospettiva. All’aumentare di k aumenta la distorsione prospettica.

Una trattazione dettagliata della matematica riguardande la proiezione

52

Per una spiegazione intuitiva è sufficiente immaginare una videocamera che si muove all’interno di uno spazio tridimensionale. In questo spazio sono contenuti i modelli tridimensionali, nel nostro caso si tratta della scacchiera e dei pezzi. L’utente sarà in grado di controllare il “movimento” di questa videocamera ideale all’interno dello spazio 3D in modo tale da poter visualizzare comodamente.

Fig. 11 - Field of view (campo visivo) della videocamera

In figura 11 è descritto il campo visivo che viene sottoposto all’utente: è di forma tronco-conica (frustum), tutto ciò che non è contenuto in esso non viene proiettato (sulla base minore, che rappresenta la superficie dello schermo) e quindi non viene visualizzato.

Progettazione dei modelli

Vi sono principalmente quattro modi per rappresentare un modello 3D:

• Modelli poligonali – Un insieme di punti nello spazio tridimensionale, detti vertici, vengono connessi da segmenti in modo da formare una maglia (mesh). La maggior parte dei modelli 3D sono costruiti in questo modo per la loro flessibilità e velocità di rendering. Tuttavia, i poligoni sono piani, quindi con essi le curvature possono soltanto essere approssimate utilizzando un gran numero di poligoni.

53

• NURBS – Le superfici NURBS sono definite da curve spline, cioè parametrizzate da punti di controllo pesati. La curva segue (senza necessariamente interpolarli) i punti. Aumentando il peso di un punto si farà in modo che la curva passi più vicino ad esso. In questo modo si riescono ad ottenere superfici estremamente lisce.

• Splines & Patches – Come le NURBS, splines and patches dipendono da line curve per definire la superficie visibile. Sono una via di mezzo fra NURBS e poligoni in termini di flessibilità e facilità di utilizzo.

• Primitives modeling – Consiste nell’utilizzare primitive geometriche come sfere, cilindri, coni o cubi, come “mattoni” per modelli più complessi. Si ottengono così costruzioni veloci, e le forme sono matematicamente precise. Richiede però di definire geometricamente il modello da costruire; ciò non è sempre possible o facile da ottenere.

Nel nostro caso, trattandosi di pezzi degli scacchi, quindi di forme geometriche non troppo complesse, i metodi migliori sarebbero modelli poligonali o primitives modeling. Quest’ultimo sembrerebbe il più indicato, tuttavia, sebbene sia controintuitivo, i modelli ottenuti sarebbero certamente più grezzi: modellare tutto tramite primitive, infatti, implicherebbe poter utilizzare soltanto curve e forme definibili geometricamente. Invece, tramite poligoni, si avrà più rapidità al momento della costruzione dei modelli (si potranno comporre facilmente tramite una serie di punti); l’arrotondamento delle superfici si potrà ottenere per suddivisioni successive, mantenendo inoltre la massima compatibilità (i formati poligonali sono i più comuni al momento).

Pezzi

Consisteranno in sette modelli poligonali, ciascuno per un tipo di pezzo. Il colore e il posizionamento sulla scacchiera verranno dati loro dal programma di gioco.

Scacchiera

Per costruirla si utilizzerà un mattoncino fondamentale (un parallelepipedo molto esteso in larghezza rispetto alla sua altezza, una sorta di “mattonella”), ripetuto 125 volte a colorazione alterna. Si visualizzeranno cioè cinque scacchiere piane sovrapposte, come in figura 1.

54

Interazione con l’utente

Mouse – Movimentazione dei pezzi

Per muovere i pezzi si deve poter, tramite mouse, selezionare il pezzo da muovere e successivamente selezionare la casella in cui muoverlo. In figura 12 è illustrato l’algoritmo ad alto livello per la selezione del pezzo.

L’utente fa click sulla

schermata dell’interfaccia

3D

No

Ha fatto click su una

casella?

Ha fatto click su un

pezzo?

No

No

Attesa di

interazione utente

Sì

Il pezzo è suo?

Sì

Il pezzo può

muovere?

Sì

Sì

Evidenziare il pezzo e le

caselle in cui esso può

muovere

(Selezione Pezzo)

Al momento è

evidenziato un

pezzo? Sì

No

La casella è

evidenziata?No

Togliere l’evidenziazione

al pezzo precedentemente

selezionato ed alle caselle

in cui esso può muovere

(Deselezione Pezzo)

Sì

Muovere il pezzo nella

casella (Spostamento

Pezzo)

Fig. 12 - Flow chart raffigurante il loop di input da mouse per l'utente

55

Il problema fondamentale però è che l’utente fa click su un punto di una superficie piana; a partire dalle coordinate piane del click bisogna risalire a quale punto dello spazio esso corrisponde. I modelli che posizioniamo nello spazio sono costituiti da triangoli. Si tratterà quindi di determinare, ciclando su tutti i modelli contenuti nello spazio, quale di essi è il più vicino alla camera fra quelli intersecati dalla semiretta avente origine nel punto in cui l’utente ha fatto click. I modelli sono composti da triangoli. Bisognerà quindi procedere in questo modo:

1. Per ogni modello controllare se la sfera di raggio minimo che lo contiene tutto interseca la semiretta in questione.

2. Se la sfera è intersecata bisognerà testare, triangolo per triangolo, se vi sono triangoli componenti il modello che intersecano la semiretta.

3. Se ve ne sono, salvare quello di distanza minima dalla camera. Se minore di quelli precedentemente trovati, memorizzare il modello a cui appartiene.

In questo modo si troverà il modello più vicino alla camera intersecato dalla semiretta. Il problema più complesso è individuare quali triangoli di un modello, ammesso che ve ne siano, siano intersecati dalla semiretta. Un buon sistema per ottenere questo risultato è utilizzare un algoritmo il cui uso è abbastanza diffuso per casi come questo, ideato da Tomas Moller e Ben Trumbore nel 2003 chiamato “Fast, Minimum Storage Ray-Triangle Intersection". Questo algoritmo permette, senza perdita di velocità rispetto agli algoritmi precedenti, di risparmiare memoria nel suo utilizzo. In appendice si allega il documento originale che sarà utilizzato per implementare l’algoritmo nella parte di realizzazione.

Tastiera – Camera

Per far in modo che il gioco sia il più controllabile possibile, si progettano due modalità di visualizzazione (camera). Una il prima persona, che permette cioè di spostare liberamente la camera per mezzo della tastiera nello spazio contenente la scacchiera.

56

Un’altra invece vincolata alle righe e alle colonne della scacchiera: ovvero, essendovi, 5 righe e 5 colonne per ciascuno dei 5 piani, con (5 + 5) ∗ 5 = 50 posizioni; ad ogni spostamento di posizione la si farà puntare parallelamente alla direzione della riga o colonna, ma sarà possibile ruotarla sul posto per facilitare la visualizzazione. L’utente potrà in qualsiasi momento cambiare camera passando da totale libertà di movimento a controllo più vincolato.

Comunicazione Interfaccia-Motore

Differenza sostanziale tra le realizzazioni di Interfaccia e Motore sarà la tecnologia d’implementazione; per la prima è necessaria una piattaforma in grado di supportare la grafica 3D e che renda il più possibile agevole lo sviluppo di videogame, mentre per il secondo è importante l’efficienza di calcolo. Perciò, per l’Interfaccia sarà certamente opportuno utilizzare una API per il game-programming. Ve ne sono tante disponibili, ma non molte soddisfano il requisito della portabilità che è stato richiesto (vedi Analisi, pag. 17). Per quanto riguarda il Motore sarà più utile una realizzazione che non giri su macchina virtuale; in questo modo si avrà il massimo dell’efficienza. Quindi un linguaggio compilato. Per soddisfare la portabilità basterà usare un linguaggio molto diffuso, in modo che esistano compilatori per esso almeno per le piattaforme più utilizzate; certo, ci sarà bisogno di ricompilare per passare da un ambiente ad un altro, ma il requisito di efficienza è certamente più importante per ottenere un Motore “intelligente” in grado di tener testa al giocatore umano. La comunicazione fra i due è sufficiente che sia in una sola direzione, cioè dall’Interfaccia al Motore, o vice versa; non ponendo vincoli in questo frangente si lascia maggior libertà in fase di realizzazione.

57

Realizzazione

Tecnologie utilizzate

Microsoft XNA (Xbox New Architecture)

Si tratta di un inseme di tool inseriti in un ambiente di runtime “managed” il cui scopo è facilitare lo sviluppo di videogame sollevando lo sviluppatore dall’onere di dover scrivere codice ripetitivo. Comprende:

• XNA Framework

Si basa sull’implementazione del .NET Compact Framework 2.0 per Xbox 360 e su .NET Framework 2.0 per Windows. E’ disponibile per Windows XP, Windows Vista e Xbox 360; permette di scrivere i videogame per il runtime di XNA: questo fa sì che essi possano girare su qualsiasi piattaforma a patto che questa supporti il runtime.

L’utilizzo di questa tecnologia quindi ci permetterebbe di portare senza troppe difficoltà il gioco su piattaforme diverse, e ci solleva inoltre dall’onere di reinventare ciò che nel gergo del game development si definisce “game loop” (e tutto ciò che esso implica).

• XNA Build

E’ un insieme di tool per la gestione degli “asset” di gioco (icone, file audio, modelli 3D, ...). Aiuta a definire la cosiddetta game asset pipeline. Quest’ultima descrive il processo attraverso il quale i contenuti vengono trasformati in forme utilizzabili dall’engine del gioco. XNA Build permette di personalizzare a vari livelli ogni stadio della suddetta pipeline.

• Mono.XNA

E’ una implementazione cross platform di XNA gaming framework. Prende il nome da Mono, ormai nota implementazione cross platform di .NET framework Gira su Windows, MacOS e Linux e usa OpenGL per la grafica 3D. Al momento è ancora in fase di realizzazione.

Questo aspetto di XNA ci assicura la portabilità richiesta nei requisiti non funzionali. XNA sarà quindi utilizzato per la realizzazione dell’Interfaccia.

58

Blender

E’ un’applicazione per grafica 3D rilasciata sotto forma di software libero sotto GNU General Public License. Può essere usato per modeling e molto altro ancora, ed è disponibile per Linux, Mac Os X e Windows. Questo lo rende più che sufficiente per lo scopo di questa tesi. Con Blender saranno costruiti i modelli 3D di pezzi e scacchiera.

ANSI C

E’ lo standard emesso dall’American National Standards Institute (ANSI) per il linguaggio di programmazione C. ANSI C è supportato praticamente da tutti i compilatori più utilizzati; perciò, ogni programma scritto in C standard garantisce la compilazione su qualsiasi piattaforma che abbia una conforme implementazione del C. Il motore, essendo nulla più che una collezione di algoritmi e strutture dati, potrà quindi essere costruito in ANSI C per massimizzarne la portabilità pur mantenendo alta l’efficienza, trattandosi di un linguaggio compilato.

Managed/Unmanaged Interoperability

Realizzando l’Interfaccia in XNA, si utilizzerà C#, un linguaggio Microsoft facente parte del CLR di .NET. Si tratterà quindi di codice che gira in macchina virtuale, ovvero managed. Per contro, il Motore sarà scritto in ANSI C. Per la realizzazione in Microsoft Windows verrà compilato come dll C++ ed esporrà delle funzioni che potranno essere richiamate dall’Interfaccia tramite il sistema di interoperabilità tra codice managed e unmanaged. Si tratterà quindi di invocare codice unmanaged dal codice managed. Vi sono alcune alternative per compiere questa operazione:

• Platform Invoke (detta anche P/Invoke) permette di richiamare funzioni scritte in qualsiasi linguaggio unmanaged a patto che la signature sia ridichiarata in codice managed.

• COM interop permette di richiamare component COM da qualsiasi linguaggio managed.

• C++ interop (anche detta It Just Works, IJW) è una caratteristica specifica del C++ che permette di utilizzare direttamente API COM e non solo. E’ più potente di COM interop ma richiede più cura.

59

Su MSDN si raccomanda di scegliere seguendo il flow-chart riportato in figura 13.

Fig. 13 - Flow chart per la scelta della tecnologia per interoperabilità managed/unmanaged

La dll del motore non sarà certo una COM API, essendo scritta in C. Con complex API si intende un’API che ha le signature dei metodi scritte in modo difficile da dichiarare in codice managed. Essendo l’API ancora da scrivere, faremo in modo che ciò non avvenga. L’API una volta scritta rimarrà tale; o comunque il numero di funzioni sarà sufficientemente piccolo (dell’ordine della decina) che anche se varierà non sarà difficile propagare la variazione anche al codice managed. Quindi la tecnologia per la comunicazione tra Interfaccia e Motore sarà Platform Invoke.

60

Realizzazione del Motore

Il motore è stato realizzato in ANSI C, non essendovi necessità o particolari benefici nel ricorrere all’OOP in un caso come questo. Esso consiste di 5 file header “.h” e 8 file “.c”.

Header files

defs.h

defs.h, contenente la definizione delle costanti, dei tipi non primitivi utilizzati e delle variabili globali. Qui sotto si riporta uno spezzone di codice contente le strutture dati utilizzate per la memorizzazione delle mosse generate. moveBytes contiene l’indice della casella di arrivo e partenza di una mossa (from e to), il pezzo a cui viene promosso nel caso di mossa di promozione (promote), una serie di bit indicante il tipo di mossa (bits: i primi 3 bit di questo char vengono usati per indicare se si tratta di una mossa di cattura, e/o di un pedone, e/o di promozione). typedef struct { int from; int to; int promote; char bits; } moveBytes;

In union con un int in modo che si riesca a compararle rapidamente. typedef union { moveBytes b; int u; } moveUni;

gener_t associa la mossa ad un punteggio (score) utilizzato per il sorting nell’implementazione dell’history heuristics. typedef struct { moveUni m; int score; } gener_t;

history_t è invece un elemento dello stack usato per mantenere la storia della partita, in modo da poter ritornare indietro di una mossa.

61

typedef struct { moveUni m; int capture; int fiftMoves; } history_t;

protos.h

protos.h contiene i prototipi delle funzioni. Si rimanda la spiegazione di ciascuna di essi alla parte che la tratta nel dettaglio. BOOLEANVAL in_check(int s); BOOLEANVAL attack(int sq, int side); void take_back(); void generate(); void generateCaptures(); void genDo(int from, int to, int bits); void generatePromotions(int from, int to, int bits); int getSimpleStrFromMove(moveBytes, char* result); void getStringSquare(int number, char* result); void initBoard(); BOOLEANVAL doMove(moveBytes m); void parseFEN(char* FEN_string); int parseMove(char *square); int evaluate(); int eval_BLACK_king(int sq); int eval_BLACK_pawn(int sq); int eval_WHITE_king(int sq); int eval_WHITE_pawn(int sq); void sort(int from); int search(int alpha, int beta, int depth); void sort_pv(); void think(BOOLEANVAL print); int quiesce(int alpha,int beta,int depth); void checkup(); int get_ms(); void print_square(int number); void print_move_str(moveBytes m); void print_result();

altri header

RaumschachChessEngine.h, stdafx.h e targetver.h, i quali poco hanno a che fare con la realizzazione effettiva dell’algoritmo; servono infatti per il wrapping del Motore in una .dll. Per completezza, sono riportati in appendice.

62

C Files

data.c

data.c contiene tutte le strutture dati necessarie allo scopo (e previste nella progettazione):

• mailbox¸addresser, pieces, e colors per la rappresentazione della scacchiera.

• offset e offsets per la movimentazione dei pezzi. • generData per contenere le mosse generate. • pv e pvLength per mantenere ogni variazione principale trovata in

ciascuna iterazione dell’iterative deepening. • history per l’implementazione di history heuristics.

E’ stato fatto largo uso di strutture dati sovrabbondanti e dati hard-coded per massimizzare la velocità di esecuzione a scapito della flessibilità ed occupazione di memoria, come richiesto dalla progettazione. Non si riportano qui le definizioni di mailbox e addresser, semplicemente il sistema descritto nella progettazione (vedi pag. 25) è stato adattato agli scacchi 3D: mailbox rappresenta un cubo 9x9x9, cioè il cubo 5x5x5 della scacchiera contenuto in un cubo sufficientemente più grande in modo da far sì che tutte le mosse possibili di un pezzo ricadano all’interno di esso. Se una mossa risulterà nello spostamento in una cella di mailbox contenente “-1” allora significa che essa è fuori dalla scacchiera. Altrimenti, si dovrà aggiornare il valore di D(�!��[E�()�� [��]] con l’intero corrispondente al tipo di pezzo e !�)��[E�()�� [��]] con l’intero corrispondente al colore del pezzo. offsets contiene il numero di direzioni in cui ciascuno dei 7 pezzi può muovere: int off_sets[7] = { 0, 24, 8, 12, 6, 26, 26 };

La matrice offset, che non riportiamo per brevità, invece, per ciascuno dei 7 pezzi contiene il numero da sommare all’indice di mailbox corrispondente alla posizione attuale per muoversi in ciascuna delle direzioni in cui il pezzo può muoversi. Di seguito si riporta il codice rimanente con a lato i commenti esplicativi. int plyCurrent; /* the number of half-moves (plyCurrent) since the root of the search tree */ int histPlyCurrent; /* h for history; the number of plyCurrent since the beginning of the game */

63

/* generData is some memory for move lists that are created by the movegenerators. The move list for plyCurrent n starts at firstMove[n] and endsat firstMove[n + 1]. */ gener_t generData[GENE_STACK]; int firstMove[MAXIMUM_PLY]; /* a "triangular" PV array; */ moveUni pv[MAXIMUM_PLY][MAXIMUM_PLY]; int pvLength[MAXIMUM_PLY]; BOOLEANVAL followPV; /* the engine will search for maxTime milliseconds or until it finishes searching maxDepth plyCurrent. */ int maxTime; int maxDepth; /* the time when the engine starts searching, and when it should stop */ int startTime; int stopTime; int fiftMoves; /* the number of moves since a capture or pawn moveUni, used to handle the fiftMoves-moveUni-draw rule */ int nodes; /* the number of nodes we've searched */ /* the history heuristic array (used for move ordering) */ int history[125][125]; /* we need an array of history_t's so we can take back the moves we make */ history_t historyData[HISTORY_STACK];

64

board.c

board.c contiene tutte le funzioni responsabili dello stato della scacchiera: attack determina se una certa casella passata come parametro è minacciata dal bianco o dal nero. E’ molto simile a generate, utilizza un algoritmo simile a quello di quest’ultima funzione, ma limitato alle mosse di cattura. generate

genera tutte le mosse pseudo-legali nell’attuale posizione (non tiene conto dello scacco al re). Spazza la scacchiera in cerca di pezzi appartenenti al lato che ha il tratto e poi determina quali caselle essi attaccano. Quando trova una mossa possible chiama genPush che la inserisce nello stack. Di seguito riportiamo parti del codice di questa funzione indicando le parti omesse con “/* --- RIASSUNTO PARTE OMESSA --- */”. void generate() { /* ---Dichiarazioni iniziali ---*/ for (i = 0; i < 125; i++) { if (colors[i] == sideToMove) { if (pieces[i] == PAWN) {

/* --- Le mosse dei pedoni non sono trattabili con il metodo degli offset perché variano a seconda della situazione delle caselle circostanti il pedone (mosse che può fare solo in cattura). Perciò sono testate al di fuori dal ciclo principale --- */

} else //se non è un pedone {

for (j = 0; j < off_sets[pieces[i]]; ++j) { //per ogni offset di questo tipo di pezzo for (n = i;;) //ciclo infinito con inizializz. {

//n rappresenta una ipotetica casella in cui //muovere

n = mail_box[addresser[n] + off_set[pieces[i]][j]]; if (n == -1) break; //se contiene -1 siamo usciti dalla scacchiera if (colors[n] != EMPTY) { if (colors[n] == sideNotToMove)

//è una mossa di cattura! genPush(i, n, 1); break; }

65

genPush(i, n, 0); //è una mossa normale if (!slide[pieces[i]])break; } } } } } }

doMove esegue una certa mossa passata come parametro e verifica se si è sotto scacco; se sì, richiama take_back.

generateCaptures genera solo le mosse di cattura pseudo-legali nell’attuale posizione. E’ molto simile a generate e ad attack. genPush inserisce una mossa nello stack generData. Assegna inoltre alla mossa lo score per l’ordinamento dell’history heuristics. void genPush(int from, int to, int bits) { gener_t *g; //Se si è mosso un pedone si invoca genPushProms if (bits & 2) { if (sideToMove == WHITE) { if (to <= Ee5) { genPushProms(from, to, bits); return; } } else { if (to >= Aa1) { genPushProms(from, to, bits); return; } } } /* ---Inserimento dati della mossa g nello stack ---*/ if (colors[to] != EMPTY)

//se si tratta di una mossa di cattura facciamo in modo che //sia valutata prima delle altre

g->score = 1000000 + (pieces[to] * 10) - pieces[from]; else g->score = history[from][to]; }

66

genPushProms inserisce nello stack una dietro l’altra le 5 possibili mosse in caso di promozione. Si fa in modo tale da osservare per prime anche le mosse di promozione, nello stesso modo che nella genPush per le mosse di cattura, perché anche a seguito di esse la situazione muta notevolmente. initBoard

inizializza la scacchiera per l’inizio della partita. void initBoard() { //inizia il bianco sideToMove = WHITE; sideNotToMove = BLACK; //azzeramento contatore delle 50 mosse consecutive fiftMoves = 0; //azzeramento contatore delle mezze-mosse(ply) esaminate plyCurrent = 0; //azzeramento contatore delle mezze-mosse dall’inizio della //partita histPlyCurrent = 0; //la lista delle mosse alla mezza-mossa n-esima inizia a //firstMove[n] e termina a firstMove[n+1] (nell’array generData)

firstMove[0] = 0; }

in_check

applica attack sulla casella in cui si trova il Re del colore passato come parametro s. BOOLEANVAL in_check(int s) { int j; for (j=0; j < 125; ++j) if (pieces[j] == KING && colors[j] == s) return attack(j, s ^ 1); }

parseMove traduce una mossa dal formato testuale scelto nell’analisi, ovvero stringa da 6 o 7 caratteri (3 per la casella di partenza, 3 per la casella di arrivo, 1 per l’iniziale dell’eventuale pezzo in cui promuovere) al formato descritto dalle strutture dati interne del Motore. parseFEN traduce la posizione in formato che si è battezzato Forsyth–Edwards-Raumschach, descritto nell’analisi, nel formato interno al Motore e aggiorna la scacchiera alla posizione letta.

67

take_back annulla l’ultima mossa eseguita. Analizzando il codice riportato in appendice si può notare che vi sono parti di codice chiaramente ridondanti e ripetute; tutto è fatto in modo da ottimizzare la velocità di esecuzione, anche a scapito del riutilizzo del codice.

search.c

contiene le funzioni che implementano l’algoritmo di ricerca così come progettato. checkup richiamato ad intervalli regolari durante il calcolo, controlla che il tempo non sia scaduto. sort esegue il sorting necessario per l’history heuristics. void sort(int from) { int i; int bs; /* best score */ int bi; /* best i */ gener_t g; bs = -1; bi = from; // cerca fra le mosse pseudo-legali della ply corrente for (i = from; i < firstMove[plyCurrent + 1]; ++i) // in modo da ottenere che la mossa con lo score

// più alto vada all’indice from. In questo modo verrà // eseguita come prossima mossa

// (si ricordi che score non ha nulla a che vedere con // la valutazione della “bontà” della mossa, ma è un indice // della variabilità della posizione che questa mossa // potrebbe potenzialmente implicare)

if (generData[i].score > bs) { bs = generData[i].score; bi = i; } g = generData[from]; generData[from] = generData[bi]; generData[bi] = g; }

68

sort_pv Viene richiamata quando l’algoritmo di ricerca sta seguendo il ramo della variazione principale(vedi pag.35) risultato dalla ricerca effettuata nel precedente ciclo di iterative deepening (funzione search). Se trova nello stack generData la mossa della variazione principale corrispondente alla ply corrente, fa in modo che venga valutata per prima. Questo perché se era considerata la migliore nel ciclo di iterative deepening precedente probabilmente lo sarà di nuovo. In questo modo si leniscono le inefficienze introdotte dall’iterative deepening, che, si ricordi, si è stati costretti ad utilizzare per poter interrompere l’elaborazione e fornire un risultato al termine del tempo limite impostato (vedi pagg. 17 e 37). void sort_pv() { int i; followPV = FALSE; for(i = firstMove[plyCurrent];

i < firstMove[plyCurrent + 1]; ++i) if (generData[i].m.u == pv[0][plyCurrent].u) { followPV = TRUE;

//così si fa sì che la mossa sia analizzata per prima generData[i].score += 10000000; return; } } think, search e quiesce implementano l’algoritmo di ricerca vero e proprio (vedi fig. 7) think richiama iterativamente search, aumentando la profondità massima di ricerca ad ogni iterazione, fino alla massima impostata. Così viene implementato l’iterative deepening, che permette di ottenere una risposta dopo un certo tempo massimo (alla peggio valutando la posizione con profondità 1, cioè muovendo praticamente a caso). void think(BOOLEANVAL print) { int i, j, x; stop_search = FALSE; //si fa in modo da poter ritornare qui nel caso finisse il

//tempo prima di raggiungere la profondità massima setjmp(env); if (stop_search) { //se è finito il tempo si fa tornare la scacchiera //com’era prima. while (plyCurrent) take_back(); return;

69

}

//--- INIZIALIZZAZIONI ---

for (i = 1; i <= maxDepth; ++i) { followPV = TRUE;

//ad ogni iterazione viene chiama search x = search(-10000, 10000, i);

//--- STAMPE CONDIZIONALI (per debug) ---

} if (x > 9000 || x < -9000)

//in questo caso è stata trovata una mossa decisiva break; } }

search implementa l’algoritm alpha-beta pruning come descritto nella progettazione. Essa richiama quiesce, dedicata alla ricerca di mosse quiescenti (nel caso nostro si è deciso di far cadere in questa categoria le mosse di cattura), quando raggiunge la profondità massima. int search(int alpha, int beta, int depth) { int i, j, x; BOOLEANVAL areWeInCheck, foundAnyMove;

//Se si è raggiunta la massima profondità, si continua //a cercare ma solo fra le mosse quiescenti

if (depth == 0) return quiesce(alpha,beta); //Si aggiorna il contatore di numero di nodi visitati ++nodes; //Si controlla che il tempo a disposizione non sia finito if ((nodes & 1023) == 0) checkup(); //Se si è raggiunta la massima profondità assoluta //si valuta la posizione e si smette. if (plyCurrent >= MAXIMUM_PLY - 1) return evaluate(); if (histPlyCurrent >= HISTORY_STACK - 1) return evaluate(); //Nel caso si sia sotto scacco è meglio continuare //a cercare anche oltre la profondità massima impostata areWeInCheck = in_check(sideToMove); if (areWeInCheck) ++depth;

//Si generano le mosse possibili per la posizione generate();

70

//Vedi sortpv (pag. 66) if (followPV) sort_pv(); foundAnyMove = FALSE; //Per ogni mossa... for (i=firstMove[plyCurrent];i<firstMove[plyCurrent+1];++i)

{ //Vedi sort (pag. 66) sort(i); //Se la mossa non è permessa, passare alla prossima if (!doMove(generData[i].m.b)) continue; foundAnyMove = TRUE;

//L’esplorazione ricorsiva dell’albero prosegue x = -search(-beta, -alpha, depth - 1); //Quando si “riemerge” dalla ricorsione, si ritorna //alla posizione precedente take_back(); //Se c’è un cutoff... if (x > alpha) {

//...history heuristics: la casella corrispondente a //questa mossa viene incrementata, così si cercherà //prima nei rami contenenti questa mossa in futuro //(vedi analisi)

history[(int)generData[i].m.b.from] [(int)generData[i].m.b.to] += depth;

if (x >= beta)

{ //in questo caso non vi saranno risultati //migliori (pruning). return beta; } alpha = x; //si aggiorna la variazione principale pv[plyCurrent][plyCurrent] = generData[i].m; for(j=plyCurrent+1;j<pvLength[plyCurrent+1];++j) pv[plyCurrent][j] = pv[plyCurrent + 1][j]; pvLength[plyCurrent] = pvLength[plyCurrent + 1]; } } //se non si sono trovate mosse legali, o si ha perso o si è //in stallo,e quindi parità (nella posizione studiata). if (!foundAnyMove) { if (areWeInCheck) return -10000 + plyCurrent; else return 0; }

71

//regola delle 50 mosse (100 plies) if (fiftMoves >= 100) return 0; return alpha; }

quiesce è quasi identica a search. La differenza sta nel fatto che essa considera soltanto le mosse di cattura, e cerca fino a che non ve ne sono più. In questo modo ci si porterà in situazioni il più statiche possibile, dove la funzione di valutazione darà il massimo risultato. int quiesce(int alpha,int beta) { /* --- INIZIALIZZAZIONE E STESSI CONTROLLI DI SEARCH --- */

//Qui si valuta subito la posizione (più probabilità di //pruning trattandosi di mosse più drastiche).

x = evaluate(); if (x >= beta) return beta; if (x > alpha) alpha = x; //Si generano le mosse di cattura generateCaptures(); if (followPV) sort_pv(); for (i=firstMove[plyCurrent];i<firstMove[plyCurrent+1];++i)

{ /*--- L’IMPLEMENTAZIONE DI ALPHA-BETA PRUNING

E’ ANALOGA A QUELLA DELLA FUNZIONE search ---*/ } return alpha; }

eval.c

eval.c contiene le funzioni e le strutture dati che servono per valutare il punteggio di una posizione. /* contiene i valori dei pezzi, come definiti in architettura (vedi) */ int piece_value[7] = { 100, 220, 780, 510, 380, 1280, 0 };

gli array che terminano in –pcsq rappresentano mappe di valori che vanno sommati ai valori dei mezzi a seconda della loro posizione sulla scacchiera. Questi valori al momento sono fissati arbitrariamente, in base alla mobilità conseguita dalla posizione; in futuro potrebbe essere interessante tentare di trovare valori migliori tramite un approccio di tipo machine-learning.

72

/* flip serve a calcolare il valore pezzo/casella per il nero. Se il valore di cavallo bianco è knight_pcsq[sq], l’equivalente per il nero è knight_pcsq[flip[sq]] */ int flip[125] = { 120, 121, 122, 123, 124, 115, 116, 117, 118, 119, 110, 111, 112, 113, 114, 105, 106, 107, 108, 109, 100, 101, 102, 103, 104, 95, 96, 97, 98, 99, 90, 91, 92, 93, 94, 85, 86, 87, 88, 89, 80, 81, 82, 83, 84, 75, 76, 77, 78, 79, 70, 71, 72, 73, 74, 65, 66, 67, 68, 69, 60, 61, 62, 63, 64, 55, 56, 57, 58, 59, 50, 51, 52, 53, 54, 45, 46, 47, 48, 49, 40, 41, 42, 43, 44, 35, 36, 37, 38, 39, 30, 31, 32, 33, 34, 25, 26, 27, 28, 29, 20, 21, 22, 23, 24, 15, 16, 17, 18, 19, 10, 11, 12, 13, 14, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, };

evaluate

calcola il valore della posizione corrente. int evaluate() {

/* --- INIZIALIZZAZIONI --- */ // si passa per tutta la scacchiera for (i = 0; i < 125; ++i) { if (colors[i] == EMPTY) continue; if (pieces[i] == PAWN) { pawn_mat[colors[i]] += piece_value[PAWN]; } else piece_mat[colors[i]] += piece_value[pieces[i]]; }

/* alla fine del ciclo, pawn_mat conterrà il valore base di tutti i pedoni neri e di tutti i pedoni bianchi*/

73

/* piece_mat conterrà il valore base degli altri pezzi. Si mantengono separati i punteggi per lasciare spazio ad eventuali sviluppi futuri in grado di tener conto della struttura dei pedoni, come già si fa negli scacchi

classici */ score[WHITE] = piece_mat[WHITE] + pawn_mat[WHITE]; score[BLACK] = piece_mat[BLACK] + pawn_mat[BLACK]; /* nel secondo ciclo vengono applicate le mappe di punteggio

-pcsq */ for (i = 0; i < 125; ++i) { if (colors[i] == EMPTY) continue; if (colors[i] == WHITE) { switch (pieces[i]) { case PAWN: score[WHITE] += eval_WHITE_pawn(i); break; case KNIGHT: score[WHITE] += knight_pcsq[i]; break; case BISHOP: score[WHITE] += bishop_pcsq[i]; break; case ROOK: break; case KING: if (piece_mat[BLACK] <= 1200)

score[WHITE] += king_endgame_pcsq[i]; //evaluate particolare per re in endgame. Il valore 1200 è del tutto empirico, per sviluppi futuri sarebbe opportuno determinare un modo migliore per definire l’endgame.

else score[WHITE] += eval_WHITE_king(i); //evaluate normale per il re bianco

break; } } else { /* --- CODICE SIMILE PER IL GIOCATORE NERO--- */ } } } /* si prepara il valore da passare all’alpha-beta pruning */ if (sideToMove == WHITE) return score[WHITE] - score[BLACK]; //else

74

return score[BLACK] - score[WHITE]; } int eval_WHITE_pawn(int sq) { int r; r = 0; r += pawn_pcsq[sq]; return r; } int eval_WHITE_king(int sq) { int r; r = king_pcsq[sq]; r *= piece_mat[BLACK]; //altro valore empirico. Futuri sviluppi possono migliorarne

//la scelta. r /= 3100; return r; }

RaumschachChessEngine.cpp e altri

Questo è il file dove sono dichiarate le funzioni che permettono all’interfaccia di interrogare il Motore e interagire con esso. E’ un file C++ perché nell’implementazione Windows del gioco è stato necessario un wrapping del motore in una DLL C++.

A questi si aggiungono main.c, utilizzato per le operazioni di debugging. dllmain.cpp e stdafx.cpp legati al wrapping del Motore in una DLL.

75

Realizzazione dei modelli 3D

Come da progettazione sono stati realizzati con Blender otto modelli 3D, uno per ogni pezzo degli scacchi più un parallelepipedo che formerà la casella fondamentale per la realizzazione della scacchiera. Per esigenze di compatibilità tra Blender e XNA sono inclusi nel progetto in formato FBX, formato proprietario di Autodesk.

Fig. 14 - Modello della regina in costruzione, in Blender

76

Fig. 15 - Il modello della regina completo in Blender

77

Realizzazione dell’Interfaccia

Premessa: XNA Application Model

La classe base su cui si basa l’application model fornito da XNA è Game. Essa fornisce un framework per far girare un “gioco”, o simulazione, basandosi su un intervallo di tempo fisso o variabile. Perciò, per creare un gioco si deriva dalla classe Game ereditando obbligatoriamente i metodi Update, Draw e Initialize. Update è demandato all’aggiornamento della logica del gioco, Draw al disegno di ciascun frame e Initialize all’inizializzazione del gioco.

Game Loop Timing

Un Game può essere o a intervalli di tempo fissi o variabili; per default, fissi. A

seconda del tipo di intervallo varierà quanto spesso è richiamato Update.

Game Loop ad intervallo fisso

Un Game ad intervallo fisso chiama il suo Update ogni intervallo di tempo dalla

durata specificat in TargetElapsedTime. Finito di girare Update, Game chiama

Draw; una volta esaurito Draw, se ancora non è ora di chiamare di nuovo Update,

aspetta.

Se Update eccede il tempo concessogli, Game assegna il valore true a

IsRunningSlowly e richima di nuovo Update senza Draw. Ovvero, “perde

frames”, ma in questo modo la simulazione rimane aggiornata nello stato interno,

anche se risulta bloccata dal punto di vista dell’utente.

Game Loop ad intervallo variabile

In questo caso Update e Draw vengono chiamati a ciclo continuo, migliorando le

prestazioni ma lasciando al programmatore tutti gli oneri della temporizzazione.

Nel caso preso in esame l’intervallo fisso è stato scelto come il più indicato, non

essendovi nella nostra simulazione operazioni di grafica molto complesse.

Game Component

GameComponent e DrawableGameComponent sono rispettivamente le due classi dalle quali derivare per costruire moduli per il proprio Game. Aggiungendoli ad esso con Game.add(...) i loro metodi Draw, Update ed Initialize saranno chiamati automaticamente.

78

Questa feature è stata utilizzata solo in parte, in quanto limitativa per la costruzione dei moduli.

Content Pipeline

XNA permette di modificare parti della pipeline che esso utilizza per il

caricamento degli asset di gioco.

Fig. 16 - Schema della Content Pipeline di XNA

E’ composta da quattro componenti principali:

1. Importer Tra gli importer standard per modelli 3D vi è anche quello per i file Autodesk .fbx, l’unico formato compatibile tra Blender ed XNA, appunto. Il tipo di input e di output varia a seconda dell’importer che si usa.

2. Content Processor Anche qui, vi sono processori diversi per ciascun tipo di oggetto; durante la realizzazione di questo progetto si è deciso utilizzare un processore custom di terze parti, per poter implementare la selezione dei modelli tramite click del mouse (vedi)

3. Content Compiler Trasforma gli oggetti in formato binario. Li compila, appunto

4. Content Loader Carica i compilati nella memoria del gioco in modo che possano essere utilizzati.

79

Librerie di terze parti

TrianglePickingProcessor

E’ un ContentProcessor custom, inserisce informazioni sul posizionamento dei vertici, che può essere utilizzato a runtime per implementare la selezione di un particolare triangolo su questo modello; è l’unico modo di ottenere la selezionabilità del modello tramite mouse. Questa classe eredita dal processore standard ModelProcessor; di esso estende il metodo Process, utilizzandolo per inserire dati custom nella proprietà Tag del modello.

XWinForms

E’ una library open source, ancora in beta, che fornisce un’interfaccia grafica simile a WinForms, anche se molto più rudimentale, utilizzabile all’interno di XNA. Su di essa si sono anche operate delle piccole modifiche e delle correzioni di bug.

ScreenManager

Per la realizzazione dell’interfaccia, è stato esteso il framework XNA con un componente denominato ScreenManager. L’obiettivo è impostare la programmabilità dell’Interfaccia a schermate. Lo ScreenManager gestisce lo stato del gioco, la visualizzazione dei menu, e la visualizzazione in generale. E’ un framework a sua volta perché permette di strutturare la simulazione che si vuol costruire per XNA in schermate, cosa che XNA da solo non permette. Ciò risulta molto comodo sopratutto per la costruzione dei menù.

GameScreen

Da questa classe si può derivare per costruire una schermata che viene visualizzata sullo schermo. Supporta effetti di transizione (transition-on e transition-off) e una modalità pop-up.

MenuScreen

Deriva da GameScreen. Visualizza una serie di MenuEntry tramite le quali è possibile navigare all’interno dei menu e fornisce la logica per gestirle. Derivando da essa si costruisce una schermata di menu. In figura 17 è rappresentata dai rettangoli azzurri.

80

Fig. 17 - Screen Flow schema dell'Interfaccia

LoadingScreen

Deriva da MenuScreen. Il suo scopo è coordinare le transizioni tra il sistema di schermate di menù ed il gioco vero e proprio, perché per transizioni molto grandi ci potrebbe essere bisogno di tempo per caricare i dati. Perciò viene visualizzato un LoadingScreen nel frattempo; ciò avviene nel seguente modo:

• Si fa in modo che tutte le schermate esistenti eseguano un transition-off.

• Si attiva uno screen di loading, che nello stesso istante eseguirà un transition-on

81

• Quando gli schermi che devono sparire completano il transition-off, il loading screen attiva lo schermo successivo (quello che potrebbe necessitare di un certo quantitativo di tempo per essere attivato)

GameplayScreen

E’ la schermata di gioco vera e propria ed è il risultato del lavoro svolto e descritto in questo documento. E’ trattata nella sua interezza nella sezione Gameplay.

Gameplay

Il “gameplay” è reso tramite la classe GameplayScreen, che rappresenta la schermata di gioco, tramite le videocamere virtuali che rendono possibile l’illusione del movimento nello spazio tridimensionale simulato, e tramite la classe PositionableModel e le derivate da essa.

Videocamere Virtuali

Le videocamere virtuali sono state organizzate in modo da essere accessibili da qualunque punto del codice. Sono organizzate nella seguente gerarchia:

• BaseCamera: classe astratta, definisce le matrici view e projection, utilizzate per la proiezione dello spazio 3D sul campo visivo, e i metodi base.

o Cubical Camera: classe che definisce la camera a movimento legato alla scacchiera (vedi progettazione)

o Free Movement Camera: classe che definisce la camera a movimento libero (vedi progettazione)

Di seguito il codice di queste tre classi:

82

BaseCamera

using System; using System.Collections.Generic; using System.Linq; using System.Text; using Microsoft.Xna.Framework; namespace Raumschach_Chess { public abstract class BaseCamera { protected static BaseCamera activeCamera = null; // View and projection protected Matrix projection = Matrix.Identity; protected Matrix view = Matrix.Identity; // protected const float angle = 0.5f; protected float turnSpeed; protected Game Game; public BaseCamera(Game game) { if (ActiveCamera == null) ActiveCamera = this; this.Game = game; } public BaseCamera(float turnspeed, Game game):this(game) { this.turnSpeed = turnspeed; } public BaseCamera(float turnspeed, Game game, Vector3

initialPosition) : this(turnspeed,game) { view *= Matrix.CreateTranslation(initialPosition); } public BaseCamera(float turnspeed, Game game, Vector3

initialPosition, Vector3 initialTarget) : this(turnspeed,game) { view *= Matrix.CreateLookAt(initialPosition,

initialTarget, Vector3.UnitY); } public static BaseCamera ActiveCamera { get { return activeCamera; } set { activeCamera = value; } } public Matrix Projection { get { return projection; } } public Matrix View

83

{ get { return view; } } public virtual void Update(GameTime gameTime){} public virtual void LoadContent() { float ratio =

(float)this.Game.GraphicsDevice.Viewport.Width / (float)this.Game.GraphicsDevice.Viewport.Height;

projection = Matrix.CreatePerspectiveFieldOfView(MathHelper.PiOver4, ratio, 10, 10000);

} } }

84

CubicalCamera

using System; using System.Collections.Generic; using System.Linq; using System.Text; using Microsoft.Xna.Framework.Input; using Microsoft.Xna.Framework; namespace Raumschach_Chess { public class CubicalCamera : BaseCamera { public int CubeEdges { get{ return cubeEdges;} } private int floor = 0; public int Floor { get { return floor; } set { int reference = CubeEdges; if (value <= -1) value = reference + value %

reference; floor = value % reference; } } private int horizontalPosition = 0; public int HorizontalPosition { get { return horizontalPosition; } set { int reference = CubeEdges * 4; if (value <= -1) value = reference + value %

reference; horizontalPosition = value % reference; } } public float step; private int cubeEdges; private Vector3 defaultPosition; private Vector3 finalTargetPosition; private Vector3 initialTargetPosition; private bool isMoving = false; private TimeSpan initialMovementTime; private float secondsToDoMovement = 1; public Vector3 finalPosition; private Vector3 initialPosition; public CubicalCamera(float turnspeed, Game game, int

cubeEdges) :base(turnspeed, game) { this.cubeEdges = cubeEdges;

85

} public override void Update(GameTime gameTime) { float delta = (float)gameTime.ElapsedGameTime.TotalSeconds; KeyboardState keyboard = Keyboard.GetState(); if (keyboard.IsKeyDown(Keys.Escape)) Game.Exit(); float deltaPitch = 0; float deltaYaw = 0; //se non ci si sta muovendo si inizia una fase di movimento if (!this.isMoving) { if (keyboard.IsKeyDown(Keys.W)) deltaPitch -= angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.S)) deltaPitch += angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.A)) deltaYaw -= angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.D)) deltaYaw += angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.Up)) { Floor++; StartMovement();

initialMovementTime = gameTime.TotalGameTime; } if (keyboard.IsKeyDown(Keys.Down)) { Floor--; StartMovement();

initialMovementTime = gameTime.TotalGameTime; } if (keyboard.IsKeyDown(Keys.Left)) {

HorizontalPosition--; StartMovement(); initialMovementTime = gameTime.TotalGameTime;

} if (keyboard.IsKeyDown(Keys.Right)) { HorizontalPosition++; StartMovement(); initialMovementTime = gameTime.TotalGameTime; } } else {//altrimenti si continua il movimento precedente, passo passo attorno al cubo

float amount = (float)(gameTime.TotalGameTime.TotalSeconds -

initialMovementTime.TotalSeconds) / secondsToDoMovement;

if (amount >= 1) { view = Matrix.CreateLookAt(finalPosition,

finalTargetPosition, Vector3.Up); this.isMoving = false; } else view = Matrix.CreateLookAt(

86

initialPosition + (finalPosition – initialPosition) * amount,

initialTargetPosition + (finalTargetPosition – initialTargetPosition) * amount,

Vector3.Up); } //aggiungo il contributo della rotazione su sé stessa della camera

Matrix Rotx = Matrix.CreateRotationX(MathHelper.ToRadians(deltaPitch));

Matrix Roty = Matrix.CreateRotationY(MathHelper.ToRadians(deltaYaw));

view *= Rotx * Roty; } public override void LoadContent() { step = ((Raumschach)Game).OptionsCurrent.SquareSize;

defaultPosition = ((Raumschach)Game).OptionsCurrent.LeftBottom +new Vector3(-step, step / 2, -step);

finalPosition = defaultPosition; view = Matrix.CreateLookAt(defaultPosition, new

Vector3(- 2*defaultPosition.X,0,-2*defaultPosition.Z) , Vector3.Up);

HorizontalPosition--; StartMovement(); initialMovementTime = TimeSpan.Zero;

base.LoadContent(); } private void StartMovement() { float x, y, z; float xTarget, zTarget; y = floor; if (HorizontalPosition < cubeEdges) { z = zTarget = horizontalPosition + 1f; x = -2; xTarget = x + 100; } else if ((HorizontalPosition >= cubeEdges) &&

(HorizontalPosition < 2 * cubeEdges)) { z = cubeEdges + 3.5f; x = xTarget = horizontalPosition - 4f; zTarget = z - 100; } else if ((HorizontalPosition >= 2 * cubeEdges) &&

(HorizontalPosition < 3 * cubeEdges)) { z = zTarget = 3 * cubeEdges - horizontalPosition ; x = cubeEdges + 3.5f; xTarget = x - 100; } else { z = -2;

87

x = xTarget = 4 * cubeEdges - horizontalPosition ; zTarget = z + 100; } initialPosition = finalPosition; finalPosition = new Vector3(step * x, step * y, step *

z) + defaultPosition; initialTargetPosition = finalTargetPosition; finalTargetPosition = new Vector3(step * xTarget, step

* y, step * zTarget) + defaultPosition; isMoving = true; } } }

88

FreeMovementCamera

using System; using System.Collections.Generic; using System.Text; using Microsoft.Xna.Framework; using Microsoft.Xna.Framework.Input; namespace Raumschach_Chess { public class FreeMovementCamera : BaseCamera { protected float speed; public FreeMovementCamera(Game game):base(game) { }

public FreeMovementCamera(float speed, float turnspeed, Game game):base(turnspeed, game)

{ this.speed = speed; }

public FreeMovementCamera(float speed, float turnspeed, Game game, Vector3 initialPosition)

: base(turnspeed,game,initialPosition) { this.speed = speed; }

public FreeMovementCamera(float speed, float turnspeed, Game game, Vector3 initialPosition, Vector3 initialTarget)

: base(turnspeed, game, initialPosition,initialTarget) { this.speed = speed; } public override void Update(GameTime gameTime) { float delta =

(float)gameTime.ElapsedGameTime.TotalSeconds; KeyboardState keyboard = Keyboard.GetState(); float deltaPitch = 0; float deltaYaw = 0; float deltaRoll = 0; float distance = 0; if (keyboard.IsKeyDown(Keys.Up)) deltaPitch -= angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.Down)) deltaPitch += angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.Left)) deltaYaw -= angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.Right)) deltaYaw += angle * turnSpeed * delta;

89

if (keyboard.IsKeyDown(Keys.Q)) deltaRoll -= angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.W)) deltaRoll += angle * turnSpeed * delta; if (keyboard.IsKeyDown(Keys.A)) distance += speed * delta; if (keyboard.IsKeyDown(Keys.Z)) distance -= speed * delta; if (keyboard.IsKeyDown(Keys.Escape)) Game.Exit();

Matrix Rotx = Matrix.CreateRotationX(MathHelper.ToRadians(deltaPitch));

Matrix Roty = Matrix.CreateRotationY(MathHelper.ToRadians(deltaYaw));

Matrix Rotz = Matrix.CreateRotationZ(MathHelper.ToRadians(deltaRoll));

view *= Rotx * Roty * Rotz; Matrix matrisce = Matrix.CreateTranslation(new Vector3(2, 3, 4) * 1000); view *= Matrix.CreateTranslation(Vector3.UnitZ * distance); } } }

90

Gestione dei modelli

PositionableModel

Seguendo l’Application Model di XNA è stato fatto sì che ogni modello caricato, sia esso pezzo degli scacchi o parte della scacchiera, contenta in sé tutta la logica che lo riguarda. E’ stata scritta perciò una classe base, PositionableModel, nella quale si è centralizzata tutta la logica base per il posizionamento del modello nello spazio tridimensionale e per la configurazione comune degli Effects predefiniti di XNA. public class PositionableModel { /* --- INIZIALIZZAZIONE E COSTRUTTORI --- */ public virtual void Draw(GameTime gameTime) { Matrix[] transforms = new Matrix[model.Bones.Count]; model.CopyAbsoluteBoneTransformsTo(transforms); foreach (ModelMesh mesh in Model.Meshes) { Matrix world =

transforms[mesh.ParentBone.Index] * WorldTransform; foreach (BasicEffect eff in mesh.Effects) { eff.World = world; //I dati vengono raccolti dalla videocamera virtuale //al momento attiva eff.Projection = BaseCamera.ActiveCamera.Projection; eff.View = BaseCamera.ActiveCamera.View; SetBasicEffectSettings(eff); } mesh.Draw(); } } /* --- Configurazione degli effects standard --- */ }

Square

Questa classe rappresenta i mattoncini fondamentali componenti la scacchiera. Anch’essa deriva da PositionableModel.

91

Piece

Questa classe deriva da PositionableModel. Tutta la parte dedicata al disegno non cambia, infatti il metodo Draw rimane lo stesso. L’animazione del pezzo è ottenuta tramite il metodo Update. La posizione finale del pezzo è determinata dalla matrice FinalWorldTransform. Quando l’animazione inizia, viene settato il punto di destinazione da raggiungere, e, fissato come tempo per l’animazione 2 sec, si somma alla matrice di posizione corrente una frazione della matrice differenza fra posizione finale e posizione iniziale. Di seguito è riportato il codice: public override void Update(GameTime gameTime) { if (!animating) { animDiff = FinalWorldTransform - wTrans; if (animDiff != zeroMatrix) { animating = true; animStartTime = gameTime.TotalGameTime; wTransAtAnimStartTime = wTrans; } } else { double msecsElaps = gameTime.TotalGameTime.TotalMilliseconds –

animStartTime.TotalMilliseconds; if (msecsElaps >= 2000) { animating = false; wTrans = FinalWorldTransform; } else { wTrans = wTransAtAnimStartTime + ((int)msecsElaps) * (animDiff / 2000); } } base.Update(gameTime); }

92

Logiche di gioco

ChessboardLogics

Da essa l’interfaccia richiama le funzioni del Motore, implementato nel file RaumschachChessEngine.dll, tramite Platform Invoke. Di seguito un esempio di metodo wrapper: //nome della dll da importare [System.Runtime.InteropServices.DllImport("RaumschachChessEngine.dll")] //l’attributo MarshalAs indica, in questo caso, come il CLR deve //interpretare il dato che gli giunge dalla dll [return: System.Runtime.InteropServices.MarshalAs(

System.Runtime.InteropServices.UnmanagedType.LPStr)]

public static extern String MakeMoveAndGetNext( //in quest’altro caso invece il MarshalAs indica come inviare un //parametro alla dll [System.Runtime.InteropServices.MarshalAs(

System.Runtime.InteropServices.UnmanagedType.LPStr)] String move, int sideToMove );

93

Conclusioni

Raggiungimento degli obiettivi

In ultima analisi, si può quindi affermare che gli obiettivi principali di questa tesi sono stati raggiunti. L’Interfaccia possiede le caratteristiche di usabilità richieste, risulta adattabile a diversi stili di visualizzazione da parte dell’utente. Il Motore risponde in modo coerente alle mosse dell’avversario. La regolabilità nel senso del tempo disponibile per una mossa e nella profondità massima di analisi è stata ottenuta e resa facilmente applicabile.

Sviluppi futuri

E’ chiaro che gli sviluppi possibili sono innumerevoli. Dal lato grafico:

• Personalizzazione dei pezzi: costruzione di modelli 3D diversi,

magari “a tema”

• Texturizzazione di pezzi e scacchiera

• Applicazione di shader più complessi: è stato utilizzato quello base offerto da XNA ma nulla vieta di elaborarne di più complessi.

Dal lato tecnico:

• Potenziamento dell’intelligenza artificiale, in particolar modo della funzione di valutazione della mossa, magari tramite Genetic Programming o altri modelli di apprendimento computerizzato

• Maggior utilizzo della library xWinForms (ancora in fase di beta testing) per ottenere un’interfaccia ancora più user-friendly.

94

Bibliografia

Letteratura

• “How Computers Play Chess”

di David N. L. Levy e Monroe Newborn • “XNA 2.0 Game Programming Recipes: A Problem-Solution

Approach” di Riemer Grootjans

Web

Wikipedia

http://www.wikipedia.org

Chess programming

• Chess programming – getting started http://www.gamedev.net/reference/programming/features/chess1/

• Computer chess programming theory http://www.frayn.net/beowulf/theory.html

• Computer chess – Top 5000 http://www.top-5000.nl/chess.htm

• Chess programming wiki http://chessprogramming.wikispaces.com/

• Computer chess information and resources http://chessprogramming.wikispaces.com/

XNA programming

• XNA Creators Club Online http://creators.xna.com/en-US/

• XNA Developer Center http://msdn.microsoft.com/en-us/aa937791.aspx

• XNA Community Forums http://forums.xna.com/forums/

95

Third Part Libraries

• XNA Framework GameEngine Development http://roecode.wordpress.com/2008/01/28/xna-framework-gameengine-development-part-7-screenmanagergamecomponent/

• GameProjects.com http://www.gameprojects.com/project/?id=e68f3464c4

3D modeling

• Blender 3D – Noob To Pro http://en.wikibooks.org/wiki/Blender_3D:_Noob_to_Pro

96

Ringraziamenti Porgo un sentito ringraziamento ai miei familiari, ai miei amici (musicisti, ingegneri e non), ed a tutti coloro che mi hanno supportato e sopportato durante questo cammino. Un grazie particolare all’intero corpo docente che si prodiga in questo delicato compito che è l’insegnamento di una materia delicata ed in continua evoluzione come l’ingegneria informatica. In particolare ai docenti Bartoli e Fermeglia, entrambi a mio modesto parere fra i migliori del corpo docente del mio corso. E grazie anche a te che stai leggendo.

97

Appendice

Fast, Minimum Storage Ray/Triangle Intersection

Tesi Specialistica - Bruno Tagliapietra

Business

Transcript of Tesi Specialistica - Bruno Tagliapietra