Busca em Árvore de Monte Carlo

Visão geral

A Busca em Árvore de Monte Carlo (Monte Carlo Tree Search, MCTS) é um algoritmo de busca do melhor primeiro (best-first search) para tomar decisões em árvores de decisão (decision trees) grandes, com alto fator de ramificação (high-branching) — especialmente quando a busca exaustiva clássica (como Minimax com Poda Alfa-Beta) se torna impraticável.

A Busca em Árvore de Monte Carlo funciona construindo uma árvore de busca parcial guiada por amostragem aleatória (random sampling) (simulações de Monte Carlo (Monte Carlo rollouts)) ou por estimativas aprendidas de valor/política (learned value/policy estimates). Seu principal ponto forte é um mecanismo explícito para equilibrar:

• Exploração (exploration): tentar ações menos visitadas para descobrir jogadas potencialmente fortes
• Exploração do conhecido (exploitation): concentrar computação em ações que já parecem promissoras

Esse trade-off é comumente tratado via UCT (Upper Confidence bounds applied to Trees), derivado da teoria de bandido multiarmado (multi-armed bandit) (ver Bandidos Multiarmados).

A Busca em Árvore de Monte Carlo é amplamente usada em:

• jogos de tabuleiro (Go, Xadrez, Shogi, general game playing)
• planejamento em Aprendizado por Reforço e controle baseado em modelo (model-based control)
• domínios com heurísticas caras ou funções de avaliação pouco claras

Quando e por que a Busca em Árvore de Monte Carlo é útil

A Busca em Árvore de Monte Carlo é uma boa escolha quando:

• A árvore de busca é enorme (o fator de ramificação é grande).
• Você consegue simular resultados de forma barata (por exemplo, um modelo de avanço do jogo (forward model)).
• Heurísticas boas são difíceis de projetar, ou você quer um algoritmo a qualquer momento (anytime algorithm) que melhore com mais computação.
• Você tem modelos aprendidos (redes de política/valor) que podem guiar a busca (comum em Aprendizado Profundo por Reforço).

Em comparação com buscas clássicas de caminho mínimo como Busca A*, a Busca em Árvore de Monte Carlo tipicamente visa tomada de decisão sob incerteza sobre resultados de longo prazo, e não encontrar um único caminho ótimo em um grafo conhecido com uma função de custo fixa.

Fundamento teórico: bandidos e UCB

Em cada ponto de decisão, a Busca em Árvore de Monte Carlo efetivamente enfrenta um problema de bandido multiarmado: cada ação é um “braço”, e puxá-lo produz uma recompensa aleatória (a partir de uma simulação ou de uma estimativa de valor).

Uma estratégia padrão para bandidos é o Limite Superior de Confiança (Upper Confidence Bound, UCB1). Para uma ação (a), o UCB seleciona:

[ \text{UCB}(a) = \bar{X}_a + c \sqrt{\frac{\ln N}{n_a}} ]

Onde:

• (\bar{X}_a): média empírica da recompensa ao escolher a ação (a)
• (n_a): número de vezes em que a ação (a) foi escolhida
• (N): número total de tentativas em todas as ações
• (c): constante de exploração (quanto maior (c), mais exploração)

O UCT aplica essa ideia dentro de uma árvore, escolhendo ações em cada nó usando a mesma forma de limite de confiança.

Ideia central: construir a árvore de forma assimétrica

A Busca em Árvore de Monte Carlo não expande a árvore inteira. Em vez disso, ela constrói incrementalmente uma árvore enviesada para linhas promissoras. O algoritmo repete um loop de quatro fases:

1. Seleção
2. Expansão
3. Simulação (ou avaliação)
4. Backup (retropropagação (backpropagation) dos resultados)

Ao longo de muitas iterações, nós que parecem melhores (maior valor, maior incerteza) recebem mais visitas.

Loop principal em detalhe

1) Seleção

Começando na raiz, escolha repetidamente uma ação filha de acordo com uma política de árvore, tipicamente UCT:

[ a^* = \arg\max_a \left( Q(s,a) + c \sqrt{\frac{\ln N(s)}{N(s,a)}} \right) ]

Onde:

• (Q(s,a)) é a estimativa atual do retorno esperado após executar (a) no estado (s)
• (N(s)) é a contagem de visitas (visit count) do estado (s)
• (N(s,a)) é a contagem de visitas da aresta ((s,a))

Isso continua até alcançar um nó que não está totalmente expandido (tem ações ainda não tentadas) ou um estado terminal.

Intuição:

• O termo (Q) explora o conhecido: prefere ações que funcionaram bem.
• O termo de raiz quadrada explora: prefere ações com menos visitas.

2) Expansão

Se o nó selecionado não for terminal e tiver ações ainda não tentadas, escolha uma dessas ações, aplique-a e adicione o estado resultante como um novo nó filho.

A expansão controla onde a árvore cresce. Com frequência, exatamente um novo nó é adicionado por iteração.

3) Simulação (rollout) ou avaliação

A partir do novo nó, estime o resultado do jogo/decisão. Tradicionalmente isso era feito por uma política de simulação aleatória (random rollout policy) até um estado terminal, produzindo uma recompensa de vitória/derrota (ou numérica).

A Busca em Árvore de Monte Carlo moderna frequentemente substitui ou complementa simulações com estimativas aprendidas:

• Rede de valor (value network): prediz diretamente o resultado esperado a partir do estado
• Rede de política (policy network): sugere quais ações são promissoras para explorar (muito usada em métodos no estilo AlphaZero)

Isso conecta a Busca em Árvore de Monte Carlo a Redes Neurais e ao planejamento aprendido (learned planning).

4) Backup (retropropagação)

Propague o resultado da simulação de volta ao longo do caminho desde o nó expandido até a raiz, atualizando estatísticas como:

• contagens de visita
• estimativas de valor-ação (Q)

Uma atualização comum mantém a média do retorno:

[ Q \leftarrow \frac{\sum \text{return}}{N} ]

Em jogos de dois jogadores de soma zero (zero-sum), os valores frequentemente são armazenados a partir da perspectiva do jogador atual, exigindo inversões de sinal (sign flips) à medida que você sobe na árvore (porque os jogadores alternam).

Pseudocode (UCT-style MCTS)

def mcts(root_state, time_budget, c):
    root = Node(root_state)

    while time_remaining(time_budget):
        node = root
        path = [node]

        # 1) Selection
        while node.is_fully_expanded() and not node.is_terminal():
            node = node.best_child_uct(c)
            path.append(node)

        # 2) Expansion
        if not node.is_terminal():
            node = node.expand_one_child()
            path.append(node)

        # 3) Simulation / Evaluation
        reward = rollout_or_evaluate(node.state)

        # 4) Backup
        for n in reversed(path):
            n.visit_count += 1
            n.total_value += reward
            reward = -reward  # typical for two-player zero-sum alternating turns

    return root.best_child_by_visits()

Where a typical UCT child selection looks like:

def uct_score(parent, child, c):
    Q = child.total_value / child.visit_count
    U = c * sqrt(log(parent.visit_count) / child.visit_count)
    return Q + U

Um exemplo prático: escolhendo uma jogada no Jogo da Velha

Mesmo em um jogo pequeno como Jogo da Velha, a Busca em Árvore de Monte Carlo ilustra a ideia com clareza:

• Estado: posição atual do tabuleiro
• Ações: jogadas legais (casas vazias)
• Simulação: jogar aleatoriamente até vitória/derrota/empate
• Recompensa: +1 para vitória, 0 para empate, -1 para derrota (na visão do jogador atual)

Após alguns milhares de iterações a partir do tabuleiro atual, a Busca em Árvore de Monte Carlo tipicamente:

• concentra a maior parte das visitas em jogadas que levam a vitórias ou empates forçados
• evita jogadas que frequentemente levam a simulações de derrota

Em jogos mais difíceis (por exemplo, Go), simulações aleatórias são barulhentas demais para serem fortes por si só, mas o mesmo loop funciona quando “simulação” vira “avaliação por rede de valor”.

Variantes e extensões importantes

UCT (Upper Confidence bounds applied to Trees)

O UCT é a variante canônica da Busca em Árvore de Monte Carlo. Ele usa pontuação no estilo UCB em cada nó e costuma ser o que as pessoas querem dizer por “MCTS vanilla”.

