intelligenza artificiale - Facoltà di · PDF fileGli studiosi di intelligenza...

Scuola Politecnica e delle Scienze di Base Corso di Laurea in Ingegneria Informatica

Elaborato finale in intelligenza artificiale

Teoria dei Giochi: Strategie di ricerca con avversari Anno Accademico 2015-2016 Relatore Prof.ssa Flora Amato Candidato: Salvatore Emanuel Fusco Matr. N46001612

Alla mia adorata mamma

Indice

Indice…………………………………………………………………... III Introduzione……………………………………………………………... 4 Capitolo 1: Giochi nell’IA..…………………….……………………...... 5 Capitolo 2: Algoritmi di ricerca con avversari………………………….. 9

2.1: Algoritmo minimax…...…….…….…………...…………...... 10

2.2: Potatura alfa-beta…….….………….………….……………. 13

2.3: Funzioni di valutazione…....……………...….....…………… 16

Capitolo 3: Il linguaggio prolog………………..……………….……... 18

Capitolo 4: Implementazione del gioco dell’othello in prolog………... 19

4.1: Gioco in esecuzione….……………………………………… 20

4.2: Implementazione in prolog…….…….…………….………... 21

Bibliografia……………………………………………………………. .45

4

Introduzione

Gli studiosi di intelligenza artificiale sono molto interessati al mondo dei giochi

poiché, in molti di essi, soprattutto quelli in cui non sono presenti elementi di

aleatorietà, l’esito è strettamente legato all’intelletto e alle capacità di ragionamento

del giocatore di turno. Vengono affrontati problemi complessi molto difficili da

risolvere, ma allo stesso tempo facili da descrivere, in quanto lo stato di un gioco si

può rappresentare facilmente e i giocatori solitamente compiono un insieme di azioni

non molto ampio le cui conseguenze sono definite da regole precise. Quindi i giochi

oggetto di studio sono quelli in cui il numero di scelte possibili da parte dei giocatori

è finito e il gioco dura un numero finito di mosse.

Il gioco degli scacchi, così come dama, backgammon e othello sono giochi in cui gli

obiettivi dei giocatori sono in conflitto. Se un giocatore vince, l’altro deve

necessariamente perdere, al massimo la partita può concludersi in pareggio. La

ricerca con avversari tratta ambienti competitivi in cui gli obiettivi degli agenti sono

in contrapposizione.

Lo scopo di questo elaborato è quello di illustrare le principali caratteristiche di

questa tipologia di giochi, sarà fatta una panoramica degli algoritmi di ricerca

attualmente in uso per sviluppare giochi artificiali, sarà, inoltre, presentata una

implementazione del gioco dell’othello mediante il linguaggio logico prolog.

5

Capitolo 1: Giochi nell’ IA

Nell’intelligenza artificiale i giochi più comuni appartengono ad una categoria

denominata a somma zero con informazione perfetta.

I giochi a somma zero sono giochi in cui i valori di utilità, alla fine della partita, sono

sempre uguali ma di segno opposto: se un giocatore guadagna, l’altro deve

necessariamente perdere. Sia g la somma totale dei guadagni dei giocatori e p la

somma totale delle perdite, in un gioco a somma zero, la differenza tra g e p vale 0.

Nei giochi a somma negativa o a somma positiva, la somma totale dei guadagni è

rispettivamente inferiore e superiore rispetto alle perdite. Nel primo caso si dice che

il gioco distrugge la ricchezza, nel secondo caso, la crea.

In economia un esempio di gioco non a somma zero si ha quando un paese con un

eccesso di un prodotto (es. televisori), instaura rapporti commerciali con un altro

paese che ha in eccesso un altro tipo di prodotto (es. lavatrici), entrambi i paesi

beneficeranno nella transazione.

I giochi, quindi, oltre ad essere competitivi(solitamente a somma zero) possono

anche essere cooperativi (solitamente non a somma zero).

In quest’ultimo caso la sottoscrizione di accordi vincolanti tra le parti assicura che

ciascun giocatore possa trarne vantaggio.

L’informazione perfetta garantisce che la conoscenza sia condivisa. Ogni giocatore è

a conoscenza dell’insieme delle strategie, quindi delle possibili azioni di ogni altro,

inoltre conosce il valore di utilità di ogni azione.

Nei giochi a informazione imperfetta gli stati del gioco sono solo parzialmente

6

esplicitati, al momento di effettuare una mossa, ogni giocatore potrebbe non

conoscere la propria posizione nel gioco e nemmeno quella degli altri giocatori.

Si riporta di seguito un breve cenno, tralasciando le regole, dei giochi a due giocatori

che maggiormente sono oggetto di studio nell’ambito delle strategie di ricerca con

avversari, con una breve menzione allo stato dell’arte.

Scacchi Gli scacchi sono un gioco da tavolo che vede contrapposti due avversari il bianco e il nero. Ogni

giocatore ha a disposizione 8 pedoni, 2 cavalli, 2 alfieri, 2 torri, una donna e un re. Vince la partita

il giocatore che da “scacco matto” al re avversario, ovvero mette il re avversario in condizione di

non potersi sottrarre alla minaccia diretta dei propri pezzi. Nel 1997 un super-computer Deep-blue

riuscì a battere il campione del mondo Garry Kasparov.

Figura 1.1 Scacchiera iniziale

Dama La Dama è un gioco da tavolo che vede contrapposti due avversari, bianco e nero. Ogni giocatore

ha a disposizione 12 pedine che può muovere solo diagonalmente sulle caselle scure non occupate

da altri pezzi. Inoltre ciascun giocatore ha la possibilità di mangiare i pezzi avversari rimuovendoli

dalla damiera. Il giocatore a cui vengono mangiati tutti i pezzi o che al suo turno di mossa è

impossibilitato a muoversi, perde la partita. Chinook è un super software per la dama progettato

dagli scienziati dell’università di Alberta(canada) capitanato da Jonathan Schaeffer, conosce tutte le

combinazioni possibili(500 miliardi di miliardi), non può mai perdere una partita al massimo può

pareggiarla.

Figura 1.2 Damiera iniziale

7

Backgammon Il Backgammon è un gioco da tavolo per due giocatori. Ogni giocatore possiede 15 pedine che

muove lungo 24 triangoli lanciando due dadi. Lo scopo del gioco è riuscire per primi a rimuovere

tutte le proprie pedine dal tavoliere, cercando allo stesso tempo, di bloccare l'avversario e di evitare

le sue azioni di disturbo. Ciascun giocatore comincia la partita con 15 pedine 2 dadi, un bussolotto e

un dado speciale. I giocatori lanciano i dadi e muovono le pedine tra le caselle(solo in senso orario)

in base al risultato ottenuto. Lo scopo del gioco è quello di portare tutte le pedine all’interno della

tavola interna e infine portarle fuori dal tavoliere.

TD Gammon è un programma sviluppato nel 1992 da Gerald Tesauro ricercatore dell’ IBM, fu il

primo programma per computer che giocasse a un livello almeno pari a quello dell’uomo.

L’addestramento della rete neurale di questo programma è avvenuto mediante algoritmi particolari.

Gerarld Tesauro in Temporal difference leaning and td-gammon definì TD-gammon come una rete

neurale che allena se stessa e apprende autonomamente.[1]

Figura 1.3 Tavoliere backgammon

Go Il gioco si svolge su una tavola di legno(goban) con 2 recipienti contenenti pietre(180 bianche e 181

nere). Sul goban(Fig 1.4) è tracciata una matrice di 19x19 linee, per un totale di 361 intersezioni.

I 2 giocatori, a turno, collocano le pietre sulle intersezioni vuote, una o più pietre possono essere

catturate dall’avversario quando il suo gruppo perde la sua ultima libertà. La libertà è una

intersezione vuota adiacente alla pietra e ad essa connessa. Quindi una pietra all’angolo ha 2 libertà,

sul lato 3 e al centro 4. Una pietra può essere piazzata in una qualunque intersezione purché, al

termine della mossa, il suo gruppo riesca a mantenere almeno una libertà. Ogni intersezione vuota

sotto il controllo di un giocatore e ogni pietra catturata vale un punto, vince il giocatore che alla fine

della partita ne totalizza di più[2] Per quanto riguarda lo stato dell’arte, il go è uno dei giochi che ha

messo più in difficoltà gli studiosi di ia, l’essere umano è riuscito spesso ad avere la meglio contro

un computer. Handtalk (Chen-Zhixing) è un programma che negli anni 1996-1997 e 2001 vinse la

coppa del modo di go per pc.

Figura 1.4 Goban con pietre

8

Tra i giochi menzionati, nel backgammon, a differenza degli altri tre, è presente un

elemento di casualità. All’inizio di ogni turno, per determinare le possibili mosse,

ciascun giocatore lancia 2 dadi. Nonostante il giocatore di turno conosca le proprie

mosse legali non può sapere il risultato dei dadi dell’avversario e quindi non può

prevedere le sue mosse potenziali.

In questi giochi oltre all’abilità bisogna considerare un elemento impredicibile: la

fortuna. Questa categoria di giochi è denominata di tipo stocastica.

Altri giochi stocastici sono i giochi di carte come il bridge, il poker e la scopa.

Oltre ad essere stocastici hanno anche la caratteristica di essere parzialmente

osservabili, quindi sono a informazione imperfetta: le carte di ogni giocatore sono

nascoste a tutti gli altri.

Un’altra distinzione è tra giochi simultanei e giochi sequenziali: in un gioco

simultaneo i giocatori scelgono simultaneamente, mentre in uno sequenziale le azioni

di ciascun giocatore seguono una determinata successione.

9

Capitolo 2: Algoritmi di ricerca con avversari

Un gioco può essere definito dal punto di vista formale come un tipo di problema di

ricerca composto da:

Uno stato iniziale

Giocatore: definisce il giocatore a cui tocca muovere in uno stato

Azioni: insieme mosse lecite in uno stato

Risultato: risultato di una mossa

Test terminazione: per determinare se la partita è finita

Utilità o funzione obiettivo: assegna un valore numerico agli stati terminali

(es: +1 vittoria, -1 sconfitta e 0 pareggio).

Il gioco è interpretato come un albero in cui la radice è la posizione di partenza, i

