Monte Carlo Tree Search: cercare senza sapere valutare

MCTS costruisce un albero di ricerca asimmetrico stimando le posizioni con partite casuali invece che con un’euristica scritta a mano. È l’algoritmo che ha portato i computer dal livello dilettante al livello superumano nel Go, e lo scheletro di ricerca dietro AlphaGo.

Perché questo capitolo

Nel 1997 Deep Blue batte Garry Kasparov a scacchi. Nel 2016 AlphaGo batte Lee Sedol a Go. Diciannove anni di distanza per due giochi da tavolo: perché tanto?

La risposta sta in un singolo ingrediente mancante. Deep Blue funzionava con la potatura alpha-beta (vedi minimax) e una funzione di valutazione scritta a mano da maestri di scacchi: materiale, struttura pedonale, sicurezza del re. Quella funzione esisteva.

Per il Go non esisteva. Valutare staticamente una posizione di Go — dire “il nero sta meglio di tanto” guardando la scacchiera — è un problema che ha resistito a trent’anni di ricerca. Il valore di una pietra dipende da configurazioni che possono estendersi su tutta la scacchiera, da gruppi vivi o morti, da territorio solo potenziale. Senza una funzione di valutazione, la ricerca classica è cieca: non sa dove guardare.

Monte Carlo Tree Search, abbreviato MCTS, risolve esattamente questo. Non chiede una funzione di valutazione: stima il valore di una posizione facendola giocare fino in fondo, molte volte, e contando chi vince. Non esplora l’albero in modo uniforme: lo costruisce asimmetrico, spendendo calcolo dove le cose si fanno interessanti. È anytime: puoi fermarlo quando vuoi e ti dà la migliore mossa trovata finora. Questi tre tratti — niente euristica, albero adattivo, anytime — lo rendono lo strumento di elezione per i domini con spazio enorme e nessuna valutazione affidabile.

Capirlo conta per tre ragioni concrete. Primo, è il ponte tra la ricerca classica di questa Parte e il deep reinforcement learning della Parte VII: AlphaGo è MCTS più reti neurali, e senza capire lo scheletro non si capisce il resto.

Secondo, lo schema “tratta ogni scelta come un bandit, bilancia esplorazione e sfruttamento” che vedremo qui ricompare ovunque ci sia da allocare un budget di prove sotto incertezza — dall’A/B testing alla scelta di quale esperimento far girare.

Terzo, dal 2023 la ricerca ad albero è arrivata al reasoning dei modelli linguistici: Tree of Thoughts e le sue varianti applicano questa stessa idea — cercare invece di indovinare — allo spazio dei ragionamenti. Chi vuole capire cosa significhi “spendere più calcolo all’inferenza” trova in MCTS il caso di studio più pulito.

Contesto

Il metodo Monte Carlo è vecchio. Il nome viene dal Casinò di Monte Carlo: lo coniarono i fisici di Los Alamos negli anni ‘40 (Stanislaw Ulam, John von Neumann, Nicholas Metropolis) per una tecnica che stima quantità difficili da calcolare tramite campionamento casuale ripetuto.

Se non sai integrare una funzione, lanci punti a caso nel suo dominio e conti quanti cadono sotto la curva. La frazione, moltiplicata per l’area del dominio, stima l’integrale. La media converge alla risposta. È questo trucco — sostituire un calcolo difficile con molti esperimenti casuali — che MCTS porta nell’albero di gioco.

Applicare il campionamento casuale al gioco è un’idea degli anni ‘90. Bernd Brügmann, fisico tedesco, nel 1993 propone “Monte Carlo Go”: valutare una mossa di Go giocando da quella posizione molte partite completamente casuali e misurando la frequenza di vittoria. Niente albero, niente euristica, solo simulazioni.

L’idea sembrava troppo grezza per essere presa sul serio e restò ai margini per oltre un decennio. Il pregiudizio era comprensibile: partite giocate a caso sembrano non avere alcun rapporto con il gioco competente. Eppure quel pregiudizio si rivelò sbagliato — non perché i rollout casuali fossero buoni, ma perché si poteva costruirci sopra qualcosa che lo era.

La svolta è del 2006, e arriva da due paper distinti pubblicati lo stesso anno.

Rémi Coulom, ricercatore francese di informatica, nel paper Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search (Computers and Games 2006) conia il termine “Monte-Carlo Tree Search” e introduce l’idea decisiva: non fare solo simulazioni piatte, ma costruire incrementalmente un albero di ricerca, usando le simulazioni per decidere quali rami dell’albero approfondire. Coulom mette l’idea nel suo programma di Go Crazy Stone, che vince il torneo computer-Go KGS dello stesso anno.

Pochi mesi dopo, Levente Kocsis e Csaba Szepesvari, due ricercatori ungheresi di machine learning, pubblicano Bandit based Monte-Carlo Planning (ECML 2006). Il loro contributo è la tree policy: come scegliere, a ogni nodo dell’albero, quale ramo seguire. La loro risposta si chiama UCT, e ha basi teoriche solide — la affrontiamo in dettaglio più avanti.

La combinazione MCTS (lo scheletro di Coulom) più UCT (la tree policy di Kocsis e Szepesvari) diventa rapidamente lo standard. Tra il 2006 e il 2009 i programmi di Go basati su MCTS — Crazy Stone, MoGo, Fuego, Zen — saltano dal livello dilettante debole al livello dilettante forte, un progresso che la ricerca classica non aveva prodotto in trent’anni. È un caso istruttivo di come un’idea algoritmica giusta possa sbloccare un campo fermo da decenni: il Go non era diventato più facile, era cambiato lo strumento per affrontarlo.

Il secondo salto è del 2016. AlphaGo (laboratorio DeepMind, paper su Nature Mastering the game of Go with deep neural networks and tree search, Silver et al. 2016) combina MCTS con due reti neurali profonde, e batte 4-1 il professionista Lee Sedol. AlphaZero (2017-2018) generalizza l’approccio a scacchi e shogi. La storia completa di AlphaGo è raccontata in alphago-2016; qui ci interessa la parte algoritmica.

Vale la pena fissare le date, perché chiariscono che MCTS non è un’invenzione del deep learning. Il framework — Coulom, Kocsis e Szepesvari — è del 2006. Le reti neurali arrivano dieci anni dopo, e si innestano su uno scheletro già maturo. Quando si dice “AlphaGo ha rivoluzionato il Go” si comprime in un nome una storia in due tempi: prima un decennio di MCTS che porta i programmi al livello dilettante forte, poi il deep learning che chiude il divario con i professionisti.

Il grafo concettuale, esplicitamente. MCTS sta accanto agli altri algoritmi di ricerca di questa Parte. search-bfs-dfs esplora l’albero in modo cieco e sistematico; MCTS lo esplora in modo guidato dalle statistiche. search-a-star guida la ricerca con un’euristica ammissibile data; MCTS sostituisce l’euristica con le simulazioni. search-ida-star e MCTS sono entrambe risposte al problema “l’albero non sta in memoria”, ma con strategie opposte: IDA* rivede i nodi, MCTS costruisce solo la parte promettente.

E MCTS sta a metà strada verso la Parte VII: formalmente è planning su un MDP, la sua tree policy è un problema di multi-armed bandit, e la sua versione con reti neurali è il cuore di AlphaGo. È uno dei pochi capitoli di questa Parte che guarda tanto indietro — alla ricerca classica — quanto avanti, ai sistemi che imparano.

L’intuizione

Due angoli distinti, prima del formalismo.

Angolo 1: il sondaggista e l’esploratore

Immagina di dover scegliere quale di cinque ristoranti prenotare per una cena importante, e di non sapere nulla di nessuno. Hai però un assistente che può andare a provarne uno e tornare con un voto. Hai tempo per cento prove totali. Come le distribuisci?

Una strategia ingenua: venti prove a testa, poi scegli il ristorante con la media più alta. Spreca calcolo. Dopo le prime prove sai già che il ristorante numero tre fa schifo: continuare a mandarci l’assistente è denaro buttato. Ma c’è il rischio opposto. Se dopo tre prove il ristorante numero uno ha la media più alta, smetti di provare gli altri? E se quella media alta fosse fortuna, tre cene capitate bene per caso? Avresti scartato per sempre opzioni mai esplorate abbastanza.

Questo è il dilemma exploration/exploitation. Sfruttare (exploitation) significa puntare sull’opzione che finora sembra migliore. Esplorare (exploration) significa provare un’opzione incerta per ridurre il rischio di averla giudicata male per sfortuna. Le due spinte tirano in direzioni opposte, e ogni prova spesa sull’una è una prova tolta all’altra.

MCTS fa esattamente questo, su scala. Ogni mossa possibile è un “ristorante”, ogni partita simulata è una “prova dell’assistente”, e l’algoritmo deve decidere, prova dopo prova, dove spendere la successiva. La parte sottile è che le mosse non sono cinque ma migliaia, e ognuna apre a sua volta un sottoalbero di altre mosse, ciascuna un dilemma annidato. MCTS gestisce questa annidatura: a ogni nodo dell’albero risolve un piccolo problema di esplorazione/sfruttamento, e la struttura ad albero compone tutti questi problemini in una ricerca globale.

Angolo 2: scolpire l’albero dove conta

L’albero di gioco completo del Go è impensabile: con un branching factor (numero medio di mosse legali per posizione) attorno a 250 e partite lunghe centinaia di mosse, il numero di posizioni eccede le particelle dell’universo osservabile. Nessun algoritmo lo enumera.

Cambia prospettiva. Invece di tenere in memoria tutto l’albero, parti da un albero minuscolo — solo la radice, la posizione corrente — e fallo crescere di un nodo per volta. A ogni iterazione l’algoritmo decide quale singolo nuovo nodo aggiungere, e lo decide guardando le statistiche raccolte finora.

I rami che hanno prodotto molte vittorie attirano nuove iterazioni, e crescono in profondità. I rami che hanno prodotto sconfitte vengono visitati di rado, e restano monconi. Dopo qualche migliaio di iterazioni l’albero in memoria è un oggetto profondamente asimmetrico: una guglia profonda lungo le linee di gioco promettenti, un cespuglio basso e largo per tutto il resto.

Vista così, MCTS è uno scultore. Il blocco di marmo — l’albero completo — è troppo grande per essere toccato tutto. MCTS scolpisce: toglie attenzione da dove non serve, la concentra dove la forma interessante sta emergendo. Ogni iterazione è un colpo di scalpello informato da tutti i colpi precedenti. Questa asimmetria adattiva è la differenza pratica chiave rispetto alla ricerca a profondità fissa di alpha-beta, che esplora tutti i rami fino allo stesso livello senza distinzione.

La meccanica

MCTS ripete una stessa iterazione migliaia di volte. Ogni iterazione si chiama simulazione, rollout o playout a seconda della convenzione, e attraversa quattro fasi. L’albero in memoria parte con la sola radice, che rappresenta lo stato corrente, e cresce di un nodo per iterazione.

Ogni nodo memorizza due numeri: $N$ , il conteggio delle visite, e $W$ , la somma dei valori dei rollout passati che lo hanno attraversato. Il valore medio del nodo è $\bar{X} = W / N$ . Due numeri per nodo: è tutto lo stato che MCTS mantiene.

Le quattro fasi

1. Selezione. Si parte dalla radice e si scende lungo l’albero già costruito. A ogni nodo si sceglie un figlio secondo la tree policy, fino a raggiungere un nodo che non è completamente espanso — ha mosse legali non ancora rappresentate come figli — oppure un nodo terminale (partita finita). La tree policy non è casuale: è qui che si bilancia esplorazione e sfruttamento, ed è qui che entra UCT, la formula della prossima sezione. La selezione è la fase “intelligente”: usa tutto ciò che le iterazioni precedenti hanno imparato.

2. Espansione. Al nodo raggiunto, se non è terminale, si aggiunge all’albero uno dei figli mancanti — di norma uno solo per iterazione. Il nuovo nodo nasce con $N = 0$ e $W = 0$ . Questo è l’unico punto in cui l’albero cresce: un nodo per iterazione, quindi dopo $k$ iterazioni l’albero ha al più $k$ nodi oltre alla radice. La memoria cresce in modo lineare, controllato.

3. Simulazione (rollout). Dal nuovo nodo si gioca una partita completa fino a uno stato terminale, usando la default policy. Nella versione classica la default policy è uniformemente casuale: si scelgono mosse legali a caso, per entrambi i giocatori, finché la partita non finisce.

Questa fase non costruisce albero e non consuma memoria: il suo unico prodotto è un esito — vittoria, sconfitta, patta, o un payoff numerico. È la parte “stupida” dell’algoritmo, e proprio perché stupida è veloce: niente da memorizzare, niente da valutare, solo mosse a caso fino al verdetto.

4. Backpropagation (backup). L’esito della simulazione viene propagato all’indietro lungo tutto il percorso radice-nodo. Per ogni nodo attraversato si incrementa $N$ di 1 e si somma l’esito a $W$ . In un gioco a due giocatori l’esito va letto dal punto di vista di chi muove a quel nodo: ciò che è vittoria per uno è sconfitta per l’altro, quindi il valore va negato a livelli alterni dell’albero. Dopo il backup le statistiche sono aggiornate e la prossima selezione ne terrà conto.

