Articolo pubblicato sul n. 7 di
MCmicrocomputer
(Edizioni Technimedia Srl - Roma) nel marzo 1982

NB: questo è il mio primo articolo... :-)
Othello
con il computer
di
Silvio Cavalcanti e
Andrea de Prisco

Tutti sappiamo che i compiti che un elaboratore può svolgere
sono innumerevoli, ed i suoi campi di applicazione,
diversissimi, sono limitati praticamente solo dalla fantasia
e dall'ingegno dei programmatori. Una delle applicazioni più
interessanti
è senza dubbio la simulazione di uno dei
contendenti di un gioco a due persone: i programmi di questo
tipo sono purtroppo tra i pili difficili da stendere, e
mettono a dura prova la perizia di chi ricerca gli algoritmi
e ne cura l'applicazione. Una volta presi dal fascino di
questa programmazione, però, si può rimanere piacevolmente
occupati per mesi nella stesura di versioni sempre più
perfette di uno stesso gioco.
Con questo articolo ci proponiamo di avvicinare il lettore
verso questo genere di programmi,
che rappresenta per molti
possessori di elaboratori un campo assai ricco di nuove
possibili esperienze.
Giochi a due persone famosissimi come gli scacchi e la dama
sono oggetto di programmazione da quando sono nati i
computer, e anche da prima: e nota infatti l'esistenza di
più o meno funzionanti macchine create per questi giochi in
tempi in cui l'unica automazione possibile era quella degli
ingranaggi da orologeria. Oggi i discendenti di quei
congegni, favoriti dai bassi prezzi dei microprocessori,
stanno entrando prepotentemente nelle nostre case sotto
l'aspetto di scatolette intelligenti capaci di intrattenerci
piacevolmente con discreti livelli di gioco.
E però sconsigliabile accostarsi per la prima volta a questo
affascinante settore con giochi complessi come gli scacchi,
che per essere ben giocati richiedono un lungo apprendistato
anche ad un cervello umano. Per le nostre applicazioni
useremo quindi un gioco forse non molto diffuso in Italia ma
avvincente, intelligente e nello stesso tempo semplice nelle
sue poche regole: l'Othello. II nostro scopo, come spiegato
in altra parte dell'articolo, è quello di spingervi alla
realizzazione di vostri programmi di gioco: per fare ciò ci
limiteremo a darvi dei suggerimenti e a presentare un
programma di esempio, molto semplice e "poco intelligente";
e tanto per mostrare che non c'e bisogno di un particolare
hardware ne riporteremo le versioni per due macchine
particolarmente diffuse, e profondamente diverse: l'Apple II
e la Texas TI-59. Naturalmente prima di fare ciò converrà
introdurre il gioco e le sue regole, a vantaggio di chi
ancora non lo conosce.
Il
gioco
L'Othello, a differenza dei più diffusi giochi a due
persone, non è molto antico: è stato messo in commercio una
decina d'anni fa su un brevetto giapponese. In verità, però,
e praticamente identico al Reversi, un gioco molto popolare
nel secolo scorso in Inghilterra, dal quale differisce solo
per la rigida posizione di partenza, che e solo una tra le
molte possibili del Reversi. II gioco si
svolge
su una scacchiera 8 per 8 generalmente verde o comunque di
un colore uniforme diverso dal bianco e dal nero, colori
destinati alle pedine. Queste, contrariamente a quelle della
dama, hanno una faccia bianca ed una nera. Nell'Othello
infatti i pezzi appartengono all'uno o all'altro giocatore a
seconda del colore della faccia superiore, e nel corso del
gioco possono venire ribaltate in modo da cambiare colore e
quindi ruolo; il numero totale di pedine è 64, quanto serve
per ricoprire completamente la scacchiera.
Per avere una notazione rigorosa delle mosse possiamo usare
una notazione simile a quella degli scacchi: colonne da A ad
H (da sinistra a destra) e righe da 1 a 8 (dal basso verso
l'alto). AII'inizio della partita si dispongono due pedine
bianche e due nere nelle caselle centrali del campo, come
illustrato in figura 1; la prima mossa è sempre del
nero.
II gioco consiste nel porre in campo, alternativamente, una
pedina col proprio colore rivolto verso l'alto, facendo sì
che questa catturi almeno una pedina avversaria (di colore
opposto). La presa avviene quando la pedina appena posata
chiude, lungo le direzioni uscenti dalla sua casella
(verticali orizzontali e diagonali), una o più pedine
avversarie fra se e una delle pedine del proprio colore che
già si trovavamo sul campo. Ancora più semplicemente: la
pedina deve essere posta sulla scacchiera in modo da
formare, anche su più direzioni, delle file continue di una
o più pedine avversarie terminanti ai due estremi con una o
più pedine proprie, di cui una deve essere quella appena
giocata. Le pedine avversarie cosi racchiuse e quindi
mangiate vengono capovolte, assumendo il colore del
mangiante. La cattura di almeno una pedina avversaria è una
condizione necessaria per poter eseguire la mossa: se il
giocatore che deve muovere non può mangiare nessuna pedina
salta il turno, e continua a farlo finché non gli sia
nuovamente possibile una mossa con cattura.
Regole tanto semplici possono forse apparire complesse se
spiegate a parole senza esempi concreti, ma uno sguardo
attento al diagramma di figura 2 sarà certamente
sufficiente a fugare ogni dubbio. La vittoria spetterà al
concorrente che a fine gioco, quando cioè tutto il campo
sarà riempito, avrà più pedine del proprio colore sulla
scacchiera. Ripetiamo che la mossa può essere effettuata
solo se e possibile mangiare almeno una pedina avversaria,
ed in questa caso è obbligatoria; deve invece essere ceduta
all'avversario in caso contrario. Se anche lui e
impossibilitato a muovere la partita termina prima che tutta
la scacchiera sia riempita, e la vittoria va, come sempre,
al concorrente rappresentato dal maggior numero di pedine in
campo.

Come già accennato, in questa articolo porremo soltanto le
basi generali del gioco, e non entreremo nel dettaglio delle
varie strategie possibili, per non limitare la fantasia di
chi volesse eventualmente aderire al nostro invito a
cimentarsi nella scrittura di un proprio programma.
Riteniamo comunque doveroso introdurre alcuni elementari
comportamenti di gioco, senza conoscere i quali non è
possibile competere neanche con giocatori poco esperti. E’
sufficiente giocare pochissime partite per capire che
durante le fasi iniziali è inutile affannarsi alla ricerca
della mossa che faccia conquistare più pedine avversarie,
mentre è molto proficuo cercare di guadagnare le caselle
strategicamente più favorevoli: le posizioni più forti, ad
esempio, sono i quattro angoli della scacchiera, in quanto
una volta conquistati non possono più venire ripresi
dall'avversario. Da essi inoltre si può partire per la
conquista definitiva dei bordi del campo: altre posizioni
molto forti strategicamente. Una pedina sui bordo può venire
catturata esclusivamente dal bordo
o
dall'angolo. Se l'avversario è valido cercherà, a sua volta,
di conquistare angoli e bordi; quindi altro compito di un
buon programma è di opporsi a che ciò avvenga con facilità.
Alla luce di quanta detto si intuisce subito che le caselle
sono più o meno buone a seconda che facciano conquistare
all'avversario posizioni negative o positive. Esempio tipico
di posizione negativa è quello della casella adiacente in
diagonale all'angolo, presa la quale diventa molto difficile
impedire all'avversario di conquistare l'angolo.
Da tutte queste parole si può estrarre subito un algoritmo
che faccia dipendere la scelta della mossa da una tabella di
valori delle singole caselle, sul tipo di quella in
figura 3; e volendo fare le cose più sofisticate la si
potrebbe rendere dinamica, ossia far variare i coefficienti
in funzione dello svolgimento del gioco e del riempimento
della scacchiera. Infatti nelle ultime mosse della partita,
quando il campo sta per riempirsi, è necessario ricordarsi
che il fine del gioco e quello di avere sulla scacchiera più
pedine dell'avversario, e quindi bisogna cercare di
capovolgere più pezzi possibile tentando di minimizzare le
prese dell'avversario nelle mosse successive.
Queste poche notizie non sono che un cenno di tutte le
finezze dell'Othello, che come per ogni altro gioco a due
persone si possono apprendere solo per esperienza diretta.
Chi volesse programmare un Othello è pertanto vivamente
consigliato di giocare qualche partita contro un buon
avversario umano, per constatare direttamente quali e quante
sottili strategie si possano escogitare e mutare nel corso
del gioco, e di quanto la sorte sia alterna fino alle
ultimissime fasi della partita. Sorge perciò I'arduo
problema, che giriamo ai lettori, di studiare una opportuna
funzione di valutazione che metta in grado il programma di
selezionare in modo pseudo-intelligente quella, tra le mosse
valide, più opportuna in un dato contesto di gioco.
L’Othello sugli elaboratori
II gioco, anche se a diversi livelli, può essere programmato
su tutti gli elaboratori, comprese le calcolatrici
programmabili. Per queste ultime però, date le modeste
capacità di memoria e soprattutto le basse velocità di
elaborazione, proponiamo di sviluppare il gioco su di una
scacchiera 6 per 6 anziché 8 per 8; questa limitazione non
toglie nulla alla logica della programmazione ed evita il
protrarsi delle partite oltre limiti ragionevoli, anche se
si perde un po' dell'agonismo della versione originale.
Prima pera di occuparsi di far giocare i vostri elaboratori
ad Othello, introduciamo il concetto di livello di gioco,
altrimenti detto "forecast level" (livello di previsione).
Chi, macchina o uomo che sia, nel giocare ricerca la mossa
migliore valutando semplicemente la immediata situazione
della scacchiera gioca al primo livello, il più elementare.
Giocare al secondo livello vuol dire che per ogni mossa
possibile si esaminano tutte le possibili risposte
dell'avversario, e si sceglie quindi la propria mossa in
modo da non concedere molte chance di buoni colpi-risposta
al nemico. Al terzo livello si gioca quella mossa che,
supponendo un'intelligente risposta dell'avversario, prepari
il campo per il colpo successivo; e cosi via per gli altri
livelli di previsione. La vostra programmabile giocherà
quasi certamente al primo livello, dati gli ovvi limiti di
memoria e velocità: chi ha invece a disposizione un
personal, qualcosina di più la potrà fare.
Detto ciò passiamo a dettagli un po' più operativi. Per far
giocare un calcolatore ad Othello è necessario dargli una
scacchiera e le pedine, bianche e nere: la scacchiera sarà
costituita da un certo insieme di variabili, mentre le
pedine saranno opportuni valori da inserire nelle stesse.
Come già accennato per le programmabili useremo il formato 6
per 6, per i personal l'8 per 8; quale insieme di variabili
per simulare la scacchiera consigliamo di usare un vettore (array
ad un solo indice): dovendo infatti analizzare tutte le
caselle sarà bene non complicarsi troppo la vita con piu
indici.

In figura 4a vediamo la rappresentazione della
scacchiera standard; le caselle 0, 9, 18, ... , 63 sono di
"bordo", ossia servono per far capire al computer se due
caselle sono o non so no sulla stessa riga. Tutto questo
perché la scacchiera all'interno del calcolatore non e che
un lungo vettore (figura 4b). Lo stesso discorso, con
ovvie modifiche, va ripetuto per il formato 6 per 6. In
entrambi i casi il nostro consiglio è di porre nelle caselle
vuote il valore zero e nei bordi il valore 1,
contrassegnando poi le caselle proprie col valore -2 e
quelle dell'avversario col valore -1. Questa scelta per le
pedine non è del tutto a caso: infatti questi valori
risultano abbastanza comodi per capovolgere Ie pedine
conquistate. La semplice istruzione di assegnazione:
contenuto casella = (-3) - contenuto casella
restituisce per l'appunto la pedina capovolta, come è facile
verificare. Basta applicare la formula a tutte le pedine da
voltare ed il gioco è fatto.
Data cosi una semplice idea della rappresentazione della
scacchiera passiamo alla ricerca delle possibili mosse. Non
ha molta importanza da quale casella incominciare, tanto
bene o male bisogna analizzarle tutte. Cominciamo ad esempio
da quella in basso a destra, la numero 71 (041 nella
scacchiera 6 per 6). Potendo giocare la nostra pedina solo
dove non ve ne siano altre, e tantomeno sui "bordi",
analizzeremo solo le caselle vuote, ossia quelle che
contengono zero. Di ogni posizione utilizzabile dobbiamo
vedere se nelle otto direzioni principali (Nord, Est, Sud,
Ovest, NE, SE, SO, NO) sia possibile conquistare pedine; a
tal fine, lo ricordiamo, è necessario che una o più pedine
avversarie siano comprese tra due o più pedine proprie, di
cui una già sulla scacchiera e una appena posata. Per
effettuare questa ricerca basta cominciare in una qualsiasi
direzione, controllando se nella casella c'e una pedina
avversaria: se non c'è si deve cambiare direzione (e al
termine delle direzioni cambiare casella), se invece c'è si
pro segue nella stessa direzione, controllando il contenuto
di ogni casella col seguente algoritmo:
si presentano tre casi:
a) Nella casella c'e un'altra pedina avversaria: allora si
prosegue nella stessa direzione.
b) Siamo usciti fuori dalla scacchiera o siamo capitati sul
bordo, o la casella esaminata è vuota: in questo caso non è
possibile mangiare, e allora si cambia direzione (o casella,
se tutte e otto le direzioni sono state esaminate).
c) E’ presente una pedina propria: è pertanto possibile
catturare tutte le pedine avversarie comprese fra la casella
analizzata per ultima e quella da cui si è partiti; si
prosegue poi la ricerca nelle restanti direzioni per
controllare se sia possibile conquistare qualche altra
pedina con la stessa mossa.
Resta
il problema di come effettuare la ricerca nelle otto
direzioni. Dando un'occhiata alla scacchiera 8 per 8 (figura
4a), noterete che, considerata una qualunque casella, ad
es. la 40, quelle adiacenti ad essa nelle otto direzioni
sono contraddistinte dai numeri: 30, 31, 32, 41, 50, 49, 48,
39; ossia 40-10, 40-9, 40-8, 40+1, 40+10, 40+9, 40+8, 40-1.
In altre parole, aggiungendo ripetutamente al val ore 40 il
valore + 8, ottenendo via via 48, 56, 64, si percorre la
direzione sud-est; un discorso analogo, con diverse
costanti, vale per le restanti direzioni. Lo schema è
riportato in figura 5; per la scacchiera 6 per 6
cambiano le costanti ma non il principio. In entrambi i casi
bisognerà stare attenti a non uscire dalla scacchiera
durante la ricerca. Il programma di esempio che vi
presentiamo, nelle versioni per Apple II e TI-59, esegue
questo test per tutte le caselle della scacchiera, e gioca
infine la mossa che conquista più pedine. Abbiamo già detto
che questa non è sempre la strategia preferibile, ed infatti
questo programma non è certo il migliore; anzi, batterlo non
è difficile. Non vogliamo però dirvi altro: il nostro scopo
non è quello di darvi un programma ma di farvelo fare,
dandovi il maggior numero di consigli.
Il programma
Per concludere diamo un breve sguardo al nostro programmino.
Bisogna subito dire che sulla 59, nonostante la riduzione
del numero di caselle, il gioco non è molto veloce (dai 3 ai
5 minuti per mossa), e ciò non solo a causa della bassa
velocità di elaborazione ma anche per la complessità del
programma, caratterizzato da numerosissimi salti e
confronti.
I due programmi fanno ne più ne meno ciò che è stato finora
descritto a parole: il diagramma di flusso è in figura 6.