nodi intermedi rappresentano lo stato del gioco, gli archi sono le possibili mosse che

ciascun giocatore può compiere e le foglie costituiscono le posizioni finali.

Si consideri un gioco a somma zero, con informazione perfetta, a turni e a due

giocatori.

A ciascun nodo viene associato un valore di utilità, per i nodi intermedi viene

chiamato valore minimax, i valori alti sono buoni per un giocatore che chiameremo

‘max’ e i valori bassi sono buoni per l’avversario che chiameremo ‘min’.

Il primo livello dell’albero avrà tanti archi quante sono le mosse possibili per il

primo giocatore(max), il numero di archi del secondo livello è legato alle mosse

possibili del secondo giocatore(min) a partire dalla mossa fatta dal primo e così via.

L’avversario di max viene chiamato min perché, il suo obiettivo, è quello di

10

minimizzare l’utile di max(per lui significherebbe vittoria).Mentre max cerca

ovviamente di massimizzare il proprio utile. Si riporta in fig. 2.1 un esempio di

albero di ricerca.

MAX

MIN

MAX

Figura 2.1 Albero di ricerca in cui sia max che il suo avversario(min) hanno tre mosse legali

2.1 Algoritmo minimax

L’algoritmo minimax è l’algoritmo più utilizzato per la progettazione di giochi. Si

basa sull’idea di sviluppare tutto l’albero di ricerca, valutarne gli stati terminali (le

foglie) come vincenti o perdenti e poi riportare all’indietro, verso la radice, la

valutazione delle mosse. In pratica l’algoritmo calcola la decisione minimax per lo

stato corrente, mediante un calcolo ricorsivo del valore minimax di ogni stato

successore. La mossa migliore viene cercata a partire dagli stati terminali del gioco

per poi risalire verso lo stato corrente: la ricorsione percorre tutto l’albero fino alle

foglie, i valori minimax vengono “portati su” attraverso l’albero durante la fase di

ritorno. Ipotizzando che il suo avversario(min) faccia la scelta a lui più favorevole,

l’algoritmo è progettato per determinare la strategia ottimale per il giocatore max e

suggerirgli la prima mossa migliore da compiere. La scelta della strategia ottima per

max assicura che essa sia almeno pari a qualsiasi altra strategia, assumendo che si

stia giocando contro un avversario infallibile.

11

Nella prossima sezione di questo paragrafo, sarà riportata una descrizione sommaria

dell’algoritmo e verrà mostrato un semplice esempio di applicazione.

Innanzitutto viene creato un nodo radice di tipo max con la posizione iniziale.

Effettuando una ricerca in profondità(1), vengono espansi i nodi fino ad una certa

profondità, coincidente con la fine del gioco; successivamente, alla profondità

raggiunta(nodi foglia), viene applicata la valutazione euristica(funzione di utilità). I

valori di utilità ottenuti vengono poi portati all’indietro verso i nodi interni fino alla

radice:

-Ai nodi min si assegna il minimo dei valori di utilità di ciascun figlio.

-Ai nodi max si assegna il massimo dei valori di utilità di ciascun figlio.

Ecco una forma di pseudocodice dell’algoritmo minimax[3]:

Funzione Decisone-minimax(stato) return azione

return argmax a∈Azioni(stato) Valore-min(RISULTATO(stato,a))

Funzione Valore-max(stato) return utilità

If Test-Terminazione(stato) then return Utilità(stato)

v -∞

for each a in Azioni(stato) do

v Max(v,Valore-min(Risultato(stato,a)))

return v

Funzione Valore-min(stato) return utilità


v ∞


v Min(v,Valore-max(Risultato(stato,a)))

return v

1: Espande sempre per primo il nodo più profondo dell’albero di ricerca corrente

12

Le funzioni valore-max e valore-min attraversano l’intero albero fino alle foglie per

determinare il valore da portare all’indietro di uno stato. La notazione “argmax

a∈Azioni(stato)” calcola lo stato successore con valore minimax più grande.

Esempio di applicazione dell’algoritmo:

MAX A

MIN B C D

MAX

E F G H I L M N O

Figura 2.2 Esempio applicazione algoritmo min max

Con riferimento alla figura 2.2, in rosso si è indicata la mossa selezionata da

minimax. E’ quella il cui figlio ha valore pari al valore del nodo.

L’algoritmo effettua una ricerca in profondità, quindi mediante la ricorsione,

raggiunge i tre nodi in basso a sinistra. A questo punto usa la funzione utilità per

scoprire i valori di ciascun nodo rispettivamente 36,5,12. Prende il minimo di questi

valori e lo restituisce come valore minimax del nodo B. Con lo stesso procedimento

si ottengono i valori dei nodi C e D. Infine il massimo tra 5,2,1 fornisce il valore 5

alla radice.

Per quanto riguarda l’analisi prestazionale, l’algoritmo minimax è completo(ammette

soluzione) se l’albero è finito ed è ottimale se l’avversario gioca al meglio. Siano b le

mosse legali in ogni punto(fattore di ramificazione) e m la massima profondità

dell’albero di ricerca; l’algoritmo ha complessità temporale di O(b^m) e spaziale

O(bm), se genera i suoi successori tutti insieme, O(m) se li genera uno per volta .

5

5 2

36 5 26 25

1

12 12 1 15

6

2

13

Lo svantaggio principale, che non rende minimax adoperabile per giochi reali, è la

complessità temporale: il numero di stati da esaminare cresce esponenzialmente con

la profondità dell’albero.

2.2 Potatura alfa-beta

Come è stato accennato alla fine del paragrafo precedente, il problema principale di

minimax è rappresentato dalla quantità enorme di nodi da esplorare. I giochi reali

sono molto complessi, sarebbe impensabile anche per un calcolatore molto potente

sviluppare tutto l’albero per decidere la mossa migliore. Ad esempio, in una normale

partita a scacchi, l’albero di gioco avrebbe un fattore di ramificazione(b) di 35 e una

profondità massima di 100. Solo all’inizio della partita le mosse disponibili

sarebbero 400, alla seconda mossa sarebbero 144000 e così via. Il numero di nodi da

esplorare potrebbe arrivare a 10^40!

Per ovviare a questa problematica si pota l’albero di ricerca in modo da evitare di

prendere in considerazione grandi porzioni dell’albero la cui esplorazione sarebbe

inutile. L’obiettivo della tecnica di potatura alfa-beta, applicata a un albero di ricerca

minimax, è quello di evitare l’esplorazione di nodi il cui valore di utilità non potrà

mai influenzare quello della radice; quindi non potrà cambiare la decisone finale.

Considerando un nodo n dell’albero in cui un giocatore abbia facoltà di muoversi, se

esiste una scelta migliore m a livello del nodo padre o di qualsiasi altro nodo

precedente, allora n non sarà mai raggiunto in tutta la partita. L’idea è quella di

potare n dopo aver esplorato alcuni suoi discendenti per raccogliere le informazioni

che permettono di autorizzare la sua potatura.

Chiamando alfa il valore della scelta migliore(quella con valore più alto) trovata

sulla strada di max e beta il valore della scelta migliore(quella con valore più basso)

trovata sulla strada di min, la ricerca aggiorna i valori alfa e beta e taglia l’albero

quando trova valori peggiori.

14

In figura 2.3 viene riportato un esempio di come avvengono i tagli, riproponendo

l’esempio di figura 2.2.

MAX A

MIN B C D

MAX

E F G H I L M N O

Figura 2.3 Esempio applicazione algoritmo di potatura alfa- beta

Espandendo il nodo B si ottengono i valori di utilità delle foglie (36,5,12) e si

assegna il minimo(5) al nodo B(beta=5). All’espansione del secondo nodo(C) si nota

che il primo figlio(H) ha valore 2, essendo 2 un minimo più piccolo di beta

l’esplorazione dei nodi I e L può essere evitata. Questo perché anche se venissero

esplorati non sarebbero presi in considerazione: max è interessato al massimo dei

nodi min(5 nel nostro caso). Continuando la ricerca si arriva al nodo M che ha valore

25. Essendo 25 più elevato del minimo valore trovato fino a questo momento(beta) si

assegna 25 al nodo D, e si continua ad esplorare le foglie. Passando al nodo N si

ottiene il valore 1 che è più basso di 25 quindi si assegna 1 al nodo D. Poiché 1 è un

minimo più piccolo di quello trovato nei nodi precedenti e poiché la scelta di max

andrà sul più grande, il nodo O può essere potato.

Allo stesso modo, considerando alberi molto più complessi , invece di potare singoli

nodi si potrebbero potare interi sottoalberi in modo da evitare l’esplorazione di

un’ampia parte dell’albero di ricerca.

L’efficacia dell’algoritmo dipende dall’ordine in cui sono esaminati gli stati.

5

5 2

36 5 26 25

1

12 12 1 15

6

2

15

Nel caso in cui tutti i successori peggiori dal punto di vista di min o di max vengano

generati prima dei migliori, non è possibile potarli. Quindi bisognerebbe cercare di

esaminare prima i successori più promettenti. Se questo venisse fatto, quindi nel caso

migliore, la complessità temporale dell’algoritmo sarebbe O(b^m/2).

Il vantaggio rispetto alla ricerca minimax pura è evidente, in questo caso si riesce ad

ottenere lo stesso risultato di minimax, ma l’esponente del fattore di ramificazione

viene dimezzato. Si consegue, quindi, lo stesso esito in metà del tempo.

Ecco una forma di pseudocodice dell’algoritmo di potatura alfa-beta[3]:

Funzione RicercaAlfa-Beta(stato) return azione

v Valore-max(stato, -∞,∞)

return azione in azioni(stato) con valore v

Funzione Valore-max(stato,alfa,beta) return utilità


v -∞


v Max(v,Valore-min(Risultato(stato,a),alfa,beta)))

if (v>=beta) then return v

alfa Max(alfa,v)

return v

Funzione Valore-min(stato,alfa,beta) return utilità


v +∞


v Min(v,Valore-max(Risultato(stato,a),alfa,beta)))

if (v<=beta) then return v

beta Max(beta,v)

return v

16

L’unica differenza rispetto all’algoritmo che implementa minimax sono le righe di

