Ricerca ad albero Monte Carlo

La ricerca ad albero Monte Carlo, abbreviata MCTS, non cerca di esaminare ogni variante alla stessa profondità. Fa crescere gradualmente un albero e usa i risultati accumulati per scegliere dove destinare la successiva porzione di calcolo. Una mossa visitata molte volte non è automaticamente buona, ma la sua stima è normalmente sostenuta da una ricerca più ampia.

Un ciclo MCTS

1. Selezione: si parte dalla posizione iniziale e si seguono i rami esistenti, bilanciando mosse che sembrano già forti con mosse ancora incerte.
2. Espansione: si aggiunge una posizione o una mossa che l’albero non aveva ancora sviluppato.
3. Valutazione: si stima il risultato dalla nuova posizione. I metodi classici possono completare partite simulate, mentre i sistemi moderni possono usare una rete neurale, cioè un modello addestrato a riconoscere schemi, per valutarla.
4. Retropropagazione: il risultato viene riportato lungo il percorso visitato, aggiornandone il numero di visite e le stime.

La ripetizione di questo ciclo bilancia sfruttamento ed esplorazione. Sfruttare significa dedicare più risorse alle zone in cui le prove sono già favorevoli. Esplorare significa verificare alternative incerte affinché una sorpresa non venga scartata troppo presto. La regola esatta che bilancia i due aspetti dipende dall’implementazione.

A differenza di minimax, MCTS decide comunemente quanto approfondire un ramo in base alle informazioni raccolte durante la ricerca, non soltanto a una profondità uniforme. In alcuni programmi scacchistici basati su reti neurali, una rete fornisce una policy, che suggerisce mosse probabili, e un value, che stima il risultato. Il value svolge un ruolo collegato a una funzione di valutazione, anche se il processo di ricerca complessivo è diverso.