I computer, gli scacchi e il Go

Per decenni, i ricercatori hanno insegnato ai computer a giocare, al fine di testare le loro capacità cognitive contro quelle degli esseri umani. Nel 1997, quando un computer IBM denominato Deep Blue ha battuto Garry Kasparov, il campione del mondo di scacchi, molta gente pensò che gli informatici avrebbero sviluppato intelligenze artificiali capaci di trionfare in qualsiasi gioco. Il Go però, con la sua vertiginosa serie di mosse possibili, ha continuato a ostacolare gli sforzi dei ricercatori.

xkcd: Reassuring

La ricetta per la costruzione di un programma di scacchi che giochi meglio di un essere umano è ormai ben definita. Si inizia elencando tutte le possibili mosse, le risposte alle mosse, e le risposte alle risposte, generando un albero ramificato che cresce tanto quanto consentono le risorse del computer. Per valutare le posizioni di gioco alla fine dei rami, il programma richiede un po di conoscenza del gioco degli scacchi, come ad esempio il valore di ogni pezzo e l'utilità della sua posizione sulla scacchiera. Poi si perfeziona l'algoritmo, "potando" i rami che, ovviamente, implicano un gioco scorretto per entrambe le parti, in modo che il programma può analizzare i restanti rami più dettagliatamente. Imposti il programma così che sia il più veloce possibile su uno o più computer e voilà, hai un Grande Maestro di scacchi. Questa ricetta si è dimostrata vincente non solo per gli scacchi, ma anche per giochi come la Dama e Othello. E' una delle grandi storie di successo nella ricerca dei Sistemi Informativi Automatizzati.

Il Go è tutta un'altra cosa. Il gioco è cambiato poco da quando è stato inventato in Cina migliaia di anni fa, e milioni di persone in tutto il mondo si divertono ancora a giocarlo. I principianti spesso imparano a giocare su una scacchiera composta da una griglia di 9 linee per 9 linee, prima di arrivare fino a quella ufficiale con la sua rete di 19-per-19. Il gioco sembra semplice, in teoria: due giocatori, a turno, mettendo le pietre sulla scacchiera cercano di occupare territori e circondare le pietre dell'avversario. Eppure lo scopo del Go rende estremamente difficile, forse impossibile, per un programma, padroneggiare il gioco con il tradizionale approccio di ricerca e valutazione. 

Per cominciare, la complessità dell'algoritmo di ricerca dipende in gran parte dalla ramificazione - cioè il numero di mosse possibili ad ogni turno. Per gli scacchi, tale fattore è di circa 40, e una partita di scacchi dura in media per circa 50 mosse. Nel Go, il fattore di ramificazione può essere superiore a 250, e una partita prosegue in media per circa 350 mosse. La proliferazione delle opzioni nel Go diventa rapidamente troppo grande per un algoritmo di ricerca standard.

C'è anche un problema più grande: mentre è abbastanza facile definire il valore delle posizioni negli scacchi, è estremamente difficile farlo in una partita di Go. Nei programmi di scacchi, una funzione relativamente semplice di valutazione somma il valore materiale dei pezzi e calcola il valore delle loro posizioni sulla scacchiera in base alla loro possibilità di attaccare o essere attaccati.

Rispetto a quello dei pezzi degli scacchi, il valore delle singole pietre del Go è molto più basso. Pertanto, la valutazione di una posizione è basata su tutte le pietre posizionate, e sul tentativo di giudicare quale di loro sarà eventualmente catturata o quale rimarrà invece al sicuro durante il corso di una lunga partita. Per fare questa valutazione, i giocatori umani si basano sia su una comprensione profonda della tattica del gioco che su una valutazione lucida della situazione complessiva sulla scacchiera. I Maestri considerano la forza dei vari gruppi di pietre e guardano il potenziale per creare, espandere, o conquistare territori su tutta la scacchiera.

Piuttosto che cercare di insegnare ad un programma di Go come eseguire questa valutazione complessa, abbiamo scoperto che la soluzione migliore è quella di saltare del tutto il processo di valutazione. Negli ultimi dieci anni, diversi gruppi di ricerca hanno sperimentato un nuovo paradigma di ricerca per i giochi, e questa tecnica ha effettivamente la possibilità di capire il Go. Sorprendentemente, si basa su sequenze di mosse casuali. Nella sua forma più semplice, questo approccio, chiamato "albero di ricerca Monte Carlo"  (Monte Carlo Tree Search, MCTS), tralascia ogni conoscenza sull'opportunità delle posizioni di gioco. Un programma che utilizza MCTS deve solo conoscere le regole del gioco.

Dalla configurazione delle pietre sulla scacchiera, il programma simula una sequenza casuale di mosse legali (giocando mosse per entrambi gli avversari) fino alla fine della partita, con conseguente vittoria o sconfitta. Lo fa automaticamente più e più volte. La magia deriva dall'uso delle statistiche. La valutazione di una posizione può essere definita come la frequenza con cui casuali sequenze di mosse conducono ad una vittoria. Per esempio, il programma potrebbe stabilire che quando si gioca la mossa A, sequenze casuali di mosse danno come risultato una vittoria il 73 per cento delle volte, mentre la mossa B porta ad una vittoria solo il 54 per cento delle volte. E' un parametro incredibilmente semplice.

Può sembrare contro intuitivo cercare di vincere una partita in cui serve una profonda strategia usando un programma che utilizza movimenti casuali per valutare le diverse scelte. Ma ci sono un sacco di precedenti che mostrano l'efficacia di questo approccio statistico. Ad esempio, la maggior parte dei motori di ricerca in Internet non tenta di analizzare una query per cercare di capire la semantica di ciò che viene chiesto, applicano solo alcuni semplici schemi numerici per classificare i risultati. I metodi Monte Carlo sono standard in discipline come la fisica delle particelle, le previsioni meteorologiche, la chimica e la finanza. Si rivelano spesso l'approccio migliore per risolvere problemi complessi, quando le conoscenze specifiche del problema sono difficili da formalizzare.

Nei giochi a due giocatori ad informazione perfetta, i Sistemi Informativi Automatizzati hanno riportato importanti successi. Tuttavia il Go 19x19, con la sua impressionante serie di possibili posizioni di gioco, rimane una sfida.

Tic-Tac-Toe
Posizioni: 104; il computer gioca perfettamente.

Oware
Posizioni: 1011; il computer gioca perfettamente.

Dama
Posizioni: 1020; il computer lo gioca perfettamente.

Othello
Posizioni: 1028; il computer gioca ad un livello sovrumano.

Go 9x9 
Posizioni: 1038; il computer gioca al livello dei migliori professionisti.

Scacchi
Posizioni: 1045; il computer gioca ad un livello sovrumano.

Xiangqi
Posizioni: 1048; il computer gioca al livello dei migliori professionisti.

Shogi
Posizioni: 1070; il computer gioca al livello dei professionisti.

Go
Posizioni: 10172; il computer gioca come un forte dilettante.

Tratto da "AIs have mastered chess. Will go be next?", di Jonathan Schaeffer, Martin Müller & Akihiro Kishimoto. L'articolo originale completo su IEEE SPECTRUM.