🤖 machine learning

Monte Carlo Permutation Search

Este artigo apresenta a Busca por Permutação de Monte Carlo (MCPS), um algoritmo de MCTS de propósito geral que supera o algoritmo GRAVE em jogos como Hex e Go ao incorporar estatísticas de simulação em todo o caminho no termo de exploração e derivar uma nova fórmula de ponderação que elimina a necessidade do hiperparâmetro de viés do GRAVE.

Autores originais: Tristan Cazenave

Publicado 2026-05-27

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Tristan Cazenave

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando resolver um quebra-cabeça complexo, como um jogo de Go ou Hex, mas não possui um supercomputador ou uma IA treinada para dizer qual é o melhor movimento. Em vez disso, você precisa confiar em "adivinhar e verificar", simulando milhares de cenários futuros aleatórios em sua mente. É assim que funciona um programa de computador chamado Monte Carlo Tree Search (MCTS).

Por muito tempo, a melhor maneira de fazer essa adivinhação foi um algoritmo chamado GRAVE. Ele era bom em olhar para o passado para prever o futuro, mas o autor deste artigo, Tristan Cazenave, pensou: "Podemos fazer melhor".

Ele criou um novo algoritmo chamado MCPS (Monte Carlo Permutation Search). Eis como ele funciona, explicado de forma simples:

As Três Maneiras de Olhar para o Passado

Para decidir qual movimento fazer a seguir, o MCPS examina seu histórico de jogos aleatórios (chamados de "simulações" ou "playouts") de três maneiras diferentes. Pense nelas como três lentes diferentes em uma câmera:

A Lente do "Caminho Exato" (Visão Padrão):
Esta examina jogos onde o jogador fez a mesma sequência exata de movimentos para chegar à posição atual e, em seguida, fez o movimento específico que estamos testando.
- Analogia: "Caminhei pela Rua Principal, virei à esquerda e depois comprei um café. Como foi isso?"
A Lente da "Ordem Não Importa" (A Atualização do GRAVE):
Esta examina jogos onde o jogador fez os mesmos movimentos para chegar à posição, mas a ordem foi ligeiramente diferente, e o movimento específico que estamos testando apareceu mais tarde no jogo.
- Analogia: "Comprei um café, depois caminhei pela Rua Principal e então virei à esquerda. São os mesmos ingredientes, apenas uma ordem diferente na receita. Ainda ficou bom?"
- Por que ajuda: Em muitos jogos, a ordem em que você coloca suas peças não altera o estado final do tabuleiro. Portanto, esta lente permite que o computador aprenda com mais jogos, não apenas com aqueles que correspondiam à ordem exata.
A Lente da "Permutação" (O Novo Segredo do MCPS):
Esta é a nova adição. Examina qualquer jogo onde o jogador usou o mesmo conjunto exato de movimentos (o caminho até a posição atual + o novo movimento), independentemente da ordem em que ocorreram.
- Analogia: "Usei um martelo, um chaves de fenda e um prego para construir uma prateleira. Não importa se martelou primeiro ou parafusou primeiro; se usei essas três ferramentas, a prateleira foi construída. Como funcionou essa combinação?"
- O Problema: Em alguns jogos (como AtariGo), a ordem importa porque o jogo pode terminar cedo (como ao capturar uma pedra). O MCPS lida com isso sendo inteligente sobre como agrupa esses movimentos.

A "Fórmula Mágica"

O artigo explica que o MCPS não escolhe apenas uma dessas visões; ele as mistura. O autor fez cálculos matemáticos para descobrir a maneira perfeita de combinar essas três fontes de informação.

Pense nisso como fazer um smoothie. Você tem três frutas (as três estatísticas). O GRAVE usava uma receita fixa que às vezes tinha um gosto estranho. O MCPS usa uma receita matematicamente perfeita que ajusta automaticamente as quantidades com base na quantidade de dados que possui para cada fruta. A melhor parte? Não é necessária uma "prova de sabor" (um humano definindo um parâmetro de viés) para acertar; a matemática faz isso automaticamente.

Como Desempenhou no Mundo Real

O autor testou o MCPS contra o antigo campeão (GRAVE) em cinco tipos diferentes de jogos:

