A Pesquisa do Google DeepMind Permite que um LLM Reescreva Seus Próprios Algoritmos de Teoria dos Jogos — E Superou os Especialistas

Projetar algoritmos para Multi-Agent Reinforcement Learning (MARL) em jogos de informação imperfeita — cenários onde os jogadores agem sequencialmente e não conseguem ver as informações privadas uns dos outros, como o pôquer — historicamente dependia de iteração manual. Pesquisadores identificam esquemas de ponderação, regras de desconto e resolvedores de equilíbrio por intuição e tentativa-e-erro. Pesquisadores do Google DeepMind propõem o AlphaEvolve, um agente de codificação evolutivo baseado em LLM que substitui esse processo manual por busca automatizada. A equipe de pesquisa aplica essa estrutura a dois paradigmas estabelecidos: Counterfactual Regret Minimization (CFR) e Policy Space Response Oracles (PSRO). Em ambos os casos, o sistema descobre novas variantes de algoritmos que têm desempenho competitivo ou superior aos baselines existentes de última geração projetados manualmente. Todos os experimentos foram executados usando o framework OpenSpiel. Contexto: CFR E PSRO CFR é um algoritmo iterativo que decompõe a minimização de arrependimento em conjuntos de informações. A cada iteração, ele acumula 'arrependimento contrafactual' — o quanto um jogador teria ganhado jogando de forma diferente — e deriva uma nova política proporcional ao arrependimento acumulado positivo. Ao longo de muitas iterações, a estratégia média no tempo converge para um Nash Equilibrium (NE). Variantes como DCFR (Discounted CFR) e PCFR+ (Predictive CFR+) melhoram a convergência aplicando regras específicas de desconto ou atualização preditiva, todas desenvolvidas por meio de design manual. O PSRO opera em um nível de abstração superior. Ele mantém uma população de políticas para cada jogador, constrói um tensor de payoff (o meta-jogo) calculando as utilidades esperadas para cada combinação de políticas populacionais e, em seguida, usa um resolvedor de meta-estratégia para produzir uma distribuição de probabilidade sobre a população. As melhores respostas são treinadas contra essa distribuição e adicionadas à população iterativamente. O resolvedor de meta-estratégia — como a distribuição da população é calculada — é a escolha de design central que o artigo visa para a descoberta automatizada. Todos os experimentos usam um oráculo de melhor resposta exata (calculado por iteração de valor) e valores de payoff exatos para todas as entradas do meta-jogo, removendo o ruído de amostragem de Monte Carlo dos resultados. O FRAMEWORK AlphaEvolve AlphaEvolve é um sistema evolutivo distribuído que usa LLMs para mutar o código-fonte em vez de parâmetros numéricos. O processo: uma população é inicializada com uma implementação padrão (CFR+ como semente para experimentos CFR; Uniforme como semente)