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:
- 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.
- Expansão: No primeiro nó com uma jogada ainda não experimentada, adiciona essa jogada como novo filho.
- Simulação: Joga a partir do novo filho até ao fim da partida, normalmente com jogadas aleatórias, para obter um resultado.
- 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.