Al termine del budget — un numero fissato di iterazioni o un limite di tempo — si sceglie la mossa alla radice. Attenzione qui: la scelta non è di norma il figlio con il valore medio più alto, ma il figlio più visitato, il most-robust child. Il conteggio visite è una statistica più stabile del valore medio: un figlio poco visitato può avere una media alta per puro caso, mentre un figlio molto visitato è quello su cui l’algoritmo ha scommesso a lungo, iterazione dopo iterazione. La robustezza batte la media rumorosa.

Pseudocodice

MCTS(stato_radice, budget):
  radice <- nodo(stato_radice)
  ripeti budget volte:
    nodo     <- SELEZIONE(radice)
    figlio   <- ESPANSIONE(nodo)
    esito    <- SIMULAZIONE(figlio.stato)
    BACKPROP(figlio, esito)
  return figlio_con_piu_visite(radice)

SELEZIONE(nodo):
  while nodo completamente espanso e non terminale:
    nodo <- argmax sui figli di UCT(figlio, nodo.N)
  return nodo

ESPANSIONE(nodo):
  if nodo terminale: return nodo
  azione <- una mossa legale non ancora tra i figli
  figlio <- nuovo nodo(applica azione a nodo.stato)
  aggiungi figlio ai figli di nodo
  return figlio

SIMULAZIONE(stato):
  while stato non terminale:
    stato <- applica una mossa legale a caso
  return esito(stato)          # es. +1 vittoria, 0 sconfitta

BACKPROP(nodo, esito):
  while nodo non nullo:
    nodo.N <- nodo.N + 1
    nodo.W <- nodo.W + esito_dal_punto_di_vista(nodo)
    nodo   <- nodo.genitore

Riga per riga. Il ciclo principale ripete le quattro fasi per tutto il budget. SELEZIONE scende finché trova un nodo da cui si può crescere — un nodo con mosse non ancora provate o uno stato di partita finita; a ogni passo prende il figlio che massimizza la formula UCT. ESPANSIONE aggiunge un figlio nuovo, l’unico punto in cui l’albero cresce. SIMULAZIONE gioca a caso fino alla fine e restituisce l’esito; non tocca l’albero. BACKPROP risale dal nodo nuovo alla radice aggiornando $N$ e $W$ di ognuno, con il segno dell’esito che dipende dal giocatore di turno a quel nodo. Alla fine si restituisce il figlio della radice col conteggio $N$ più alto.

Due proprietà strutturali emergono già da questo pseudocodice. La prima è il controllo della memoria: poiché ogni iterazione aggiunge esattamente un nodo, dopo $k$ iterazioni l’albero occupa spazio proporzionale a $k$ , indipendentemente da quanto sia profondo l’albero di gioco completo. È una differenza netta rispetto a BFS, dove la frontiera può esplodere esponenzialmente. La seconda è il comportamento anytime: il ciclo ripeti budget volte può essere interrotto in qualsiasi momento e l’albero resta in uno stato valido — le statistiche raccolte fino a quel punto sono coerenti, e figlio_con_piu_visite restituisce comunque una mossa sensata. Più iterazioni si concedono, più la stima si affina, ma non c’è un livello da “completare” come in alpha-beta. Per un programma che gioca a tempo, dove il budget per mossa cambia da situazione a situazione, questa graduale degradabilità è preziosa.

UCT: la tree policy

Resta da definire UCT, il cuore della fase di selezione. A ogni nodo, scegliere quale figlio seguire è un problema di multi-armed bandit: ogni figlio è una leva di cui non conosci il valore vero, lo stimi dai rollout passati, e devi decidere se puntare sul migliore osservato o provare uno incerto. Kocsis e Szepesvari hanno proposto di trapiantare su ogni nodo l’algoritmo di bandit UCB1 (Upper Confidence Bound 1, di Auer, Cesa-Bianchi e Fischer, 2002, vedi ucb-thompson). La formula di selezione: al nodo genitore con $n$ visite totali, si sceglie il figlio $j$ che massimizza

$\text{UCT}(j) = \bar{X}_j + C \sqrt{\frac{\ln n}{n_j}}$

Termine per termine. $\bar{X}_j$ è il valore medio del figlio $j$ : la somma dei valori dei rollout che lo hanno attraversato, divisa per il numero di quei rollout. Di norma è normalizzato in $[0, 1]$ — per esempio la frazione di vittorie. È il termine di exploitation: premia i figli che storicamente hanno reso bene.

$n_j$ è il numero di visite del figlio $j$ . $n$ è il numero di visite del genitore, quindi $n$ è la somma degli $n_j$ su tutti i figli — ogni volta che la selezione passa per il genitore, prosegue verso esattamente un figlio.

$C$ è la costante di esplorazione (chiamata anche $C_p$ ): regola quanto peso dare al secondo termine. Per ricompense in $[0, 1]$ un valore teoricamente motivato è $C = \sqrt{2}$ , ma in pratica si tara empiricamente sul dominio. È l’unico vero iperparametro dell’algoritmo base.

Il secondo termine, $C \sqrt{\ln n / n_j}$ , è il bonus di esplorazione. In parole povere: un figlio poco visitato — $n_j$ piccolo — riceve un bonus grande, quindi viene scelto anche se il suo valore medio è basso. Man mano che $n_j$ cresce, il denominatore cresce e il bonus si restringe: l’attenzione su quel figlio cala perché ormai lo si conosce.

Il numeratore $\ln n$ cresce con il totale delle visite, ma lentamente: garantisce che, dato abbastanza tempo, ogni figlio continui a ricevere qualche visita — nessuno viene abbandonato per sempre. La crescita logaritmica è la chiave: abbastanza rapida da non chiudere nessuna porta, abbastanza lenta da non sprecare quasi nulla sulle opzioni già scartate.

Geometricamente il bonus è la larghezza di un intervallo di confidenza sulla stima $\bar{X}_j$ : UCT sceglie il figlio con l’estremo superiore dell’intervallo più alto. È il principio “optimism in the face of uncertainty” — ottimismo davanti all’incertezza: agisci come se ogni opzione poco esplorata fosse buona quanto plausibilmente potrebbe essere, e se lo è davvero, lo scoprirai.

Kocsis e Szepesvari hanno dimostrato che UCT è consistente: al crescere del numero di simulazioni, la probabilità di scegliere alla radice una mossa sub-ottima tende a zero, e il valore stimato alla radice converge al valore minimax dell’albero — la risposta che darebbe la ricerca minimax esatta. Hanno anche derivato bound a campione finito sull’errore di stima.

