Home page > Recensioni > Archivio > Come fare un programma
Come fare un programma che gioca a Othello (o ad altro)
di Beppi Menozzi
Come pensa uno di quei fortissimi programmi quando gioca a Othello?
Come può un banale programma battere campioni del mondo scafati?
Se volete una risposta a queste domande la cosa migliore è che
andiate a prelevarvi il file della tesi di Michael Buro, che ha
programmato Logistello, attualmente il più forte programma
del mondo.
Qui vorrei invece dare una spiegazione molto rapida di come funziona
un forte programma di Othello (e di qualsiasi gioco in genere) per
chi volesse tentare l'avventura della programmazione.
Un programma è formato sostanzialmente di 3 parti:
- Una libreria per giocare le aperture
ed un sistema per la creazione e l'uso di una libreria che dipende
dal proprio stile di gioco.
- Un algoritmo, ovvero una funzione di
valutazione che prenda una scacchiera e restituisca un punteggio.
- Un motore che, tramite l'uso di
sofisticate tecniche di ricerca in un albero, analizzi tutte le
sequenze di mosse e valuti quella migliore utilizzando l'algoritmo
del punto precedente come valutazione delle foglie dell'albero.
Il gioco del nostro programma sarà forte quando riusciremo
ad avere un algoritmo forte in grado di valutare, per mezzo del nostro
motore, un albero di mosse sufficientemente grande.
Sappiamo che in un gioco come l'Othello non esiste una regola che
permetta di trovare sempre automaticamente la mossa migliore, per cui
il nostro algoritmo sarà solo una approssimazione, più
accurata possibile, dell'ipotetico gioco perfetto.
Più questa approssimazione verrà spinta in
profondità nell'albero delle possibili mosse ancora da giocarsi,
più sarà probabile avere una approssimazione migliore.
Questo discorso vale per qualsiasi gioco di riflessione che non abbia
un metodo per vincere automaticamente.
Come costruire l'algoritmo?
Un bel dilemma!
In realtà molti giocatori, anche fortissimi, hanno tentato
di costruire algoritmi a mano, ma i risultati, sebbene eccellenti,
sono sempre stati in qualche modo inferiori a quelli conseguiti
utilizzando tecniche di apprendimento.
Qui voglio solo dare una impolverata di tali tecniche, che entrano
nella teoria complessissima dell'intelligenza artificiale e sono
tecniche di matematica molto avanzata che si possono imparare
leggendo interi libri...
Nel gioco dell'Othello vengono correntemente usati tali metri di
valutazione di una scacchiera:
- mobilità assoluta (cioè il numero di mosse
in possesso di un colore);
- mobilità potenziale (cioè il numero di pedine
a contatto con caselle vuote o, a volte, le caselle vuote in
contatto con le pedine di un certo colore);
- a volte il numero di pedine;
- pattern sui bordi, intorno agli angoli, in mezzo alla scacchiera
(cioè viene preso un gruppo di caselle, ad esempio le 8
caselle di un bordo della scacchiera, e ad ogni possibile
combinazione di neri, bianchi e caselle vuote per tale pattern
viene assegnato un punteggio).
La somma dei punteggi restituisce un valore che è il
risultato dell'algoritmo per una particolare scacchiera, che
dovrà essere propagato nell'albero delle mosse.
Quello che è importante, è poter assegnare dei valori
ben bilanciati ad ognuno di questi punti, in maniera che una posizione
con un tot di punteggi dovuti a tutti i diversi pattern,
mobilità e così via, dia una approssimazione sensata,
e questo è in genere appannaggio di un computer più
che di un uomo.
Quello che in genere si fa è utilizzare una funzione di errore:
si conosce il risultato di una partita, si calcola quanto questa si
discosta dal valore restituito dalla nostra funzione, e, presumendo
di aver giocato bene la partita e che il finale sia perfetto, si
possono aggiornare i valori dei diversi pattern incontrati in maniera
da poter giocare meglio la prossima volta.
Naturalmente la minimizzazione dell'errore, la cosiddetta "separazione
delle features", la scelta dei pattern, sono tutte tecniche che non
starò a spiegare qui per motivi di spazio.
Spero solo di avervi un po' incuriosito e un giorno di poter giocare
a Othello contro una vostra creatura!