Princípios básicos da Busca em Grafos de Monte Carlo
- A Busca em Árvores de Monte Carlo (MCTS), quando aplicada a um grafo direcionado em vez de uma árvore, torna-se a "Busca em Grafos de Monte Carlo" ("MCGS"), que às vezes é considerada difícil de implementar.
- Como a literatura acadêmica existente segue a explicação "padrão" da MCTS para árvores, é conceitualmente difícil entender como generalizá-la para grafos.
- Este documento apresenta uma explicação considerada mais intuitiva, essencialmente equivalente, mas mais limpa, e deriva a partir de princípios básicos por que a busca em grafos deve funcionar dessa maneira.
Introdução / contexto
- Em busca em árvore de jogos ou em outras aplicações de busca em árvore, é possível encontrar várias sequências de jogadas ou ações possíveis que levam ao mesmo estado.
- Por exemplo, no xadrez,
1. d4 d5 2. Nf3 leva à mesma posição que 1. Nf3 d5 2. d4.
- Quando esse tipo de situação é possível em um jogo, o número de casos possíveis cresce geometricamente junto com a profundidade da busca, tornando buscas profundas mais caras do que o necessário.
- Idealmente, queremos que esses ramos da busca compartilhem computação.
- No entanto, implementações padrão de MCTS tratam o jogo como uma árvore ramificada e reexploram de forma ineficiente posições duplicadas dentro da árvore.
Explicação comum da MCTS - árvore de estatísticas em execução
- A MCTS costuma ser descrita como um algoritmo que acompanha estatísticas em execução dos playouts que passam pelos nós de uma árvore.
- Cada nó representa um único estado do jogo e acompanha a contagem de visitas (N) e a média em execução (Q) dos valores de utilidade amostrados pelos playouts.
- Uma única iteração ou playout de MCTS consiste em amostrar a próxima ação a explorar ao descer pela árvore, expandir a árvore ao alcançar um novo estado, estimar a utilidade U do novo estado e, ao subir de volta pela árvore, incrementar N em cada nó e atualizar a média Q com a nova utilidade U amostrada.
O que dá errado em um grafo?
- Se o algoritmo acima for aplicado diretamente a um grafo acíclico direcionado em vez de uma árvore, ele pode se tornar incorreto.
- Isso ocorre porque a MCTS costuma ser explicada em termos de estatísticas em execução dos playouts como uma extensão de métodos baseados em bandido de múltiplos braços.
- Czech, Korus e Kersting resolveram esse problema e chegaram a um algoritmo sólido, mas existe uma forma alternativa de abordar a MCTS a partir da perspectiva de aprendizado de política online.
- Nessa explicação alternativa, a generalização para grafos surge de forma relativamente natural.
Reinterpretando MCTS como otimização de política regularizada
- Quando a MCTS atualiza estatísticas em diferentes nós, na prática ela está executando uma forma de aprendizado de política online.
- A distribuição de visitas da MCTS representa aproximadamente uma política "posterior" que melhora gradualmente a política prévia P da rede neural para maximizar a utilidade esperada.
Executando corretamente a Busca em Grafos de Monte Carlo
- Todos os problemas que surgem ao estender a MCTS para grafos vêm da suposição de visitas ao nó filho apenas a partir de nós pais.
- Como a teoria garante que as contagens acumuladas de ações selecionadas pelo PUCT fornecem uma política posterior que aproxima a política otimizada π, é isso que deve ser acompanhado.
- Se usarmos a interpretação de que o valor Q reportado por um nó é o valor esperado da política posterior, podemos aplicar a fórmula recursiva de Q sem precisar tratar de como calcular playouts individuais.
Discussão sobre escolhas de implementação
- O algoritmo apresentado neste documento é muito semelhante ao algoritmo de Czech, Korus e Kersting, mas há algumas escolhas de implementação e algumas diferenças pequenas.
- Há várias maneiras que podem ser escolhidas em nome da simplicidade de implementação, como estratégias para reduzir a "desatualização" dos valores Q ou o uso de atualizações idênticas em vez de incrementais.
Opinião do GN⁺
- Este artigo pode despertar o interesse de pessoas ligadas à inteligência artificial e à teoria dos jogos ao apresentar a complexidade da Busca em Grafos de Monte Carlo (MCGS) e uma nova abordagem para entendê-la.
- Algoritmos como MCTS desempenham um papel importante em jogos estratégicos complexos como xadrez e Go, contribuindo para o desenvolvimento de inteligência artificial nesses jogos.
- No entanto, o conteúdo abordado neste artigo pode ser um pouco difícil para engenheiros de software iniciantes, exigindo conhecimento teórico prévio.
- Ao implementar MCGS, um ponto a considerar é como equilibrar eficiência e precisão do algoritmo, algo que pode ter grande impacto no desempenho em ambientes reais de jogo.
- Um projeto ou produto com função semelhante é o AlphaZero, da DeepMind, que atingiu um nível superior ao dos melhores humanos em xadrez, Go e shogi.
1 comentários
Comentários no Hacker News
A exploração de grafos é necessária para o avanço do raciocínio em inteligência artificial, e LLMs simples vão falhar. O link traz muitas boas referências, incluindo Zobrist hashing para tabelas de jogos. É preciso encontrar um bom hashing para descrições de estado baseadas em linguagem para que a exploração de grafos não exploda computacionalmente. Boas leituras sobre busca em árvores são 'Thinking Fast and Slow' e 'Teaching Large Language Models to Reason with Reinforcement Learning', que comparam a abordagem de MCTS com outras estratégias atuais de RL.
Reconheci imediatamente, pela URL do HN, o desenvolvedor genial do KataGo. As postagens dele no Reddit em cbaduk são consistentemente excelentes.
Sobre o nome "Monte-Carlo Tree Search", os leitores devem perceber que não há nada de "Monte-Carlo" no algoritmo mencionado, e que ele é totalmente determinístico. É estranho que o MCTS geralmente seja implementado de forma determinística. Eu tinha presumido que houvesse aleatoriedade na amostragem.
O artigo mencionado passou completamente fora do meu radar quando eu estava estudando MCTS. Vai ser muito divertido tentar essa modificação na próxima oportunidade.
Conhecimento de contexto: