A busca em árvore Monte Carlo (MCTS) é um algoritmo heurístico de busca em árvore usado em processos de decisão, particularmente em softwares que jogam jogos de tabuleiro. Ela 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. A MCTS foi combinada com redes neurais em 2016 e, desde então, tem sido aplicada a jogos como Xadrez, Shogi, Damas, Gamão, Bridge de Contrato, Go, Scrabble e Clobber, bem como a videogames de estratégia por turnos e aplicações não relacionadas a jogos.
O algoritmo opera por meio de playouts repetidos, também chamados de roll-outs, em que o jogo é jogado até o fim com movimentos aleatórios. Os resultados desses playouts são usados para ponderar nós na árvore de jogo, tornando os nós melhores mais propensos a serem escolhidos em playouts futuros. Essa abordagem difere da busca minimax tradicional ao evitar uma função de avaliação estática, baseando-se em vez disso em resultados simulados.
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 precisão e independência de domínio em jogo da velha, Othello e xadrez. Em 1989, W. Ertel, J. Schumann e C. Suttner aplicaram métodos semelhantes à prova automatizada de teoremas, melhorando algoritmos de busca não informados. Em 1992, B. Brügmann usou pela primeira vez 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 a UCT.
Em 2006, Rémi Coulom cunhou o nome busca em árvore Monte Carlo, enquanto L. Kocsis e Cs. Szepesvári desenvolveram o algoritmo UCT (Limites Superiores de Confiança aplicados a Árvores). S. Gelly et al. implementaram a UCT no programa MoGo, que alcançou o nível dan no Go 9×9 em 2008. O programa Fuego também começou a derrotar amadores fortes no Go 9×9 nessa época. Em janeiro de 2012, o programa Zen venceu por 3:1 contra um jogador amador 2 dan em um tabuleiro 19×19.
O Google DeepMind desenvolveu o AlphaGo, que em outubro de 2015 se tornou o primeiro programa a derrotar um jogador profissional humano de Go sem handicap em um tabuleiro de tamanho completo. Em março de 2016, o AlphaGo derrotou Lee Sedol por 4:1, ganhando um nível honorário de 9 dan. O AlphaGo combinou a MCTS com redes neurais artificiais, um método de aprendizado profundo, para avaliação de política e valor, marcando um marco significativo no aprendizado de máquina.
Princípio de Operação
A MCTS concentra-se em analisar os movimentos mais promissores, expandindo a árvore de busca com base em amostragem aleatória. Cada rodada consiste em quatro etapas:
- Seleção: Começando do nó raiz (estado atual do jogo), selecione nós filhos sucessivos até que um nó folha seja alcançado. A seleção é enviesada para favorecer movimentos promissores, frequentemente usando UCT.
- Expansão: A menos que o nó folha termine o jogo, crie um ou mais nós filhos representando movimentos legais.
- Simulação: Complete um playout aleatório a partir de um nó filho escolhido, jogando até que o jogo seja decidido.
- Retropropagação: Atualize os nós no caminho do filho até a raiz com o resultado do playout, incrementando as contagens de simulação e as contagens de vitórias adequadamente.
Em jogos com empates, um empate incrementa o numerador em 0,5 e o denominador em 1 para ambos os jogadores. Isso garante que as escolhas de cada jogador se expandam em direção a movimentos que maximizem seu próprio valor.
Algoritmo UCT
O algoritmo UCT, introduzido em 2006, aplica Limites Superiores de Confiança à busca em árvore. Ele equilibra exploração e explotação selecionando nós filhos com base em sua recompensa média e um bônus para nós menos visitados. Isso permite que a árvore de busca se expanda em direção aos movimentos mais promissores enquanto ainda explora alternativas. A UCT tornou-se o padrão para implementações de MCTS, incluindo no MoGo e em programas posteriores.
Aplicações
A MCTS tem sido usada 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. Ela também lida com jogos não determinísticos como Skat, Pôquer, Magic: The Gathering e Colonos de Catan. Em jogos de estratégia por turnos, Total War: Rome II usa MCTS em sua IA de campanha de alto nível. Além de jogos, a MCTS tem aplicações em problemas de planejamento e otimização.
A combinação de MCTS com redes neurais, como no AlphaGo, provou ser particularmente eficaz. Essa abordagem híbrida usa redes neurais para guiar a seleção e avaliar posições, reduzindo a necessidade de playouts aleatórios extensos. Programas subsequentes, como o AlphaZero, estenderam isso ao Xadrez e ao Shogi, alcançando desempenho sobre-humano.