codice che permettono la gestione e l’aggiornamento dei valori di alfa e beta.

Un caso reale in cui la potatura alfa-beta ha dimostrato un enorme successo è con il

programma per gli scacchi Deep Blue di IBM. Deep Blue è noto per aver sconfitto il

campione del mondo Garry Kasparov in una partita di esibizione. Il super calcolatore

è composto da 32 processori che eseguivano ricerche alfa beta con più di 512 chip

specializzati nella generazione delle mosse e nella loro valutazione.

Il programma di scacchi, scritto in C, ha portato il fattore ramificazione medio da 35

a 6. Arriva ad esplorare alberi profondi 12/13 semimosse in 3 minuti circa.

L’algoritmo è capace di calcolare ben 200 milioni di posizioni al secondo!

2.3 Funzioni di valutazione

Nonostante la potatura alfa-beta sia molto più efficiente rispetto alla ricerca minimax

pura, anch’essa, almeno per una porzione dell’albero di ricerca, deve raggiungere gli

stati terminali. Per alcuni giochi questo non solo potrebbe essere oneroso dal punto

di vista computazionale, ma anche temporale: in qualsiasi gioco che si rispetti la

risposta dell’avversario deve avvenire in un tempo accettabile.

Claude Shannon nel suo articolo programming a computer for playing

chess(1950)[4], propose di tagliare la ricerca prima di raggiungere le foglie,

applicando una funzione di valutazione euristica agli stati. In questo modo,

l’algoritmo minimax viene modificato in modo che nodi non terminali diventino nodi

foglia. La funzione di valutazione è una stima dell’utilità attesa a partire da una

determinata posizione del gioco.

La corretta stima di questa funzione è essenziale per il corretto funzionamento

dell’algoritmo: valutazioni scorrette sui punteggi relativi alle diverse configurazioni

potrebbero condurre il programma a decisioni errate.

La funzione di valutazione deve quindi essere consistente con l’utilità, qualora

17

venisse applicata a stati terminali, efficiente da calcolare e deve riflettere la

probabilità effettiva di vittoria: se un giocatore ha più probabilità di vincere rispetto

all’avversario, deve avere un valore maggiore.

Matematicamente essa ha la forma di una somma ponderata:

valutazione = ∑ wi fi , in cui:

fi è una feature che indica una caratteristica di un posizionamento.

Ad esempio fi per la dama potrebbe essere il numero di dame oppure il numero di

pedoni del bianco, per l’othello il numero di pedine che un giocatore possiede, nel

gioco degli scacchi il numero di pezzi posseduti da un giocatore di un particolare

tipo(pedone,alfiere,cavallo,regina). Oltre al numero di elementi potrebbe riferirsi

anche a un determinato posizionamento degli stessi, che strategicamente abbia un

valore.

wi, invece, indica il peso di ciascun elemento. Negli scacchi si assegna

approssimativamente un valore ad ogni pezzo: i pedoni valgono 1, i cavalli e gli

alfieri 3, le torri 5 e la regina 9. Nel gioco della dama, la dama avrà sicuramente un

peso maggiore rispetto al pedone.

Oltre al tipo, anche il posizionamento dei pezzi potrà avere il suo peso wi. Ad

esempio, il posizionamento di un pezzo in caselle che strategicamente portano a una

perdita, aggiunge un peso negativo alla valutazione totale.

Poiché spesso il peso dei pezzi dipende dallo stato della partita: un pezzo a inizio

partita potrebbe avere un peso diverso quando la partita sta terminare, la valutazione

totale potrebbe considerare anche delle combinazioni non lineari.

Alcune feature(es num di pezzi), ad una determinata profondità dell’albero,

potrebbero dare una valutazione non corretta sull’esito della partita e la valutazione

di uno stato, potrebbe essere completamente smentita dalle mosse successive

dell’avversario. Il test di taglio, quindi la valutazione dei nodi, dovrebbe essere fatta

solo in posizioni quiescenti, ovvero in stati in cui si è “certi” che nelle mosse

successive non si abbia un cambio di rotta.

18

Capitolo 3: Il linguaggio prolog

Il prolog(PROgramming in LOGic) è un linguaggio logico o dichiarativo largamente

utilizzato nelle applicazioni di intelligenza artificiale, è stato progettato e

implementato a Marsiglia nel 1972 da Colmerauer e Roussel.

Un linguaggio logico descrive la conoscenza di un problema mentre i linguaggi

procedurali (c,c++,java ) descrivono uno specifico procedimento risolutivo.

In un linguaggio logico un problema è caratterizzato da oggetti, da relazioni tra essi,

e da proposizioni che esprimono proprietà logiche su queste relazioni.

Il prolog è un linguaggio formale che utilizza fatti e regole per determinare la verità

e la falsità di un obiettivo.

I fatti descrivono cose e situazioni sempre vere, le regole descrivono come le

informazioni si legano tra di loro e permettono di dedurre nuove situazioni vere sulla

base dei fatti a disposizione . Gli obiettivi sono le “domande” a cui rispondere. Fatti

e regole formano la base di conoscenza del programma. Il programma è “chiuso”

vengono considerate solo le informazioni che gli vengono fornite. L’esecuzione di

un programma è la derivazione di una conseguenza logica del programma stesso:

similmente a quanto avviene con la dimostrazione di un teorema.

Per qualsiasi approfondimento sulla semantica e sulla sintassi del linguaggio si

rimanda alla documentazione ufficiale[5]

19

Capitolo 4: Implementazione del gioco dell’othello

L’ Othello o reversi è un gioco da tavolo a informazione perfetta per due giocatori

inventato da Lewis Waterman nel 1880.

In questo capitolo sarà riportato un esempio di implementazione del suddetto gioco

in prolog, il codice è stato eseguito mediante la shell swi prolog [6].

Si riporta una rapida spiegazione delle regole del gioco facendo riferimento al sito

della federazione nazionale gioco othello[7].

Si gioca in 2 (nero vs bianco) su una othelliera 8x8 con 64 pedine bicolori(bianche e nere). A

partire da una disposizione iniziale delle pedine (figura 4.1) comincia il nero. Ciascun giocatore, al

suo turno, poggia una pedina del proprio colore su una casella ancora vuota. Una pedina può

imprigionare una o più pedine avversarie, le pedine imprigionate saranno capovolte in modo da

renderle del colore del giocatore che le imprigiona. I giocatori possono attaccare l’avversario in una

o più direzioni(orizzontale,verticale e diagonale), anche contemporaneamente. Affinché una pedina

possa imprigionare altre deve essere posizionata in una casella adiacente alla pedina da

imprigionare e deve avere all’altra estremità una pedina dello stesso colore.

Fig 4.1 Othelliera iniziale Fig 4.2 Mosse legali del nero

Tocca al nero

In Fig 4.2, con le mosse F-5 ed E-6, il nero imprigionerebbe la pedina bianca in E5, con la mossa

C-4 e D-3 il nero imprigionerebbe la pedine bianca in D-4.

20

Supponiamo che il nero scelga D-3 la scacchierà risultante sarebbe la seguente:

Fig 4.2 Imprigionamento pedina D-4 Fig 4.2 Possibili risposte bianco

Con i si sono indicate le tre possibili risposte da parte del bianco, il bianco potrebbe rispondere in

orizzontale C-5 imprigionando D-5, in verticale E-3 imprigionando E-4 e in diagonale C-3

imprigionando D-4. A questo punto la partita proseguirà.

Ciascun giocatore, al suo turno, deve giocare obbligatoriamente una pedina per imprigionare

almeno un disco avversario. Nel caso in cui non abbia mosse legali da compiere, il giocatore passa,

e tocca nuovamente all'avversario, fino all'esaurimento delle mosse per entrambi.

Vince la partita chi, quando è stata giocata l'ultima mossa, ha più pedine dell'avversario. In caso di

pari pedine, la partita è dichiarata patta.

4.1 Gioco in esecuzione

Prima di passare ai dettagli implementativi, in questo paragrafo viene riportato il

gioco in esecuzione. Dopo aver lanciato il gioco dalla shell prolog con il comando

start(). Viene mostrato un menu di scelta che consente all’utente di selezionare la

modalità di gioco desiderata(fig 4.3). Nel gioco dell’othello inizia sempre il nero,

selezionando la modalità 1, il nero è il giocatore umano, mentre con la 2, il nero è il

computer. Dopo aver effettuato la scelta, viene stampata a video l’othelliera

iniziale(fig 4.4). Le righe e le colonne sono numerate da 0 a 7, i trattini (-)

rappresentano le caselle vuote, X e O rappresentano rispettivamente la presenza di

una pedina nera e di una pedina bianca.

Figura 4.3 Figura 4.4

21

Ad esempio facendo la scelta 2, viene stampata a video l’othelliera con la mossa del

nero e viene richiesto al giocatore umano(bianco) di inserire la sua mossa di

risposta(fig 4.5). Supponendo che scelga riga 5(digitando 5.) e colonna 4(digitando

4.). L’othelliera risultante sarà quella mostrata in fig 4.6

Figura 4.5 Figura 4.6

A questo punto il nero(computer) risponderà con una sua mossa e così via. Al

termine della partita sarà stampato a video un messaggio per decretare il vincitore.

4.2 Implementazione in prolog

Il gioco è stato implementato in modo che la mossa del computer, in risposta alla

mossa del giocatore umano, venga scelta mediante l’algoritmo minimax con potatura

alfa-beta. L’algoritmo esplorerà l’albero fino ad una certa profondità , applicherà la

funzione di valutazione(pag 30) agli stati a quella profondità e sceglierà lo stato con

il valore più alto. Quindi la mossa in risposta a quella del giocatore umano sarà

quella che porta allo stato scelto. Il grado di profondità dell’albero di ricerca

potrebbe essere un indicatore di difficoltà del gioco: aumentando la profondità un

giocatore umano non esperto non riesce a competere contro un computer. Per una

complessità computazionale e temporale accettabile si è scelto di esplorare l’albero

fino alla profondità 5. Quindi il computer sceglierà la mossa da effettuare a partire

da tutte le combinazioni possibili per 5 turni di gioco, simulando le sue azioni e