Observações práticas comuns:

• A constante de exploração (c) depende do domínio.
• Recompensas devem ser escaladas de modo sensato (por exemplo, em ([-1, 1])) para que (c) tenha um significado estável.
• Em domínios estocásticos, UCT ainda funciona, mas a variância pode ser alta; melhores políticas de simulação/avaliação ajudam.

Alargamento progressivo (para espaços de ação grandes ou contínuos)

A Busca em Árvore de Monte Carlo padrão supõe que você consegue enumerar ações legais em um nó. Em domínios com:

• fatores de ramificação extremamente grandes (por exemplo, muitas jogadas possíveis)
• ações contínuas (controle de robôs, ajuste de parâmetros)

você pode não querer expandir todas as ações de uma vez.

O alargamento progressivo (progressive widening) limita o número de filhos em função da contagem de visitas:

[ |\text{children}(s)| \le k \cdot N(s)^\alpha ]

onde (k > 0) e (0 < \alpha < 1). À medida que o nó é mais visitado, você permite que mais ações sejam consideradas.

Isso é especialmente importante em problemas de planejamento ligados a Processos de Decisão de Markov com controles contínuos.

PUCT (UCT guiado por política, comum em sistemas no estilo AlphaZero)

Quando você tem um prior de política (P(s,a)) (frequentemente de uma rede neural), você pode guiar a exploração para jogadas provavelmente boas:

[ a^* = \arg\max_a \left( Q(s,a) + c_{\text{puct}} , P(s,a), \frac{\sqrt{N(s)}}{1 + N(s,a)} \right) ]

Isso desloca a “exploração” de ser puramente baseada em visitas para ser informada por priors aprendidos, o que é central em agentes modernos para jogos.

Esse estilo é comumente discutido em Aprendizado Profundo por Reforço e planejamento baseado em modelo.

Outros aprimoramentos comuns (brevemente)

• Tabelas de transposição (transposition tables): muitos jogos têm estados repetidos alcançáveis por diferentes ordens de jogadas (um grafo acíclico direcionado (Directed Acyclic Graph, DAG) em vez de uma árvore). Compartilhar estatísticas entre transposições pode melhorar significativamente a eficiência.
• Heurísticas RAVE / AMAF (RAVE / AMAF heuristics): reutilizam informação de simulações sobre jogadas vistas mais adiante em uma simulação para acelerar o aprendizado inicial (historicamente mais comum em Go).
• Busca em Árvore de Monte Carlo paralela (Parallel MCTS): executa simulações concorrentemente; técnicas como “perda virtual (virtual loss)” reduzem múltiplas threads comprometendo-se demais com o mesmo caminho.
• Reutilização da árvore (tree reuse): após fazer uma jogada no jogo real, reutiliza a subárvore correspondente como a nova raiz (grande ganho de velocidade em problemas de decisão sequencial).

Escolhas práticas de projeto

Escolhendo uma política de simulação ou de avaliação

Uma política de simulação pode ser:

• uniformemente aleatória (simples, frequentemente fraca)
• heurística (conhecimento do domínio melhora o sinal)
• aprendida (rede de política)
• sem simulação (avaliação apenas por valor)

À medida que os domínios ficam mais complexos, simulações tendem a ser substituídas por avaliação aprendida porque simulações ingênuas ficam barulhentas demais.

Projeto de recompensa e detalhes do backup

• Use faixas de recompensa consistentes (por exemplo, ([-1,1])).
• Em configurações multi-jogador ou não-soma-zero, backups são mais complexos do que inversões de sinal; você pode armazenar retornos vetoriais ou usar generalizações de teoria dos jogos.
• Desconto (por exemplo, (\gamma)) pode ser usado para planejamento de longo horizonte como em aprendizado por reforço.

Ajuste da constante de exploração

• (c) maior: mais exploração, melhor para evitar “travamento” precoce, mas pode desperdiçar computação.
• (c) menor: mais exploração do conhecido, foco mais rápido, mas pode perder ações fortes porém inicialmente pouco amostradas.

Na prática, (c) é ajustado empiricamente por domínio e pelo escalonamento da recompensa.