Si entra dal punto K se gioca per prima la macchina, dal
punto A altrimenti. Sulla 59 si deve innanzitutto premere E
per inizializzare la scacchiera, poi si preme RST R/S per
far giocare prima lei, altrimenti si imposta la propria
mossa e si preme A. Ricordiamo che la numerazione delle
caselle è differente nel caso 6 per 6 da quello 8 per 8, e
che per passare si gioca nella casella 0.
Entrambi i programmi sfruttano la stessa subroutine (W nel
flow-chart) per ricercare le mosse e capovolgere le pedine:
lo stato del flag 1 (la variabile logica F nella versione
BASIC) indica quale delle due funzioni viene svolta.
Ripetiamo che questo programma è solo di esempio, e manca di
molte funzioni accessorie: ad esempio non controlla la
validità delle mosse dell'avversario, e non si accorge della
fine della partita. L'importante però è che chiarisca il
meccanismo di gioco (anzi, uno dei tanti meccanismi
possibili), e non è difficile abbellirlo e completarlo un
tantino.
Conclusione
Con questo articolo speriamo di aver suscitato il vostro
interesse verso I'Othello e I'intelligenza artificiale.
Crediamo di aver mostrato chiaramente come, con un po' di
pazienza, sia possibile insegnare ad un computer a fare
qualcosa di tipicamente umano: giocare. Va anche detto che
il programma-giochetto, ben noto specialmente ai piccoli
informatici in virtù della sua onnipresenza sui manuali
delle programmabili, ha un alto valore didattico sia perché
non deve necessariamente essere una banalità, sia perché
psicologicamente dà molta soddisfazione giocare contro un
proprio programma: se vince la macchina si ha il merito di
aver sviluppato un buon algoritmo di gioco, se vince il
programmatore si ha la soddisfazione di non essersi lasciati
fregare da una scatolina ignorante e presuntuosa ...
A questa punto vi lasciamo ai vostri computer: buon lavoro,
e non mancate di farci conoscere i risultati.
Impaginato
originale...
Articolo pubblicato
su
www.digiTANTO.it - per ulteriori informazioni
clicca qui
|