Licenciar o YOLO
Voltar ao glossário da Ultralytics

Monte Carlo Tree Search (MCTS)

A busca em árvore de Monte Carlo (MCTS) escolhe ações expandindo uma árvore de busca com simulações e priorizando jogadas promissoras. É usada no AlphaGo e em robôs.

A busca em árvore de Monte Carlo (MCTS) é um algoritmo de planeamento que escolhe a próxima ação expandindo uma árvore de futuros possíveis a partir de muitas simulações, dedicando mais recursos às jogadas mais promissoras. Precisa apenas de uma forma de gerar jogadas e resultados válidos, como as regras de um jogo ou um simulador, e não exige uma função de avaliação escrita manualmente. É também um algoritmo anytime: parar em qualquer momento devolve a melhor jogada encontrada até então, e mais tempo resulta numa resposta melhor. Rémi Coulom deu nome ao método em 2006, o mesmo ano em que Levente Kocsis e Csaba Szepesvári publicaram o UCT, a regra de seleção que se tornou a forma padrão do método. A MCTS transformou o Go computacional em poucos anos, mais tarde impulsionou o AlphaGo e o AlphaZero e é agora usada para planear o comportamento de robôs e veículos e para pesquisar etapas de raciocínio em modelos de linguagem grandes (LLMs).

Como funciona a MCTS#

A busca mantém uma árvore cuja raiz é a posição atual e cujos nós registam quantas vezes foram visitados e quantas dessas visitas resultaram numa vitória. Cada iteração tem quatro fases:

  1. Seleção: A partir da raiz, percorre nós totalmente explorados, escolhendo o filho com a pontuação UCT mais alta, que equilibra taxas de vitória elevadas com jogadas raramente experimentadas.
  2. Expansão: No primeiro nó com uma jogada ainda não experimentada, adiciona essa jogada como novo filho.
  3. Simulação: Joga a partir do novo filho até ao fim da partida, normalmente com jogadas aleatórias, para obter um resultado.
  4. Retropropagação: Sobe novamente pelo caminho e atualiza a contagem de visitas e o total de vitórias de cada nó com o resultado.

Quando se esgota o orçamento, o algoritmo joga com o filho mais visitado da raiz, uma escolha mais estável do que a do filho com a média mais alta.

Equilíbrio entre exploração e aproveitamento#

O UCT trata a escolha em cada nó como um problema de bandido multiarmado e aplica a fórmula UCB1: a pontuação de um filho é a sua taxa de vitórias w/n mais c·√(ln N / n), em que n é a contagem de visitas do filho, N é a do progenitor e c é uma constante de exploração, igual a √2 em teoria e ajustada na prática. O segundo termo diminui à medida que uma jogada é experimentada mais vezes, por isso algumas vitórias afortunadas não a podem fazer excluir as restantes, e uma jogada negligenciada acaba por ter outra oportunidade.

Este exemplo em Python executa MCTS num jogo simples: os jogadores retiram de uma a três pedras de uma pilha de 10, e ganha quem retirar a última pedra.

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}")

Retirar duas pedras recebe 1.889 das 2.000 visitas e vence 91% das simulações, contra 68 visitas para retirar uma e 43 para retirar três. É a jogada vencedora: deixar 8, um múltiplo de 4, permite ao primeiro jogador responder a cada jogada do adversário deixando novamente um múltiplo de 4 até a pilha ficar vazia. A busca encontrou a jogada apenas com simulações aleatórias e estatísticas de visitas, sem qualquer estratégia codificada.

Do AlphaGo ao AlphaZero e MuZero#

O fator de ramificação médio do Go, de cerca de 250 jogadas legais, comparado com cerca de 35 no xadrez, tornava impossível a busca exaustiva, e a MCTS impulsionou o aumento da força dos programas de Go desde o final dos anos 2000. O AlphaGo da DeepMind orientou a MCTS com uma rede de política que propunha jogadas prováveis e avaliava posições com uma rede de valor e simulações rápidas, e, em março de 2016, venceu Lee Sedol por 4–1. O AlphaZero e o MuZero foram mais longe. O AlphaZero eliminou por completo as simulações, avaliou as posições folha com uma rede de valor e treinou essa rede com partidas que jogava contra si próprio, usando as contagens de visitas de cada busca como alvo para a sua rede de política, o que torna a MCTS uma etapa de melhoria da política no aprendizado por reforço. O MuZero executou a mesma busca dentro de um modelo aprendido do ambiente, pelo que jogou Go, xadrez, shogi e jogos Atari sem receber as respetivas regras.

MCTS para planeamento e raciocínio#