La consistenza conta concettualmente: MCTS con UCT non è un’euristica fortunata, è un algoritmo con una garanzia asintotica. Con budget infinito gioca in modo perfetto. Il problema, come vedremo in “Dove si rompe”, è che “asintotico” può voler dire molto lontano: la garanzia dice che converge, non quanto in fretta.

Varianti ed estensioni

L’algoritmo base descritto sopra è il punto di partenza, non il punto di arrivo. La survey di Browne del 2012 cataloga decine di varianti; ne basta un assaggio per capire dove l’algoritmo si lascia migliorare.

Le default policy informate sostituiscono i rollout uniformemente casuali con simulazioni meno stupide: poche regole euristiche leggere — evitare mosse manifestamente perdenti, preferire pattern locali noti — che rendono il rollout un giocatore meno pessimo, al prezzo di renderlo più lento. È il compromesso che i programmi di Go pre-AlphaGo hanno affinato per anni.

Il progressive bias e il progressive widening intervengono sulla selezione e sull’espansione. Il primo aggiunge alla formula UCT un termine euristico che pesa di più quando le visite sono poche e svanisce quando aumentano: dà una direzione finché le statistiche sono ancora rumorose. Il secondo limita il numero di figli espansi a un nodo, lasciandolo crescere solo man mano che il nodo viene visitato — utile quando le azioni sono moltissime.

RAVE (Rapid Action Value Estimation) e la sua variante AMAF (All Moves As First) condividono informazione tra rami: l’idea è che una mossa buona in un punto dell’albero sia spesso buona anche altrove, quindi le statistiche di una mossa vengono aggregate su più nodi per dare stime utili prima di aver accumulato visite specifiche. Tutte queste varianti hanno lo stesso scopo: dare a MCTS un anticipo, perché l’algoritmo base parte da zero conoscenza a ogni nodo.

Perché i rollout casuali producono stime sensate

Una domanda lecita: perché una partita giocata a caso dovrebbe dire qualcosa sul valore di una posizione? Da sola, una singola partita casuale è quasi rumore.

Il punto è la media. Da una posizione $P$ faccio mille partite casuali e ne vinco 700: la frequenza $0{,}7$ è una stima Monte Carlo del valore di $P$ . Per la legge dei grandi numeri (vedi legge-grandi-numeri-clt) la media campionaria converge al valore atteso al crescere del numero di campioni, e per il teorema del limite centrale l’errore della stima si restringe come $1/\sqrt{m}$ , dove $m$ è il numero di rollout. Stimare una quantità difficile facendo molti esperimenti casuali e mediando: questo è il metodo Monte Carlo, ed è il motivo del nome MCTS.

Quel $1/\sqrt{m}$ ha una conseguenza pratica scomoda: per dimezzare l’errore di stima servono quattro volte più rollout. È un rendimento decrescente. È anche il motivo per cui la qualità della valutazione delle foglie conta tanto: una value network appresa che valuta una posizione in un colpo solo evita di dover spendere migliaia di rollout per ottenere la stessa precisione.

Una sottigliezza, che il capitolo deve rendere onesta. La stima Monte Carlo converge al valore della posizione sotto la default policy — cioè quando entrambi giocano a caso — non al valore di gioco perfetto. Un rollout uniformemente casuale è un giocatore pessimo. Ciò che rende MCTS forte non è la qualità del singolo rollout: è che la fase di selezione costruisce progressivamente un albero che approssima il gioco minimax. Vicino alla radice le mosse sono scelte da UCT, in modo quasi ottimo; solo nella coda profonda della simulazione si gioca a caso. Più simulazioni si fanno, più l’albero UCT cresce in profondità e più la componente casuale arretra. Il backup chiude il ciclo: una posizione che porta spesso a sconfitte vede il suo $\bar{X}$ scendere, UCT la visita meno, l’albero si concentra altrove. È questa asimmetria adattiva — non i rollout in sé — la fonte della forza.

Il confronto con il Monte Carlo “piatto” rende la cosa concreta. Monte Carlo piatto significa: dalla radice, per ogni mossa legale, fai un grande numero di rollout casuali, e scegli la mossa con la frequenza di vittoria media più alta. Niente albero, niente selezione adattiva. È esattamente la Monte Carlo Go di Brügmann del 1993, e ha un tetto basso: distribuisce il budget in modo uniforme tra tutte le mosse alla radice, e ogni rollout resta casuale dall’inizio alla fine. MCTS fa due cose in più, ed è da queste due che viene il salto di forza. Primo, concentra il budget: tramite UCT spende molti più rollout sulle mosse promettenti e quasi nessuno su quelle che hanno già fallito, quindi le stime delle mosse buone diventano molto più precise a parità di budget totale. Secondo, sostituisce progressivamente il caso con la ricerca: man mano che l’albero cresce in profondità, i primi passi di ogni simulazione non sono più casuali ma scelti da UCT, e solo la coda resta casuale. Il Monte Carlo piatto resta fermo al livello del 1993; MCTS, con gli stessi rollout casuali come materia prima, raggiunge il livello dilettante forte. La differenza non è nei rollout, è in cosa ci si costruisce sopra.

Esempi

Esempio 1 — Il calcolo di UCT, numeri alla mano

Un nodo genitore è stato visitato $n = 100$ volte. Ha tre figli, con queste statistiche dopo le iterazioni precedenti:

Figlio	Visite $n_j$	Valore medio $\bar{X}_j$
A	70	0.62
B	20	0.68
C	10	0.55

Quale figlio sceglie la selezione? Calcoliamo UCT per ciascuno, con $C = \sqrt{2} \approx 1{,}41$ e $\ln 100 \approx 4{,}61$ .

Figlio A: bonus $= 1{,}41 \cdot \sqrt{4{,}61 / 70} = 1{,}41 \cdot \sqrt{0{,}0659} = 1{,}41 \cdot 0{,}257 = 0{,}362$ . UCT $= 0{,}62 + 0{,}362 = 0{,}982$ .

Figlio B: bonus $= 1{,}41 \cdot \sqrt{4{,}61 / 20} = 1{,}41 \cdot \sqrt{0{,}231} = 1{,}41 \cdot 0{,}480 = 0{,}677$ . UCT $= 0{,}68 + 0{,}677 = 1{,}357$ .

Figlio C: bonus $= 1{,}41 \cdot \sqrt{4{,}61 / 10} = 1{,}41 \cdot \sqrt{0{,}461} = 1{,}41 \cdot 0{,}679 = 0{,}957$ . UCT $= 0{,}55 + 0{,}957 = 1{,}507$ .

