Othello Strutture dati ed implementazione in prolog Approfondimento per il corso di Linguaggi Logici...

OthelloStrutture dati ed implementazione in prolog

Approfondimento per il corso di Linguaggi Logici A.A. 2006/07

Cappellazzo Pietro

Carminati Roberto

Othello - Strutture dati ed implementazione in Prolog 2

Othello: Le Regole

Othello si gioca in due, su una scacchiera 8x8, con 64 pedine bicolori. Un giocatore ha il Nero, l'avversario il Bianco.

La disposizione iniziale delle pedine sulla scacchiera è rappresentata in figura, inizia a giocare il Nero.

Le “x” in figura rappresentano le mosse possibili.


Othello: Le Regole

Al suo turno ogni giocatore poggia una pedina, con la faccia del proprio colore rivolta verso l'alto, su una casella ancora vuota.

Una pedina imprigiona quelle avversarie in una o più direzioni (orizzontale, verticale e/o diagonale), rendendo le pedine imprigionate del proprio colore (ovvero capovolgendole).


Othello: Le Regole

Il giocatore, al suo turno, è obbligato a giocare appoggiando una pedina in modo da imprigionare almeno un disco avversario.

ESEMPIO: posizionando la pedina nera in b-4(“x” in figura), si girerà solo la pedina bianca in c-4.


Othello: Le Regole

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

Nonostante la sua apparente semplicità, la complessità dell'Othello è elevatissima, superiore a quella della dama e poco inferiore a quella degli scacchi.


Implementazione: Strutture dati

Inizialmente è stata definita la scacchiera, come una lista di triple.

Ogni tripla (X,Y,V) è composta dalle coordinate X,Y e dal valore della casella.

La tavola vuota sarà quindi rappresentata come: [(1,1,0),(2,1,0),(3,1,0),…,(8,1,0),(1,2,0),…,(8,8,0)]


Implementazione: Strutture dati

I valori Assegnati ad ogni casella possono essere: 0 Casella Vuota 1 Casella con pedina Nera 2 Casella con pedina Bianca

Le future operazioni di modifica del valore, l’unica modifica che sarà effettuata sulla struttura dati, una volta inizializzata,non influenzeranno l’ordine della lista.


Implementazione:Rappresentazione grafica La scacchiera viene stampata a

video come vediamo in figura

I punti rappresentano caselle vuote (0)

x e o rappresentano rispettivamente la presenza di una pedina nera (1) oppure bianca (2)

(6,8,0)

(5,8,2)

(4,8,1)


Implementazione: Inizializzazione Inizialmente viene generata la

scacchiera: Lista di 64 terne (X,Y,Val), ordinate

per righe Val viene posto a 0, casella vuota

Vengono quindi posizionate le pedine iniziali Nelle coordinate d-4 e e-5 vengono

posizionate le pedine nere (4,4,0)(4,4,1) (5,5,0)(5,5,1)

in d-5 ed e-4 quelle bianche (4,5,0)(4,5,2) (5,4,0)(5,4,2)


Implementazione: Turno del giocatore A questo punto inizia il gioco vero e proprio, la

prima mossa spetta al giocatore con le pedine nere (umano): Viene disegnato il tavolo attuale Si controlla se il giocatore può muovere Si richiede la mossa in input Se la mossa inserita è corretta si esegue, altrimenti

si ritorna al punto precedente Si passa il turno al giocatore che controlla le pedine

bianche (computer oppure umano)


Implementazione:Controllo Disponibilità mosse Per controllare se sono disponibili mosse:

Comincio a considerare le mosse a partire dalla casella con coordinate a-1.

Se la mossa è valida viene inserita tra le clausole del programma, altrimenti viene ignorata.

Continua con le casella a-2,a-3,...,a-8,b-1,…,h-8 se trova una mossa disponibile la aggiunge

Se giunti alla casella h-8, non ci sono mosse disponibili, siamo sicuri che il giocatore non può muovere (il turno passa all’avversario)

Altrimenti, se sono disponibili mosse, ne viene richiesta una in input


Implementazione:Esecuzione di una mossa Per eseguire una mossa:

Posiziono la pedina sulla scacchiera Comincio dal basso e giro le caselle del colore

opposto contenute fra la pedina posizionata ed un’altra dello stesso colore

Continuo in tutte le altre direzioni in questo ordine:


Implementazione:Esecuzione di una mossa Se la scacchiera non è cambiata dopo queste

operazioni (la lista risultante è uguale a quella di partenza), allora la mossa effettuata non è valida:

Se la mossa non è valida lo segnalo e chiedo una nuova mossa in input

Altrimenti passo il turno al prossimo giocatore


Implementazione: Turno del compuer A questo punto nel caso in cui la mossa passi al

computer (modalità singolo giocatore):

Viene disegnato il tavolo Si controlla se il computer può muovere Si decide quale mossa effettuare Si esegue la mossa Si passa il turno al giocatore che controlla le pedine

nere


Implementazione:Scelta della mossa Il computer non sceglie la mossa da effettuare in

modo casuale, ma effettua la giocata che farà capovolgere più pedine avversarie:

La scelta, avviene simulando tutte le mosse disponibili.

A seconda del livello di difficoltà la simulazione procede per 1, 3 oppure 5 turni.


Implementazione:Simulazione mosse La mossa da effettuare viene scelta simulando tutte le combinazioni

possibili per 1,3 oppure 5 turni:

Vengono generate tutte le mosse valide possibili Con un turno al massimo 64 Con tre turni 643

Con cinque turni 645

Ad ogni mossa viene assegnato un punteggio, corrispondente al numero di pedine avversarie girate