Hex (O Casamento Perfeito): Neste jogo, a ordem dos movimentos nunca altera o tabuleiro final. O MCPS foi um grande vencedor aqui, especialmente em tabuleiros maiores. Foi como ter um mapa que mostrava todos os caminhos possíveis, não apenas aquele que você percorreu.
Go (O Pensador Profundo): Em tabuleiros pequenos, eles foram aproximadamente iguais. Mas em tabuleiros grandes, conforme o computador recebia mais tempo para pensar, o MCPS se sobressaiu. Foi melhor em usar esse tempo extra para explorar mais profundamente as linhas de jogo mais promissoras, enquanto o método antigo ficava preso explorando opções superficiais.
AtariGo (O Finalizador Rápido): Este é um jogo onde a primeira captura vence. Aqui, a ordem importa. Surpreendentemente, o MCPS ainda venceu, mas sua vantagem foi maior em tabuleiros pequenos onde o jogo termina rapidamente. Em tabuleiros grandes, o jogo fica longo demais para o truque da "ordem não importa" ajudar tanto.
NoGo (O Vencedor Consistente): Este é um jogo onde você perde se capturar. O MCPS venceu quase em todos os lugares, derrotando consistentemente o método antigo por uma margem sólida.
Wargame (O Demônio da Velocidade): Neste jogo de estratégia personalizado, o MCPS não apenas jogou melhor; jogou mais rápido. Simulou jogos que terminaram mais cedo e encontrou a estratégia vencedora mais rapidamente, permitindo executar mais simulações no mesmo período de tempo.

A Conclusão

O artigo afirma que o MCPS é uma maneira mais inteligente e eficiente para computadores jogarem jogos sem precisar de aprendizado profundo ou treinamento massivo.

Ele funciona ao perceber que, em muitos jogos, o conjunto de movimentos que você faz é mais importante do que a ordem em que os faz. Ao contar todas as vezes que um conjunto específico de movimentos apareceu em jogos aleatórios, o MCPS constrói uma melhor "intuição" sobre quais movimentos são bons. É como um detetive que percebe que, mesmo que os suspeitos tenham chegado em uma ordem diferente, o fato de todos terem estado no local é a verdadeira pista.

O resultado é uma ferramenta de propósito geral que supera o melhor método anterior em quase todos os cenários testados, tornando-se um novo padrão poderoso para IA de jogos quando você não tem um supercomputador à disposição.

Resumo Técnico: Busca de Permutação Monte Carlo (MCPS)

Declaração do Problema

A Busca em Árvore Monte Carlo (MCTS) é um algoritmo dominante para jogos e tomada de decisão, particularmente em domínios onde o aprendizado por reforço profundo é inviável devido à falta de dados de treinamento ou restrições computacionais (por exemplo, Jogo Geral). Embora variantes da MCTS, como GRAVE (Generalized RAVE), tenham melhorado o UCT padrão ao utilizar estatísticas de nós ancestrais e heurísticas All-Moves-As-First (AMAF), elas dependem de duas fontes principais de informação: estatísticas de simulações iniciadas com uma jogada específica e estatísticas de simulações onde a jogada aparece posteriormente.

O artigo identifica uma limitação nas abordagens existentes: elas não exploram plenamente as informações estatísticas contidas em simulações onde a sequência de jogadas que leva a um nó aparece em uma ordem diferente. Em jogos com propriedades comutativas (como Hex), qualquer permutação de jogadas leva ao mesmo estado. Em jogos não comutativos (como AtariGo), as permutações podem levar a estados diferentes, ainda que o artigo hipotetize que o valor estatístico das jogadas permaneça informativo. O objetivo é desenvolver um algoritmo MCTS de propósito geral que melhore o GRAVE sem exigir ajuste específico do problema, treinamento de modelo ou hiperparâmetros de viés.

Metodologia

Conceito Central: Busca de Permutação Monte Carlo (MCPS)

A MCPS introduz uma terceira fonte de estatísticas ao processo de avaliação de nós. Para avaliar uma ação $a$ em um nó $s$ alcançado por um caminho $(a_0, a_1, \dots, a_d)$ , a MCPS agrega dados de três conjuntos distintos de simulações:

Estatísticas Diretas ( $Q$ ): Simulações que começam com o caminho até $s$ seguido imediatamente pela ação $a$ .
Estatísticas AMAF ( $\tilde{Q}$ ): Simulações que começam com o caminho até $s$ , onde a ação $a$ aparece posteriormente na sequência (abordagem padrão do GRAVE).
Estatísticas de Permutação ( $\set{Q}$ ): Simulações que contêm o conjunto de jogadas $\{a_0, a_1, \dots, a_d, a\}$ em qualquer ordem e em qualquer posição.

Derivação Matemática dos Pesos

O artigo fornece uma derivação matemática para combinar esses três estimadores. Assumindo que as estatísticas são independentes, os autores derivam os pesos que minimizam a variância do estimador combinado.
Sejam $n$ , $\tilde{n}$ e $\hat{n}$ as contagens de amostras para as três estatísticas. Os pesos ótimos ( $\beta, \tilde{\beta}, \hat{\beta}$ ) são proporcionais às suas contagens de amostras:
$\beta = \frac{n}{n + \tilde{n} + \hat{n}}, \quad \tilde{\beta} = \frac{\tilde{n}}{n + \tilde{n} + \hat{n}}, \quad \hat{\beta} = \frac{\hat{n}}{n + \tilde{n} + \hat{n}}$
Essa combinação convexa elimina a necessidade do hiperparâmetro de viés usado no algoritmo GRAVE, fornecendo um esquema de ponderação livre de parâmetros.

Implementação Algorítmica

