Il prossimoProssima guida
Catena Markov Monte Carlo
Tecnico
GUIDA TECNICA
Monte Carlo Tree Search (MCTS) è un algoritmo di pianificazione che decide la mossa migliore costruendo selettivamente un albero di ricerca e simulando molti futuri possibili.
Ascolta questa guidaNarrato dall'IA · ~2 min
It powered breakthroughs like AlphaGo and excels in games with enormous numbers of possible positions.
MCTS trova decisioni forti senza esaminare in modo esaustivo ogni possibilità. Si ripete quattro passaggi migliaia di volte: Selezione (scendere dall'albero esistente utilizzando una regola che bilancia le mosse promettenti con quelle poco esplorate), Espansione (aggiungere un nuovo nodo figlio su una foglia), Simulazione o 'lancio' (giocare il gioco fino a un risultato, storicamente con mosse casuali o euristiche) e Backpropagation (spingere indietro il risultato, aggiornando i conteggi delle vittorie e delle visite lungo il percorso). Nel corso di molte iterazioni l'albero cresce in modo asimmetrico, concentrando gli sforzi sulle linee più promettenti. La mossa scelta è solitamente il figlio root visitato più spesso. Il suo punto di forza è essere "in qualsiasi momento" e in gran parte indipendente dal dominio: funziona solo in base alle regole del gioco, migliorando man mano che viene speso più calcolo.
AlphaGo e AlphaZero padroneggiano Go, scacchi e shogi combinando MCTS con le reti neurali
Motori di gioco generali per giochi da tavolo come Hex, Othello e Settlers of Catan
Pianificazione della retrosintesi in chimica, ricerca di alberi di reazione per sintetizzare molecole bersaglio
Guidare il ragionamento in più fasi o la generazione di codice nei moderni sistemi LLM ricercando i passaggi candidati
MCTS è sempre più fuso con il deep learning, come in AlphaZero e MuZero, quest'ultimo apprende il proprio modello di ambiente in modo che MCTS possa pianificare senza che gli vengano date delle regole. Oltre ai giochi da tavolo, si sta diffondendo alla pianificazione, alla pianificazione della sintesi chimica, alla dimostrazione di teoremi e come strato deliberato di "ragionamento basato sulla ricerca" su ampi modelli linguistici per migliorare la risoluzione dei problemi in più fasi.
Newsletter gratuita
Tre storie verificate sull'IA ogni mattina nei giorni feriali, scritte in un inglese semplice. Gratuito per sempre, senza pubblicità.
Un'email ogni giorno feriale. Disiscriviti con un clic. Non vendiamo né condividiamo mai il tuo indirizzo.
Mettiti alla prova
Feedback immediato su ogni risposta e un certificato condivisibile con un ID verificabile una volta superato un corso.
Sostieni l'istruzione gratuita sull'IA. AI Understanding è un'organizzazione non profit 501(c)(3) — nessun annuncio, nessun paywall, mai. Fai una donazione
Monte Carlo Tree Search (MCTS) è un algoritmo di pianificazione che decide la mossa migliore costruendo selettivamente un albero di ricerca e simulando molti futuri possibili. Ha alimentato scoperte come AlphaGo ed eccelle nei giochi con un numero enorme di posizioni possibili.
Ogni iterazione MCTS seleziona un percorso lungo l'albero, espande un nuovo nodo, simula un risultato e propaga il risultato per aggiornare le statistiche.
L'UCT aggiunge un bonus di esplorazione che cresce per i nodi visitati raramente, bilanciando lo sfruttamento delle mosse conosciute con l'esplorazione di quelle incerte.
Un rollout riproduce il gioco dal nodo appena espanso a un risultato terminale (tradizionalmente tramite mosse casuali o euristiche) per stimare il valore di quel nodo.
The 2016 AlphaGo system combined Monte Carlo simulation with policy and value networks, and also retained a fast rollout policy.
Il figlio radice più visitato viene generalmente scelto perché l'esplorazione intensa riflette una fiducia sostenuta nella forza di quella mossa.
Continua a imparare
Altre guide selezionate per questo argomento
Il prossimoProssima guida
Catena Markov Monte Carlo
Tecnico