- Monte-Carlo Graph Search (MCGS) é uma abordagem para jogos em que várias sequências de jogadas transitam para o mesmo estado, aplicando MCTS em um grafo dirigido em vez de uma árvore para compartilhar a exploração duplicada
- Se os contadores de visitas N e o valor médio Q do MCTS tradicional forem levados diretamente para um DAG, a contagem de visitas de filhos compartilhados pode se desalinha r com as estimativas de política e valor dos pais, tornando o algoritmo potencialmente incorreto
- Ao ver o MCTS como otimização regularizada de política, a distribuição de visitas por ação produzida pelo PUCT pode ser interpretada como uma política posterior, e Q como a utilidade esperada dessa política
- Um MCGS correto acompanha, separadamente das visitas ao nó filho, as visitas à aresta N(n,a), e recalcula Q como uma soma ponderada de
U(n) com os Q dos filhos, preservando o significado de política e valor também no grafo
- Na implementação real, ainda restam escolhas como stale Q, atualizações incrementais, se o playout deve continuar a partir de um filho transposto, e como lidar com colisões de hash e ciclos no jogo; hoje o KataGo usa atualizações idempotentes
Estados de transposição que a busca em árvore não captura
- Na busca em árvore de jogos, pode acontecer de diferentes sequências de jogadas levarem por transposição (transposition) ao mesmo estado
- No xadrez,
1. d4 d5 2. Nf3 e 1. Nf3 d5 2. d4 chegam à mesma posição
- Em jogos com transposições, à medida que a profundidade de busca aumenta, os estados duplicados podem crescer exponencialmente, então é desejável compartilhar o cálculo do mesmo estado
- Implementações comuns de MCTS tratam o jogo como uma árvore de ramificações e voltam a explorar várias instâncias da mesma posição
- Otimizações de baixo nível, como cache de avaliação da rede neural para posições repetidas, podem reduzir o custo
- Mas ainda fica o problema de que, mesmo que uma tática importante seja descoberta em uma instância e a avaliação seja corrigida, isso não se propaga para as outras instâncias
- Se o espaço de estados for modelado como um grafo acíclico dirigido (DAG), um estado alcançado por vários caminhos pode ser representado como um único nó
- O foco aqui é como o MCTS deve funcionar em um DAG, deixando de lado na maior parte o tratamento de jogos com ciclos reais
MCTS padrão: uma árvore que acumula estatísticas de execução
- O MCTS padrão armazena em memória uma árvore de nós correspondente à parte já explorada do jogo
- Cada nó normalmente acompanha os seguintes valores
N: número de playouts que até agora passaram por este nó ou terminaram neleQ: média acumulada dos valores de utilidade amostrados por esses playouts
- Um playout segue a seguinte ordem
- Começa na raiz e desce escolhendo a próxima ação segundo a fórmula de exploração
- Ao alcançar um estado ainda não explorado, adiciona um novo nó
- Obtém a utilidade
U do novo estado. O exemplo é consultar o value head de uma rede neural
- Volta pela árvore, incrementando
N de cada nó e atualizando a média Q
- No MCTS no estilo AlphaZero, a seleção de ações usa a fórmula PUCT
N(a): número de vezes que a ação a foi tentada; na árvore, isso é igual ao N do nó filho apontado por essa açãoQ(a): utilidade média da ação a; na árvore, isso é igual ao Q do nó filhoPlayerToMove: reflete se o jogador atual está maximizando ou minimizandoP(a): probabilidade prévia, como a previsão de política da rede neuralc_PUCT: constante ajustável
- “PUCT” vem da família Predictor UCT/UCB, que usa uma distribuição prévia prevista; a variante do AlphaZero difere da forma original
- O MCTS moderno pode ser determinístico ao usar avaliação por rede neural, mas o “Monte-Carlo” do nome vem do método antigo de fazer rollouts aleatórios até o fim para estimar a utilidade
- Depois de repetir playouts até acabar o orçamento computacional da jogada, a ação final escolhida na raiz não é a de maior
Q, mas sim o filho com maior contagem de visitas N
- Um filho com
Q alto e N baixo pode ser apenas um erro que pareceu bom por ruído em uma busca rasa
- A distribuição de visitas da raiz,
N(a) / ΣN(b), pode ser usada como alvo de aprendizado de política no loop de treinamento do AlphaZero
Problemas ao aplicar isso ingenuamente a um DAG
- Dá para manter quase o mesmo código de MCTS em árvore e, quando um novo estado do jogo já existir em
nodes_by_hash, apenas fazer o ponteiro apontar para o nó existente
- Esse método não preserva a hipótese da árvore de que a contagem de visitas do nó filho é igual à contagem de visitas da ação escolhida no pai
- Exemplo de situação
- O nó A prefere a ação que leva ao nó C, e o
Q de A é determinado principalmente por cerca de 30 playouts que exploraram C
- C também é visitado cerca de 40 vezes por outros caminhos de transposição
- Depois, C passa a ser ainda mais visitado por outro caminho de transposição, e a descoberta de uma tática mais profunda faz sua estimativa de utilidade subir de
0.39 → 0.51
- Como os playouts que atualizaram C não passaram por A, o
Q de A não reflete essa nova avaliação de C
- Mesmo que A volte a receber playouts depois disso, o PUCT pode explorar outras ações com poucas visitas em vez de C, que já tem muitas visitas
- Isso acontece porque C parece “já suficientemente explorado”
- Como resultado, o
Q de A pode até cair
- Essa extensão ingênua para grafos pode introduzir um viés artificial na média dos playouts, fazendo o pai explorar mais outras jogadas quanto mais um caminho de transposição visita uma linha já preferida
- O algoritmo se torna potencialmente incorreto, a ponto de nem ficar claro se converge para a jogada ótima mesmo com busca infinita
Atualizar todos os pais também não resolve
- Quando um nó é atualizado por um playout, também se pode imaginar refletir essa atualização não só nos pais realmente percorridos, mas em todos os pais e ancestrais
- Nesse esquema, o caso anterior de A-C permitiria atualizar também a utilidade de A
- Mas em outro exemplo, o pai D é contaminado por muitas visitas ao filho transposto F, que ele próprio não prefere
- O melhor filho de D é E, com
Q = 0.56, e o Q = 0.55 de D está de acordo com isso
- D explorou F apenas uma vez, mas F já foi visitado 9 vezes por outro caminho, totalizando 10 visitas
- Se depois F for visitado mais 100 vezes por outros caminhos e continuar com baixa utilidade, a estratégia de atualizar todos os pais pode arrastar o
Q de D até 0.35
- Do ponto de vista de D, ele não queria alocar tantos playouts a F, então atualizar todos os pais também quebra o significado da política
Ver o MCTS como otimização de política
valor maximizado por π:
Σ π(a) Q(a) - λ_N D_KL(P || π)
- Significado dos componentes
Σ π(a) Q(a): utilidade esperada estimada ao seguir a política πD_KL(P || π): divergência KL reversa que mede a diferença entre a política prévia P e a política posterior πλ_N: coeficiente que define a força do termo de KL e diminui conforme o número de visitas cresce
- A distribuição de visitas pode ser vista como uma política posterior que parte da política prévia
P da rede neural e vai melhorando à medida que mais visitas acumulam evidência sobre a utilidade das ações
- Assim, o MCTS pode ser interpretado como um algoritmo que executa simultaneamente um pequeno aprendizado online de política em cada nó da árvore
- Essa visão explica por que a distribuição de visitas se parece com a política de um agente forte e por que ela é usada como alvo de aprendizado de política no AlphaZero
- Também é possível calcular a solução exata do problema de otimização e usá-la como política, mas na prática isso pode dar peso excessivo a jogadas que receberam poucas visitas e por acaso parecem ter
Q alto
- Usar a distribuição de visitas como política posterior é mais robusto, porque uma jogada só ganha peso alto se realmente for bastante explorada
Reinterpretando Q: de média de playout para valor esperado da política
- Na definição padrão,
Q(n) de um nó n é a média das utilidades dos playouts que visitaram n
Q(n) = (1 / N(n)) Σ U(p)
- Reescrevendo isso em termos dos filhos, temos
Q(n) = (1 / N(n)) ( U(n) + Σ N(c) Q(c) )
- Aqui,
U(n) é a estimativa bruta de utilidade produzida pela rede neural para o próprio nó n, e N(c) Q(c) é o valor dos filhos ponderado pela contagem de visitas de cada filho
- Assim,
Q pode ser interpretado como uma média ponderada pela distribuição de visitas dos Q dos filhos
- Se a distribuição de visitas é a política posterior otimizada pelo MCTS, então
Q(n) é a utilidade esperada regularizada ao seguir essa política posterior
- Nessa interpretação, cada nó continua otimizando sua política para maximizar os
Q informados pelos filhos e atualiza seu próprio Q como a estimativa mais recente da utilidade esperada alcançável com essa política
- Se o
Q dos nós filhos converge para o valor ótimo em termos de teoria dos jogos, então a política e o Q do pai também convergem recursivamente para o ótimo
MCGS correto: separar visitas à aresta e visitas ao filho
- O problema no grafo surge porque se assume que as visitas ao filho de um pai ocorrem somente por meio desse pai
- Quando há caminhos de transposição, a contagem de visitas do nó filho pode diferir arbitrariamente do número de visitas que o PUCT queria alocar a partir daquele pai
- A solução é acompanhar separadamente o número acumulado de vezes que o PUCT escolheu uma ação em um nó específico
- Cada nó
n passa a acompanhar os seguintes valores
N(n): número total de vezes que esse nó foi visitadoN(n,a): número de vezes que o PUCT escolheu a ação a no nó n, isto é, a contagem de visitas da arestaQ(n) = (1 / N(n)) ( U(n) + Σ N(n,a) Q(n,a) )
- Aqui,
Q(n,a) é igual a Q(c) do nó filho c alcançado pela ação a
- No cálculo do PUCT, também se usa a contagem de visitas da aresta, e não a contagem de visitas do filho
argmax_a PlayerToMove(n) * Q(n,a)
+ c_PUCT P(n,a) sqrt(Σ N(n,b)) / (1 + N(n,a))
- O algoritmo básico escolhe as ações ao longo do caminho do playout, conecta a um nó já existente quando encontra um estado transposto, e na volta incrementa as visitas da aresta antes de recalcular
N e Q como função dos valores dos filhos
- Em alto nível, isso é semelhante a Monte-Carlo Graph Search for AlphaZero, de Czech, Korus e Kersting, mas aqui é derivado da perspectiva de otimização de política, e não da perspectiva de estatísticas de execução
Escolhas de implementação: stale Q e forma de atualização
- O pseudocódigo apresentado atualiza apenas os nós do caminho realmente percorrido pelo playout
- Por isso, o
Q de nós em caminhos não percorridos pode ficar stale Q
- Ainda assim, em teoria, o método é correto
- Fórmulas de exploração padrão como o PUCT tentam todas as ações infinitamente no limite
- Quando um nó é visitado de novo, seu
Q é calculado corretamente naquele momento usando o Q atual dos filhos e as visitas de aresta
- Em um DAG, no limite isso pode convergir para o valor ótimo em termos de teoria dos jogos
- O stale Q pode reduzir a eficiência da busca
- É possível manter ponteiros imediatos para os pais e atualizar também o
Q deles
- Também dá para atualizar todos os ancestrais em ordem topológica e eliminar o estado stale
- Outra opção é atualizar apenas o caminho do playout enquanto uma thread paralela separada procura nós stale e os atualiza
- O pseudocódigo usa atualizações idempotentes
- Não importa que atualizações intermediárias tenham ocorrido antes: ao visitar um nó uma vez,
N e Q passam a ficar corretos em relação aos valores atuais dos filhos
- Atualizações incrementais também são possíveis, mas em grafos é mais difícil torná-las equivalentes, ou equivalentemente corretas no limite
- Czech et al. abordam isso a partir da ótica de estatísticas de execução, então usam fórmulas mais incrementais
- Além da contagem de visitas da aresta, armazenam também o Q da aresta
- Incluem um mecanismo para o stale Q se aproximar gradualmente do valor mais recente, junto com um hiperparâmetro de tolerância a erro
- O pseudocódigo apresentado mostra que é possível fazer o MCGS funcionar sem novos hiperparâmetros de tolerância a erro nem armazenamento de Q por aresta
- O KataGo atualmente usa a fórmula idempotente
Continuar ou não o playout a partir de um filho transposto
- No MCTS em árvore, aumentar a visita da aresta e aumentar a visita do filho são o mesmo evento
- No grafo, por causa das transposições, o nó filho pode já ter sido visitado mais vezes do que aquela aresta específica
- Nesse caso, pode-se considerar que o filho já foi suficientemente visitado, interromper o playout, aumentar só a visita da aresta e então atualizar o pai e os ancestrais
- Razão para preferir interromper
- Se a visita da aresta é baixa e a visita do filho é alta, a informação marginal de visitar mais uma vez esse filho pode ser pequena
- Razão para preferir continuar
- Um nó cujo número de visitas é maior do que o da aresta provavelmente recebe transposições de vários pais e influencia mais partes da busca, então uma avaliação precisa pode ser mais importante
- Essa escolha continua sendo um campo experimental
- Também é possível usar uma regra por limiar e interromper só quando a visita do filho for suficientemente maior do que a visita da aresta
- O KataGo interrompe o playout por padrão, mas oferece opções de configuração para continuar ou interromper apenas probabilisticamente em parte dos casos
- O pseudocódigo não interrompe o playout; se necessário, basta adicionar uma checagem de uma linha com a condição
child.N <= edge_visits
Hashes, nós terminais e ciclos reais do jogo
- No pseudocódigo, nós terminais do jogo são recalculados como
N = 1, U = Q = utilidade do resultado do jogo, independentemente da contagem de visitas
- A contagem de visitas da aresta correspondente no pai ainda aumenta normalmente, então essa abordagem também funciona
- Se o resultado do jogo for estocástico e não for possível calcular diretamente a utilidade esperada, pode ser importante incrementar
N a cada visita ao nó terminal e fazer a média dos resultados amostrados
- Também é possível tratar a utilidade terminal de forma mais ampla para propagar valores comprováveis mais rapidamente pelo grafo
- MCTS/MCGS em geral não têm um mecanismo para reconhecer valores de utilidade certos, então quando estados terminais são importantes eles não convergem para o ótimo de forma tão barata quanto buscas clássicas como alpha-beta
- Para encontrar transposições, assume-se um hash único do estado do jogo
- Produzir um hash realmente livre de colisões para estados complexos pode ser difícil e caro
- Um Zobrist hash suficientemente grande, como 128 bits ou 192 bits, costuma ser suficiente na prática para praticamente evitar colisões, desde que os estados não sejam construídos de forma adversarial
- Para evitar recursão infinita quando uma colisão de hash criar um ciclo, pode-se adicionar detecção de ciclo
- O tratamento de ciclos reais vindos das próprias regras do jogo, como superko no Go ou repetição tripla no xadrez, não é discutido em detalhe
- O apêndice de 2024-03-10 fornece um link para um Google Docs com ideias mais preliminares sobre repetição e tratamento de ciclos, e pode exigir experimentos heurísticos específicos para cada jogo
- No tratamento de Go do KataGo, usa-se um resultado específico do jogo segundo o qual, para voltar à posição original depois de uma certa jogada, são necessárias pelo menos
S + E - 1 jogadas; isso permite limitar com segurança o compartilhamento de nós em situações relacionadas a ciclos
1 comentários
Comentários do Hacker News
Acho que esse tipo de busca em grafos é necessário para avançar o raciocínio em IA. Só com LLM simples, a chance de falhar é grande
O link tem muitas boas referências, incluindo hashing de Zobrist para tabelas de jogos https://en.wikipedia.org/wiki/Zobrist_hashing
Para que o custo computacional da busca em grafos não exploda, é preciso encontrar um bom hashing adequado a descrições de estado baseadas em linguagem
Sobre busca em árvores, também vale ler Thinking Fast and Slow: https://arxiv.org/abs/1705.08439 e Teaching Large Language Models to Reason with Reinforcement Learning, que compara a abordagem de MCTS com outras estratégias atuais de aprendizado por reforço: https://arxiv.org/abs/2403.04642
Um passo adiante poderia ser aprender em conjunto a representação de estado e o algoritmo de busca. A ideia seria buscar sobre uma representação de estado de rede neural da qual o algoritmo de busca consiga extrair custos
https://sites.google.com/view/genie-2024/
O Genie da DeepMind é um bom exemplo de modelagem de estados discretos. A rede neural aprende uma representação muito complexa, incluindo detecção de colisão e ações. Em vez de decodificar esse estado em pixels, provavelmente seria possível buscar diretamente sobre ele
Claro, na prática essa arquitetura pode ser bem diferente
Pegar um conjunto de argumentos lógicos, encontrar uma forma de atribuir um hash a cada argumento e representar esses hashes de argumentos em uma árvore de Merkle aninhada de acordo com os primeiros princípios
Se algum argumento for refutado com sucesso, o hash desse argumento muda, e os hashes dos subargumentos também se invalidam
Assim que vi o autor na URL do HN, reconheci na hora o gênio que criou o KataGo: https://github.com/lightvector/KataGo
Os posts que ele publica em https://www.reddit.com/r/cbaduk/ também são consistentemente excelentes
Não tenho tanta experiência assim com xadrez, mas sou cético quanto à afirmação de que a mesma posição se repete com frequência suficiente dentro da árvore de busca para ser importante. Queria ver medições reais com Leela Zero
Se incluir no estado a tripla repetição e a regra dos 50 lances, a chance de repetição deve ficar muito menor; digo isso mesmo sem considerar essa parte
É estranho o trecho que diz que, apesar do nome “Monte-Carlo Tree Search”, não há nenhum Monte Carlo no algoritmo acima e ele é totalmente determinístico. Eu achava que as implementações usuais de MCTS eram determinísticas; presumia que a amostragem tivesse aleatoriedade
Em projetos parecidos de hoje, isso foi substituído por avaliações neurais de qualidade maior. Jogar lances aleatórios para ver quem vence não é muito bom, mas na época era a melhor estratégia conhecida
No fim, a parte Monte Carlo nunca foi essencial no que hoje continua sendo chamado de MCTS; era mais um recurso de segunda linha. Por isso o nome acabou ficando um pouco infeliz
O interessante é que a maioria dos métodos de Monte Carlo depende de geradores pseudoaleatórios, não de geradores verdadeiramente aleatórios, então com a mesma semente e a mesma entrada o resultado sempre será o mesmo, de forma determinística
Esse algoritmo consulta uma rede neural em vez de usar um gerador pseudoaleatório comum e heurísticas separadas. A rede neural é uma heurística sobre um espaço de busca enorme e, dependendo do treino, funciona como um gerador pseudoaleatório muito ruim fortemente enviesado para certos resultados, acabando por parecer um gerador pseudoaleatório com heurística aplicada
O ponto importante é que isso é uma especialização de MCTS, então tecnicamente não se encaixa em todos os casos de uso
Quando fui estudar MCTS, o artigo citado no texto estava completamente fora do meu radar. Na próxima oportunidade, parece que seria bem divertido rodar eu mesmo essa modificação
Seria bom ter uma introdução simples
Em jogos nos quais o mesmo estado pode ser alcançado por vários caminhos, pode haver muito desperdício de memória ao registrar repetidamente o mesmo nó de estado em ramos diferentes
Este texto examina bem a abordagem de busca em grafos. Essencialmente, faz-se o cálculo extra de hash do estado do jogo para verificar se é um nó já visitado e, em troca, economiza-se memória
Como não é preciso registrar de novo nós já vistos, a árvore sem ciclos vira um grafo acíclico direcionado
Por causa disso, é preciso ajustar um pouco a busca em árvore para obter o resultado correto. Em especial, faz mais sentido otimizar por aresta, ou seja, ação ou jogada, do que por vértice, isto é, estado
É um ensaio técnico bem escrito, em estilo de programação literária, por alguém que entende muito bem do assunto