quelle dell’avversario, per poi scegliere quella con il valore di utilità più alto.

22

La descrizione dell’algoritmo inizia dal file principale: GiocoOthello.pl, le regole

richiamate da altri file (es Othelliera.pl) saranno solo accennate per poi essere trattate

nel dettaglio quando si considereranno i file che le contengono.

File GiocoOthello.pl:

La regola iniziale start( ), invocata dalla shell prolog, richiama a sua volta

start(Profondità,Righe,Colonne) dove Profondità è la profondità massima

dell’albero di ricerca, Righe e Colonne sono le righe è le colonne dell’othelliera

tradizionale(8x8). Dopo aver asserito come clausole globali numrighe e numcolonne,

viene invocata la regola inizializza_othelliera contenuta nel file Othelliera.pl(pag 31

riga 1)che definisce l’othelliera iniziale con le pedine iniziali(fig 4.4) senza stamparla

a video. Viene poi invocata la regola seleziona_modalita(Scelta).

start():-

start(5,8,8).

/*La profondità max dell'albero di ricerca è impostata a 5, 8 sono le righe e le colonne della

tavola di gioco*/

start(Profondità,Righe,Colonne):-

( /*Asserisce il termine Righe come primo fatto del predicato numrighe*/

asserta(numrighe(Righe)),

asserta(numcol(Colonne)),

inizializza_othelliera(0,[],Othelliera),

seleziona_modalita(Scelta),

gioco(Othelliera,Scelta,Profondità,black),

distruggi_var

),!.

start(_,_,_):-

distruggi_var.

seleziona_modalita(Scelta):-

writeln('Seleziona modalità di gioco'),

writeln('1. Uomo vs IA'),

writeln('2. IA vs Uomo'),

writeln('3. Uomo vs Uomo'),

write('Inserisci un numero '),

read(Modalità),

( Modalità is 1 ->

Scelta is Modalità,

writeln('IA contro uomo'),

writeln(''),!

;

Modalità is 2 ->

Modalità is 2,

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

23

La regola seleziona modalità consente all’utente di scegliere tra le 3 diverse modalità

di gioco. Digitando 1 sarà selezionata l’opzione uomo contro ia, 2 ia contro uomo e 3

uomo contro uomo. Inizia sempre il nero, in 1 è l’uomo e in 2 è il computer.

gioco(Othelliera, Scelta, Profondità, Colore):-

stampa_othelliera(Othelliera),

stampa_giocatore(Colore),

othelliera_piena(Othelliera,OthellieraPiena),

(

OthellieraPiena = yes ->

mostra_risultati(Othelliera)

;

trova_mosse(Othelliera, Colore, ListaMosse),

member(_, ListaMosse),

colore_avversario(Colore,ColoreAvversario),

(

Scelta = 1 ->

(

Colore = black ->

mossa_uomo(Mossa, ListaMosse),!,

imposta_pedina(Othelliera, Mossa, Colore, Othelliera_Dopo_Mossa),

gioco(Othelliera_Dopo_Mossa, 1, Profondità, ColoreAvversario),!

;

Colore = white ->

mossa_ia(Othelliera, Profondità, white, Othelliera_Dopo_Mossa),!,


)

;

Scelta = 2 ->

(

Colore = black ->

mossa_ia(Othelliera, Profondità, Colore, Othelliera_Dopo_Mossa),!,


;


writeln('Uomo contro IA'),

writeln(''),!

;

Modalità is 3 ->


writeln('Uomo contro Uomo '),

writeln(''),!

;

writeln('Mossa non valida'),

writeln(''),

seleziona_modalita(Scelta)

).

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

24

Colore = white ->




)

Scelta = 3 ->




)

).

gioco(Othelliera, Scelta, Profondità, Colore):-

trova_mosse(Othelliera, Colore, ListaMosse),!,

not(member(_,ListaMosse)),!,

colore_avversario(Colore, ColoreAvversario),

(trova_mosse(Othelliera, ColoreAvversario, ListaMosseAvversario),

member(_,ListaMosseAvversario))->

writeln('Non hai mosse valide da fare.'),

gioco(Othelliera, Scelta, Profondità, ColoreAvversario),!

;

/*Se anche l'avversario non ha mosse valide mostra risultati */

writeln('Nessun giocatore ha almeno una mossa valida.'),

mostra_risultati(Othelliera)

).

/*Regola che dato un colore permette di ottenere quello dell’avversario */

colore_avversario(white, black).

colore_avversario(black, white).

mostra_risultati(Othelliera):-

nl,

conta_pedine(black, Othelliera, NumNero, NumBianco),

writef('Nero %d\n',[NumNero]),

writef('Bianco %d\n',[NumBianco]),

abs(NumNero-NumBianco, Diff),

(

NumNero > NumBianco ->

writef('Nero vince per %d pedine\n', [Diff])

;

NumNero < NumBianco ->

writef('Bianco vince per %d pedine\n', [Diff])

;

write('Partita terminata in parità \n')

),

nl.

getRigaCol(R,C):-

numrighe(R),

numcol(C).

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

25

La regola gioco numero 1(riga 43) ha come argomenti l’othelliera inizializzata in

start, la profondità dell’albero, la scelta fatta e il colore del giocatore di turno.

Invocando dal file othelliera.pl la regola stampa_othelliera (pag 34 riga 33) viene

stampata a video l’othelliera su cui si svolgerà la partita(fig 4.4).

Dopo aver mostrato il giocatore a cui tocca muovere con stampa_giocatore (riga

122 e 126), si va a verificare se l’othelliera è piena, ovvero se le pedine in gioco

occupano tutte le caselle disponibili.

Quando l’othelliera è piena la partita termina, viene quindi richiamata la regola

mostra_risultati, che, dopo aver contato(riga 104) il numero di pedine nere e il

numero di pedine bianche, decreta il vincitore: se il numero di pedine nere è

maggiore delle bianche, vince il nero, altrimenti vince il bianco. Qualora il numero di

pedine fosse uguale la partita sarebbe patta.

Considerando l’othelliera nello stato iniziale(fig 4.4), quindi non piena alla riga 48,

si procede con la partita cercando le mosse disponibili a partire dall’othelliera

corrente con la regola trova_mosse di othelliera.pl(pag 39 riga 245). Nella variabile

ListaMosse saranno inserite le mosse legali del giocatore di turno. Dopo aver

invocato la regola colore_avversario, che dato un colore definisce quello avversario,

dovrà essere invocata la regola che indica il giocatore a cui tocca muovere(umano o

ia). Supponendo che sia stata effettuata la scelta numero 1 e il giocatore di turno sia

umano, verrà invocata la regola mossa uomo(definita alla riga 130). Quest’ultima

acquisisce in input la mossa scelta dal giocatore umano, dopo aver opportunamente

verificato che essa rientri tra le mosse legali per quel giocatore(riga 135). Acquisita

la mossa viene invocata la regola imposta_pedina (pag 40 riga 313) di Othelliera.pl,

il cui compito è quello di inserire la pedina nella posizione scelta e “capovolgere “

le pedine avversarie interessate alla mossa; si otterrà in questo modo una nuova

Othelliera(Othelliera_Dopo_Mossa).

Alla riga 60 è presente una chiamata ricorsiva che invoca nuovamente la stessa

regola, ma con parametri diversi. Al posto di Othelliera viene considerata l’

26

othelliera dopo la mossa e al posto di colore quello avversario(nel caso considerato è

il bianco).

Richiamando la regola gioco, supponendo che l’othelliera non sia piena e che ci

siano mosse legali da compiere, tocca al computer; quindi viene invocata la regola

mossa_ia (riga 63, definita alla riga 144).

Prima di illustrare il modo in cui il computer sceglie la sua prossima mossa, si vuole

giustificare la presenza della regola gioco numero 2(riga 85).

Alla riga 48, se l’othelliera non è piena, si procede con la partita cercando le mosse

disponibili a partire dall’othelliera corrente. Nella variabile ListaMosse saranno

stampa_giocatore(white):-

nl,

writeln('Tocca al giocatore bianco (O)'),!.

stampa_giocatore(black):-

nl,

writeln('Tocca al giocatore nero (X)'),!.

mossa_uomo(Mossa, ListaMosse):-

write('Inserisci la riga della casella scelta: '),

read(RigaInput),

write('Insersci la colonna della casella scelta: '),

read(ColonnaInput),

member(Mossa, ListaMosse),

nth0(0, Mossa, RigaInput),

nth0(1, Mossa, ColonnaInput).

mossa_uomo(Mossa, ListaMosse):-

writeln('Mossa non valida, riprova'),

writeln(''),

mossa_uomo(Mossa, ListaMosse).

mossa_ia(Othelliera, Profondità, Colore, Othelliera_Dopo_Mossa):-

garbage_collect,

alpha_beta_pruning(Othelliera, Profondità, Colore, Othelliera_Dopo_Mossa, _).

distruggi_var:-

numrighe(Righe),

numcol(Colonne),

retract(numrighe(Righe)),

retract(numcol(Colonne)).

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

27

inserite le mosse legali del giocatore di turno, se il giocatore di turno non ha mosse

legali da compiere la regola gioco numero 1 fallisce. In prolog quando una regola

fallisce il motore inferenziale cerca di soddisfare il goal corrente applicando un’altra

regola presente nella base di conoscenza. Viene quindi invocata la regola gioco

numero 2(riga 85), quest’ultima verifica se l’avversario ha mosse legali da

compiere(riga 89), in caso affermativo viene stampato a video un messaggio (riga

91) e il turno passa al giocatore avversario. Se anche l’avversario non ha mosse legali

da compiere, la partita termina alla riga 93 e, mediante la regola mostra_risultati,

viene decretato il vincitore. Nel primo caso, il passaggio del turno all’avversario

viene implementato mediante la chiamata ricorsiva gioco (riga 92). La ricorsione

rievoca la regola gioco numero 2(riga 85) ma la presenza di mosse da compiere ne

comporta il fallimento alla riga 87, quindi il passaggio del turno avviene con la

successiva invocazione della regola gioco numero 1(riga 43). La regola mossa_ia

invoca a sua volta la regola potatura_alfa_beta definita nel file

