Othello e Reversi
13/05/2008

Lo scopo di questa serie di interventi è quello di illustrare e analizzare il livello raggiunto dai programmi per computer in una serie di popolari giochi.

L’Othello è un gioco astratto a informazione perfetta per due giocatori. E'stato brevettato nel 1971 dal giapponese Goro Hasegawa, ma Lewis Waterman già nel 1880 aveva ideato un gioco simile, conosciuto come Reversi. I due giochi sono differenti solo per la situazione iniziale, con la “scacchiera” vuota per il Reversi e inizializzata con quattro pedine per l’Othello.
Ogni giocatore dispone di 32 dischi bicolori (neri da un lato, bianchi dall’altro) e lo spazio del gioco è costituito da una tavola quadrata di otto per otto caselle monocolore. Si muove alternativamente (inizia il nero) posizionando una nuova pedina in una casella vuota in modo da imprigionare, tra la pedina che si sta giocando e quelle del proprio colore già presenti sulla scacchiera, una o pù pedine avversarie. A questo punto le pedine imprigionate vengono girate e cambiano colore. Sono ammesse solo le mosse con le quali si gira almeno una pedina, se non è possibile farlo si salta il turno. Quando nessuno dei giocatori ha la possibiltà di muovere (quasi sempre accade quando la scacchiera è piena), si contano le pedine e chi ne ha il maggior numero vince. Ogni anno dal 1971 si disputano campionati nazionali e i campionati del mondo a cui partecipano oltre trenta nazioni. La diffusione e l’organizzazione dell’Othello e del Reversi è in Italia affidata a FNGO (Federazione Nazionale Gioco Othello) mentre a livello mondiale opera la WOF (World Othello Federation). Il ranking dei migliori giocatori del mondo è di solito dominato dai giapponesi ed in generale dagli asiatici, con l’eccezione di un giocatore americano al sesto posto. Attualmente due italiani, Michele Borassi ed Andrea Silvola ed un giocatore francese occupano le posizioni 18, 19, 20 della classifica mondiale, primi giocatori europei della classifica.
Le regole sono molto semplici, ma il gioco è molto complesso e può essere padroneggiato solo con lungo impegno. Per il Reversi, il numero di posizioni legalmente raggiungibili (state-space complexity) è circa 10 alla 28, mentre il numero di possibili partite che possono essere giocate (game tree size) è circa 10 alla 58. Il gioco è stato completamente risolto per scacchiere 4x4 e 6x6 e si è dimostrata una vittoria per il secondo giocatore (il Bianco). Nel gioco tradizionale su una scacchiera 8x8 i programmi stannno dimostrando empiricamente che probabilmente a gioco corretto il gioco è patto. Si ipotizza che su scacchiere ancora più grandi potrebbero aumentare le chanche del primo giocatore (il Nero).

Giocatori di silicio

Già da molti anni i migliori software battono facilmente i migliori giocatori umani; nel 1980 il programma The Moor battè il campione del mondo, mentre nel 1997 il programma Logistello sconfisse il campione giapponese Takeshi Murakami (campione del mondo nel 1996, 1998 e 2000) con il punteggio di 6 a 0. Anche per i migliori giocatori umani è molto difficile visualizzare lunghe sequenze di pedine che cambiano colore, mentre in questo i programmi non hanno problemi ad arrivare fino alle venti mosse nel mediogico e trenta in finale. Inoltre, rispetto agli scacchi anche le funzioni di valutazioni sono molto più sofisticate, essendo basate su configurazioni di pedine e su pattern di riconoscimento, e utilizzando milioni di parametri numerici che sono ottenuti anche con tecniche di regressione lineare.
Per la ricerca delle mosse vengono usate molte delle tecniche utilizzati anche per i programmi scacchistici (e per molti altri giochi, in realtà) come l’alpha-beta pruning, come la tecnica della “risposta killer”, le tavole di trasposizione… Per la funzione di valutazione, si è visto dalla pratica dei migliori giocatori umani che due concetti molto importanti sono la mobilità (il numero di mosse disponibili) e la minimizzazione delle pedine di confine (e cioè adiacenti a case vuote). La conseguenza paradossale di queste due strategie e che nel primo mediogioco è assolutamente sconveniente avere molte più pedine dell’avversario. Questi due concetti appaiono globali, ma si è scoperto che ci si può limitare a valutarli su scala locale (righe, colonne, angoli, …) e poi a sommare insieme i valori ottenuti.
Attualmente il programma più forte e più usato dai giocatori di Othello è sicuramente Wzebra (http://radagast.se/othello/) di Gunnar Andersson


Nicola Vozza