Seleção: O valor de uma jogada é calculado como a média ponderada dos três estimadores.
Cálculo de Estatísticas de Permutação: Para calcular $\hat{Q}$ eficientemente, o algoritmo usa uma janela deslizante de simulações recentes (padrão $W=10.000$ ) representadas como bitsets. Para um nó $s$ , o algoritmo intersecciona os bitsets de todas as jogadas no caminho até $s$ para identificar simulações contendo a sequência completa do caminho. Em seguida, intersecciona esse resultado com o bitset da jogada candidata $a$ para isolar as simulações relevantes. Isso é realizado usando operações de palavras de 64 bits (POPCOUNT e bit-scan) para eficiência.
Congelamento: Uma vez que um nó acumula um número limite de visitas ( $\rho=30$ ), suas estatísticas de permutação são calculadas e "congeladas". Esse nó atua então como referência para toda a sua subárvore, permitindo que os descendentes herdem essas estatísticas sem recalculá-las.
Codificação de Jogadas: Para permitir a transferência de conhecimento entre diferentes posições no tabuleiro, as jogadas são mapeadas para códigos inteiros baseados em características relevantes para o jogo (por exemplo, jogador, célula de destino, gatilho de combate) em vez de coordenadas exatas.

Principais Contribuições

Extensão Algorítmica: A proposta da MCPS, que integra estatísticas de permutação na regra de seleção da MCTS, estendendo o algoritmo GRAVE.
Melhoria Teórica: Uma derivação de fórmulas de ponderação que minimizam a variância do estimador sob suposições de independência, removendo a necessidade do hiperparâmetro de viés do GRAVE.
Implementação Eficiente: Um método para calcular estatísticas de permutação usando bitsets e janelas deslizantes, permitindo que o algoritmo lide com a explosão combinatória das ordens de jogadas de forma eficiente.
Aplicabilidade Geral: Demonstração de que o algoritmo funciona em diversos tipos de jogos (comutativos e não comutativos) sem ajuste específico de parâmetros.

Resultados Experimentais

Os autores testaram a MCPS contra o GRAVE em cinco jogos: Hex, Go, AtariGo, NoGo e um Jogo de Guerra assimétrico personalizado. Em todos os casos, 800 jogos foram jogados por configuração (400 com cada algoritmo jogando primeiro) sob orçamentos de tempo idênticos.

Hex: A MCPS supera o GRAVE em tabuleiros $7\times7$ e maiores, com taxas de vitória atingindo 70–76% em tabuleiros maiores. Em $5\times5$ , a sobrecarga dos bitsets desfavorece ligeiramente a MCPS. A vantagem cresce com o tamanho do tabuleiro porque a MCPS constrói árvores mais profundas.
Go: A MCPS supera o GRAVE em tabuleiros $7\times7$ e maiores. Notavelmente, em tabuleiros maiores ( $13\times13$ , $15\times15$ ), a diferença nas taxas de vitória aumenta significativamente à medida que o orçamento de tempo aumenta (até 63,75% em 2s). A MCPS consistentemente constrói árvores mais profundas com mais tempo, enquanto a profundidade da árvore do GRAVE frequentemente estagna ou diminui.
AtariGo: A MCPS supera o GRAVE em todas as configurações, com os maiores ganhos em tabuleiros pequenos ( $5\times5$ , $7\times7$ ). A vantagem diminui em tabuleiros maiores porque o jogo frequentemente termina antes que a busca alcance o estado terminal, limitando o benefício de árvores mais profundas.
NoGo: A MCPS mostra a melhoria mais uniforme, superando o GRAVE em todas as células com taxas de vitória entre 57% e 69%. A melhoria é consistente em todos os tamanhos de tabuleiro e orçamentos de tempo.
Jogo de Guerra: A MCPS supera o GRAVE em tabuleiros $9\times9$ e maiores. O algoritmo executa 15–33% mais rápido (mais simulações por segundo) devido a comprimentos de simulação mais curtos e converge em estados decisivos do jogo mais rapidamente.

Significado e Alegações

O artigo afirma que a MCPS representa uma melhoria significativa sobre o GRAVE para aplicações de MCTS de propósito geral, particularmente em cenários onde o aprendizado profundo não é uma opção. O mecanismo principal para o sucesso é a "regra de seleção melhor informada", que permite ao algoritmo:

Construir árvores de busca mais profundas.
Reduzir o trabalho de simulação por iteração (em alguns jogos).
Chegar mais perto de estados terminais (em jogos como AtariGo).
Converter tempo de computação adicional em exploração mais profunda de linhas promissoras (observado no Go).

Os autores enfatizam que o algoritmo é de propósito geral, não exigindo modificações ou treinamento específicos do problema. Os resultados sugerem que o benefício da MCPS é mais pronunciado quando a vantagem de profundidade resultante cai dentro do horizonte de decisão relevante do jogo. O artigo conclui que o conceito de combinar três fontes de estatísticas é reutilizável para outros tipos de estatísticas além das permutações.