Viene selezionata la mossa che porta al punteggio maggiore

Se due mosse diverse portano allo stesso punteggio viene selezionata la prima rilevata, la visita della scacchiera avviene sempre in ordine (a-1,a-2,…a-8,b-1,…,h-8).


Un esempio di utilizzo:human vs computer Simuliamo uno spezzone di partita, per far

meglio capire come vengono gestite le varie fasi di gioco:

E’ il turno del giocatore: Viene disegnato il tavolo attuale


Un esempio di utilizzo:turno del giocatore Viene selezionata la clausola di programmapossibile_muovere(ColorePedina,Tavolo)che verifica se esiste almeno una mossa valida nel tavolo per il giocatore, selezionando a sua volta:genera_possibili_mosse(X,Y,CPedina,Tavolo)

che a partire dalla casella a-1 verifica se la mossa attuale è valida:

se lo è la inserisco tra le clausole di programma utilizzando asserta(possibile_mossa(X,Y,ColorePedina)

altrimenti continua senza inserire


Un esempio di utilizzo:turno del giocatore Quando abbiamo analizzato tutta la scacchiera

controlliamo se abbiamo generato delle mosse. In questo esempio sono disponibili le seguenti mosse:

c-2, c-3, c-4, d-2, g-2, g-3, h-4.


Un esempio di utilizzo:turno del giocatore Verificata la disponibilità di mosse, il programma ne richiede in input

una al giocatore, che inserirà la mossa, in questo caso: c-4 (fig 1).

L’input viene letto, e viene selezionata la clausola esegui_mossa(X,Y,CPedina,Tavolo,TavoloNew)questa:

inserisce la pedina sulla scacchiera (fig 2) capovolge le pedine avversarie racchiuse tra la pedina appena poggiata

e le altre già presenti nella scacchiera (fig 3).

Fig.1 Fig.2 Fig.3


Un esempio di utilizzo:turno del computer A questo punto è il computer che deve muovere. I primi

passi sono identici a quelli effettuati per il giocatore umano: disegno del tavolo e verifica dell’esistenza di almeno una mossa.


Un esempio di utilizzo:turno del computer In questo caso non viene richiesto un input, ma viene lanciata la

clausola simula(X,Y,CPedina,Livello,Lista), questa: valuta ogni possibile mossa valida, in questo esempio, ipotizziamo che

sia stato selezionato il livello di difficoltà normale, quindi la simulazione continuerà per 3 turni.

Saranno prese in considerazione (incluse fra le clausole di programma) man mano solo le mosse che incrementano il punteggio; vengono generate tutte le mosse a partire da b-4,b-5,b-7,d-6,f-5 (le

mosse disponibili appena riscontrate) vengono simulate le risposte del giocatore umano e nuovamente, le future mosse del computer In totale vengono valutate circa 53 mosse (supponendo di trovare circa 5

mosse valide per ogni combinazione)


Un esempio di utilizzo:turno del computer Arrivati al terzo turno,ogni volta che viene

generata una mossa: Se è la prima, oppure ha punteggio maggiore rispetto

all’ultima inserita, viene inserita tra le clausole di programma,

altrimenti viene ignorata.

La mossa che alla fine viene selezionata,sarà la prima mossa rilevata che porta al massimo punteggio (caselle avversarie girate), in quanto le altre che portano allo stesso punteggio vengono ignorate.


Un esempio di utilizzo:turno del computer

• In questo esempio vediamo come alla mossa b-4 viene temporaneamente assegnato il punteggio 2 (dato dalla mossa b-7 del terzo turno)

• Questo punteggio non è definitivo in quanto devono ancora essere controllate tutte le possibili risposte simulate (in verde)

I Turno

Mosse valutate: 5

II Turno – Mosse ≈ 52 III Turno – Mosse ≈ 53


Un esempio di utilizzo:turno del computer In questo caso il computer sceglie come risposta

b-4, in quanto porta anche dopo tre turni ad aver girato più caselle avversarie possibile.

La mossa viene quindi eseguita, esattamente come accadeva nel turno del giocatore


Sviluppi futuri

Implementare algoritmi di intelligenza artificiale più efficienti Non è stata posta attenzione alla maggiore

importanza che hanno le caselle sugli angoli che una volta acquisite non possono più essere capovolte dall’avversario.

Un altro stratagemma utilizzato dai giocatori professionisti è quello di massimizzare le mosse a propria disposizione e, contemporaneamente, minimizzare il numero delle mosse a disposizione dell'avversario.


Sviluppi futuri

Nella nostra implementazione prima che un giocatore effettui la proprio mossa, il programma controlla l’esistenza di tutte le mosse disponibili. Si può sfruttare questa ricerca per visualizzare in tempo reale

tali mosse (facilitando anche il gioco). Si possono escludere in modo automatico le mosse non valide

digitate dal giocatore.


Conclusioni

Utilizzare la programmazione logica rende semplice l’implementazione di giochi logici e la relativa intelligenza artificiale.

Dal punto di vista prestazionale però si incontrano dei problemi; questo è dovuto al fatto che il prolog interpreta il codice, che quindi non viene ottimizzato (alto uso della memoria e cpu).


Riferimenti

http://www.fngo.it Federazione Nazionale Gioco Othello

Prothello (Prolog Othello), M.Purtonen, M.Komu, Jan 2003

Othello Strutture dati ed implementazione in prolog Approfondimento per il corso di Linguaggi Logici...

Documents

Transcript of Othello Strutture dati ed implementazione in prolog Approfondimento per il corso di Linguaggi Logici...