Vince il figlio C, con il punteggio UCT più alto, $1{,}507$ . Eppure C ha il valore medio peggiore dei tre, $0{,}55$ . La selezione lo sceglie perché è il meno esplorato: solo 10 visite, quindi la sua stima è la più incerta e merita un controllo. Se invece guardassimo solo il valore medio sceglieremmo B.

Questo è il punto dell’esempio: nelle fasi iniziali UCT spinge verso le opzioni poco provate. Più avanti, quando C avrà accumulato visite, il suo bonus si ridurrà e la scelta si sposterà verso chi ha la media migliore. Il bonus è un correttivo temporaneo contro il rischio di abbandonare un’opzione giudicata male per pochi campioni sfortunati.

Si noti anche il figlio A: ha 70 visite e media $0{,}62$ , il punteggio UCT più basso dei tre. UCT lo sta di fatto mettendo da parte — non perché sia stato giudicato definitivamente cattivo, ma perché ormai lo si conosce bene e altre opzioni meritano attenzione. Se nelle prossime decine di iterazioni B e C confermassero medie inferiori a $0{,}62$ , il bonus di A — che cresce lentamente con $\ln n$ — finirebbe per riportarlo in gioco. Nessun ramo viene chiuso per sempre: questa è la differenza con una potatura definitiva.

Esempio 2 — MCTS in codice, su tic-tac-toe

Tic-tac-toe (filetto) è abbastanza piccolo da seguire, abbastanza grande da mostrare la meccanica. Lo stato è la griglia 3x3, le azioni le caselle libere, l’esito $+1$ se vince chi ha mosso per primo, $0$ altrimenti.

import math, random

class Nodo:
    def __init__(self, stato, genitore=None):
        self.stato = stato
        self.genitore = genitore
        self.figli = []
        self.N = 0          # visite
        self.W = 0.0        # somma valori
        self.azioni_da_provare = stato.mosse_legali()

def uct(figlio, n_genitore, C=1.41):
    if figlio.N == 0:
        return float('inf')          # un nodo mai visto va provato subito
    media = figlio.W / figlio.N
    bonus = C * math.sqrt(math.log(n_genitore) / figlio.N)
    return media + bonus

def selezione(nodo):
    while not nodo.azioni_da_provare and nodo.figli:
        nodo = max(nodo.figli, key=lambda f: uct(f, nodo.N))
    return nodo

def espansione(nodo):
    if not nodo.azioni_da_provare:
        return nodo                  # nodo terminale, niente da espandere
    azione = nodo.azioni_da_provare.pop()
    figlio = Nodo(nodo.stato.applica(azione), genitore=nodo)
    nodo.figli.append(figlio)
    return figlio

def simulazione(stato):
    stato = stato.copia()
    while not stato.finito():
        stato = stato.applica(random.choice(stato.mosse_legali()))
    return stato.esito()

def backprop(nodo, esito):
    while nodo is not None:
        nodo.N += 1
        nodo.W += esito if nodo.stato.turno_avversario() else (1 - esito)
        nodo = nodo.genitore

def mcts(stato_radice, budget):
    radice = Nodo(stato_radice)
    for _ in range(budget):
        nodo   = selezione(radice)
        figlio = espansione(nodo)
        esito  = simulazione(figlio.stato)
        backprop(figlio, esito)
    return max(radice.figli, key=lambda f: f.N).azione_che_porta_qui

Le quattro fasi sono le quattro chiamate dentro il ciclo for. Da notare il caso figlio.N == 0 in uct: un nodo mai visitato riceve punteggio infinito, così la selezione lo prova prima di confrontarlo con gli altri — è il modo standard di garantire che ogni figlio sia visitato almeno una volta. La riga di backprop con 1 - esito gestisce il cambio di prospettiva tra i due giocatori. Alla fine si restituisce la mossa che porta al figlio più visitato, non al figlio con $W/N$ più alto.

Esempio 3 — L’albero che cresce, iterazione dopo iterazione

Per vedere l’asimmetria emergere serve seguire le prime iterazioni a mano. Prendiamo una radice $R$ con tre mosse legali, $A$ , $B$ , $C$ . All’inizio l’albero è solo $R$ , con $N = 0$ .

Iterazione 1. Selezione: $R$ non è completamente espanso, ci si ferma subito. Espansione: si aggiunge $A$ . Simulazione: una partita casuale da $A$ , esito sconfitta, valore $0$ . Backpropagation: $A$ diventa $(N{=}1, W{=}0)$ , $R$ diventa $(N{=}1)$ . L’albero ha due nodi.

Iterazione 2. Selezione: $R$ ha ancora mosse non provate ( $B$ , $C$ ), ci si ferma a $R$ . Espansione: si aggiunge $B$ . Simulazione da $B$ : esito vittoria, valore $1$ . Backup: $B$ è $(1, 1)$ , $R$ è $(N{=}2)$ .

Iterazione 3. Si aggiunge $C$ . Simulazione: esito vittoria, valore $1$ . $C$ è $(1, 1)$ , $R$ è $(N{=}3)$ . Ora $R$ è completamente espanso: tutti e tre i figli esistono.

Iterazione 4. Selezione: $R$ è completamente espanso, quindi si applica UCT ai tre figli. $A$ ha media $0$ , $B$ e $C$ hanno media $1$ ; i bonus sono uguali perché tutti hanno $n_j = 1$ . Vince un figlio a media $1$ , diciamo $B$ . $B$ non è espanso: ci si ferma. Espansione: si aggiunge un figlio di $B$ , chiamiamolo $B_1$ . Simulazione da $B_1$ : esito sconfitta dal punto di vista di chi muove a $B$ . Backup: $B_1$ aggiornato, $B$ diventa $(2, ?)$ , $R$ diventa $(N{=}4)$ .

Il punto da cogliere: dopo poche iterazioni l’albero non è bilanciato. $A$ , che ha perso al primo rollout, ha media $0$ e riceverà visite solo quando il suo bonus di esplorazione lo riporterà in gioco; resta un moncone. $B$ e $C$ , che hanno vinto, attirano le iterazioni successive e crescono in profondità. Se andassimo avanti mille iterazioni vedremmo una guglia profonda sotto il ramo che continua a rendere, e cespugli bassi altrove. Nessuno ha programmato questa forma: emerge dal ciclo selezione-backup. È lo scultore dell’Angolo 2, osservato al rallentatore.

Esempio 4 — AlphaGo: rimpiazzare il caso con reti neurali

MCTS classico ha due punti deboli evidenti su un gioco come il Go. La selezione, all’inizio, esplora tutte le mosse legali quasi alla cieca — ma le mosse legali sono centinaia, e la maggior parte è ovviamente cattiva a un occhio esperto. E i rollout casuali sono un giocatore pessimo: in Go una partita giocata a caso fino alla fine dice pochissimo.

