Le tre cose che davamo per scontate#
Tutto quello che il capitolo ha costruito finora poggia su tre regali che nessuno ha mai messo per iscritto, perché sembravano ovvi. Conviene scriverli adesso, uno per riga, e poi toglierli uno alla volta: perché è togliendoli che si arriva a tutto il resto del libro.
Le regole: si possono interrogare quante volte si vuole. Prima di muovere davvero, il programma prova mille mosse nella sua testa e per ciascuna sa esattamente dove porta, gratis e senza conseguenze. Sposta la torre, guarda, e la rimette dov’era.
L’arrivo: si sa riconoscere. Le tessere in ordine, il re sotto scacco matto, l’incrocio giusto. C’è un test che dice sì o no.
Il voto: si sa dare a una posizione di mezzo. Non un voto esatto, ma un voto sensato: chi sta meglio, quanto manca.
Nel mondo vero ognuno dei tre può mancare, e le tre parti che seguono li tolgono uno per volta: prima il voto, che è quello che si rompe più facilmente; poi l’arrivo; per ultime le regole, che sono quelle che fanno cadere tutto il resto. Ognuno, mancando, porta a un pezzo diverso del libro, e l’ultimo porta al capitolo dopo questo.
Quando nessuno sa scrivere il voto#
Il voto è il primo dei tre a cadere, ed è caduto su un gioco preciso.
Agli scacchi il voto si sa scrivere: quanti pezzi ho, quanto vale ciascuno, se il re è al riparo, come stanno i pedoni. È la somma della sezione precedente, e funziona: nel 1997 il programma Deep Blue, che faceva esattamente questo e la potatura vista qui, giocò sei partite contro Garri Kasparov, che era il giocatore più forte del mondo, e ne uscì in vantaggio per tre punti e mezzo a due e mezzo: due vittorie contro una, e tre patte, che valgono mezzo punto a testa.
Il Go è un altro gioco, e conviene dire com’è fatto perché in Italia lo si vede di rado. Si gioca su una griglia grande, diciannove righe per diciannove, e i pezzi sono sassolini tutti uguali, bianchi e neri, che si posano sugli incroci e da lì non si muovono più. Non ci sono re, torri o alfieri: c’è solo il disegno che i sassolini formano, e vince chi alla fine ha circondato più territorio.
E qui il voto non si sa scrivere. Non c’è materiale da contare, perché i pezzi sono tutti uguali e restano fermi; quanto valga un sassolino dipende da come stanno i suoi vicini e i vicini dei vicini, cioè da un disegno che può occupare mezza griglia. Una posizione forte i giocatori la riconoscono a colpo d’occhio, ma la regola con cui la riconoscono nessuno è mai riuscito a scriverla in una formula, e non per pigrizia: ci si è provato per trent’anni. E senza il voto, tutta la macchina della sezione precedente si ferma: si guarda avanti, si arriva al punto in cui bisogna fermarsi, e lì non c’è niente da leggere.
Non sai giudicare una posizione? E allora non giudicarla: da lì, gioca la partita fino in fondo tirando le mosse a caso, e guarda come finisce. Poi rifallo. Poi rifallo mille volte. Alla fine non hai un giudizio, hai un conteggio: da questa posizione, tirando a caso, ho vinto (mettiamo) seicentotrenta volte su mille.
A caso, ma con un divieto: non si posa un sassolino dentro un buco circondato tutto da sassolini propri. È una mossa che nessun giocatore farebbe, perché riempie con le proprie mani il territorio che stava tenendo. E senza quel divieto due giocatori che tirano a caso disfano quello che hanno appena costruito, le partite rischiano di non finire più, e mille partite che non finiscono non contano niente.
Detta così sembra assurdo, perché nessuna di quelle mille partite somiglia a una partita vera: sono mosse a caso, giocate malissimo da tutti e due. Ed è proprio questo il punto: giocate malissimo da tutti e due. Se una posizione è davvero buona per me, resta buona anche in un mondo in cui giochiamo tutti a caso, perché il vantaggio non dipende dalla mia bravura. Il conteggio non misura come andrebbe la partita: misura quanto la posizione è comoda, e per scegliere una mossa spesso basta.
Le partite da tirare, poi, non sono infinite, e servono a scegliere fra le mosse che potrei fare adesso: mille per ciascuna sarebbero troppe. Allora se ne dà qualcuna a tutte, si guarda quali stanno rendendo, e le prove successive vanno soprattutto lì; qualcuna però resta sempre per le mosse provate poco, perché tre partite andate male possono essere solo sfortuna. E dove va la partita successiva lo decide un conto, sempre lo stesso.
E dentro la mossa che sta rendendo si rifà la stessa cosa, con le risposte che l’avversario potrebbe darle. Un pezzetto alla volta cresce un disegno di rami, fitto dalla parte che conta e quasi vuoto altrove, e ogni partita nuova parte dal fondo del ramo già scavato invece che da qui.
Il punto di rottura c’è ed è serio: questo funziona nei giochi in cui una posizione buona resta buona anche giocando male. Ci sono giochi in cui non è così, in cui esiste una sola continuazione che salva e tutte le altre perdono: lì tirare a caso dice sempre «si perde», e non distingue più niente. Agli scacchi, per esempio, questo trucco da solo non funziona bene, e infatti agli scacchi non è così che si è vinto.
La mossa è sostituire la valutazione statica \(\mathrm{ev}(s)\) con una stima campionaria: da \(s\) si simulano \(N\) partite fino alla fine con una politica rapida (nella versione più semplice, uniforme sulle mosse legali, con l’eccezione di quelle che nel Go riempirebbero un proprio occhio, cioè un incrocio vuoto circondato da sassolini propri: senza quel divieto le partite a caso rischiano di non finire) e si usa la frazione di vittorie come stima del valore. Stimare una quantità che non si sa calcolare campionando a caso e facendo la media si chiama metodo Monte Carlo, ed è un attrezzo che il libro riuserà in tre posti diversi: qui su un albero di gioco, nel capitolo sul reinforcement learning per stimare il valore di uno stato dalle partite giocate, e nei modelli generativi per stimare integrali che non hanno forma chiusa.
Resta da dire come si distribuisce il budget di simulazioni fra i figli della radice, e la risposta è esattamente il dilemma fra esplorare e sfruttare che il capitolo sul reinforcement learning introdurrà con i bandit a più braccia. Dare più prove a ciò che finora rende, senza smettere di provare ciò di cui si sa poco, e con una regola che quantifichi quel «senza smettere».
Valutare una posizione giocando partite a caso non è un’idea del 2006: nel Go ci era arrivato per primo Bernd Brügmann [Brugmann93], che nel 1993, senza dare al programma nessuna conoscenza oltre alle regole, sul nove per nove aveva raggiunto la forza di un principiante. Quello che nasce in quegli anni è la fusione delle due cose, e nasce in due tempi. Prima l’albero che cresce una simulazione alla volta, con un modo di risalire i valori che comincia facendo la media e finisce facendo il minimax: è di Rémi Coulom [Cou06], che fra i propri riferimenti mette Brügmann. Poi la regola che decide dove spendere la simulazione successiva, cioè la stessa regola dei bandit (si chiama UCB1, e sceglie il ramo col miglior compromesso fra quanto ha reso finora e quanto poco lo si è provato) applicata a ogni nodo dell’albero [KSzepesvari06]: è la seconda a dare al metodo le sue garanzie di convergenza, che però dicono che la stima arriva, non quanto in fretta.
C’è un limite, e il metodo se lo porta dietro: la stima campionaria è tanto più informativa quanto più il valore di una posizione è robusto rispetto alla qualità del gioco. Nei domini in cui il valore dipende da una singola linea forzata, le simulazioni casuali sono rumore puro.
Questa idea ha un nome, ricerca ad albero Monte Carlo (in inglese Monte Carlo tree search, abbreviata in MCTS). «Monte Carlo» è il nome che i matematici danno da ottant’anni ai metodi che stimano per sorteggio quello che non si sa calcolare, e da dove venga quel nome lo racconta la sezione sui metodi Monte Carlo, nel capitolo sul reinforcement learning. Ma il metodo non si esaurisce nel contare le partite: quello che lo rende praticabile è non spartire le simulazioni in parti uguali, perché darne mille a una mossa palesemente perdente è tempo buttato. E la stessa scelta si rifà più sotto, dentro la mossa che sta rendendo: è di lì che viene l’albero del nome.
Il libro la costruisce per intero nella sezione su MCTS e AlphaGo, dove serve a raccontare come una rete neurale e una ricerca si aiutino a vicenda. Qui interessa solo il suo posto in questa storia, che è preciso: nasce per rispondere al voto che manca, ed è la ragione per cui il Go, che alla ricerca classica aveva resistito per trent’anni, ha cominciato a cedere.
Quando l’arrivo non si sa dire#
L’arrivo cade più silenziosamente del voto, e per questo è più insidioso.
In tutti i problemi di questo capitolo c’era un test che diceva «sei arrivato». Ma prova a scriverlo per «trova una buona sistemazione dei turni del personale». Un test in realtà c’è, e non serve a niente: dice se una sistemazione sta in piedi (nessuno di turno due volte nello stesso momento), e di sistemazioni che stanno in piedi ce ne sono milioni, quasi tutte pessime. Quello che manca è il test per buona, e quello non si scrive: ci sono soluzioni migliori e peggiori, e nessun punto in cui si è finito.
Quando succede questo, la ricerca cambia natura, e diventa una cosa che tutti abbiamo fatto almeno una volta: sistemare i mobili in una stanza. Non c’è una disposizione «giusta» che a un certo punto scatta; c’è quella di adesso, ci sono gli spostamenti che la migliorano un po’, e a un certo punto si smette perché è ora di cena. Nessuno ha finito: uno ha smesso.
Questa famiglia di metodi il libro la incontra altrove sotto altri nomi. È quello che fa la discesa del gradiente dei richiami di matematica, cioè il modo in cui una rete neurale impara: si parte da una configurazione qualunque, si guarda da che parte migliora, ci si sposta di un passo, e nessuno dice mai che si è arrivati. Ed è quello che rifà lo sciame di particelle dei sistemi multi-agente, dove a spostare i mobili sono in tanti insieme e nessuno comanda.
Quando le regole non si possono interrogare#
Le regole sono il regalo più grosso dei tre, e toglierle è quello che apre il capitolo sul reinforcement learning.
Ti siedi a un tavolo, davanti c’è un gioco che non hai mai visto, e nessuno ti dà il regolamento. Non puoi provare una mossa nella tua testa, perché non sai dove porta. Puoi solo farla per davvero, e guardare che cosa succede. E se era una mossa disastrosa, il disastro te lo tieni: non c’è nessun «rimetto la torre dov’era».
Sparisce, di colpo, tutto quello che il capitolo ha costruito. Non c’è albero da esplorare, perché per costruire l’albero bisognerebbe sapere dove portano le mosse. Non c’è potatura, perché non ci sono rami. Non c’è nemmeno il modo di guardare avanti di un passo.
Quello che resta, all’inizio, è una cosa sola: provare, vedere com’è andata, e ricordarsi com’è andata. Chi ha fatto una mossa mille volte in situazioni simili sa, senza conoscere le regole, che di solito finisce bene. Non ha una mappa: ha un’esperienza.
Dopo abbastanza partite, però, il regolamento comincia a intravedersi: se ogni volta che fai quella cosa succede quell’altra, ti sei scritto una regola tua. E allora torni a provare le mosse nella testa come facevi prima, ma su un regolamento indovinato al posto di quello vero. Di una mossa o due funziona bene. Se ne incateni dieci, ogni pezzo storto si somma a quelli di prima, e il finale che ti figuri non ha più molto a che fare con quello che succederà davvero al tavolo.
Formalmente cade la disponibilità di \(\mathrm{ris}(s,a)\) e di \(c(s,a,s')\): la funzione di transizione e la funzione di costo esistono ma non sono interrogabili, se non eseguendo davvero l’azione e osservando l’esito. È la condizione dell’apprendimento per rinforzo, e la differenza operativa non è di grado ma di natura: la ricerca spende calcolo per guardare futuri immaginati, il rinforzo spende esperienza per stimare valori da futuri davvero accaduti.
Le due cose non sono alternative, e i capitoli che seguono lo mostrano in tre modi. Se il modello manca ma lo si può imparare, si ricade nel caso di questo capitolo usando il modello appreso al posto di quello vero: è la famiglia dei metodi basati su modello, col rischio che gli errori del modello si accumulino lungo i rami immaginati. Se esiste una rete che suggerisce dove guardare, la ricerca smette di essere cieca e diventa quella di AlphaGo e dei suoi successori [SHM+16]. E se il modello non c’è affatto, restano i metodi del capitolo sul reinforcement learning.
Resta un punto di contatto: anche a modello ignoto, pensare prima di rispondere paga. Il calcolo speso al momento della risposta invece che durante l’addestramento è una forma di ricerca, e la sezione sul post-addestramento la tratterà per esteso, parlando dei modelli che scrivono una lunga brutta copia prima di rispondere.
Conviene guardare i tre casi tutti insieme, perché messi in fila dicono una cosa che presa uno per uno non si vede: non sono tre difficoltà, sono tre destinazioni. Senza il voto si arriva alla ricerca ad albero Monte Carlo; senza l’arrivo si finisce nell’ottimizzazione, cioè nel migliorare senza mai arrivare, quella della discesa del gradiente dei richiami di matematica e degli sciami; senza le regole da interrogare, all’apprendimento per rinforzo. Un metodo di intelligenza artificiale, spesso, è il nome che diamo a un regalo che ci hanno tolto.
Da ricordare
Tutta la ricerca di questo capitolo poggia su tre regali: le regole, che si possono interrogare quante volte si vuole per provare le mosse nella propria testa; l’arrivo, che si sa riconoscere; e il voto, che si sa dare a una posizione di mezzo.
Se manca il voto (è il caso del Go, dove nessuno è mai riuscito a scriverlo), lo si sostituisce con un conteggio: da qui, gioca mille partite a caso e guarda quante ne vinci. Le partite non si spartiscono in parti uguali fra le mosse candidate: ne va di più a quelle che stanno rendendo, e qualcuna resta sempre per quelle provate poco. Funziona nei giochi in cui una posizione comoda resta comoda anche giocando male, e non funziona dove esiste una sola continuazione che salva.
Se manca l’arrivo, la ricerca smette di cercare una strada e si mette a migliorare quello che ha, fermandosi quando scade il tempo, come si fa sistemando i mobili in una stanza.
Se mancano le regole da interrogare, all’inizio casca tutto: non c’è albero, non c’è potatura, non c’è niente da guardare avanti. Resta provare per davvero e ricordarsi com’è andata, e questo ha un nome: apprendimento per rinforzo. Poi il regolamento comincia a intravedersi, e si torna a provare le mosse nella testa su quello indovinato: di una mossa o due funziona, di dieci incatenate ogni pezzo storto si somma a quelli di prima.
Da ricordare
Le tre ipotesi implicite della ricerca classica sono: modello interrogabile (\(\mathrm{ris}\) e \(c\) disponibili a costo nullo), test di terminazione definito, valutazione degli stati intermedi scrivibile.
Cade la valutazione: si sostituisce \(\mathrm{ev}(s)\) con una stima campionaria ottenuta simulando partite fino in fondo, e si distribuiscono le simulazioni risolvendo un problema di esplorazione contro sfruttamento. È la ricerca ad albero Monte Carlo [Cou06, KSzepesvari06], che il libro costruisce nella sezione su MCTS e AlphaGo.
Cade il test di terminazione: il problema diventa di ottimizzazione, non di ricerca di un cammino.
Cade il modello interrogabile: si entra nell’apprendimento per rinforzo. La distinzione operativa è che la ricerca spende calcolo su futuri immaginati e il rinforzo spende esperienza su futuri accaduti; il ponte fra i due sono i metodi che imparano il modello e poi ci cercano dentro.
Il capitolo che viene adesso toglie il regalo più grosso dei tre, quello di poter provare le mosse nella propria testa. In cambio dà una cosa che qui non c’è mai stata. La ricerca, per raffinata che sia, ricomincia da zero a ogni mossa: quello che ha capito pensando alla mossa di prima lo butta via, e la partita di ieri non le ha insegnato niente. Chi impara, invece, la seconda volta comincia da dove era arrivato.