RicercaAlfaBetaConEuristica.pl, in cui, oltre alla definizione delle regole per

eseguire la ricerca, vi sono anche le regole che permettono di calcolare il valore

euristico in uno stato. File RicercaAlfaBetaConEuristica.pl:

/* Dove stato è l'othelliera corrente e nuovo stato è l’othelliera dopo la mossa, valore è il valore

euristico */

potatura_alfa_beta(Stato, Profondità, Colore, NuovoStato, Valore):-

potatura_alfa_beta(Colore,Profondità, Stato, Colore, NuovoStato, Valore, -100000, 100000).

potatura_alfa_beta(ColoreChiamante,_, Stato, _, Stato, Valore, _, _) :-

fine(ColoreChiamante, Stato, Valore),!.

potatura_alfa_beta(ColoreChiamante,0, Stato, _, Stato, Valore, _, _) :-

valutazione(ColoreChiamante, Stato, Valore),!.

/*Colore è il colore del giocatore che eseguirà la prossima mossa*/

potatura_alfa_beta(ColoreChiamante,Profondità, Stato, Colore, NuovoStato, Valore, Alfa, Beta)

:-

Profondità > 0,

garbage_collect,

trova_stati(ColoreChiamante, Stato, Colore, ListaStati),


NProfondità is Profondità - 1,

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

28

/*Se il primo fallisce ritorna alla profondità precedente */

catch(

potatura_alfa_beta(ColoreChiamante,ListaStati, NProfondità, Colore, ColoreAvversario,

NuovoStato, Valore, Alfa, Beta),

_,

potatura_alfa_beta_recover(ColoreChiamante,ListaStati, Profondità, Colore,

ColoreAvversario, NuovoStato, Valore, Alfa, Beta)

).

potatura_alfa_beta(ColoreChiamante,[Stato], Profondità, _, ColoreAvversario, Stato, Valore,

Alfa, Beta):- !,

potatura_alfa_beta(ColoreChiamante,Profondità, Stato, ColoreAvversario, _, Valore, Alfa,

Beta).

potatura_alfa_beta(ColoreChiamante,[Stato|Rest], Profondità, Colore, ColoreAvversario,

NuovoStato, Valore, Alfa, Beta) :-

potatura_alfa_beta(ColoreChiamante,Profondità, Stato, ColoreAvversario, _, X, Alfa, Beta),

(

pota(Colore, X, Alfa, Beta) ->

(

NuovoStato = Stato,

Valore is X

);

(

ricalcola(Colore, X, Alfa, Beta, Nalfa, NBeta),

potatura_alfa_beta(ColoreChiamante,Rest, Profondità, Colore, ColoreAvversario, B, Y,

Nalfa, NBeta),

valmigliori(Colore, X, Y, Stato, B, NuovoStato, Valore)

)

).

potatura_alfa_beta_recover(ColoreChiamante,ListaStati, Profondità, Colore, ColoreAvversario,

NuovoStato, Valore, Alfa, Beta):-

/*print_message(_, Error),*/

writef('rispistino profondità: %d\n', [Profondità]),

garbage_collect,

potatura_alfa_beta(ColoreChiamante,ListaStati, 0, Colore, ColoreAvversario, NuovoStato,

Valore, Alfa, Beta).

pota(black, Valore, _, Beta):-

/*writeln('potato nero),*/

Valore >= Beta.

pota(white, Valore, Alfa, _):-

/*writeln('potato bianco'),*/

Valore =< Alfa.

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

29

Alla riga 4 viene invocata una nuova regola potatura_alfa_ beta in cui si

inizializzano anche i valori di alfa(-100000) e beta(100000). La profondità di ricerca

parte da n(5 nel nostro caso), quando è maggiore di zero, viene richiamata la regola

trova_stati di othelliera.pl(pag 35 riga 114). La regola trova_stati a partire da uno

stato, quindi dall’othelliera corrente, per ogni possibile mossa legale, trova le

othelliere corrispondenti. Quindi, considerando l’albero di ricerca minimax, trova

tutti i possibili figli dello stato corrente. Per migliorare l’efficienza dell’algoritmo, la

regola trova_stati non inserisce i figli nella variabile ListaStati in modo casuale, ma

ordinati in base al loro valore di utilità. Alla riga 22 viene invocata la regola

potatura_alfa_beta, definita alla riga 34. La ricorsione che permette di raggiungere i

nodi terminali fino a profondità zero è implementata delle regola potatura_alfa_beta

alla riga 36, quindi si avanza di profondità, mediante l’invocazione delle regola alla

riga 13. Quando la profondità arriva a 0, dalla riga 36 viene invocata la regola

definita alla riga 9. Qui la ricerca in profondità viene tagliata e viene fatta una

valutazione degli stati terminali. A questo punto ripercorrendo le chiamate fatte,

tramite la chiamata ricorsiva potatura_alfa_beta riga 45, vengono esplorati solo

alcuni nodi dell’albero e non tutti. Le regole che permettono di potare i nodi che non

verranno sicuramente esplorati e aggiornare i valori alfa e beta sono:pota e ricalcola.

Qualora si dovesse arrivare ad una situazione di othelliera piena prima di tagliare la

ricerca a profondità n, verrebbe invocata la regola fine, il valore restituito sarà

semplicemente la differenza tra pedine nere e pedine bianche.

/* Ricalcola i valori di alfa e beta */

ricalcola(black, Valore, Alfa, Beta, Nalfa, Beta):-

max_list([Alfa, Valore], Nalfa).

ricalcola(white, Valore, Alfa, Beta, Alfa, NBeta):-

min_list([Beta, Valore], NBeta).

/* Calcola i migliori valori in base al colore che muove*/

valmigliori(black, X, Y, A, _, A, X):- X>=Y,!.

valmigliori (black, _, Y, _, B, B, Y).

valmigliori (white, X, Y, A, _, A, X):- X=<Y, !.

valmigliori (white, _, Y, _, B, B, Y).

68

69

70

71

72

73

74

75

76

77

78

30

La prossima sezione del file RicercaAlfaBetaConEuristica.pl riporta la definizione

delle regole valutazione e fine per il calcolo del valore euristico in uno stato.

/*Valutazione euristica nero*/

valutazione(black,Othelliera, Valore):-

conta_pedine(black, Othelliera, PedineNere, PedineBianche),

PedineTotali is PedineNere + PedineBianche,

Differenza_pedine is PedineNere - PedineBianche,

posizioni_valide(Othelliera, black, MosseValideNero),

posizioni_valide(Othelliera, white, MosseValideBianco),

Diff_mosse_valide is MosseValideBianco-MosseValideNero ,

(

(PedineTotali<36)->

ValoreDifferenzaPedine is Differenza_pedine,

ValoreDifferenzaMossa is Diff_mosse_valide

;

ValoreDifferenzaPedine is Differenza_pedine,

ValoreDifferenzaMossa is 0

),

Valore is ValoreDifferenzaPedine+ValoreDifferenzaMossa.

fine(black,Othelliera, Valore):-

othelliera_piena(Othelliera),


Valore is PedineNere - PedineBianche.

/*Valutazione euristica bianco*/

valutazione(white,Othelliera, Valore):-


ValorePedina is (PedineNere - PedineBianche),!,



ValoreDifferenza is (MosseValideNero - MosseValideBianco),!,

Valore is ( ValorePedina + ValoreDifferenza).

fine(white,Othelliera, Valore):-


MosseValideNero is 0,!,


MosseValideBianco is 0,!,


Valore is (PedineNere - PedineBianche),!.

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

31

Il valore di utilità per il giocatore nero è dato dalla differenza tra il numero di pedine

nere e il numero di pedine bianche presenti sull’othelliera corrente, sommato alla

differenza tra le mosse valide del bianco e le mosse valide del nero. Alla riga 81 con

la regola conta_pedine di othelliera.pl(pag 43 riga 419 ) vengono contate il numero

di pedine bianche e nere. Dopo aver fatto la somma e la differenza dei valori ottenuti,

viene richiamato la regola posizioni_valide di othelliera.pl (pag 37 riga 181), in

modo da ottenere il numero di mosse valide del nero e del bianco per poi fare la

differenza dei valori ottenuti(var Diff_mosse_valide). Quest’ultimo parametro ha

peso solo se il numero di pedine totali è inferiore a 36. Se non lo è, per il calcolo del

valore euristico, si considera solo la differenza delle pedine. Il calcolo del valore

euristico del bianco è identico al nero, ad eccezione del controllo sulle pedine totali.

L’ultimo file del gioco è il file in cui sono definite molte regole che sono state già

trattate. File Othelliera.pl:

inizializza_othelliera(Rigaiesima,OthellieraTemporanea,Othelliera):-

numrighe(R),

Rigaiesima=R,

Othelliera=OthellieraTemporanea,

!.

inizializza_othelliera(Rigaiesima,OthellieraTemporanea,Othelliera):-

numrighe(R),

Rigaiesima<R,

inizializza_righe(Rigaiesima,0,[],Riga),

append(OthellieraTemporanea,[Riga],NOthellieraTemporanea),

NRigaiesima is Rigaiesima+1,

inizializza_othelliera(NRigaiesima,NOthellieraTemporanea,Othelliera).

inizializza_righe(_,Coljesima,TempRiga,Riga):-

numcol(C),

Coljesima=C,

append(TempRiga,[],Riga),

!.

inizializza_righe(Rigaiesima,Coljesima,TempRiga,Riga):-

numrighe(R),

numcol(C),

Coljesima<C,

CentroDx is C/2, /*Rig e col partono da 0 */

CentroSx is C/2-1,

CentroSotto is R/2,

CentroSopra is R/2-1,

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

32

La regola Inizializza_othelliera, inizializza la tavola di gioco sulla quale avverrà la

partita (fig 4.4 pag 20). L’inizializzazione procede da sinistra verso destra scorrendo

le colonne e le righe dell’othelliera: parte dalla casella 0,0 poi 0,1, 0,2, fino a 7,7.

La regola viene quindi invocata passando 0 alla Rigaiesima. Alla prima invocazione

la regola in riga 1 fallisce a causa del fallimento della clausola Rigaiesima(0)=R(8),

il motore inferenziale invoca la seconda Inizializza_othelliera, quest’ultima, dopo

