Licenza YOLO
Torna al glossario di Ultralytics

Monte Carlo Tree Search (MCTS)

La ricerca ad albero Monte Carlo (MCTS) sceglie le azioni costruendo un albero di ricerca a partire da simulazioni, concentrandosi sulle mosse promettenti. È usata in AlphaGo e nei robot.

La ricerca ad albero Monte Carlo (MCTS) è un algoritmo di pianificazione che sceglie l'azione successiva costruendo un albero di possibili futuri a partire da molte simulazioni, assegnando una parte maggiore del budget alle mosse che sembrano più promettenti. Richiede soltanto un modo per generare mosse legali ed esiti, per esempio le regole di un gioco o un simulatore, e non una funzione di valutazione scritta a mano. È anche un algoritmo anytime: interromperlo in qualsiasi momento restituisce la migliore mossa trovata fino a quel momento, e più tempo produce una risposta migliore. Rémi Coulom ha dato un nome al metodo nel 2006, lo stesso anno in cui Levente Kocsis e Csaba Szepesvári hanno pubblicato UCT, la regola di selezione diventata la forma standard del metodo. In pochi anni MCTS ha trasformato il Go giocato al computer, ha poi alimentato AlphaGo e AlphaZero e oggi viene usata per pianificare il comportamento di robot e veicoli e per esplorare passaggi di ragionamento nei modelli linguistici di grandi dimensioni (LLM).

Come funziona MCTS#

La ricerca mantiene un albero la cui radice è la posizione corrente e i cui nodi memorizzano quante volte sono stati visitati e quante di queste visite hanno portato a una vittoria. Ogni iterazione comprende quattro fasi:

  1. Selezione: Partendo dalla radice, si scende attraverso i nodi completamente esplorati scegliendo il figlio con il punteggio UCT più alto, che bilancia percentuali di vittoria elevate e mosse provate di rado.
  2. Espansione: Al primo nodo con una mossa non ancora provata, la si aggiunge come nuovo figlio.
  3. Simulazione: Dal nuovo figlio si simula la partita fino alla fine, tradizionalmente con mosse casuali, per ottenere un risultato.
  4. Retropropagazione: Si risale lungo il percorso e si aggiornano per ogni nodo il numero di visite e il totale delle vittorie in base al risultato.

Quando il budget si esaurisce, l'algoritmo gioca la mossa figlia della radice più visitata, una scelta più stabile rispetto a quella con la media più alta.

Bilanciare esplorazione e sfruttamento#

UCT considera la scelta in ogni nodo come un problema del bandito a più bracci e applica la formula UCB1: il punteggio di un figlio è il suo tasso di vittoria w/n più c·√(ln N / n), dove n è il numero di visite del figlio, N quello del genitore e c è una costante di esplorazione, pari a √2 in teoria e calibrata nella pratica. Il secondo termine diminuisce man mano che una mossa viene provata più spesso, così una mossa con poche vittorie fortunate non può escludere tutte le altre e una mossa trascurata viene prima o poi rivalutata.

Questo esempio Python esegue MCTS su un piccolo gioco: i giocatori prendono da uno a tre sassi da un mucchio di 10 e vince chi prende l'ultimo.

import math
import random

# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {}  # visits and wins per node; a node is the sequence of pile sizes from the root


def rollout(stones):
    """Play random moves to the end and return 1 if the player to move wins."""
    turn = 0
    while stones:
        stones -= random.randint(1, min(3, stones))
        turn ^= 1
    return turn


def search(node):
    """Run one MCTS iteration below a node and return 1 if the player to move there wins."""
    if node[-1] == 0:
        return 0  # the opponent took the last stone
    children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
    unvisited = [c for c in children if c not in N]
    if unvisited:  # expansion, then simulation
        child = random.choice(unvisited)
        N[child], W[child] = 0, 0
        result = 1 - rollout(child[-1])
    else:  # selection by UCT, balancing win rate against how rarely a child was tried
        child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
        result = 1 - search(child)
    N[child] += 1  # backpropagation, with wins counted for the player who moved into the child
    W[child] += result
    return result


for _ in range(2000):
    search((10,))
    N[(10,)] += 1
for take in (1, 2, 3):
    child = (10, 10 - take)
    print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")

Prendere due sassi riceve 1.889 delle 2.000 visite e vince il 91% delle simulazioni, contro le 68 visite per prenderne uno e le 43 per prenderne tre. È la mossa vincente: lasciando 8, un multiplo di 4, il primo giocatore può rispondere a ogni mossa ripristinando un multiplo di 4 finché il mucchio non è vuoto. La ricerca l'ha trovata basandosi soltanto su simulazioni casuali e statistiche delle visite, senza alcuna strategia codificata.

Da AlphaGo ad AlphaZero e MuZero#

Il fattore di ramificazione medio del Go, circa 250 mosse legali contro le circa 35 degli scacchi, lo rendeva al di là delle possibilità di una ricerca esaustiva; dalla fine degli anni 2000 in poi, MCTS ha guidato i progressi nella forza dei programmi di Go. AlphaGo di DeepMind guidava MCTS con una rete di policy che proponeva le mosse probabili e valutava le posizioni sia con una rete di valore sia con simulazioni rapide, e nel marzo 2016 ha battuto Lee Sedol per 4-1. AlphaZero e MuZero sono andati oltre. AlphaZero ha eliminato del tutto le simulazioni, ha valutato le posizioni foglia con una rete di valore e l'ha addestrata sulle partite giocate contro sé stessa, usando i conteggi delle visite di ogni ricerca come obiettivo per la sua rete di policy; in questo modo MCTS diventa un passaggio di miglioramento della policy nell'apprendimento per rinforzo. MuZero ha eseguito la stessa ricerca all'interno di un modello appreso dell'ambiente, giocando così a Go, scacchi, shogi e giochi Atari senza averne ricevuto le regole.

