Busca em árvore de Monte Carlo

A busca em árvore de Monte Carlo, abreviada como MCTS, não tenta examinar todas as variantes até a mesma profundidade. Ela expande uma árvore gradualmente e usa os resultados acumulados para decidir onde investir a próxima parcela de cálculo. Um lance muito visitado não é automaticamente bom, mas sua estimativa costuma estar respaldada por mais busca.

Um ciclo de MCTS

1. Seleção: parte da posição inicial e segue os ramos existentes, equilibrando lances que já parecem fortes com lances que ainda são incertos.
2. Expansão: adiciona uma posição ou um lance que a árvore ainda não desenvolveu.
3. Avaliação: estima o resultado a partir da nova posição. Métodos clássicos podem completar partidas simuladas, enquanto sistemas modernos podem usar uma rede neural, um modelo treinado para reconhecer padrões, para avaliá-la.
4. Retropropagação: leva o resultado de volta pelo caminho percorrido e atualiza as contagens de visitas e as estimativas.

A repetição desse ciclo equilibra aproveitamento e exploração. Aproveitamento significa investir mais esforço onde as evidências já são favoráveis. Exploração significa testar alternativas incertas para que uma surpresa não seja descartada cedo demais. A regra exata de equilíbrio depende da implementação.

Ao contrário de minimax, a MCTS geralmente decide quanto investigar um ramo com base nas evidências coletadas durante a própria busca, não apenas em uma profundidade uniforme. Em alguns programas de xadrez baseados em redes neurais, uma rede fornece uma política, que sugere lances prováveis, e um valor, que estima o resultado. Esse valor desempenha um papel relacionado ao de uma função de avaliação, embora o processo completo de busca seja diferente.