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 - Strutture dati ed implementazione in Prolog 3
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 - Strutture dati ed implementazione in Prolog 4
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 - Strutture dati ed implementazione in Prolog 5
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.
Othello - Strutture dati ed implementazione in Prolog 6
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)]
Othello - Strutture dati ed implementazione in Prolog 7
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.
Othello - Strutture dati ed implementazione in Prolog 8
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)
Othello - Strutture dati ed implementazione in Prolog 9
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)
Othello - Strutture dati ed implementazione in Prolog 10
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)
Othello - Strutture dati ed implementazione in Prolog 11
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
Othello - Strutture dati ed implementazione in Prolog 12
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:
Othello - Strutture dati ed implementazione in Prolog 13
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
Othello - Strutture dati ed implementazione in Prolog 14
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
Othello - Strutture dati ed implementazione in Prolog 15
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.
Othello - Strutture dati ed implementazione in Prolog 16
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).
Othello - Strutture dati ed implementazione in Prolog 17
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
Othello - Strutture dati ed implementazione in Prolog 18
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
Othello - Strutture dati ed implementazione in Prolog 19
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.
Othello - Strutture dati ed implementazione in Prolog 20
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
Othello - Strutture dati ed implementazione in Prolog 21
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.
Othello - Strutture dati ed implementazione in Prolog 22
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)
Othello - Strutture dati ed implementazione in Prolog 23
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.
Othello - Strutture dati ed implementazione in Prolog 24
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
Othello - Strutture dati ed implementazione in Prolog 25
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
Othello - Strutture dati ed implementazione in Prolog 26
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.
Othello - Strutture dati ed implementazione in Prolog 27
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.
Othello - Strutture dati ed implementazione in Prolog 28
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).
Othello - Strutture dati ed implementazione in Prolog 29
Riferimenti
http://www.fngo.it Federazione Nazionale Gioco Othello
Prothello (Prolog Othello), M.Purtonen, M.Komu, Jan 2003