Detto altrimenti, MCTS base spreca calcolo in due punti. Spreca esplorando mosse che un giocatore esperto scarterebbe a colpo d’occhio, e spreca valutando le foglie con rollout casuali invece che con un giudizio informato. Entrambi gli sprechi vengono dal fatto che l’algoritmo base non ha conoscenza pregressa: parte da zero.

AlphaGo sostituisce entrambi i pezzi con reti neurali apprese. Una policy network stima, per ogni posizione, una distribuzione di probabilità sulle mosse buone: invece di esplorare alla cieca, la selezione parte con un prior che concentra le visite sulle mosse plausibili. Una value network stima direttamente la probabilità di vittoria da una posizione, senza giocare la partita fino in fondo: sostituisce in larga parte il rollout casuale.

La formula di selezione diventa una variante chiamata PUCT (Predictor + UCT), in cui il bonus di esplorazione è pesato dalla probabilità a priori $P(s, a)$ data dalla policy network. In forma schematica il bonus è proporzionale a

$P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}$

dove $P(s,a)$ è il prior della policy network, $N(s)$ le visite del nodo e $N(s,a)$ le visite del ramo dell’azione $a$ . L’effetto: l’esplorazione non è più uniforme tra i figli, ma indirizzata verso le mosse che la rete ritiene promettenti. Confrontata con la formula UCT classica, la differenza è che il bonus non dipende solo da quanto un ramo è stato visitato, ma anche da quanto la rete lo ritiene a priori promettente.

AlphaZero, due anni dopo, fa un passo ulteriore: elimina del tutto i rollout casuali — la value network basta a valutare le foglie — e impara le reti da zero, solo giocando contro sé stesso. Lo schema concettuale resta quello di Coulom e di Kocsis-Szepesvari; cambiano le euristiche che lo guidano, che da casuali diventano apprese. È la differenza tra uno scultore bendato e uno che vede: lo scalpello — MCTS — è lo stesso.

C’è una conseguenza che vale la pena esplicitare. In AlphaGo le quattro fasi restano le stesse — selezione, espansione, simulazione, backpropagation — e la consistenza asintotica di UCT non viene persa. Ciò che cambia è il punto di partenza: invece di partire da zero conoscenza e accumularla rollout dopo rollout, MCTS parte con un prior della policy network che è già un buon giocatore, e una valutazione delle foglie che è già accurata. La ricerca non costruisce la conoscenza, la raffina. Vista da questa angolazione, MCTS in AlphaGo è un amplificatore: prende una rete neurale che gioca discretamente e, spendendo calcolo in ricerca, ne produce una mossa migliore di quella che la rete da sola sceglierebbe. Questo amplificatore è anche il motore dell’addestramento: in self-play, la mossa scelta da MCTS è un bersaglio migliore di quella della rete grezza, e la rete viene addestrata a imitare la propria versione potenziata dalla ricerca. È un ciclo in cui ricerca e apprendimento si tirano a vicenda.

Esempio 5 — La trappola che MCTS non vede

Un esempio costruito per illuminare il limite. Immagina una posizione di scacchi in cui il bianco ha una sola mossa che pareggia — un preciso scacco perpetuo — e ogni altra mossa perde rapidamente. La mossa salvifica richiede una sequenza forzata di sei semimosse esatte: una deviazione qualsiasi e il pareggio svanisce.

MCTS con rollout casuali da questa posizione fa quasi sempre rollout che, lungo la sequenza forzata, sbagliano almeno una mossa — i rollout giocano a caso, e la probabilità di azzeccare sei mosse precise di fila a caso è minuscola. Quindi la frequenza di vittoria stimata per la mossa salvifica sarà bassissima: MCTS la giudicherà cattiva quanto le altre, o peggio, e non le darà priorità. Un programma alpha-beta con una valutazione decente, invece, esplora la sequenza forzata in modo sistematico fino in fondo e trova il pareggio.

Questo non contraddice la consistenza di UCT. Dato budget sufficiente, l’albero UCT crescerebbe lungo la sequenza forzata, le mosse a caso arretrerebbero, e il pareggio verrebbe trovato. Ma “budget sufficiente” qui può significare un numero di iterazioni proibitivo, perché la trappola è stretta e profonda. L’esempio mostra il regime in cui MCTS soffre: tattica forzata, dove una sola linea conta e i rollout casuali la mancano sistematicamente. È il motivo per cui, prima che le value network rimpiazzassero i rollout, MCTS puro non ha mai dominato gli scacchi come ha dominato il Go.

Applicazioni pratiche

Giochi. È il dominio nativo. Go, scacchi e shogi con AlphaZero; general game playing, dove un programma deve giocare a giochi che non ha mai visto, descritti da regole formali, e non può quindi avere euristiche pre-scritte — MCTS è perfetto perché non ne richiede. Per i giochi a informazione imperfetta (carte, dove non vedi la mano avversaria) esistono varianti come ISMCTS (Information Set MCTS).

Planning e decisione sotto incertezza. MCTS è formulato per i Markov Decision Process (vedi markov-decision-process): ovunque ci sia un albero di decisione grande e un simulatore che, dato uno stato e un’azione, restituisce lo stato successivo, MCTS si applica. Scheduling, pianificazione robotica di traiettorie, ottimizzazione combinatoria, controllo di processi. Il requisito pratico è uno solo, ma stringente: serve un modello del mondo — un simulatore — su cui fare i rollout. Quando il simulatore non esiste o è troppo costoso da eseguire, MCTS non parte: è un metodo basato su simulazione, e senza simulazione non ha materia prima.

Reasoning dei modelli linguistici. Dal 2023 la ricerca ad albero è entrata nel reasoning degli LLM. Tree of Thoughts e le varianti che usano esplicitamente MCTS sul ragionamento — con il modello come policy che genera i passi e un reward model come funzione di valutazione — sono un’area di ricerca attiva. Il punto in dettaglio sotto.

Agenti. Un agente che deve pianificare una sequenza di azioni con tool, e che può simulare gli esiti delle proprie azioni, può usare MCTS per cercare nel proprio spazio di piani: ogni nodo è uno stato del task, ogni azione un tool call, l’esito un giudizio sul completamento. La difficoltà pratica è proprio il simulatore: simulare l’effetto di un tool call sul mondo reale è spesso impossibile a costo ragionevole — eseguire il comando è l’unico modo di sapere cosa fa. Per questo MCTS sugli agenti resta una direzione di sperimentazione più che una pratica consolidata; funziona meglio dove gli esiti delle azioni sono prevedibili o reversibili.