aver verificato che la Rigaiesima sia minore di R(8), invoca inizializza righe

passando 0 a Coljesima. Alla prima invocazione la prima regola alla riga 15 fallisce

poiché Coljsesima è diversa da 8. Viene quindi invocata la seconda(riga 20) che

attraverso una serie di chiamate ricorsive a partire da 0,0 arriva a 0,7. Arrivati a 0,7,

alla successiva invocazione, la prima regola inizializza righe ha successo, appende la

lista vuota alla riga appena creata e ritorna a inizializza_othelliera. Dopo aver

aggiunto la riga appena creata all’othelliera che si sta formando, si passa alla riga

successiva(NRigaiesima is Rigaiesima+1) e con la ricorsione viene richiamato

inizializza_righe. Il procedimento appena descritto avviene in maniera iterativa alla

riga successiva e a tutte le altre righe rimanenti. Ogni casella dell’othelliera può

assumere 3 valori: nero, bianco e vuoto. Le clausole riga 28-37 servono ad

inizializzare le 4 caselle come mostrato in fig 4.4 pag 20. Quando con la ricorsione si

arriverà alle caselle 3,3 e 4,4 il valore assegnato sarà nero, mentre alle 3,4 e 4,3 il

valore sarà bianco, tutte le altre saranno caselle vuote.

(

( (Rigaiesima = CentroSopra , Coljesima = CentroSx);

(Rigaiesima = CentroSotto , Coljesima = CentroDx) ) ->

Colore=black

;

( (Rigaiesima = CentroSopra , Coljesima = CentroDx);

(Rigaiesima = CentroSotto , Coljesima = CentroSx) ) ->

Colore = white

;

Colore = empty

),

append(TempRiga,[Colore],NTempRiga),

NColjesima is Coljesima+1,

inizializza_righe(Rigaiesima,NColjesima,NTempRiga,Riga).

27

28

29

30

31

32

33

34

35

36

37

38

39

40

33

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

stampa_othelliera(Othelliera):-

tab(4),

stampa_head(0),

stampa_body(0,0,Othelliera),

nl.

stampa_head(Coljesima):-

numcol(C),

Coljesima=C,

nl,

write(' ----'),

for(1,C,1,write('--')), /*Per i=0 i<c con incremento 1 disegna trattini */

nl,

!.

stampa_head(Coljesima):-

write(Coljesima),

tab(1),


stampa_head(NColjesima).

stampa_body(Rigaiesima,Coljesima,_):-

numrighe(R),

numcol(C),

Rigaiesima is R-1,

Coljesima is C,

!.

stampa_body(Rigaiesima,Coljesima,Othelliera):-

numcol(C),

(

Coljesima=0 ->

write(Rigaiesima),

write(' | '),

NRigaiesima is Rigaiesima,


stampa_pedina(Rigaiesima,Coljesima,Othelliera)

;

Coljesima=C ->


NColjesima is 0,

nl

;



stampa_pedina(Rigaiesima,Coljesima,Othelliera)

),

stampa_body(NRigaiesima,NColjesima,Othelliera).

34

Stampa_othelliera viene invocata dalla regola gioco nel file principale per stampare a

video l’othelliera su cui si svolgerà la partita. Alla riga 44 invoca stampa_head il cui

compito è quello di stampare la parte superiore del tavolo di gioco ovvero i numeri

delle colonne e i trattini sottostanti. La regola alla riga 57, a partire dalla colonna 0,

stampa i numeri, quando attiva a 7, la stampa_head riga 48 ha successo e con un

ciclo for stampa i trattini sottostanti. Dopo aver stampato l’intestazione, si ritorna alla

riga 45 per stampare la parte restante dell’othelliera.

Stampa_body alla colonna 0 stampa i numeri delle righe e il bordo separatore di

sinistra, incrementa le colonne per la successiva invocazione e invoca

stampa_pedina. Quest’ultima verifica che la pedina rientri nell’othelliera (regola

verifica_indice), e in base al valore assunto dalla pedina, stampa nella casella

(rigaiesima,coljesima) un X se è nera, un O se è bianca e un – se è vuota. Il valore

della pedina si estrae dalla lista con i 2 predicati nth0(riga 104-105). Dopo aver

stampato la pedina si passa alla casella successiva mediante la ricorsione (riga 90).

Alla fine di una riga(Coljesima=C) si passa alla successiva, e con le clausole dalla

riga 86-88 si stampano le pedine in tutte le altre posizioni diverse dal bordo.

stampa_pedina(Rigaiesima, Coljesima, Othelliera):-

pedina(Othelliera, Rigaiesima, Coljesima, Pedina),

(Pedina=black->

write('X ')

;

Pedina=white ->

write('O ')

;

write('- ') ).

pedina(Othelliera, Rigaiesima, Coljesima, Pedina):-

verifica_indice(Rigaiesima,Coljesima),

nth0(Rigaiesima,Othelliera,Riga),

nth0(Coljesima,Riga,Pedina).

verifica_indice(Rigaiesima,Coljesima):-

numrighe(R),

numcol(C),

Rigaiesima>=0,

Rigaiesima<R,

Coljesima>=0,

Coljesima<C.

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

35

La

/*Trova stati, a partire dalla Lista delle mosse legali in un determinato stato, permette di trovare

tutte le othelliere corrispondenti*/

trova_stati(ColoreChiamante, Stato, Colore, ListaStati):-

trova_othelliere(ColoreChiamante, Stato, Colore, ListaStati).

trova_othelliere(ColoreChiamante, Othelliera, Colore, ListaOthelliere):-

trova_mosse(Othelliera, Colore, ListaMosse),

trova_othelliere(ColoreChiamante, Othelliera, Colore, ListaOthelliereOrdinate, [],

ListaMosse),

primi_elementi(ListaOthelliereOrdinate, [], ListaOthelliere).

trova_othelliere(_, Othelliera,_, ListaOthelliere, [], []):-

append([], [[Othelliera, 0]], ListaOthelliere),!.

trova_othelliere(_, _, _, ListaOthelliere, ListaOthelliere, []):-!.

trova_othelliere(ColoreChiamante, Othelliera, Colore, ListaOthelliere, ListaOthelliereCorrente,

[Mossa|RestListaMosse]):-


ordina_othelliere(ColoreChiamante, Colore, ListaOthelliereCorrente,

Othelliera_Dopo_Mossa, NListaOthelliere),

trova_othelliere(ColoreChiamante, Othelliera, Colore, ListaOthelliere, NListaOthelliere,

RestListaMosse),!.

ordina_othelliere(ColoreChiamante, Colore, ListaOthelliereCorrente, Othelliera_Dopo_Mossa,

NListaOthelliere):-

valutazione(ColoreChiamante, Othelliera_Dopo_Mossa, Numero),

ordina_othelliere_aux(Colore, [Othelliera_Dopo_Mossa, Numero],

ListaOthelliereCorrente, [], NListaOthelliere).

ordina_othelliere_aux(_, Othelliera, [], ListaCorrente, ListaFinale):-

append(ListaCorrente, [Othelliera], ListaFinale),!.

ordina_othelliere_aux(Colore, Othelliera, [Primo|Rest], ListaCorrente, ListaFinale):-

nth0(1, Primo, Valore),

nth0(1, Othelliera, NuovoValore),

(

Colore = black ->

NuovoValore >= Valore

;

NuovoValore =< Valore

),

append(ListaCorrente, [Othelliera], TempList),

append(TempList, [Primo|Rest], ListaFinale),!.

ordina_othelliere_aux(Colore, Othelliera, [Primo|Rest], ListaCorrente, ListaFinale):-

append(ListaCorrente, [Primo], NListaCorrente),

ordina_othelliere_aux(Colore, Othelliera, Rest, NListaCorrente, ListaFinale),!.

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

36

La regola trova stati a partire da uno stato permette di trovare tutte le othelliere che

si otterrebbero selezionando ogni possibile mossa legale.

La regola trova trova_stati invoca trova_othelliere. Trova_othelliere innanzitutto

trova tutte le mosse legali a partire da uno stato, mediante trova_mosse(definita a pag

39 riga 248). Successivamente invoca la regola ricorsiva trova_othelliere righe 128-

133, che, per ogni mossa presente il ListaMosse, invoca imposta_pedina(pag 40 riga

313), il cui compito è quello di impostare una singola pedina e capovolgere

eventualmente quelle avversarie. Le othelliere ottenute, saranno inserite in una lista

che sarà restituita da trova_stati alla regola chiamante. Prima di inserire le othelliere

nella lista, mediante la regola ordina_othelliere(riga 136), avviene il calcolo del

valore di utilità nello stato considerato. Con l’invocazione di ordina_othelliere_aux

l’inserimento nella lista non è casuale ma avviene in base al valore di utilità dello

stato. Se il chiamante è il nero, in ordine crescente (148-155) altrimenti decrescente.

La regola othelliera_piena viene invocata per verificare se la partita è giunta al

termine. Se non c’è nessuna casella vuota(riga 165), l’othelliera è considerata piena;

altrimenti, OthellieraPiena assumerebbe il valore ‘no’. Alla riga 170 la regola

othelliera_vuota è vera se è presente almeno una casella libera.

othelliera_piena(Othelliera,OthellieraPiena):-

flatten(Othelliera,PedinaList),

list_to_set(PedinaList,PedinaSet),

(

not(member(empty,PedinaSet))->

OthellieraPiena = yes

;

OthellieraPiena = no

).

othelliera_vuota(Othelliera):-

member(Riga, Othelliera),

member(Pedina, Riga),

Pedina = empty,!.

othelliera_piena(Othelliera):-

flatten(Othelliera, PedinasList),

list_to_set(PedinasList, PedinasSet),

not(member(empty, PedinasSet)).

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

37

/*posizioni valide trova il numero di mosse valide per il giocatore di turno*/

posizioni_valide(Othelliera, Colore, Numero):-

posizioni_valide(Othelliera, Colore, 0, 0, 0, Numero).

posizioni_valide(_, _, Rigaiesima, Coljesima, Numero, Numero):-

numrighe(R),

numcol(C),

Rigaiesima is R-1,

Coljesima is C,!.

