Autopartida

No artigo anterior, apresentamos os conceitos básicos do aprendizado por reforço. Agora, vamos explorar uma das chaves para o sucesso do AlphaGo — Autopartida (Self-Play).

Este é um conceito aparentemente contraditório: Como a IA pode ficar mais forte jogando contra si mesma?

A resposta é profunda e elegante, envolvendo teoria dos jogos, dinâmica evolutiva e a natureza do aprendizado.

---

Por que a autopartida funciona?

Explicação intuitiva

Imagine que você é um iniciante de Go, praticando sozinho em uma ilha deserta:

1. Você joga uma partida, jogando tanto com as pretas quanto com as brancas
2. Após a partida, você analisa quais jogadas foram boas e quais foram ruins
3. Na próxima partida, você tenta evitar os erros anteriores
4. Você repete este processo milhões de vezes

Intuitivamente, isso parece problemático:

• Se seu nível é muito baixo, ambos os lados jogam mal, o que você pode aprender?
• Você poderia cair em "equilíbrio errado" — ambos os lados jogam errado mas se anulam?

Mas na realidade, a autopartida pode produzir progresso contínuo. Eis o porquê:

Descoberta progressiva de fraquezas

A insight chave é: mesmo que ambos os lados sejam a mesma IA, o resultado de cada partida ainda contém informação.

Posição A: IA escolheu jogada X, eventualmente venceu
Posição A: IA escolheu jogada Y, eventualmente perdeu

→ Conclusão: Na posição A, X é melhor que Y

Através de estatísticas de muitas partidas, a IA pode aprender quais escolhas são melhores em cada posição. Esta é a essência do gradiente de política: boas escolhas são reforçadas, más escolhas são suprimidas.

Aprendizado adversarial

A autopartida tem uma propriedade especial: o oponente de treinamento se adapta automaticamente ao seu nível.

Ciclo de treinamento 1: IA descobre uma tática eficaz T
Ciclo de treinamento 2: IA como oponente aprende a defender contra T
Ciclo de treinamento 3: IA original é forçada a encontrar tática melhor T'

Isso forma uma corrida armamentista (Arms Race), ambos os lados continuamente descobrindo e superando as fraquezas um do outro.

Comparação com partidas humanas

Método de treinamento	Vantagens	Desvantagens
Partidas humanas	Aprende a cristalização da sabedoria humana	Limitado ao nível humano
Autopartida	Potencial de melhoria ilimitado	Pode cair em ótimo local
Combinação de ambos	Início rápido + melhoria contínua	Melhor estratégia

A versão original do AlphaGo primeiro usou partidas humanas para aprendizado supervisionado, depois autopartida para aprendizado por reforço. O AlphaGo Zero provou que apenas autopartida pode alcançar nível super-humano.

---

Perspectiva da teoria dos jogos

Equilíbrio de Nash

Na teoria dos jogos, Equilíbrio de Nash (Nash Equilibrium) é um estado estável: neste estado, nenhum jogador tem motivo para mudar sua estratégia unilateralmente.

Para jogos de soma zero com informação perfeita como Go, o equilíbrio de Nash tem significado especial:

$\pi^* = \arg\max_\pi \min_{\pi'} V(\pi, \pi')$