Il ponte verso il reasoning degli LLM

Negli anni 2023-2026 l’idea di “cercare in un albero invece di generare una singola sequenza” è arrivata al ragionamento dei modelli linguistici. Qui serve disciplina: distinguere ciò che è documentato da ciò che è analogia o speculazione.

Ciò che è documentato. Tree of Thoughts (Yao et al., NeurIPS 2023, Tree of Thoughts: Deliberate Problem Solving with Large Language Models) generalizza il chain-of-thought, la tecnica per cui un LLM produce passaggi intermedi di ragionamento prima della risposta. Invece di un’unica catena lineare, l’LLM genera un albero di “thought” — ogni nodo è un passo di ragionamento intermedio — ne valuta i nodi usando il modello stesso come giudice, e percorre l’albero con BFS o DFS, con la possibilità di guardare avanti e tornare indietro.

Su Game of 24, un rompicapo aritmetico, GPT-4 con chain-of-thought risolve il 4% dei problemi; con Tree of Thoughts il 74%. È un salto grosso, e viene dalla stessa intuizione di MCTS: cercare batte indovinare quando il problema ha la forma di un albero.

Tree of Thoughts nella sua forma originale usa BFS e DFS, non MCTS. Ma la struttura del problema è la stessa di MCTS: stato uguale ragionamento parziale, azione uguale prossimo passo, valutazione uguale giudizio del modello. Lavori successivi hanno applicato MCTS in modo esplicito al reasoning, con il modello come policy e un process reward model — un valutatore addestrato a giudicare i singoli passi di un ragionamento — come funzione di valutazione. È un filone con paper espliciti.

Ciò che è analogia, non filiazione documentata. L’idea di spendere più calcolo al momento dell’inferenza per ottenere risposte migliori si chiama test-time compute, o inference-time scaling. I modelli “o1-style” — o1 di OpenAI, rilasciato a fine 2024, e i thinking model successivi tra cui DeepSeek-R1 — producono lunghe catene di ragionamento prima della risposta, e la loro qualità scala con il calcolo speso all’inferenza. Che questi modelli scalino con il test-time compute è documentato. Che il loro meccanismo interno sia MCTS non lo è: i laboratori non hanno pubblicato l’architettura di o1, e molte fonti divulgative ipotizzano un legame con la ricerca ad albero, ma resta ipotesi. Il legame onesto da fare è concettuale, e va marcato come tale: MCTS è l’esempio canonico di come trasformare calcolo in qualità tramite ricerca, e il reasoning a test-time è la stessa idea applicata a un dominio diverso — lo spazio dei ragionamenti invece dello spazio delle mosse di gioco. È analogia di principio, non discendenza architetturale dimostrata. Affermare “o1 è MCTS sotto il cofano” significa scambiare un’analogia per un fatto.

MCTS contro minimax e alpha-beta

MCTS e la ricerca minimax (vedi minimax) attaccano lo stesso problema — scegliere la mossa migliore in un albero di gioco — con filosofie opposte. Vale la pena allinearle punto per punto, perché la scelta tra le due non è una questione di moda ma di proprietà del dominio.

Valutazione delle posizioni. Minimax con potatura alpha-beta esplora l’albero fino a una profondità limite, poi valuta le posizioni raggiunte con una funzione euristica. Quella funzione è il prerequisito: senza, alpha-beta è cieco al limite di profondità. MCTS non la richiede — la sostituisce con i rollout — oppure, nella versione AlphaGo, con una value network appresa. Questo è il discrimine storico tra scacchi e Go: per gli scacchi la funzione euristica esisteva, per il Go no.

Forma dell’esplorazione. Alpha-beta esplora a profondità sostanzialmente uniforme: con iterative deepening completa il livello $d$ , poi il $d+1$ , e la potatura taglia i rami provatamente inutili ma senza concentrare lo sforzo in modo adattivo sui rami promettenti. MCTS costruisce un albero asimmetrico: profondo dove le statistiche dicono “qui si decide”, superficiale altrove. Per branching factor alto questa selettività è decisiva — esplorare uniformemente 250 rami per livello è insostenibile.

Comportamento anytime. Alpha-beta a profondità $d$ deve completare il livello $d$ per dare una risposta affidabile: interrotto a metà livello, la sua stima è inconsistente. MCTS è genuinamente anytime: ogni iterazione in più affina marginalmente le statistiche, e fermarsi in qualsiasi momento restituisce la migliore mossa trovata finora. Per i giochi a tempo, dove il budget per mossa varia, è una proprietà comoda.

Garanzie. Alpha-beta con una funzione di valutazione esatta restituisce la mossa ottima entro l’orizzonte di ricerca — è una garanzia forte ma locale all’orizzonte. UCT garantisce ottimalità solo asintotica: con budget infinito converge al valore minimax, con budget finito può sbagliare. Nessuna delle due “vince” in assoluto.

Quando scegliere cosa. Dominio con buona euristica di valutazione e branching factor moderato — scacchi, dama: alpha-beta resta competitivo o superiore. Dominio con branching factor alto e nessuna euristica forte — Go: MCTS domina. I sistemi più forti al 2026 non scelgono: combinano. AlphaZero usa MCTS come scheletro ma con una value network che svolge il ruolo della funzione di valutazione di alpha-beta; alcuni motori di scacchi recenti innestano idee MCTS dentro architetture nate da alpha-beta. La distinzione netta tra i due mondi è più una comodità didattica che una frontiera tecnologica.

Dove si rompe

MCTS non è un algoritmo universale. I suoi limiti sono istruttivi quanto i suoi meccanismi.

Le trappole tattiche strette. È il fallimento classico, già anticipato nell’Esempio 5. Considera una posizione dove una sola mossa specifica salva la partita, e tutte le altre perdono. I rollout casuali, da quella posizione, quasi mai trovano la sequenza salvifica per puro caso: la frequenza di vittoria stimata sarà bassa, e MCTS giudicherà la posizione peggiore di quanto sia.

Negli scacchi, dove le linee tattiche forzate sono frequenti, MCTS puro con rollout casuali è notoriamente debole proprio per questo — è uno dei motivi per cui i motori di scacchi sono rimasti a lungo basati su alpha-beta. La consistenza di UCT garantisce che, con abbastanza tempo, l’albero crescerà fino a trovare la mossa giusta; ma “abbastanza tempo” può essere proibitivo.

La consistenza è solo asintotica. UCT converge al gioco perfetto, ma il numero di simulazioni necessarie cresce molto con il branching factor e con la profondità delle trappole. Con un budget finito — e ogni budget reale è finito — MCTS può scegliere la mossa sbagliata. La garanzia teorica rassicura sul lungo termine ma non dice nulla su quanto bene si gioca con un milione di rollout invece di un miliardo.