posizioni_valide(Othelliera, Colore, RigaIndex, Coljesima, NumeroCorrente, NumeroFinale):-

numcol(C),

Coljesima is C,

NRigaIndex is RigaIndex + 1,

posizioni_valide(Othelliera, Colore, NRigaIndex, 0, NumeroCorrente, NumeroFinale),!.

posizioni_valide(Othelliera, Colore, RigaIndex, ColonnaIndex, NumeroCorrente,NumeroFinale):-

singola_mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore),

NNumeroCorrente is NumeroCorrente + 1,

NColonnaIndex is ColonnaIndex + 1,

posizioni_valide(Othelliera, Colore, RigaIndex, NColonnaIndex, NNumeroCorrente,

NumeroFinale),!.

posizioni_valide(Othelliera, Colore, RigaIndex, ColonnaIndex, NumeroCorrente,NumeroFinale):-


posizioni_valide(Othelliera, Colore, RigaIndex, NColonnaIndex, NumeroCorrente,

NumeroFinale),!.

singola_mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore) :-

pedina(Othelliera, RigaIndex, ColonnaIndex, Pedina),

Pedina = empty,

direzioni_legali(Direzione),

member(DirezioneOffset, Direzione),

nth0(0, DirezioneOffset, RigaOffset),

nth0(1, DirezioneOffset, ColonnaOffset),

RigaDelVicino is RigaIndex + RigaOffset,

ColonnaDelVicino is ColonnaIndex + ColonnaOffset,


pedina(Othelliera, RigaDelVicino, ColonnaDelVicino, PedinaDelVicino),

PedinaDelVicino = ColoreAvversario,

trova_colore(Othelliera, RigaDelVicino, ColonnaDelVicino, RigaOffset, ColonnaOffset,

Colore),!.

/*Le 8 possibili direzioni di azione per ogni mossa */

direzioni_legali(ListaDirezioni) :-

ListaDirezioni = [[-1, 0],[-1, 1],[0, 1],[1, 1],

[1, 0],[1, -1],[0, -1],[-1,-1]].

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

38

La regola posizioni_valide viene invocata dalle funzioni di valutazione per ottenere,

a partire da una othelliera corrente, il numero di mosse valide legali. Le 8 possibili

direzioni in cui è possibile agire sono state definite con la regola direzioni_legali.

Se la casella non si trova ai bordi dell’othelliera si può agire in orizzontale, verticale

e in diagonale(sud,sud est,est,nord est,nord, nord ovest,ovest,sud ovest). Ovviamente

le mosse che andrebbero oltre i bordi non sono legali. La regola ricorsiva

posizioni_valide(riga 196), qualsiasi sia lo stato dell’othelliera corrente, a partire

dalla casella 0,0 e muovendosi da sinistra verso destra, esplora l’intera othelliera.

Iniziando da 0,0 invoca singola_mossa_valida, alla riga 210, se la casella è vuota, si

prosegue, altrimenti attraverso il fallimento della regola e l’invocazione di

posizioni_valide alla riga 203, si avanza di una colonna. Questo avviene fino alla

casella in riga 7 e colonna 7. Tornando alla riga 210 supponendo che una casella sia

vuota, si valutano le direzioni legali di una mossa, scelta una direzione ci si muove di

una riga o di una colonna per verificare se vi è una pedina avversaria in una

posizione adiacente alla direzione scelta. Qualora ci fosse, verrebbe richiamato la

regola trova_colore, il cui obiettivo è quello di trovare, sulla direzione scelta, una

pedina dello stesso colore del giocatore che muove; in modo che la mossa sia

considerata legale. Qualora la trovasse e non fallisse si ritornerebbe in posizioni

valide e verrebbe incrementata la variabile che indica il numero di mosse legali.

/* (1) Trova colore, cerca una pedina delle stesso colore (2) cerca una pedina del colore

avversario, viaggia nella direzione scelta per trovare una pedina dello stesso colore */

trova_colore(Othelliera, RigaIndex, ColonnaIndex, RigaOffset, ColonnaOffset, Colore) :-

NRigaOffset is RigaIndex + RigaOffset,

NColonnaOffset is ColonnaIndex + ColonnaOffset,

pedina(Othelliera, NRigaOffset, NColonnaOffset, Pedina),

Pedina = Colore.

trova_colore(Othelliera, RigaIndex, ColonnaIndex, RigaOffset, ColonnaOffset, Colore) :-

NRigaIndex is RigaIndex + RigaOffset,

NColonnaIndex is ColonnaIndex + ColonnaOffset,

pedina(Othelliera, NRigaIndex, NColonnaIndex, Pedina),


Pedina = ColoreAvversario,

trova_colore(Othelliera, NRigaIndex, NColonnaIndex, RigaOffset, ColonnaOffset,

Colore).

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

39

/*Trova mosse, trova le mosse legali a partire da uno stato */

trova_mosse(Othelliera, Colore, ListaMosse):-

trova_mosse(Othelliera, Colore, 0, 0, [], ListaMosse).

trova_mosse(_, _, Rigaiesima, Coljesima, ListaMosse, ListaMosse):-

numrighe(R),

numcol(C),

Rigaiesima is R-1,

Coljesima is C,!.

/*Cerca le mosse valide esaminando ad una ad una tutte le caselle andando da sinistra verso

destra per poi scendere alla riga successiva */

trova_mosse(Othelliera, Colore, RigaIndex, Coljesima, ListaMosse, ListaFinale):-

numcol(C),

Coljesima is C,

NRigaIndex is RigaIndex + 1,

trova_mosse(Othelliera, Colore, NRigaIndex, 0, ListaMosse, ListaFinale),!.

trova_mosse(Othelliera, Colore, RigaIndex, ColonnaIndex, ListaMosse, ListaFinale):-

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, DirezioneValidaOffsets),

append(ListaMosse,[[RigaIndex, ColonnaIndex, DirezioneValidaOffsets]], NMovesList),


trova_mosse(Othelliera, Colore, RigaIndex, NColonnaIndex, NMovesList, ListaFinale),!.

trova_mosse(Othelliera, Colore, RigaIndex, ColonnaIndex, ListaMosse, ListaFinale):-


trova_mosse(Othelliera, Colore, RigaIndex, NColonnaIndex, ListaMosse, ListaFinale),!.

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, DirezioneValidaOffsets):-


Pedina = empty,

direzioni_legali(Direzione),

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, Direzione, [],

DirezioneValidaOffsets).

mossa_valida(_, _, _, _, [], CorrenteDirezioneOffsetValida, DirezioneValidaOffsets):-

CorrenteDirezioneOffsetValida \= [],

CorrenteDirezioneOffsetValida = DirezioneValidaOffsets.

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, Direzione,

CorrenteDirezioneOffsetValida, DirezioneValidaOffsets):-

Direzione = [DirezioneOffset|DirezioneRest],

mossa_valida_offset(Othelliera, RigaIndex, ColonnaIndex, Colore, DirezioneOffset),

append(CorrenteDirezioneOffsetValida, [DirezioneOffset],

NCorrenteDirezioneOffsetValida),

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, DirezioneRest,

NCorrenteDirezioneOffsetValida, DirezioneValidaOffsets).

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

40

La regola trova_mosse viene invocata da diverse regole, il suo obiettivo è quello di

trovare tutte le mosse legali a partire da uno stato. La ricerca è molto simile a quella

effettuata dalla regola posizioni_valide. Si parte da 0,0 e si procede da sinistra verso

destra attraverso l’invocazione della regola ricorsiva mossa valida. Se la casella

considerata è vuota, viene invocata la regola ricorsiva mossa_valida numero 3 (riga

285 ) che controlla per ogni direzione, mediante mossa_valida_offset, se vi è una

possibile mossa legale. Mossa_valida_offset verifica che la casella adiacente sulla

direzione scelta sia occupata da una pedina avversaria, e in caso affermativo, cerca

una pedina del proprio colore sulla direzione scelta (regola trova_colore riga 236).

Qualora la regola dovesse fallire, si valuterebbe un’altra direzione selezionata tra le 8

possibili.

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, Direzione,

CorrenteDirezioneOffsetValida, DirezioneValidaOffsets):-

Direzione = [_|DirezioneRest],

mossa_valida(Othelliera, RigaIndex, ColonnaIndex, Colore, DirezioneRest,

CorrenteDirezioneOffsetValida, DirezioneValidaOffsets).

mossa_valida_offset(Othelliera, RigaIndex, ColonnaIndex, Colore, DirezioneOffset):-


Pedina = empty,

nth0(0, DirezioneOffset, RigaOffset),

nth0(1, DirezioneOffset, ColonnaOffset),

RigaDelVicino is RigaIndex + RigaOffset,

ColonnaDelVicino is ColonnaIndex + ColonnaOffset,


pedina(Othelliera, RigaDelVicino, ColonnaDelVicino, PedinaDelVicino),

PedinaDelVicino = ColoreAvversario,

trova_colore(Othelliera, RigaDelVicino, ColonnaDelVicino, RigaOffset, ColonnaOffset,

Colore).

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

/* Imposta una singola pedine e capovolge quelle avversarie */

imposta_pedina(Othelliera, Mossa, Colore, Othelliera_Dopo_Mossa):-

nth0(0, Mossa, Riga),

nth0(1, Mossa, Colonna),

nth0(2, Mossa, DirezioneValidaOffsets),

imposta_singola_pedina(Othelliera, Riga, Colonna, Colore, OthellieraConPedine),

imposta_pedine_sugli_offset(OthellieraConPedine, Riga, Colonna, Colore,

DirezioneValidaOffsets, Othelliera_Dopo_Mossa).

311

312

313

314

315

316

317

318

319

41

imposta_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, Colore,

Othelliera_Dopo_Mossa):-

mossa_valida(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, Colore,

DirezioneValidaOffsets),

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, Colore,

OthellieraConPedine),

imposta_pedine_sugli_offset(OthellieraConPedine, IndiceRigaPedina,

IndiceColonnaPedina, Colore, DirezioneValidaOffsets, Othelliera_Dopo_Mossa).

imposta_pedine_sugli_offset(Othelliera_Dopo_Mossa, _, _, _, [], Othelliera_Dopo_Mossa):-!.

