Visão geral
A Busca em Árvore de Monte Carlo (do inglês Monte Carlo Tree Search - MCTS) é um algoritmo de busca heurística utilizado em processos de tomada de decisão, especialmente em jogos de estratégia complexos e problemas de inteligência artificial. Diferente de métodos de busca exaustiva que tentam calcular todas as possibilidades, o MCTS utiliza simulações aleatórias e estatísticas para explorar o espaço de busca de forma seletiva, focando em caminhos mais promissores.
O algoritmo ganhou notoriedade mundial ao compor o núcleo do sistema AlphaGo, da DeepMind, que derrotou campeões mundiais no jogo Go. Sua eficácia reside na capacidade de equilibrar a exploração de novas possibilidades com a exploração de estratégias que já demonstraram bons resultados em simulações anteriores.
Funcionamento do algoritmo
O MCTS opera através da construção iterativa de uma árvore de busca, onde cada nó representa um estado do ambiente. O processo é composto por quatro fases principais que se repetem até que o limite de tempo ou de iterações seja atingido:
- Seleção: A partir da raiz, o algoritmo navega pela árvore seguindo uma política de seleção (frequentemente baseada no valor UCB - Upper Confidence Bound) que equilibra a exploração de nós pouco visitados e a exploração de nós com alto valor estimado.
- Expansão: Quando um nó folha é alcançado, o algoritmo cria um ou mais nós filhos, expandindo a árvore para estados ainda não explorados.
- Simulação (Rollout): A partir do novo nó, realiza-se uma sequência de jogadas (frequentemente aleatórias ou guiadas por uma heurística simples) até atingir um estado terminal, obtendo-se um resultado (vitória, derrota ou empate).
- Retropropagação (Backpropagation): O resultado da simulação é propagado de volta pelos nós percorridos na árvore, atualizando as estatísticas de vitória e o número de visitas de cada nó, o que guiará as futuras seleções.