Othello con il computer

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.