imposta_pedine_sugli_offset(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, Colore,

DirezioneValidaOffsets, Othelliera_Dopo_Mossa):-

DirezioneValidaOffsets = [DirezioneOffsetValida|DirezioneValidaOffsetsRest],

imposta_pedine_su_offset(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, Colore,

DirezioneOffsetValida, OthellieraTemporanea),

imposta_pedine_sugli_offset(OthellieraTemporanea, IndiceRigaPedina,

IndiceColonnaPedina, Colore, DirezioneValidaOffsetsRest, Othelliera_Dopo_Mossa).


DirezioneOffsetValida, Othelliera_Dopo_Mossa):-

nth0(0, DirezioneOffsetValida, RigaOffset),

nth0(1, DirezioneOffsetValida, ColonnaOffset),

NRigaOffset is IndiceRigaPedina + RigaOffset,

NColonnaOffset is IndiceColonnaPedina + ColonnaOffset,


Pedina = Colore,

Othelliera = Othelliera_Dopo_Mossa,!.


DirezioneOffsetValida, Othelliera_Dopo_Mossa):-

nth0(0, DirezioneOffsetValida, RigaOffset),

nth0(1, DirezioneOffsetValida, ColonnaOffset),

NRigaOffset is IndiceRigaPedina + RigaOffset,

NColonnaOffset is IndiceColonnaPedina + ColonnaOffset,



Pedina = ColoreAvversario,

imposta_singola_pedina(Othelliera, NRigaOffset, NColonnaOffset, Colore,

OthellieraTemporanea),

imposta_pedine_su_offset(OthellieraTemporanea, NRigaOffset, NColonnaOffset, Colore,

DirezioneOffsetValida, Othelliera_Dopo_Mossa).

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, Colore,

Othelliera_Dopo_Mossa):-

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, 0, 0, Colore,

[], Othelliera_Dopo_Mossa, []).

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

339

340

341

342

343

344

345

346

347

348

349

350

351

352

353

354

355

356

357

358

359

360

361

362

363

364

365

366

367

368

42

imposta_singola_pedina(_, IndiceRigaPedina, _, Rigaiesima, Coljesima, _, OthellieraRisultante,

Othelliera_Dopo_Mossa, RigaPedina):-

numrighe(R),

numcol(C),

IndiceRigaPedina is R-1,

Rigaiesima is R-1,

Coljesima is C, append(OthellieraRisultante, [RigaPedina], Othelliera_Dopo_Mossa),!.

imposta_singola_pedina(_, _, _, Rigaiesima, 0, _, Othelliera_Dopo_Mossa,

Othelliera_Dopo_Mossa, _):-

numrighe(R),

Rigaiesima is R,!.

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceRigaColonna, IndiceRigaPedina,

Coljesima, Colore, OthellieraRisultante, Othelliera_Dopo_Mossa, RigaIndex):-

numrighe(R),

numcol(C),

Coljesima is C,

IndiceRigaPedina \= (R-1),

NIndiceRigaCorrente is IndiceRigaPedina + 1,

append(OthellieraRisultante, [RigaIndex], NOthellieraRisultante),

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceRigaColonna,

NIndiceRigaCorrente, 0, Colore, NOthellieraRisultante, Othelliera_Dopo_Mossa, []).

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, IndiceRigaPedina,

IndiceColonnaPedina, Colore, OthellieraRisultante, Othelliera_Dopo_Mossa, RigaPedina):-

append(RigaPedina, [Colore], NRigaPedina),

NIndiceColonnaCorrente is IndiceColonnaPedina + 1,

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina,

IndiceRigaPedina, NIndiceColonnaCorrente, Colore, OthellieraRisultante,

Othelliera_Dopo_Mossa, NRigaPedina).

imposta_singola_pedina(Othelliera, IndiceRigaPedina, IndiceColonnaPedina, IndiceRigaPedina,

IndiceColonnaCorrente, Colore, OthellieraRisultante, Othelliera_Dopo_Mossa, RigaPedina):-

IndiceColonnaCorrente \= IndiceColonnaPedina,

pedina(Othelliera, IndiceRigaPedina, IndiceColonnaCorrente, Pedina),

append(RigaPedina, [Pedina], NRigaPedina),

NIndiceColonnaCorrente is IndiceColonnaCorrente + 1,


IndiceRigaPedina, NIndiceColonnaCorrente, Colore, OthellieraRisultante,

Othelliera_Dopo_Mossa, NRigaPedina).


IndiceRigaCorrente, _, Colore, OthellieraRisultante, Othelliera_Dopo_Mossa, RigaPedina):-

IndiceRigaPedina \= IndiceRigaCorrente,

nth0(IndiceRigaCorrente, Othelliera, RigaCorrente),

append(OthellieraRisultante, [RigaCorrente], NOthellieraRisultante),

NIndiceRigaCorrente is IndiceRigaCorrente + 1,


NndiceRigaCorrente, 0, Colore, NOthellieraRisultante, Othelliera_Dopo_Mossa, RigaPedina).

369

370

371

372

373

374

375

376

377

378

379

380

381

382

383

384

385

386

387

388

389

390

391

392

393

394

395

396

397

398

399

400

401

402

403

404

405

406

407

408

409

410

411

412

413

414

415

416

417

418

43

La regola imposta pedina, richiama molte regole già definite, riceve la mosse e dopo

aver verificato che sia una mossa valida richiama la regola imposta_singola_pedina.

La regola imposta_singola_pedina è composta da una serie di chiamate ricorsive che

permettono di arrivare alla posizione desiderata e aggiungere la pedina all’othelliera.

Successivamente con imposta_pedine_su_offset, in base alla direzione di azione, si

vanno a “capovolgere” le pedine avversarie interessate. Il procedimento di ricerca

delle pedine da capovolgere è analogo a quello descritto in trova_mosse e

trova_posizioni.

conta_pedine(Colore,Othelliera,Pedine,PedineAvversario):-

conta_pedine(0,0,Colore,Othelliera,0,0,Pedine,PedineAvversario).

conta_pedine(Rigaiesima,Coljesima,_,_,PedineBuffer,PedineAvversarioBuf,Pedine,PedineAvver

sario):-

numrighe(R),

numcol(C),

Rigaiesima is R-1,

Coljesima is C,

Pedine = PedineBuffer,

PedineAvversario is PedineAvversarioBuf,

!.

conta_pedine(Rigaiesima,Coljesima,Colore,Othelliera,PedineBuffer,PedineAvversarioBuf,Pedine

,PedineAvversario):-

numcol(C),

colore_avversario(Colore,ColoreAvversario),

(

Coljesima=C ->


NColjesima is 0,

NPedineBuffer is PedineBuffer,

NPedineAvversarioBuf is PedineAvversarioBuf

;



pedina(Othelliera, Rigaiesima, Coljesima, Pedina),

( Pedina = Colore ->

NPedineBuffer is PedineBuffer+1,


;

Pedina = ColoreAvversario ->


NPedineAvversarioBuf is PedineAvversarioBuf +1

419

420

421

422

423

424

425

426

427

428

429

430

431

432

433

434

435

436

437

438

439

440

441

442

443

444

445

446

447

448

449

450

451

452

44

La regola conta_pedine a partire da 0,0 si muove sull’othelliera esaminando tutte le

caselle da sinistra a destra, e mediante la chiamata ricorsiva conta_pedine numero 3,

conta il numero di pedine possedute da un giocatore e dall’avversario(righe 446-

455). Sono state poi definite dalla riga 462 alla riga 483 alcune regole standard di

utilità che vengono richiamate dalle altre regole.

;



)

),

conta_pedine(NRigaiesima,NColjesima,Colore,Othelliera,NPedineBuffer,NPedineAvversarioBuf

,Pedine,PedineAvversario).

for(V,V,_,_) :- !.

for(Inzio,Fine,Inc,Azione) :-

Fine > Inzio,

NuovoValore is Inzio+Inc,

call(Azione),

for(NuovoValore,Fine,Inc,Azione).

primi_elementi([], ListaOthelliere, ListaOthelliere):-!.

primi_elementi([Primo|Rest], Temp, Othelliere):-

nth0(0, Primo, Othelliera),

append(Temp, [Othelliera], NTemp),

primi_elementi(Rest, NTemp, Othelliere).

min_list([Primo|Rest], Min):-

min_list_aux(Rest, Primo, Min).

min_list_aux([], Min, Min):-!.

min_list_aux([Primo|Rest], MinCorrente, Min):-

Primo < MinCorrente,

min_list_aux(Rest, Primo, Min),!.

min_list_aux([_|Rest], MinCorrente, Min):-

min_list_aux(Rest, MinCorrente, Min),!.

max_list([Primo|Rest], Max):-

max_list_aux(Rest, Primo, Max).

max_list_aux([], Max, Max):-!.

max_list_aux([Primo|Rest], MaxCorrente, Max):-

Primo > MaxCorrente,

max_list_aux(Rest, Primo, Max),!.

max_list_aux([_|Rest], MaxCorrente, Max):-

max_list_aux(Rest, MaxCorrente, Max),!.

max(A,B,Max):-

A >= B->

Max=A

;

Max=B.

453

454

455

456

457

458

459

460

461

462

463

464

465

466

467

468

469

470

471

472

473

474

475

476

477

478

479

480

487

482

483

45

Bibliografia

[1] wiki backgammon, https://it.wikipedia.org/wiki/Regole_del_backgammon

[2] Federazione italiana gioco go, http://www.figg.org/

[3] Stuart Russell, Peter Norvig, Artificial intelligence: a modern approach,

Prentice Hall.

[4] Claude E. Shannon, Programming a computer for playing chess,

Philosophical Magazine, Ser.7, Vol. 41, No. 314 - March 1950

[5] Documentazione ufficiale prolog, http://www.swi-prolog.org/pldoc/index.html

[6] Shell swi-prolog, http://www.swi-prolog.org/Download.html

[7] Federazione nazionale gioco othello, http://www.fngo.it/regole.asp

intelligenza artificiale - Facoltà di · PDF fileGli studiosi di intelligenza...

Documents

Transcript of intelligenza artificiale - Facoltà di · PDF fileGli studiosi di intelligenza...