Monte Carlo Tree Search: Uma Revisão de Desvantagens, Vantagens e Limitações em Jogos Multijogador Complexos

1. Introdução

A Monte Carlo Tree Search (MCTS) é uma família de algoritmos de busca que constrói uma árvore de decisão em quatro etapas: seleção, expansão, simulação e retropropagação. Em vez de exigir uma função de avaliação completa para cada estado, o método estima a qualidade das ações a partir de inúmeras simulações, equilibrando a exploração de alternativas raramente visitadas com a explotação de ações conhecidas. Essa característica contribuiu para resultados expressivos em jogos como Go, Xadrez e Shogi, especialmente em ambientes de dois jogadores com informação perfeita (BROWNE et al., 2012).

No entanto, os jogos digitais e de tabuleiro contemporâneos apresentam condições mais complexas: vários oponentes, informação oculta, aleatoriedade, grandes espaços de ação e decisões em tempo real. Nessas situações, uma simulação adicional nem sempre produz uma decisão melhor. Um número maior de jogadores amplia a árvore de busca e dificulta a modelagem das respostas dos oponentes. A informação imperfeita pode causar fusão de estratégias quando estados ocultos são tratados de forma inadequada, enquanto a pressão de tempo reduz o orçamento computacional disponível. Apesar da crescente aplicação da MCTS nesses cenários, a literatura permanece fragmentada e concentrada em jogos clássicos.

2. Objetivos

O objetivo geral deste trabalho foi identificar e organizar limitações recorrentes da MCTS em jogos digitais e de tabuleiro multijogador, especialmente em ambientes com informação imperfeita, estocasticidade e restrições de tempo.

Como objetivos específicos, o trabalho buscou reunir as estratégias que mitigam essas limitações e identificar lacunas de pesquisa que possam orientar estudos futuros e favorecer avaliações mais comparáveis e reprodutíveis.

3. Metodologia

Foi realizada uma revisão de literatura sobre estudos publicados entre 2013 e 2025, com buscas nas bases de dados IEEE Xplore, HAL Science Ouverte e Google Scholar. As estratégias de busca combinaram os termos "Monte Carlo Tree Search" e "MCTS" com expressões relacionadas a jogos digitais, jogos de tabuleiro e jogos multijogador. A triagem considerou trabalhos cujo título ou resumo abordasse MCTS, uma variante direta ou um método híbrido aplicado a jogos competitivos ou cooperativos. Foram excluídos estudos fora do escopo, documentos sem acesso ao texto completo e trabalhos cujo escopo não fosse compatível com os objetivos da revisão.

As buscas recuperaram 24 registros, dos quais dois eram duplicados entre as consultas, resultando em 22 trabalhos únicos potencialmente relevantes (17 em inglês e cinco em francês). Após a triagem, 18 estudos foram selecionados para análise completa e quatro foram excluídos. O corpus final reuniu 13 estudos do IEEE Xplore, três do HAL e dois encontrados por meio do Google Scholar, e, entre os selecionados, 15 textos estavam em inglês e três em francês. Os trabalhos foram classificados por tipo de jogo, algoritmo utilizado, restrições do ambiente, resultados relatados e estratégias de mitigação. A análise temática foi organizada em três categorias estruturais de limitação, limites de desempenho, pontos cegos táticos e trade-offs na modelagem de oponentes, e dois amplificadores dependentes do domínio, informação imperfeita e decisões em tempo real.

4. Resultados e Discussão

Os estudos analisados indicam que a MCTS apresenta desempenho mais consistente em jogos com estados bem definidos, fator de ramificação moderado e orçamento computacional suficientemente grande para um alto número de simulações. Entre os 18 trabalhos selecionados, oito abordaram jogos digitais, seis investigaram jogos de tabuleiro ou de mesa e os demais analisaram jogos de cartas, ambientes de jogo geral ou aplicações relacionadas. Algoritmos baseados em MCTS foram utilizados em 14 estudos, frequentemente combinados com redes neurais, abstrações do espaço de ação, políticas de simulação e técnicas de ajuste de parâmetros.

