Monte Carlo tree search (MCTS) é um algoritmo heurístico de busca em árvore utilizado para processos de decisão, especialmente em softwares que jogam jogos de tabuleiro. Ele resolve a árvore de jogo focando nos movimentos mais promissores, expandindo a árvore de busca com base em amostragem aleatória do espaço de busca. O MCTS foi combinado com redes neurais em 2016 e, desde então, tem sido aplicado a jogos como Xadrez, Shogi, Damas, Gamão, Bridge de Contrato, Go, Scrabble e Clobber, além de jogos de estratégia por turnos e outros domínios.
O algoritmo opera por meio de playouts repetidos, ou roll-outs, nos quais jogos são simulados até o fim com movimentos aleatórios. Os resultados desses playouts são usados para ponderar nós na árvore de jogo, guiando seleções futuras para movimentos mais promissores. Cada rodada do MCTS consiste em quatro etapas: seleção, expansão, simulação e retropropagação.
História
O método de Monte Carlo, que usa amostragem aleatória para problemas determinísticos, remonta à década de 1940. Em 1987, Bruce Abramson combinou a busca minimax com um modelo de resultado esperado baseado em playouts aleatórios de jogos, demonstrando sua eficácia no jogo da velha e em outros jogos. Em 1989, W. Ertel, J. Schumann e C. Suttner aplicaram métodos semelhantes à prova automatizada de teoremas, melhorando os tempos de busca. Em 1992, B. Brügmann usou a abordagem em um programa de Go. Em 2002, Chang et al. propuseram a Amostragem Adaptativa em Múltiplos Estágios (AMS), que introduziu exploração e explotação baseadas em UCB em árvores de Monte Carlo, estabelecendo as bases para o UCT.
Em 2006, Rémi Coulom cunhou o termo Monte Carlo tree search, enquanto L. Kocsis e Cs. Szepesvári desenvolveram o algoritmo UCT (Upper Confidence bounds applied to Trees). S. Gelly et al. implementaram o UCT no programa MoGo, que alcançou o nível dan no Go 9x9 até 2008. Em 2012, o programa Zen venceu uma partida contra um jogador amador de 2 dan em um tabuleiro 19x19. O AlphaGo do Google DeepMind, usando MCTS com redes neurais, tornou-se o primeiro programa a derrotar um jogador humano profissional de Go em 2015 e venceu Lee Sedol em 2016.
Princípio de Funcionamento
O foco do MCTS está em analisar os movimentos mais promissores, expandindo a árvore de busca com base em amostragem aleatória. Cada playout simula um jogo até o fim, e os resultados ponderam os nós para que melhores movimentos sejam escolhidos com mais frequência. A Busca de Jogo Pura de Monte Carlo básica aplica playouts iguais a cada movimento legal e seleciona o movimento com mais vitórias.
Cada rodada do MCTS envolve quatro etapas:
- Seleção: Partindo da raiz, seleciona nós filhos sucessivos até atingir um nó folha.
- Expansão: Cria um ou mais nós filhos a partir da folha, a menos que o jogo esteja decidido.
- Simulação: Completa um playout aleatório a partir do novo nó.
- Retropropagação: Atualiza as estatísticas dos nós ao longo do caminho do novo nó até a raiz.
Algoritmo UCT
O algoritmo UCT equilibra exploração e explotação usando a fórmula do Limite Superior de Confiança. Ele seleciona nós filhos com base na taxa média de vitórias e em um bônus para nós menos visitados, permitindo que a árvore se expanda em direção a movimentos promissores enquanto ainda explora alternativas. Essa abordagem é central para a eficiência do MCTS.
Aplicações
O MCTS tem sido usado em programas para jogos de tabuleiro como Hex, Havannah, Jogo das Amazonas e Arimaa, bem como em videogames em tempo real, como Ms. Pac-Man e Fable Legends. Também se aplica a jogos não determinísticos, como skat, pôquer, Magic: The Gathering e Colonos de Catan. Além de jogos, o MCTS foi explorado em problemas de planejamento e otimização.
Significância
A combinação do MCTS com redes neurais profundas, como no AlphaGo, marcou um marco na inteligência artificial e no aprendizado de máquina. Demonstrou como a busca heurística pode ser integrada a métodos de aprendizado profundo para alcançar desempenho sobre-humano em domínios complexos, influenciando pesquisas subsequentes em IA generativa e outras áreas.