Robôs e veículos autónomos usam MCTS para planear em situações incertas, como entrar no trânsito, e variantes como o POMCP estendem-na a processos de decisão de Markov parcialmente observáveis, acompanhando uma crença sobre estados ocultos. Uma busca que planeia a partir de imagens de câmara precisa de um estado para a raiz: por exemplo, um braço robótico que joga xadrez pode usar um modelo Ultralytics YOLO26 treinado com imagens do tabuleiro para localizar todas as peças, e a posição recuperada torna-se a raiz da busca.

No raciocínio de LLMs, cada nó é uma solução parcial e cada aresta, uma etapa de raciocínio; um modelo de recompensa de processo ou uma verificação da resposta pontua os ramos. O rStar-Math da Microsoft usou MCTS com um modelo de preferência de processo para elevar o Qwen2.5-Math-7B de 58,8% para 90,0% no benchmark MATH. O Tree of Thoughts pesquisa etapas de raciocínio usando busca em largura ou em profundidade. O MCTS tem sido mais difícil de usar durante o treinamento: a DeepSeek o listou entre as tentativas malsucedidas para o DeepSeek-R1, porque o espaço de sequências de tokens é muito maior que o de um jogo de tabuleiro e é difícil treinar o modelo de valor que orienta a busca; em vez disso, treinou o R1 com aprendizado por reforço com recompensas verificáveis.

Explore as soluções

Visão computacional no desporto

Visão computacional no desporto

Descubra como o Ultralytics YOLO impulsiona a visão computacional no esporte com rastreamento de jogadores e bolas, análise de desempenho, insights para treinadores e reabilitação de atletas.
Saiba mais
Visão computacional para imagens aéreas

Visão computacional para imagens aéreas

Transforma imagens de drones e aéreas em informações em tempo real para a agricultura, a aquacultura, a conservação e a análise geoespacial com Ultralytics YOLO.
Saiba mais
Visão computacional no setor aeroespacial

Visão computacional no setor aeroespacial

Aplica visão computacional na indústria aeroespacial com Ultralytics YOLO para inspecionar aeronaves, detetar objetos estranhos na pista (FOD), apoiar operações aeroportuárias em terra e detetar defeitos em materiais compósitos.
Saiba mais
Visão computacional na segurança

Visão computacional na segurança

Protege todas as instalações com os modelos Ultralytics YOLO. A IA visual permite monitorizar perímetros, detetar ameaças, reconhecer matrículas e melhorar a segurança no local de trabalho.
Saiba mais
Visão computacional na robótica

Visão computacional na robótica

Potencia máquinas mais inteligentes com os modelos Ultralytics YOLO. A IA visual na robótica permite navegação autónoma, perceção, rastreamento de objetos e controlo em tempo real.
Saiba mais
Visão computacional na logística

Visão computacional na logística

Otimize a logística com os modelos Ultralytics YOLO. A IA de visão permite inspecionar pacotes, fazer triagem, rastrear veículos e monitorar a segurança em tempo real nos armazéns.
Saiba mais
Visão computacional no varejo

Visão computacional no varejo

Reinvente o varejo com os modelos Ultralytics YOLO. A IA de visão permite rastrear o estoque, monitorar prateleiras, gerenciar filas e obter insights mais inteligentes sobre clientes.
Saiba mais
Visão computacional na área da saúde

Visão computacional na área da saúde

Desenvolva soluções de saúde com os modelos Ultralytics YOLO. A IA de visão na área da saúde permite obter imagens médicas mais rapidamente, diagnósticos mais inteligentes e monitoramento de pacientes.
Saiba mais
Visão computacional na manufatura

Visão computacional na manufatura

Otimize a manufatura com modelos Ultralytics YOLO. A IA visual impulsiona o controle de qualidade, a detecção de defeitos, a conformidade com o uso de EPI e a automação da linha de montagem.
Saiba mais
Visão computacional no setor automotivo

Visão computacional no setor automotivo

Aplique visão computacional no setor automotivo com modelos Ultralytics YOLO. A IA visual aumenta a segurança viária, aprimora a assistência ao condutor e viabiliza a automação de veículos para estradas mais inteligentes.
Saiba mais
Visão computacional na agricultura

Visão computacional na agricultura

Leve a IA de visão à agricultura inteligente com os modelos Ultralytics YOLO. Aprimore o monitoramento de plantações, o rastreamento de animais e a agricultura de precisão para obter safras maiores e mais inteligentes.
Saiba mais

Vamos construir juntos o futuro da IA!

Comece sua jornada rumo ao futuro do aprendizado de máquina