Onde $V(\pi, \pi')$ é o valor esperado quando a estratégia $\pi$ joga contra a estratégia $\pi'$.

Este é o famoso Princípio Minimax: a melhor estratégia é aquela que tem o melhor desempenho no pior cenário.

Autopartida e equilíbrio de Nash

Teoricamente, se a autopartida pode convergir, ela deve convergir para o equilíbrio de Nash. Para jogos determinísticos como Go, o equilíbrio de Nash é o jogo perfeito.

Mas o espaço de estados do Go é muito grande ($10^{170}$), é impossível encontrar o verdadeiro equilíbrio de Nash. A autopartida na verdade está aproximando este equilíbrio.

Fictitious Play (Jogo fictício)

A autopartida está relacionada ao conceito de Fictitious Play na teoria dos jogos:

1. Cada jogador observa o histórico de estratégias do oponente
2. Calcula a distribuição média das estratégias do oponente
3. Escolhe a melhor resposta contra esta distribuição média

Sob certas condições, pode-se provar que o Fictitious Play converge para o equilíbrio de Nash.

A autopartida do AlphaGo pode ser vista como uma implementação de rede neural deste conceito.

---

Mecanismo da autopartida

Fluxo básico

Fluxo de autopartida do AlphaGo:

Algoritmo: Self-Play Training

Inicialização: Policy Network π_θ (pode começar de aprendizado supervisionado ou inicialização aleatória)

Repetir os seguintes passos até convergência:

1. Gerar dados de partida
   Para i = 1 até N (em paralelo):
     a. Usar política atual π_θ para uma autopartida
     b. Coletar trajetória: τ_i = (s_0, a_0, r_1, s_1, a_1, ...)
     c. Registrar resultado final z_i ∈ {-1, +1}

2. Atualizar política
   a. Calcular gradiente de política:
      ∇J = (1/N) Σ_i Σ_t ∇_θ log π_θ(a_t|s_t) · z_i
   b. Atualizar parâmetros: θ ← θ + α · ∇J

3. Atualizar rede de valor
   a. Treinar Value Network com pares (s, z)
   b. Minimizar: L = E[(V_φ(s) - z)²]

4. Opcional: Avaliar e salvar checkpoint
   a. Nova política joga contra versões antigas
   b. Se taxa de vitória > 55%, atualizar pool de oponentes

Geração de dados de treinamento

Cada autopartida produz uma trajetória (trajectory):

$\tau = (s_0, a_0, s_1, a_1, \ldots, s_T, z)$

Onde:

• $s_t$: estado do tabuleiro no passo $t$
• $a_t$: ação escolhida no passo $t$
• $z$: resultado final (+1 vitória, -1 derrota)

Uma partida de 200 movimentos produz 200 amostras de treinamento. Com centenas de milhares de autopartidas por dia, a quantidade de dados de treinamento é impressionante.

Atualização de política

Usar gradiente de política para atualizar a Policy Network:

$\theta \leftarrow \theta + \alpha \cdot \nabla_\theta \mathbb{E}\left[\sum_t \log \pi_\theta(a_t|s_t) \cdot z\right]$

O efeito desta atualização:

• Se eventualmente vencer ($z = +1$), aumenta a probabilidade de todos os movimentos
• Se eventualmente perder ($z = -1$), diminui a probabilidade de todos os movimentos

Isso parece grosseiro — ao vencer pode haver jogadas ruins, ao perder pode haver boas jogadas. Mas através de estatísticas de muitas partidas, esse "ruído" é nivelado, jogadas verdadeiramente boas são identificadas.

Treinamento da rede de valor

A Value Network usa treinamento de regressão (regression):

$\phi \leftarrow \phi - \beta \cdot \nabla_\phi \mathbb{E}\left[(V_\phi(s) - z)^2\right]$

Isso faz a Value Network aprender a prever: a partir da posição atual, qual é a probabilidade de vitória eventual?

O papel da Value Network é:

1. Fornecer avaliação de nó folha no MCTS
2. Servir como baseline para gradiente de política
3. Uso direto para avaliação de posição

---

Importância da aleatoriedade

Evitar ciclos determinísticos

Se a autopartida for completamente determinística, pode cair em ciclo:

Política A sempre joga abertura fixa
Política A vs Política A sempre produz mesma partida
Apenas uma partida é repetidamente aprendida
IA não pode explorar outras possibilidades

É por isso que aleatoriedade é crucial na autopartida.

Fontes de aleatoriedade

Maneiras do AlphaGo introduzir aleatoriedade na autopartida:

1. A própria rede de política é estocástica

A Policy Network produz distribuição de probabilidade, não escolha determinística:

$a \sim \pi_\theta(a|s)$

Mesma posição, cada vez pode escolher jogada diferente.

2. Parâmetro de temperatura

Usar temperatura mais alta durante treinamento para aumentar diversidade:

$\pi_\tau(a|s) = \frac{\pi_\theta(a|s)^{1/\tau}}{\sum_{a'} \pi_\theta(a'|s)^{1/\tau}}$

• $\tau > 1$: mais aleatório, mais exploração
• $\tau < 1$: mais determinístico, mais exploitation
• $\tau = 1$: distribuição original

3. Ruído de Dirichlet (Dirichlet Noise)

O AlphaGo Zero adiciona ruído de Dirichlet às probabilidades prévias do nó raiz durante autopartida:

$P(s, a) = (1 - \varepsilon) \cdot \pi_\theta(a|s) + \varepsilon \cdot \eta_a$

Onde $\eta \sim \text{Dir}(\alpha)$, $\varepsilon = 0.25$, $\alpha = 0.03$ (para as 361 ações do Go).

Isso garante que mesmo jogadas de probabilidade muito baixa tenham chance de serem exploradas.

Método de pool de oponentes (Population)

Outra maneira de aumentar diversidade é manter um pool de oponentes:

Pool de oponentes = [π_1, π_2, π_3, ..., π_k] (diferentes versões de políticas)

Cada partida:
1. Selecionar aleatoriamente um oponente do pool
2. Jogar contra esse oponente
3. Usar resultado para atualizar política atual
4. Periodicamente adicionar políticas melhoradas ao pool

Benefícios deste método:

• Diversidade: oponentes de diferentes estilos
• Estabilidade: evita overfitting a oponente específico
• Robustez: aprende a lidar com várias estratégias

Tanto o AlphaGo original quanto o AlphaGo Zero usaram técnicas similares.

---

Curva de crescimento de força de jogo

Sistema de classificação Elo

Para rastrear mudanças na força de jogo da IA, o AlphaGo usou o Sistema de classificação Elo.

Princípio básico do sistema Elo:

$P(\text{A vence}) = \frac{1}{1 + 10^{(R_B - R_A)/400}}$

Onde $R_A$ e $R_B$ são as pontuações Elo de ambos os lados.

• Diferença de 200: mais forte esperado vencer 75%
• Diferença de 400: mais forte esperado vencer 90%
• Diferença de 800: mais forte esperado vencer 99%

Crescimento de força de jogo do AlphaGo

Vamos visualizar o crescimento de força de jogo das várias versões do AlphaGo:

載入中...

Análise de velocidade de crescimento

Da curva, podemos observar vários fenômenos interessantes:

1. Crescimento rápido inicial

Nas primeiras horas de treinamento, a IA aprende regras básicas e táticas simples. Esta é a fase de frutos de fácil colheita — há muitos erros óbvios para corrigir.

2. Crescimento estável no meio

Conforme erros básicos são eliminados, a IA começa a aprender táticas e joseki mais sutis. Velocidade de crescimento diminui, mas ainda estável.

3. Crescimento desacelera no final

Quando a IA já está muito forte, melhorar mais se torna difícil. Pode precisar descobrir estratégias completamente novas, não apenas corrigir erros.

O momento de superar humanos

Marcos-chave na curva de treinamento do AlphaGo:

Marco	Equivalente a	Tempo para alcançar
Superar amadores fortes	Elo ~2700	Cerca de 3 horas
Superar Fan Hui	Elo ~3500	Cerca de 36 horas
Superar Lee Sedol	Elo ~4500	Cerca de 60 horas
Superar AlphaGo original	Elo ~5000	Cerca de 72 horas

Estes números (do AlphaGo Zero) são impressionantes: a IA em 3 dias do zero superou milhares de anos de sabedoria humana de Go.

---

Análise de convergência

A autopartida converge?

Esta é uma importante questão teórica. Resposta curta: sob certas condições sim, mas Go é muito complexo para provar rigorosamente.

Garantias teóricas

Para jogos mais simples (como jogo da velha), pode-se provar:

1. Existência: existe equilíbrio de Nash (Teorema Minimax)
2. Convergência: certos algoritmos (como Fictitious Play) convergem para equilíbrio de Nash

Para Go, não temos garantia rigorosa de convergência, mas evidências experimentais mostram:

• Força de jogo melhora continuamente
• Sem oscilação óbvia ou degradação
• Força final supera todos os humanos conhecidos

Possíveis modos de falha

Problemas que a autopartida pode encontrar:

1. Ciclo de estratégias (Strategy Cycling)

Estratégia A derrota estratégia B
Estratégia B derrota estratégia C
Estratégia C derrota estratégia A

Isso realmente acontece em alguns jogos (como pedra-papel-tesoura). Mas Go tem complexidade suficiente, este tipo de ciclo puro parece não ocorrer.

2. Overfitting a si mesmo

A IA pode aprender estratégias que só funcionam contra seu próprio estilo, não contra outros estilos de oponentes. Por isso o AlphaGo joga contra diferentes versões de si mesmo, e eventualmente testa contra jogadores humanos.

3. Ótimo local

A IA pode cair em ótimo local — uma estratégia "razoável mas não a melhor". Aleatoriedade e muitas partidas ajudam a evitar este problema.

Observações práticas

Das observações do processo de treinamento do AlphaGo:

1. Progresso contínuo: pontuação Elo sobe continuamente com treinamento
2. Sem degradação: não há queda repentina de força de jogo
3. Evolução de estilo: estilo de jogo da IA muda gradualmente com treinamento
4. Descoberta de novos joseki: IA descobre aberturas e táticas nunca usadas por humanos

Estas observações mostram que, embora não tenhamos garantia teórica, a autopartida funciona na prática.

---

Detalhes de implementação

Autopartida paralela

Para acelerar o treinamento, o AlphaGo usa autopartida massivamente paralela:

Decisões de design chave:

• Síncrono vs assíncrono: AlphaGo usa atualizações assíncronas, Workers não precisam esperar uns pelos outros
• Frequência de atualização: atualiza parâmetros a cada N partidas completadas
• Seleção de oponente: seleciona aleatoriamente uma das versões recentes como oponente

Estratégia de checkpoint

Salvar checkpoints de modelo periodicamente, para:

1. Pool de oponentes: manter diferentes versões de oponentes
2. Avaliação: rastrear mudanças de força de jogo
3. Recuperação de falhas: pode recuperar se treinamento for interrompido

# Pseudocódigo
def training_loop():
    for iteration in range(num_iterations):
        # Gerar dados de partida
        trajectories = parallel_self_play(current_policy, num_games=1000)

        # Atualizar política
        update_policy(trajectories)

        # Avaliar e salvar periodicamente
        if iteration % 100 == 0:
            elo = evaluate_against_pool(current_policy)
            save_checkpoint(current_policy, elo)

            if elo > best_elo:
                add_to_pool(current_policy)
                best_elo = elo

Requisitos de recursos de treinamento

A escala de treinamento do AlphaGo é impressionante:

Versão	Hardware	Tempo de treinamento	Partidas de autopartida
AlphaGo Fan	176 GPUs	Vários meses	~30M
AlphaGo Lee	48 TPUs	Várias semanas	~30M
AlphaGo Zero	4 TPUs	3 dias	~5M
AlphaGo Zero (versão 40 dias)	4 TPUs	40 dias	~30M

Note que o AlphaGo Zero alcançou força maior com menos hardware e menos tempo — isso é melhoria de eficiência algorítmica.

Configuração de hiperparâmetros

Alguns hiperparâmetros chave:

# Configurações de autopartida
NUM_PARALLEL_GAMES = 5000      # Número de partidas simultâneas
GAMES_PER_ITERATION = 25000    # Partidas por iteração
MCTS_SIMULATIONS = 1600        # Simulações MCTS por movimento

# Configurações de treinamento
BATCH_SIZE = 2048              # Tamanho do lote de treinamento
LEARNING_RATE = 0.01           # Taxa de aprendizado inicial
L2_REGULARIZATION = 1e-4       # Weight decay

# Configurações de exploração
TEMPERATURE = 1.0              # Temperatura para primeiros 30 movimentos
DIRICHLET_ALPHA = 0.03         # Parâmetro de ruído de Dirichlet
EXPLORATION_FRACTION = 0.25    # Proporção de ruído

Estes hiperparâmetros foram ajustados através de muitos experimentos e têm impacto significativo no efeito do treinamento.

---

Variantes de autopartida

AlphaGo original

Fluxo de treinamento do AlphaGo original:

1. Aprendizado Supervisionado (SL): aprender de partidas humanas
   → Produz SL Policy Network (π_SL)

2. Aprendizado por Reforço (RL): autopartida
   Inicializar π_RL = π_SL
   Pool de oponentes = [π_SL]

   Repetir:
     a. π_RL joga contra políticas do pool
     b. Atualizar π_RL com gradiente de política
     c. Se π_RL ficou mais forte, adicionar ao pool

   → Produz RL Policy Network (π_RL)

3. Treinamento da rede de valor:
   Usar π_RL para autopartida e gerar posições
   Treinar V(s) para prever taxa de vitória

AlphaGo Zero

O AlphaGo Zero simplificou este fluxo:

1. Autopartida pura (sem dados humanos)
   Inicializar rede aleatória f_θ

   Repetir:
     a. Usar MCTS + f_θ para autopartida
     b. Treinar cabeça de política e cabeça de valor simultaneamente
     c. Atualizar f_θ

   → Rede única produz política e valor simultaneamente

Melhorias chave:

• Sem necessidade de dados humanos: começa do zero
• Rede única: política e valor compartilham características
• Treinamento mais conciso: aprendizado end-to-end

AlphaZero

O AlphaZero generalizou ainda mais:

Mesmo algoritmo, diferentes jogos:
- Go: alcançou nível superior ao AlphaGo Zero
- Xadrez: superou Stockfish
- Shogi: superou Elmo

Única parte específica do jogo: codificação de regras

Isso prova que autopartida é um paradigma de aprendizado universal, não limitado ao Go.

---

O que os humanos aprenderam?

Novos joseki descobertos pela IA

A autopartida produziu muitas jogadas nunca usadas por humanos:

1. Inovações de abertura

Algumas aberturas preferidas pelo AlphaGo:

• Invasão 3-3: invadir canto cedo
• Jogadas altas: tradicionalmente consideradas "instáveis"
• Variação grande avalanche: humanos consideram complexa demais para calcular

2. Nova avaliação de posição

A avaliação de certas posições pela IA difere muito da dos humanos:

• Certas formas aparentemente "finas" são na verdade sólidas
• O valor de certa "espessura" é superestimado
• Reavaliação de "sente" e "gote"

Impacto no Go humano

Após o AlphaGo, o Go profissional mudou significativamente:

1. Diversificação de aberturas: jogadores profissionais começaram a usar novas aberturas descobertas pela IA
2. Mudança de métodos de treinamento: IA se tornou ferramenta principal de treinamento de profissionais
3. Repensando teoria de Go: muita "teoria" tradicional foi questionada e corrigida
4. Nova estética: começando a apreciar Go estilo IA

Ke Jie disse após perder para o AlphaGo:

"O AlphaGo me fez redescobrir o Go. Eu achava que humanos entendiam Go, agora sei que apenas tocamos a superfície."

---

Reflexões filosóficas

A natureza do aprendizado

A autopartida levanta questões profundas sobre aprendizado:

De onde vem o conhecimento?

• Aprendizado humano depende de informação externa (professores, livros, experiência)
• IA de autopartida só tem regras, sem conhecimento externo
• Mas ainda pode "descobrir" conhecimento — de onde vem este conhecimento?

A resposta pode ser: o conhecimento está implícito nas regras e estrutura do jogo. As regras do Go definem o que são boas e más jogadas, a autopartida apenas revela estas estruturas implícitas.

Criatividade e descoberta

Quando a IA joga o "Movimento de Deus" (Movimento 37), isso é criação ou descoberta?

Uma visão é: aquele movimento sempre "existiu" nas regras do Go, a IA apenas o "descobriu". Outra visão é: a IA "criou" aquele movimento, porque ninguém (incluindo a própria IA) sabia disso antes.

Esta questão não tem resposta padrão, mas desafia nossa compreensão tradicional de criatividade.

O lugar da inteligência humana

Se a IA pode do zero, através de autopartida, superar milhares de anos de sabedoria humana, o que isso significa para os humanos?

Visão otimista:

• IA é uma ferramenta criada por humanos
• Descobertas da IA podem melhorar a compreensão humana
• Humanos podem colaborar com IA para alcançar níveis mais altos

Visão cautelosa:

• Em certas áreas, computação pura pode superar intuição humana
• Precisa repensar o valor de "habilidades especializadas"
• Métodos de educação e treinamento podem precisar mudar

---

Correspondência de animações

Os conceitos centrais abordados neste artigo e números de animação:

Número	Conceito	Correspondência física/matemática
E5	Ciclo de autopartida	Iteração de ponto fixo
E6	Evolução de estratégia	Dinâmica evolutiva

---

Resumo

A autopartida é uma das tecnologias-chave para o sucesso do AlphaGo. Aprendemos:

1. Por que funciona: aprendizado adversarial, descoberta progressiva de fraquezas
2. Mecanismo: coleta de trajetórias, gradiente de política, treinamento de rede de valor
3. Aleatoriedade: parâmetro de temperatura, ruído de Dirichlet, pool de oponentes
4. Crescimento de força de jogo: sistema Elo, análise de curva de crescimento
5. Convergência: garantias teóricas e observações práticas
6. Detalhes de implementação: treinamento paralelo, estratégia de checkpoint, hiperparâmetros

No próximo artigo, exploraremos como o AlphaGo combina redes neurais com MCTS, aproveitando as vantagens de ambos.

---

Leitura adicional

• Próximo artigo: Combinação de MCTS e Redes Neurais — A combinação perfeita de intuição e raciocínio
• Artigo anterior: Introdução ao Aprendizado por Reforço — Conceitos básicos de aprendizado por reforço
• Relacionado: Visão Geral do AlphaGo Zero — O avanço a partir do zero

---

Referências

1. Silver, D., et al. (2016). "Mastering the game of Go with deep neural networks and tree search." Nature, 529, 484-489.
2. Silver, D., et al. (2017). "Mastering the game of Go without human knowledge." Nature, 550, 354-359.
3. Silver, D., et al. (2018). "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play." Science, 362(6419), 1140-1144.
4. Heinrich, J., & Silver, D. (2016). "Deep Reinforcement Learning from Self-Play in Imperfect-Information Games." arXiv preprint.
5. Lanctot, M., et al. (2017). "A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning." NeurIPS.