A primeira limitação identificada diz respeito ao desempenho da busca. Embora aumentar o número de simulações geralmente melhore a qualidade da decisão, os ganhos marginais tendem a diminuir à medida que novas simulações começam a revisitar trajetórias já suficientemente exploradas. Resultados obtidos em Go, jogos de estratégia em tempo real e jogos de tabuleiro mostram que dobrar o orçamento computacional pode produzir benefícios reduzidos ou nulos após certo ponto. Além disso, estudos sobre profundidade de habilidade mostram que esse limite depende tanto da complexidade do jogo quanto da configuração do agente. As estratégias de mitigação incluem abstração do espaço de ação, simplificação das simulações e ajuste automático de políticas, constantes de exploração e estratégias de rollout por meio do N-Tuple Bandit Evolutionary Algorithm (NTBEA) (GOODMAN; PEREZ-LIEBANA; LUCAS, 2024).

A segunda limitação corresponde aos pontos cegos do raciocínio tático. Como a MCTS estima o valor médio das continuações amostradas, o algoritmo pode falhar em posições que exigem reconhecer sequências táticas específicas, ameaças de longo prazo ou configurações pouco frequentes. Em Go, situações como escadas e o semeai ilustram cenários em que uma estrutura tática evidente para jogadores experientes pode não ser identificada pela busca.

A terceira limitação envolve a modelagem de oponentes. Em jogos com três ou mais participantes, o processo de busca deve representar não apenas as decisões do jogador na raiz da árvore, mas também as possíveis respostas de cada adversário. Modelos que mantêm estruturas independentes para cada oponente tendem a representar melhor o comportamento estratégico, embora aumentem significativamente o custo computacional. Em contrapartida, abordagens simplificadas, como a Paranoid Search e políticas generalizadas, reduzem esse custo, mas podem falhar em representar comportamentos relevantes. A literatura sugere que abordagens baseadas em foco seletivo, generalização das respostas dos adversários e decomposição da árvore são alternativas promissoras, embora ainda sejam pouco avaliadas em jogos com um grande número de participantes (BAIER; KAISERS, 2020).

A informação imperfeita intensifica essas limitações. Em jogos de cartas, Pokémon e outros ambientes com estados ocultos, a determinização, que consiste em assumir uma possível configuração da informação desconhecida e buscar como se ela fosse verdadeira, pode causar a fusão de estratégias incompatíveis. A Information Set MCTS, uma variação da busca em árvore de Monte Carlo projetada para lidar com incerteza, reduz esse problema ao agrupar estados que o jogador não consegue distinguir, preservando apenas a informação realmente disponível no momento da decisão (COWLING; POWLEY; WHITEHOUSE, 2012). Ainda assim, a aleatoriedade inerente ao ambiente e a necessidade de inferir o comportamento dos oponentes continuam a limitar a confiabilidade das estimativas produzidas.

Em ambientes de tempo real, como jogos de estratégia, MOBAs e jogos de tiro em primeira pessoa, as restrições de tempo tornam-se um fator crítico. A MCTS deve selecionar ações em intervalos muito curtos enquanto gerencia espaços de ação combinatórios, múltiplas unidades e observações parciais. Nesse contexto, abstrações hierárquicas, macro-ações, poda de ações e políticas obtidas por meio de aprendizado supervisionado ou aprendizado por reforço aparecem como estratégias recorrentes (ONTAÑÓN, 2013). Em algumas situações, métodos alternativos podem apresentar melhor desempenho. O Rolling Horizon Evolutionary Algorithm (RHEA), por exemplo, evolui sequências curtas de ações e realiza replanejamento contínuo, mostrando-se particularmente adequado para jogos cooperativos e ambientes altamente estocásticos nos quais a árvore de busca muda rapidamente (SFIKAS; LIAPIS, 2022).

Também foram identificadas aplicações da MCTS que dependem menos de decisões em tempo real, como balanceamento automático, playtesting e apoio ao design de jogos. Nesses cenários, o tempo de processamento deixa de ser uma restrição crítica, permitindo explorar extensivamente diferentes configurações, identificar desequilíbrios e avaliar alternativas de design. Embora a maioria dos estudos relate resultados favoráveis às abordagens propostas, alguns trabalhos observaram desempenho inferior da MCTS em comparação com técnicas concorrentes, como nos jogos Kingdomino e Pandemic.

5. Conclusão

A revisão também identificou cinco oportunidades relevantes para pesquisas futuras: (i) adoção e padronização de benchmarks compartilhados para jogos multijogador com informação imperfeita; (ii) avaliação sistemática de técnicas de modelagem de oponentes em jogos com um número maior de participantes; (iii) investigação da relação entre a complexidade percebida por jogadores humanos e a profundidade efetiva da busca; (iv) estudo de séries competitivas melhor de três e melhor de cinco, considerando o histórico de picks e bans; e (v) expansão das aplicações da MCTS em balanceamento automático, playtesting e geração procedural de conteúdo.