What rebuilding AlphaGo teaches us about self-play, RL, and future of LLMs - Eric Jang
Eric Jang explica como reconstruiu o AlphaGo do zero durante seu sabático, detalhando Monte Carlo Tree Search, redes neurais de política e valor, e auto-aprendizagem. O episódio conecta esses conceitos ao futuro dos LLMs, destacando como a busca em árvore pode superar a ineficiência do RL tradicional em modelos de linguagem.
Dwarkesh Patel (host)Eric Jang (ex-VP de IA na 1X, ex-Google DeepMind Robotics)
MCTS usa seleção (PUCT), expansão, avaliação (rede de valor) e backup para construir a árvore de busca incrementalmente, sem precisar explorar todo o espaço de estados.
A rede de política e a rede de valor compartilham representações em uma única arquitetura (ex.: ResNet), acelerando o aprendizado e garantindo consistência entre as previsões.
O auto-aprendizado do AlphaGo funciona como um operador de melhoria: MCTS gera políticas melhores que a rede bruta, e a rede é treinada para imitar essas políticas, criando um ciclo de refinamento.
MCTS é mais eficiente que RL ingênuo porque fornece um sinal de supervisão para cada ação individual (baixa variância), enquanto RL baseado em trajetórias inteiras sofre com alta variância e crédito esparso.
A capacidade de uma rede neural rasa (10 camadas) de amortizar uma busca combinatorialmente intratável sugere que muitos problemas NP-difíceis têm estrutura que pode ser explorada por redes neurais.
Em problemas sem modelo determinístico (ex.: StarCraft), o Neural Fictitious Self-Play (NFSP) substitui MCTS por treinar políticas de melhor resposta contra oponentes fixos, depois destilando-as em uma política mista.
A diferença fundamental entre MCTS e Q-learning é que MCTS planeja sobre trajetórias futuras não visitadas, enquanto Q-learning propaga recompensas para trás usando trajetórias já coletadas.
Para LLMs, a abordagem atual de RL (reforçar trajetórias que passam em testes) é análoga ao RL ingênuo de alto-variância; MCTS poderia oferecer um sinal mais local e eficiente, mas requer uma função de valor confiável.
Regras do Go e diferenças entre regras humanas e computacionais
O objetivo do Go é ocupar território colocando pedras pretas e brancas em um tabuleiro 19x19; pedras são capturadas quando todos os 4 vizinhos ortogonais são ocupados pelo oponente.
Nas regras Tromp-Taylor (usadas por AIs), jogadas de suicídio são permitidas e resolvidas imediatamente como captura, diferentemente das regras humanas (chinesas, japonesas).
A pontuação Tromp-Taylor conta pedras no tabuleiro mais interseções vazias cercadas apenas por um jogador; interseções tocadas por ambos os jogadores não contam para ninguém.
Humanos encerram o jogo por consenso (ambos passam e concordam com o território), enquanto AIs jogam até o fim para resolução determinística.
O jogo termina quando um jogador renuncia ou ambos passam consecutivamente; sob Tromp-Taylor, é necessário preencher todo o tabuleiro para determinar o vencedor.
Monte Carlo Tree Search (MCTS) sem redes neurais
O espaço de busca do Go é enorme: ~361 movimentos iniciais, profundidade de 250-300 jogadas, resultando em uma árvore com mais nós que átomos no universo.
MCTS constrói a árvore incrementalmente, evitando expansão completa: a cada simulação, seleciona um nó promissor, expande um filho, avalia o resultado e faz backup do valor.
A seleção usa a fórmula UCB1: argmax_a [Q(s,a) + c * sqrt(ln(N) / n_a)], onde Q é o valor médio da ação, N é o total de visitas ao nó pai, e n_a é o número de visitas à ação.
O termo de exploração (sqrt(ln(N)/n_a)) garante que ações pouco visitadas sejam eventualmente exploradas, mesmo com Q baixo.
O backup propaga o resultado (vitória/derrota) das folhas para os nós ancestrais, atualizando Q como a média dos valores dos filhos.
Sem redes neurais, MCTS é lento porque a maioria das ações leva a estados de baixo valor, exigindo muitas simulações para convergir.
Redes de política e valor: arquitetura e treinamento inicial
A rede de política (policy network) mapeia o estado do tabuleiro para uma distribuição de probabilidade sobre os 361 movimentos possíveis.
A rede de valor (value network) estima a probabilidade de vitória do jogador atual a partir do estado (valor entre 0 e 1).
Arquitetura típica: entrada codificada como 3 canais (preto, branco, vazio) → ResNet → duas cabeças: uma para política (361 saídas) e uma para valor (1 saída).
Eric Jang testou transformers, mas ResNets performaram melhor com orçamento computacional limitado, devido ao viés indutivo de convoluções locais.
O treinamento inicial pode usar dados de jogos humanos experts: a rede aprende a prever os movimentos dos vencedores e o resultado final do jogo.
Mesmo sem busca, a política pura (argmax da rede) já é um jogador forte, demonstrando que redes rasas (~10 camadas, ~3M parâmetros) podem capturar intuição do jogo.
MCTS com redes neurais: seleção, expansão, avaliação e backup
A cada simulação, a seleção usa PUCT: argmax_a [Q(s,a) + c_puct * P(s,a) * sqrt(N) / (1 + n_a)], onde P(s,a) é a probabilidade da política para aquela ação.
Ao atingir um nó não terminal, ele é expandido: a rede de política gera probabilidades para os filhos, e a rede de valor estima o valor do novo estado.
A avaliação original do AlphaGo Lee combinava a saída da rede de valor com uma jogada completa (rollout) usando a política pura, mas versões posteriores (AlphaGo Zero) eliminaram o rollout.
O backup atualiza Q(s,a) como a média dos valores de todos os filhos visitados, propagando recursivamente até a raiz.
Após N simulações (ex.: 200-2048), a política final é a distribuição de visitas normalizada: π(a|s) ∝ n_a^(1/τ), onde τ é um parâmetro de temperatura.
A árvore MCTS é descartada a cada movimento; apenas a política resultante é usada para selecionar a jogada.
Auto-aprendizagem (self-play) e melhoria iterativa
O algoritmo de treinamento do AlphaGo usa MCTS como operador de melhoria: para cada estado visitado durante o jogo, MCTS gera uma política melhor (π_MCTS) que a política bruta (π_θ).
A rede é treinada para minimizar a divergência entre π_θ e π_MCTS (loss de política) e o erro quadrático entre o valor previsto e o resultado real do jogo (loss de valor).
Isso é análogo ao algoritmo DAGGER em robótica: mesmo em trajetórias perdedoras, MCTS fornece ações corretivas para cada estado, gerando um sinal de supervisão denso.
O processo é iterativo: após treinar a rede para imitar MCTS com N simulações, a nova rede serve como ponto de partida para MCTS com N simulações, que agora alcança um nível ainda mais alto.
A função de valor precisa ser precisa para que MCTS funcione; Eric recomenda inicializar com dados humanos ou jogos aleatórios em tabuleiros pequenos (9x9) para bootstrapping.
Um problema comum é o colapso da função de valor em estados raros (ex.: finais de jogo); a solução é não permitir que o bot desista em uma fração dos jogos, gerando dados de resolução completa.
Comparação com RL ingênuo e conexão com LLMs
RL ingênuo (reforçar trajetórias vencedoras) sofre de alta variância: em 100 jogos entre agentes iguais, apenas ~1 jogo tem um movimento realmente melhor, mas 99 jogos geram 99×300 ações com sinal nulo ou enganoso.
A variância do gradiente no RL multi-step cresce quadraticamente com o comprimento da trajetória (devido ao produto de log-probabilidades e recompensas), tornando o aprendizado ineficiente.
LLMs atualmente usam RL de passo único (a sequência inteira é uma única ação), o que evita o problema de crédito multi-step, mas limita a eficiência da supervisão.
MCTS oferece um sinal de supervisão por ação (baixa variância), enquanto RL em LLMs precisa 'sugar a supervisão por um canudo' (analogia de Karpathy), dependendo de muitas trajetórias para extrair sinal útil.
Para aplicar MCTS em LLMs, seria necessário uma função de valor confiável para truncar a busca, o que ainda é um desafio em aberto (pesquisas do Google em 2023-2024 exploraram árvores de raciocínio).
Neural Fictitious Self-Play (NFSP) como alternativa sem busca
Em jogos sem modelo determinístico (ex.: StarCraft), não é possível construir uma árvore de busca facilmente; NFSP substitui MCTS por treinar políticas de melhor resposta contra oponentes fixos.
O processo: fixa um oponente (π_B), treina uma política π_BR usando RL model-free (PPO, SAC, etc.) para maximizar vitórias contra π_B.
Repete para múltiplos oponentes (π_B, π_C, π_D) e depois destila todas as políticas de melhor resposta em uma política mista que joga bem contra qualquer oponente.
NFSP ainda usa o princípio de 'rotular ações com um professor melhor', mas o professor é um RL model-free em vez de busca em árvore.
A desvantagem é que o RL model-free ainda sofre com alta variância, mas a destilação múltipla ajuda a reduzir o overfitting a um oponente específico.
Conexão entre MCTS e Q-learning
MCTS e Q-learning compartilham a ideia de propagar valores futuros para trás: MCTS faz backup de valores de folhas simuladas, enquanto Q-learning usa a equação de Bellman: Q(s,a) = r + γ * max_a' Q(s',a').
A diferença crucial: MCTS planeja sobre trajetórias não visitadas (simulações), enquanto Q-learning planeja sobre trajetórias já coletadas (experiência passada).
Q-learning permite recuperar uma política a partir dos valores Q (argmax), sem modelar explicitamente a política, similar ao que MCTS faz com as visitas.
Em problemas de alta dimensão (robótica), onde a simulação é cara, Q-learning é preferível; em jogos determinísticos como Go, MCTS é mais eficiente por usar busca direcionada.
Implicações para o futuro dos LLMs e problemas NP-difíceis
O fato de uma rede neural de 10 camadas conseguir amortizar a busca combinatorial do Go sugere que muitos problemas considerados NP-difíceis têm estrutura que pode ser explorada por redes neurais.
Isso não resolve P vs NP, mas mostra que aproximações práticas são possíveis mesmo para problemas intratáveis no pior caso (ex.: protein folding, AlphaTensor).
A previsão de propriedades macroscópicas (ex.: quem vence no Go) é mais fácil do que prever estados microscópicos exatos, análogo a prever a trajetória de um furacão vs. a velocidade do vento em um ponto.
Sistemas caóticos (como o tempo) podem ter atratores de baixa dimensão (ex.: Lorenz attractor) que são previsíveis em escala macro, mesmo que micro-estados sejam imprevisíveis.
Isso sugere que funções de valor podem ser treinadas para problemas complexos (clima, mercados financeiros) se houver uma estrutura macroestável subjacente.
Passos práticos
Para implementar um Go AI do zero: comece com regras Tromp-Taylor e um tabuleiro 9x9 para testes rápidos.
Inicialize a rede com dados de jogos humanos experts (ex.: KGS Go dataset) para obter uma política e valor razoáveis antes de tentar auto-aprendizagem.
Use ResNets em vez de transformers para problemas com forte estrutura local e orçamento computacional limitado.
Implemente MCTS com PUCT, começando com 200 simulações por movimento; aumente gradualmente conforme a rede melhora.
Para evitar colapso da função de valor, force o bot a jogar até o fim em 10% dos jogos de auto-aprendizagem, mesmo em posições perdedoras.
Se o problema não permite busca em árvore (ex.: ambientes contínuos), considere NFSP: treine políticas de melhor resposta contra oponentes fixos e destile-as.
Ao treinar RL para LLMs, explore variantes de advantage estimation (GAE) para reduzir a variância do gradiente em trajetórias longas.
Para problemas com estrutura macro previsível (ex.: previsão do tempo), foque em treinar funções de valor que capturem propriedades agregadas, não estados exatos.
Frases marcantes
"Uma rede neural de 10 camadas consegue amortizar e aproximar com alta fidelidade um problema de busca quase intratável."
"MCTS não tenta fazer crédito-assignment sobre vitórias; ele melhora o rótulo de cada ação individualmente."
"O que parece um problema NP-difícil no pior caso pode ter estrutura suficiente para ser resolvido na prática por redes neurais."
"Em RL ingênuo, você tem um sinal de supervisão para cada 99×300 ações neutras e uma ação realmente boa — a variância é péssima."
"A diferença entre MCTS e Q-learning é que um planeja sobre futuros não visitados, o outro sobre trajetórias já coletadas."
"Se você quer que MCTS funcione, a função de valor precisa ser precisa — senão a busca inteira desanda."
Mencionados no episódio
AlphaGo (DeepMind) - sistema de IA que venceu o campeão mundial de Go Lee Sedol
AlphaGo Zero (DeepMind) - versão que aprendeu sem dados humanos, apenas auto-aprendizagem
KataGo (David Wu, Jane Street) - implementação open-source de Go AI com eficiência 40x maior que AlphaGo Zero
Monte Carlo Tree Search (MCTS) - algoritmo de busca usado em AlphaGo
PUCT (Predictor Upper Confidence bound for Trees) - variante do UCB usada no AlphaGo
ResNet (Residual Network) - arquitetura de rede neural usada no AlphaGo
Transformer (Vaswani et al.) - arquitetura alternativa testada por Eric Jang
DAGGER (Dataset Aggregation) - algoritmo de imitation learning mencionado como análogo
Neural Fictitious Self-Play (NFSP) - algoritmo usado em AlphaStar e OpenAI Five
PPO (Proximal Policy Optimization) - algoritmo RL mencionado para treinar best responses
General Advantage Estimation (GAE) - paper de John Schulman sobre redução de variância em RL
Lorenz attractor - sistema caótico usado como analogia para previsibilidade macro
AlphaFold (DeepMind) - exemplo de problema NP-difícil resolvido por rede neural
AlphaTensor (DeepMind) - outro exemplo de problema combinatorial resolvido por RL
KGS Go dataset - dataset de jogos humanos experts mencionado para inicialização
Tromp-Taylor rules - regras de Go usadas por AIs, sem ambiguidades
Lee Sedol - jogador humano que perdeu para AlphaGo em 2016
Andrej Karpathy - mencionou a analogia 'sucking supervision through a straw'
Joshua Schlick - mencionado por pesquisa sobre redes neurais no limite do caos
Reiner - blog post sobre similaridade entre criptografia e redes neurais