Giocatori di silicio: Backgammon
12/01/2009

Lo scopo di questa serie di interventi è quello di illustrare e analizzare la forza di gioco dei programmi per computer in una serie di popolari giochi.

Per costruire buoni giocatori di silicio, nel backgammon le tecniche utilizzate negli scacchi non funzionano. Anche se apparentemente le regole del gioco sono più semplici, la presenza dei dadi fa si che l’albero delle varianti ben presto “esploda”, e diventa impossibile utilizzarlo in pratica. Tirando due dadi ci sono 21 possibili risultati (15 con probabilità 1/18 e 6 con probabilità 1/36) e poiché in media in una posizione tipica un tiro può essere utilizzato per una ventina di possibili mosse già al livello di una semimossa, l’albero delle varianti dovrebbe contenere 400 rami (a scacchi ricordiamo che sono una quarantina, a dama meno di dieci).


Tuttavia si è scoperto che è possibile utilizzare un altro approccio, basato sulle rete neurali ed in particolare su una tecnica chiamata in inglese “Temporal Difference Learning”. In pratica i software imparano giocando contro se stessi ed in questo modo migliorano le loro capacità.

Il primo forte software (utilizzava logica fuzzy ma non le l’approccio delle reti neurali) è stato scritto verso la fine degli anno Settanta del secolo scorso da Hans Berliner, campione del mondo di scacchi per corrispondenza ed autore del controverso libro “The System”.

Il primo programma ad usare le reti neurali è statoTD-Gammon, sviluppato da Gerald Tesauro all’IBM.
Kit Woolsey dichiarò di TD-Gammon che “non si sono dubbi che il suo giudizio posizionale è migliore del mio”.



Nella fase di uscita delle pedine, i software si appoggiano a speciali tabelle precostituite. Ma la parte che ci pare più interessante è quella relativa al cosiddetto roll out. In una data posizione, tirati i dadi, per scegliere la sua mossa i software giocano migliaia di partite e poi optano per la mossa che ottiene i migliori risultati, cioè scelgono la mossa così come hanno “imparato” a giocare…

Il concetto chiave dell’”autoapprendimento” è il seguente: ad ogni segnale di ingresso (input) viene prodotto un segnale in uscita (output) e da questo viene prodotto un segnale di feedback che indica la bontà dell’output. L’obiettivo è quello di generare input che ottengano il massimo rinforzo in termini di feedback. L’apprendimento può avvenire sia con l’aiuto di un “insegnante esterno” che in maniera totalmente autonoma. Abbastanza sorprendentemente, diremmo, si è scoperto che i risultati migliori si sono ottenuti senza l’interferenza di esperti umani che suggerivano gli output migliori. Inizialmente difficoltà tecniche nel modellizzare l’euristica umana hanno fatto si che fosse percorsa la strada del totale autoapprendimento, ma a quel punto i software hanno cominciato a mettere in luce molti errori nell’approccio strategico umano.

Il feedback può anche essere rilasciato solo al termine di una lunga catena di input ed output. L’idea base del metodo “Temporal Difference” è quella di fare in modo che ad ogni passo la predizione per un dato input sia più vicina alla predizione successiva nel prossimo momento di calcolo.
Interessante osservare che proprio la presenza dell’evento casuale rende efficiente l’approccio a rete neurale; in altri giochi (come ad esempio il go), quando si è provato ad applicare questo metodo, i software finiscono per esplorare sempre le stesse posizioni senza ottenere nessun reale miglioramento.

Per chi ne volesse sapere di più rimandiamo ad un articolo dello stesso Gerald Tesauro disponibile anche sul web.

Alcuni tiri di apertura che una volta erano giocati automaticamente dai migliori giocatori oggi sono stati rivisti proprio grazie a quanto mostrato dai software di gioco. Anche il gioco in alcune situazioni di mediogioco è risultato abbastanza diverso da quanto era ritenuto corretto dai migliori giocatori.

I programmi più diffusi oggi sono i commerciali Jellyfish e Snowie, lo shareware BGBlitz ed il free software GNU Backgammon. Tutti sono allo stesso livello (e forse qualcosa di più) dei migliori giocatori al mondo.


Nicola Vozza

n.vozza@turingduchamp.org