Dama
21/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.

Crediamo non occorra spiegare le regole della Dama, ma può invece essere utile ricordare che quella che si gioca in Italia è solo una delle molte varianti, tra le quali vanno almeno segnalate la dama inglese e la dama internazionale. La dama inglese (draughts in Irlanda e Gran Bretagna, checkers negli Stati Uniti) rispetto alla dama italiana ha le seguenti caratteristiche: la scacchiera si dispone come negli scacchi, iniziano i neri, e più sostanziali, le pedine possono catturare le “dame” e le regole di cattura sono meno stringenti che nella dama italiana. La Dama Internazionale, che in molti paesi (Francia, Olanda, Belgio, Svizzera) è l’unica dama giocata, è stata scelta come standard internazionale dalla Federazione Internazionale. La dama internazionale si gioca su una damiera 10 per 10 con 20 pedine a testa. Le pedine possono catturare le “dame” e solo per catturare possono andare anche all’indietro. La dama può essere mossa di quante caselle vuole (salto lungo) e anche quando cattura non è obbligata a fermarsi immediatamente dopo il pezzo mangiato (ma sono in ogni caso obbligatorie le prese multiple). A volte si può trovare scritto che la “dama volante” si può muovere diagonalmente di quante caselle vuole come l’Alfiere, ma il movimento lungo della dama preesisteva a quello dell’Alfiere e della Regina degli Scacchi; anzi pare molto probabile che sia stata la “dama volante” ad ispirare il cambiamento delle regole degli scacchi durante il tardo medioevo.

Esistono software di gioco per tutte le versioni, e molti possono giocare a più di una ma forse il caso più interessante è quello di Chinook e della dama inglese. È di circa un anno fa l’annuncio che la dama inglese è stata risolta. La notizia ha anche avuto un certo risalto a livello internazionale ma non ci risulta che in Italia se ne sia parlato poi molto.

Nel corso del 2007, un team guidato da Jonathan Schaeffer, professore all’University of Alberta in Canada ha infatti annunciato di aver risolto debolmente il gioco della dama (inglese): un gioco si dice risolto debolmente se è possibile fornire un algoritmo che assicuri una vittoria, per un giocatore o una patta per l’altro contro ogni possibile mossa dell’avversario, a partire dalla prima mossa.

Un gioco invece si dice risolto in maniera “forte” se è possibile costruire un algoritmo in grado di produrre un gioco perfetto a partire da ogni tipo di posizione, anche se sono già stati commessi degli errori.

A differenza di quello che si può leggere su qualche sito anche autorevole, non esiste un file contenente tutte le informazioni su ogni posizione legale che può verificarsi durante il gioco, e quale mossa porterà alla patta, se possibile, o alla vittoria (si tratterebbe in quel caso di un gioco risolto in maniera forte).

Ebbene, grazie a Chinook e tredici anni di analisi è stato possibile dimostrare che a gioco corretto la dama inglese è patta.
A rigore, bisognerebbe dire che la dama italiana non è risolta, ma essendo un gioco più semplice, almeno dal punto di vista della complessità matematica del gioco inglese, la possibilità di risolverla è implicita in quella della dama inglese.

Fino al 1994, Chinook era un “normale software”, che per quanto già in grado di battere i migliori giocatori al mondo, non era perfetto e commetteva degli errori. Ma a Schaeffer il traguardo della perfezione sembrava così vicino che egli decise di allargare il progetto, puntando non più al gioco agonistico ma a risolvere completamente il gioco. A questo scopo centinaia di computer hanno collaborato per svolgere il lavoro per circa 13 anni, anche se ad un certo punto, nel 1996, al team di lavoro il compito apparve al di fuori delle possibilità del tempo e ci fu un interruzione fino al 2001.
Schaeffer ed il suo gruppo hanno iniziato dai finali, costruendo un database con tutti i possibili finali fino a 8 pezzi, ma nel 1996 arrivare a nove pezzi sembra oltre le possibilità della tecnologia. Nel 2001, una nuova generazione di computer permise di arrivare agevolmente fino a dieci pezzi (cosicché il database conteneva 39 trilioni di posizioni). Il prossimo passo era quello di arrivare, partendo dall’apertura, fino ai finali con dieci pezzi. Di tutte le aperture possibili di una mossa e mezza (tre ply: mossa del Nero, mossa del Bianco, mossa del Nero) che sono circa 300, oltre 100 sono trasposizioni, molte altre sono semplicemente troppo cattive per uno dei due giocatori (l’equivalente scacchistico di 1. e4 e5 2. Aa6). Rimanevano da analizzare 19 linee di apertura. Queste linee di apertura sono state seguite (in alcuni casi per più di settanta mosse) fino a raggiungere il database dei finali. Il 27 aprile 2007 il database delle aperture e quello dei finali sono stati uniti, dimostrando che a gioco corretto la dama inglese è patta. Questo risultato, non è stato una sorpresa per nessuno, perché ai più alti livelli di gioco un gran numero di partite finisce in parità (ben oltre le percentuali scacchistiche). A causa delle differenze delle regole non si può concludere che anche la dama italiana sia patta, ma in realtà il gran numero di patte che si ha anche nella dama italiana tra giocatori competenti ne è un buon indizio.

Gli appassionati del gioco, che si calcolano in circa 200 milioni, comunque non appaiono turbati dalla notizia e come è giusto che sia, continuano a giocare al loro gioco preferito.

Lo scopo dell’ultimo progetto di Schaeffer non era quindi più quello di creare un forte “giocatore di Silicio”, ma appunto quello di risolvere completamente il gioco, ma facendo un passo indietro, proviamo a chiederci come funziona un giocatore di silicio di dama, come possono essere Chinook o altri.
Gli strumenti informatici utilizzati sono molto simili a quelli dei software scacchistici, e così abbiamo un albero delle varianti, il metodo Minimax, il metodo alpha-beta, l’effetto orizzonte, un algoritmo per la valutazione delle posizioni, ... Per quest’ultimo punto, come a scacchi, anche qui c’è un fattore materiale ed una valutazione più legata alla posizione occupata dai pezzi. Dal punto di vista del materiale pare che per un giocatore di dama la domanda più importante sia: quante pedine vale una dama? (Per la dama italiana la risposta sembra essere più di tre in apertura e mediogioco, meno di due in finale). Altri fattori valutativi riguardano le case su cui si trovano i pezzi, le formazioni di pezzi, il numero di mosse disponibili, il numero di caselle disponibili ….

Per la dama internazionale non sussistono le motivazioni scientifiche che hanno spinto il gruppo di Schaeffer, né quelle scientifiche ed economiche presenti nel mondo degli scacchi, eppure nel 2003 Buggy, il più forte software per il gioco della dama su cento caselle, ha battuto uno dei più forti giocatori al mondo, il GM senegalese N’Diaga Samb abbastanza nettamente, per 4 a 2 e 5 a 1 (2 incontri su tre partite, con un punto per il pareggio e due per la vittoria).

Nicola Vozza