MCTS per la pianificazione e il ragionamento#

Robot e veicoli autonomi usano MCTS per pianificare in situazioni incerte, come l'immissione nel traffico; varianti come POMCP la estendono ai processi decisionali di Markov parzialmente osservabili, tracciando una distribuzione di credenze sugli stati nascosti. Una ricerca che pianifica a partire da immagini della fotocamera ha bisogno di uno stato iniziale: per esempio, un braccio robotico che gioca a scacchi può usare un modello Ultralytics YOLO26 addestrato su immagini della scacchiera per individuare ogni pezzo; la posizione ricostruita diventa la radice della ricerca.

Nel ragionamento degli LLM, ogni nodo è una soluzione parziale e ogni arco un passaggio del ragionamento; un modello di ricompensa del processo o una verifica della risposta assegna un punteggio ai rami. rStar-Math di Microsoft ha usato MCTS con un modello di preferenza del processo per portare Qwen2.5-Math-7B dal 58,8% al 90,0% nel benchmark MATH. Tree of Thoughts esplora invece i passaggi di ragionamento con una ricerca in ampiezza o in profondità. MCTS è stato più difficile da usare durante l'addestramento: DeepSeek lo ha annoverato tra i tentativi non riusciti per DeepSeek-R1, perché lo spazio delle sequenze di token è molto più ampio di quello di un gioco da tavolo e il modello di valore che guida la ricerca è difficile da addestrare. Ha invece addestrato R1 con l'apprendimento per rinforzo con ricompense verificabili.

Esplora le soluzioni

La visione artificiale nello sport

La visione artificiale nello sport

Scopri come Ultralytics YOLO alimenta la computer vision nello sport con il tracciamento di giocatori e palloni, l'analisi delle prestazioni, gli approfondimenti per gli allenatori e la riabilitazione degli atleti.
Scopri di più
Computer vision per immagini aeree

Computer vision per immagini aeree

Trasforma immagini aeree e riprese da drone in informazioni utili in tempo reale per agricoltura, acquacoltura, conservazione e analisi geospaziale con Ultralytics YOLO.
Scopri di più
Computer vision nel settore aerospaziale

Computer vision nel settore aerospaziale

Applica la visione artificiale nel settore aerospaziale con Ultralytics YOLO per l'ispezione degli aeromobili, il rilevamento di FOD sulle piste, le operazioni di terra aeroportuali e il rilevamento di difetti nei materiali compositi.
Scopri di più
Visione artificiale nella sicurezza

Visione artificiale nella sicurezza

Proteggi ogni sito con i modelli Ultralytics YOLO. L'IA visiva alimenta il monitoraggio perimetrale, il rilevamento delle minacce, il riconoscimento delle targhe e la sicurezza sul lavoro.
Scopri di più
Visione artificiale nella robotica

Visione artificiale nella robotica

Dai più potenza alle macchine intelligenti con i modelli Ultralytics YOLO. Nell'ambito della robotica, l'IA visiva alimenta la navigazione autonoma, la percezione, il tracciamento degli oggetti e il controllo in tempo reale.
Scopri di più
Visione artificiale nella logistica

Visione artificiale nella logistica

Semplifica la logistica con i modelli Ultralytics YOLO. L'IA per la visione consente l'ispezione dei pacchi, la selezione, il tracciamento dei veicoli e il monitoraggio della sicurezza nei magazzini in tempo reale.
Scopri di più
Visione artificiale nel commercio al dettaglio

Visione artificiale nel commercio al dettaglio

Ripensa il commercio al dettaglio con i modelli Ultralytics YOLO. L'IA per la visione consente di tracciare le scorte, monitorare gli scaffali, gestire le code e ottenere informazioni più approfondite sui clienti.
Scopri di più
Visione artificiale in ambito sanitario

Visione artificiale in ambito sanitario

Crea soluzioni sanitarie con i modelli Ultralytics YOLO. In ambito sanitario, l'IA per la visione consente di elaborare più rapidamente le immagini mediche, migliorare la diagnostica e monitorare i pazienti.
Scopri di più
Computer vision nella produzione

Computer vision nella produzione

Ottimizza la produzione con i modelli Ultralytics YOLO. La visione basata sull'IA migliora il controllo qualità, il rilevamento dei difetti, la conformità ai requisiti sui DPI e l'automazione delle linee di assemblaggio.
Scopri di più
Computer vision nel settore automobilistico

Computer vision nel settore automobilistico

Applica la computer vision al settore automobilistico con i modelli Ultralytics YOLO. La visione basata sull'IA migliora la sicurezza stradale, i sistemi di assistenza alla guida e l'automazione dei veicoli, per strade più intelligenti.
Scopri di più
Visione artificiale in agricoltura

Visione artificiale in agricoltura

Porta l'IA visiva nell'agricoltura intelligente con i modelli Ultralytics YOLO. Gestisci il monitoraggio delle colture, il tracciamento del bestiame e l'agricoltura di precisione per ottenere raccolti più abbondanti e intelligenti.
Scopri di più

Costruiamo insieme il futuro dell'IA!

Inizia il tuo percorso verso il futuro del machine learning