Orçamentando computação

A Busca em Árvore de Monte Carlo é um algoritmo a qualquer momento: ela retorna uma jogada em qualquer ponto, mas melhora com mais iterações. Orçamentos podem ser:

• número fixo de simulações
• tempo fixo de relógio (wall-clock)
• adaptativo (mais tempo em posições críticas)

Usos comuns em jogos e planejamento

Jogos (informação perfeita)

A Busca em Árvore de Monte Carlo ficou famosa no Go computacional e é amplamente usada em:

• Go, Hex e outros jogos de alto fator de ramificação
• variantes de engines de Xadrez/Shogi em formas híbridas
• frameworks de general game playing

Nesses domínios, a Busca em Árvore de Monte Carlo serve como uma alternativa poderosa à busca minimax profunda, especialmente quando combinada com priors/valores aprendidos.

Planejamento com um simulador (tomada de decisão baseada em modelo)

Se você tem um modelo gerativo (generative model) (um simulador que consegue avançar de um estado para o próximo), a Busca em Árvore de Monte Carlo pode planejar sem uma tabela de transição completa explícita — útil em:

• robótica (planejamento de sequências de ação)
• pesquisa operacional (escalonamento, alocação)
• planejamento probabilístico

Isso se relaciona a conceitos de aprendizado por reforço como planejamento em Processos de Decisão de Markov, e contrasta com métodos de Programação Dinâmica que exigem uma estrutura mais explícita.

Tomada de decisão online

Em configurações “online” (agir agora e depois replaniar), a Busca em Árvore de Monte Carlo pode:

• planejar a partir do estado atual sob incerteza
• incorporar novas observações a cada passo
• reutilizar partes da árvore entre timesteps (reutilização da árvore)

Isso a torna prática em tarefas sequenciais em que o futuro é grande demais para resolver offline.

Pontos fortes e limitações

Pontos fortes

• Escala para árvores enormes ao concentrar a busca onde importa.
• A qualquer momento: mais computação rende melhores decisões.
• Flexível ao domínio: funciona apenas com um simulador; nenhuma heurística artesanal é necessária (embora ajude).
• Integra aprendizado naturalmente via redes de política/valor.

Limitações

• Precisa de muitas simulações quando recompensas são esparsas ou simulações são barulhentas.
• Fraca sem uma boa política de avaliação/simulação em domínios complexos (por exemplo, simulações aleatórias em Go têm baixo sinal).
• Lidar com ações contínuas exige técnicas como alargamento progressivo.
• Sem garantia global de otimalidade com computação finita; existe convergência assintótica sob condições, mas o desempenho prático depende fortemente de orientação.

Relação com outros métodos de busca

• Em comparação com Minimax: a Busca em Árvore de Monte Carlo amostra e se concentra em linhas promissoras em vez de buscar exaustivamente até uma profundidade fixa.
• Em comparação com Busca A*: A* tipicamente trata de caminhos mínimos com custos conhecidos e heurísticas admissíveis, enquanto a Busca em Árvore de Monte Carlo trata de tomada de decisão sob resultados incertos de longo horizonte usando amostragem.
• Em pipelines de aprendizado por reforço: a Busca em Árvore de Monte Carlo pode atuar como um planejador (planner) que melhora a seleção de ações além de uma rede de política bruta, e também pode gerar alvos de treinamento (por exemplo, distribuições de visita).

Resumo

A Busca em Árvore de Monte Carlo é uma abordagem poderosa e de propósito geral para tomada de decisão em árvores grandes. Ela melhora iterativamente uma árvore de busca parcial repetindo:

1. Seleção (frequentemente via UCT)
2. Expansão
3. Simulação / avaliação
4. Backup

Variantes-chave como UCT, alargamento progressivo, e formas guiadas por política como PUCT tornam a Busca em Árvore de Monte Carlo prática em domínios discretos e em domínios grandes/contínuos. Seu impacto é especialmente visível em IA para jogos e sistemas modernos de planejamento aumentados por aprendizado, onde simulação e estimativas aprendidas de valor/política trabalham juntas para produzir decisões fortes sob orçamentos apertados de computação.

---