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:

  1. 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.
  2. Un algoritmo, ovvero una funzione di valutazione che prenda una scacchiera e restituisca un punteggio.
  3. 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:

  1. mobilità assoluta (cioè il numero di mosse in possesso di un colore);
  2. 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);
  3. a volte il numero di pedine;
  4. 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!