Ricerca e pianificazione: l’albero dei futuri#
Una cassa di ingranaggi e contatti elettrici, in una sala di Parigi, gioca a scacchi da sola davanti al pubblico. Dentro non c’è nessuno, a differenza del famoso Turco, che un giocatore nascosto ce l’aveva, e con quello aveva girato l’Europa più di un secolo prima: l’ha costruita l’ingegnere spagnolo Leonardo Torres Quevedo, funziona dal 1912, e quel giorno del 1914 riconosce da sé dove sono i pezzi, muove i propri e non ha bisogno di nessuno che le dica che cosa fare.
Gioca una situazione sola, e non è l’inizio della partita ma la sua coda, quella che negli scacchi si chiama finale: da una parte re e torre, dall’altra il re avversario e nient’altro. Ma lo gioca contro chiunque, da qualunque posizione, e il matto lo dà sempre. Non lo dà in fretta: ci mette più mosse del necessario, a volte tante che un arbitro, contando le cinquanta mosse oltre le quali il regolamento dichiara patta (cioè pareggio), avrebbe già fermato la partita; la macchina il regolamento non lo conosce, e al matto arriva lo stesso. E non è questo il punto. Il punto è come fa.
E come fa è la cosa che a noi serve: non pensa avanti. Non immagina le mosse dell’avversario, non prova continuazioni, non valuta niente. Guarda dove sono i tre pezzi e applica una regola fissa, scritta a mano dentro gli ingranaggi, del tipo «se il re nemico sta in questa fascia, porta la torre una riga più in là». Quella regola esiste perché re e torre contro re è un problema abbastanza piccolo da avere una ricetta: qualcuno l’ha trovata, l’ha scritta, e la macchina la esegue.
Per la partita intera, di ricetta non ce n’è. Nessuno sa scrivere una regola che, guardando una posizione qualunque di scacchi, dica quale mossa fare. E allora bisogna fare l’altra cosa, quella che fa un giocatore umano davanti alla scacchiera: immaginare. Se muovo qui lui risponde là, e allora io potrei… Questo capitolo è su come si immagina in modo ordinato, che è la prima grande idea dell’intelligenza artificiale e ha un nome asciutto: ricerca. Guardata dal lato di quello che restituisce, cioè una sequenza di mosse da eseguire poi nell’ordine, la stessa faccenda si chiama pianificazione: è la parola che sta nel titolo, e in questo capitolo le due si possono leggere come sinonimi.
Gli stati, le mosse, e l’albero che ne esce#
Per immaginare in modo ordinato servono tre cose sole, e sono le stesse per gli scacchi, per il navigatore satellitare e per quel rompicapo di plastica in cui si fanno scivolare delle tessere numerate dentro una cornice.
Serve dire in che situazione ci si trova, e quella descrizione si chiama stato: la posizione di tutti i pezzi sulla scacchiera, l’incrocio in cui sono adesso, la disposizione delle tessere. Serve dire che cosa si può fare, cioè quali mosse sono ammesse in quello stato e in quale stato portano. E serve sapere quando si è arrivati, cioè riconoscere lo stato di fine.
Da queste tre cose l’oggetto che nasce è sempre lo stesso. Dallo stato di partenza si dipartono tante linee quante sono le mosse possibili; da ciascuno degli stati che ne escono, altrettante; e così via. È un albero, la stessa forma degli alberi decisionali, e ogni situazione che ci sta dentro è un nodo. È un albero capovolto rispetto a quelli veri: la radice sta in cima, e in fondo, alla punta di ogni ramo, ci sono le foglie, i nodi in cui non si va più avanti perché la partita è finita. Ogni cammino dalla radice a una foglia è un futuro possibile.
Prendi il rompicapo con le tessere numerate che scorrono in una cornice, quello in cui c’è una casella vuota e bisogna rimettere i numeri in ordine facendo scivolare una tessera per volta nel buco.
Lo stato è come stanno adesso le tessere. Le mosse sono le tessere che in questo momento confinano con la casella vuota, e sono due, tre o quattro a seconda di dove il buco si trova. Lo stato di fine è i numeri in ordine.
Adesso disegna, su un foglio e senza toccare il rompicapo: come restano le tessere dopo una mossa lo sai in anticipo, senza farla, e lo sai per tutte le mosse che vuoi. In cima metti la situazione di partenza. Sotto, una casella per ciascuna mossa che puoi fare: mettiamo che siano tre, e che restino tre a ogni riga. La riga dopo ne ha nove, quella dopo ancora ventisette, la quarta ottantuno. Dopo quattro righe hai disegnato centoventi caselle e non sei arrivato da nessuna parte: la soluzione, per un rompicapo mescolato bene, sta una ventina di mosse più in basso.
E parecchie di quelle caselle sono lo stesso rompicapo disegnato due volte. Fai scivolare il 7 nel buco, poi rimettilo dov’era: le tessere stanno come stavano. Sul foglio però sono due caselle lontane fra loro, e sotto a ciascuna ricominci da capo a disegnare tutto quello che viene dopo. Le situazioni davvero diverse in cui il rompicapo può trovarsi sono tante, ma sono un numero fisso. Le caselle sul foglio no: ogni situazione ne prende una per ogni strada che ci arriva, e di strade se ne possono inventare quante si vuole.
Quel disegno è l’albero, e non lo si costruisce mai tutto. Se ne costruisce un pezzetto, si guarda, si decide da che parte continuare.
Un problema di ricerca è definito da cinque componenti: lo spazio degli stati \(\mathcal{S}\); lo stato iniziale \(s_0 \in \mathcal{S}\); l’insieme delle azioni ammesse \(\mathcal{A}(s)\) per ogni stato; una funzione di transizione \(\mathrm{ris}(s, a)\) che dice in quale stato si finisce; e un test di terminazione. Se le azioni hanno costi diversi si aggiunge \(c(s, a, s')\), il costo del passo.
Da questa definizione discende l’albero di ricerca, che non va confuso con lo spazio degli stati. Lo spazio degli stati è un grafo: stati diversi si possono raggiungere per strade diverse, e la stessa posizione può ripresentarsi (la cosa ha un nome, trasposizione, e la sezione sui giochi ci torna). L’albero di ricerca è invece l’oggetto che l’algoritmo srotola, e in cui lo stesso stato può comparire in mille punti diversi, uno per ogni cammino che ci arriva. È l’albero, non il grafo, a esplodere.
Le due misure che governano tutto sono il fattore di ramificazione \(b\), cioè quante mosse ci sono in media in uno stato, e la profondità, che conviene distinguere in due: \(d\) è quella a cui sta la soluzione, \(m\) quella massima dell’albero. Un albero completo fino a profondità \(d\) ha circa \(b^d\) nodi, e questo è l’unico conto del capitolo da ricordare: il costo non si somma di livello in livello, si moltiplica.
Perché l’albero esplode, e perché è il problema#
Conviene mettere dei numeri, perché è la differenza fra un problema difficile e un problema che non si affronta affatto.
Negli scacchi, in una posizione tipica, le mosse legali sono circa trentacinque, e una partita dura in media una ottantina di mosse contando quelle di tutti e due i giocatori. L’albero completo di una partita ha quindi qualcosa come trentacinque elevato a ottanta nodi: un 3 seguito da altre centoventitré cifre [RN20].
Un numero così non è «tanto». È un numero che non ha riscontro fisico: gli atomi dell’universo osservabile si stimano attorno a un 1 seguito da ottanta zeri, cioè con più di quaranta cifre in meno. Se ogni atomo fosse un calcolatore che esamina una posizione al secondo dal Big Bang a oggi, l’albero degli scacchi non sarebbe stato sfiorato.
Non è una curiosità, ma il problema del capitolo. Tutto quello che segue esiste per una ragione sola, e cioè per guardare pochissimo di quell’albero e decidere bene lo stesso. Le strade sono due: guardare nel posto giusto (e per farlo serve un fiuto, cioè una stima di quanto manca), e smettere di guardare dove non serve (e per farlo serve accorgersi che un ramo è già peggio di uno che si conosce).
Fig. 11.1 Tre mosse per stato sono poche, e bastano. Il numero a destra non aumenta di tre a ogni riga: si moltiplica per tre, e dopo venti righe è un numero con dieci cifre. Con le trentacinque mosse degli scacchi e ottanta righe, le cifre diventano centoventiquattro.#
Il numero di destra in Fig. 11.1 è il motivo per cui questo capitolo non parla mai di costruire l’albero: parla sempre di quale pezzetto costruire.
Che cosa si sa del mondo#
Da qui in avanti una macchina non si limita a riconoscere quello che ha davanti: decide che cosa fare. E quello che si può decidere dipende da quanto si sa del mondo. I casi sono tre, e conviene averli in testa da adesso, perché dicono che cosa fa questo capitolo e che cosa fa quello dopo.
Il mondo si conosce, ed è piccolo. Si può passare in rassegna ogni situazione possibile e calcolare, per ciascuna, quanto vale: se il mondo è un labirinto, segnare accanto a ogni casella quanto conviene trovarcisi. È quello che fa nella sua prima metà il capitolo sul reinforcement learning, e un labirinto ha poche caselle, quindi si possono guardare tutte.
Il mondo si conosce, ed è enorme. Le situazioni sono più di quante se ne possano guardare, e allora non si guardano tutte: si guarda in avanti dalla situazione in cui ci si trova adesso, lungo pochi rami scelti bene, e si decide solo la mossa da fare subito. È questo capitolo.
Il mondo non si conosce. Nessuno ci dice dove porta una mossa né quanto paga: bisogna provare e vedere come va. È l’apprendimento per rinforzo, cioè il punto in cui quel capitolo va a finire, ed è la ragione per cui i due stanno uno accanto all’altro.
Dall’albero dei futuri alle sue potature#
La strada, da qui, è in tre tappe. La prima è la ricerca in un mondo che non ha avversari, dove l’unico nemico è la dimensione: si comincia dal cercare a tentoni, si misura quanto costa, e si introduce l’unica cosa che cambia davvero le proporzioni, cioè una stima di quanto manca alla fine. Ne esce un algoritmo del 1968 che si chiama A* (si legge «a stella»), quello con cui ancora oggi si cercano i percorsi più brevi, dai navigatori ai videogiochi, e la condizione precisa che deve valere perché quella stima non faccia sbagliare strada.
La seconda mette un avversario dall’altra parte del tavolo, e cambia tutto: metà dei rami li sceglie qualcuno che vuole il contrario di quello che vogliamo noi. Ne escono il modo di ragionare sui giochi a due, la potatura che permette di ignorare interi rami senza guardarli, e il difetto che tutte le ricerche a profondità limitata si portano dietro: il disastro che sta un passo oltre l’ultimo che si è guardato.
La terza fa una cosa sola, e la fa alla fine perché prima non si poteva: mette in chiaro le cose che le prime due hanno dato per scontate, e le toglie una per volta. Ognuna, mancando, porta a un pezzo diverso del libro, e la più grossa porta esattamente al capitolo dopo questo.
Da ricordare
La prima macchina che ha giocato a scacchi da sola non pensava affatto: seguiva una regola scritta a mano, e poteva farlo perché il finale che giocava era abbastanza piccolo da avere una regola.
Per i problemi che una regola non ce l’hanno bisogna immaginare i futuri: da dove sono adesso, che cosa succede se faccio questa mossa, e poi quella, e poi quell’altra. I futuri immaginati formano un albero, in cui la stessa situazione ricompare in tanti punti diversi, uno per ogni strada che ci arriva.
L’albero esplode, e non per poco: guardando un passo più avanti il numero di futuri non aumenta di un po’, si moltiplica. Per gli scacchi si arriva a un numero di centoventiquattro cifre, cioè più di quaranta cifre in più di quante ne servano per contare gli atomi dell’universo.
Quindi l’albero non si costruisce mai tutto. Tutto il capitolo è su come si sceglie il pezzetto da costruire: guardare nel posto giusto, e smettere di guardare dove non serve.
Da ricordare
Un problema di ricerca è (stati, stato iniziale, azioni, transizione, test di fine), più eventualmente i costi. Da lì discende l’albero di ricerca, che è quello che l’algoritmo srotola, distinto dal grafo dello spazio degli stati in cui la stessa situazione si raggiunge per strade diverse.
Le due grandezze che governano il costo sono il fattore di ramificazione \(b\) e la profondità: un albero completo fino a \(d\) ha \(O(b^d)\) nodi. Per gli scacchi \(b \approx 35\) e una partita dura in media ottanta mosse dei due giocatori insieme, cioè \(35^{80} \approx 3 \cdot 10^{123}\), un numero di centoventiquattro cifre [RN20].
La ricerca è pianificazione a modello noto: si assume di poter interrogare la funzione di transizione quante volte si vuole, senza pagare pegno. È l’ipotesi che il capitolo sul reinforcement learning toglierà.
Rispetto alla programmazione dinamica di quel capitolo, che calcola il valore di tutti gli stati, qui si guarda in avanti dal solo stato corrente. Dove il fondo si raggiunge, come nel rompicapo, ne esce il piano intero; dove non si raggiunge, come nei giochi, ne esce la sola mossa da fare adesso, e il lavoro si rifà da capo alla mossa dopo.
Il pezzetto più piccolo che valga la pena costruire è quello che comincia adesso: un albero senza avversari, in cui l’unica difficoltà è che è grande.