La default policy conta, e tararla è un’arte. Il rollout uniformemente casuale è il caso peggiore. I programmi di Go forti pre-AlphaGo non usavano rollout puramente casuali: usavano default policy “pesanti”, con piccole regole euristiche che rendevano le partite simulate più realistiche.

Ma una default policy più informata è anche più lenta — meno rollout per secondo — e può introdurre bias sistematici: se la regola euristica sbaglia in modo consistente, tutte le simulazioni ereditano lo stesso errore, e mediare non lo corregge. Il bilanciamento tra qualità e velocità del rollout è delicato e dipende dal dominio. È uno dei motivi per cui AlphaZero ha eliminato del tutto i rollout: una value network appresa è più affidabile di qualsiasi default policy scritta a mano.

La costante di esplorazione $C$ va tarata. Il valore teorico $\sqrt{2}$ vale per ricompense esattamente in $[0,1]$ e sotto ipotesi che il dominio reale spesso viola. In pratica $C$ è un iperparametro: troppo basso e MCTS sfrutta troppo presto, restando incollato a una mossa che sembrava buona; troppo alto ed esplora troppo, diluendo il budget su rami inutili. Non c’è un valore giusto universale.

Spazio delle azioni grande o continuo. MCTS nella forma base assume un insieme finito e non troppo grande di azioni a ogni nodo. Con migliaia di azioni per stato la fase di espansione fatica a coprirle: il budget si esaurisce prima ancora di aver provato ogni figlio una volta sola.

Con azioni continue — un angolo di sterzo, una forza da applicare — la formulazione base non si applica affatto, perché i figli sarebbero infiniti. Servono varianti dedicate, come il progressive widening, che limitano artificialmente quante azioni considerare e le aumentano solo man mano che il nodo viene visitato.

Non parallelizza in modo banale. Far girare più simulazioni in parallelo è desiderabile, ma due rollout simultanei vedono statistiche non ancora aggiornate dall’altro, e tendono a esplorare lo stesso ramo — il parallelismo si mangia da solo, perché tutti i thread imboccano la stessa strada.

Esistono soluzioni — virtual loss (penalizzare temporaneamente un ramo appena imboccato da un altro thread), parallelizzazione a livello di albero o di radice — ma introducono ciascuna un compromesso tra fedeltà alle statistiche e velocità, e nessuna è gratis.

Restano alcuni fraintendimenti tipici da sfatare, quelli che ricorrono quando si racconta MCTS in modo sbrigativo.

“Il rollout casuale gioca bene.” No: un rollout uniformemente casuale è un giocatore pessimo. La forza di MCTS viene dall’aggregazione di molti rollout e soprattutto dalla fase di selezione UCT che costruisce un albero quasi-minimax. Confondere “MCTS è forte” con “i rollout casuali sono buoni” porta a conclusioni sbagliate sul perché funziona.

“Si sceglie il figlio col valore medio più alto.” Di norma no: si sceglie il figlio più visitato, il most-robust child. Il valore medio di un figlio poco visitato è una stima rumorosa, alta talvolta per fortuna; il conteggio visite riflette la scommessa cumulativa dell’algoritmo ed è più stabile. Esistono varianti che decidono per valore o per una combinazione, ma il default è il conteggio.

“MCTS converge al gioco perfetto in fretta.” La consistenza di UCT è asintotica. Con budget finito MCTS può sbagliare, e la convergenza al minimax richiede un numero di iterazioni che cresce molto con il branching factor e la profondità delle trappole. “Garanzia di convergenza” non significa “convergenza rapida”.

“Il test-time compute degli LLM è MCTS.” Non documentato. Il test-time scaling dei modelli o1-style è documentato come fenomeno; il loro meccanismo interno non è pubblicato. MCTS sul reasoning esiste come filone con paper espliciti, ma identificarlo col funzionamento di o1 è speculazione.

“UCB1 e epsilon-greedy sono la stessa esplorazione.” No. Epsilon-greedy esplora a caso con probabilità fissa $\epsilon$ , ignorando quanto un’opzione sia incerta. UCB1 esplora in modo mirato: più bonus alle opzioni meno provate, e bonus che svanisce man mano che i dati arrivano. È esplorazione guidata dall’incertezza, non casuale.

Collegamenti

search-bfs-dfs — BFS e DFS esplorano l’albero in modo cieco e sistematico; MCTS lo esplora guidato dalle statistiche dei rollout. Utile contrapporre i due regimi.
search-a-star — A* guida la ricerca con un’euristica ammissibile data a priori; MCTS sostituisce l’euristica con le simulazioni. Stesso problema, strategie opposte.
search-ida-star — IDA* e MCTS sono entrambe risposte all’albero che non sta in memoria: IDA* rivede i nodi con budget crescente, MCTS costruisce solo la parte promettente.
minimax — il confronto centrale: MCTS contro minimax e alpha-beta, quando ognuno vince e quando perde.
multi-armed-bandits — la fase di selezione di MCTS è un problema di bandit a ogni nodo; il trade-off esplorazione/sfruttamento nasce qui.
ucb-thompson — UCB1, l’algoritmo di bandit che UCT trapianta su ogni nodo dell’albero.
markov-decision-process — MCTS è formalmente planning su un MDP; questo capitolo dà il framework.
legge-grandi-numeri-clt — perché mediare molti rollout casuali produce una stima sensata, e a che velocità l’errore si restringe.
alphago-2016 — la storia di AlphaGo, dove MCTS incontra il deep learning e il Go cade.

Per andare oltre

Coulom R. — “Efficient Selectivity and Backup Operators in Monte-Carlo Tree Search” (Computers and Games 2006). Il paper che conia il termine MCTS e introduce la costruzione incrementale dell’albero.
Kocsis L., Szepesvari C. — “Bandit based Monte-Carlo Planning” (ECML 2006). Il paper di UCT: la tree policy basata su UCB1, con la dimostrazione di consistenza.
Browne C. et al. — “A Survey of Monte Carlo Tree Search Methods” (IEEE Transactions on Computational Intelligence and AI in Games, 2012). La survey di riferimento: definisce le quattro fasi in modo canonico e mappa decine di varianti.
Silver D. et al. — “Mastering the game of Go with deep neural networks and tree search” (Nature, 2016). Il paper di AlphaGo: MCTS guidato da policy e value network.
Yao S. et al. — “Tree of Thoughts: Deliberate Problem Solving with Large Language Models” (NeurIPS 2023). La ricerca ad albero applicata al reasoning dei modelli linguistici.