Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding

1. O Problema

O artigo aborda o desafio de gerar automaticamente conteúdo de jogos de alta qualidade e diversificado, especificamente no contexto de montagem de decks no jogo de cartas colecionáveis Hearthstone.

• Desafio Principal: Avaliar a qualidade de um deck candidato é extremamente custoso computacionalmente. Devido à alta variância dos estados iniciais e ações estocásticas no jogo, é necessário simular pelo menos 200 partidas contra oponentes variados para obter uma avaliação confiável de um único deck.
• Limitação de Métodos Anteriores: Algoritmos de Diversidade de Qualidade (Quality Diversity - QD), como o MAP-Elites, são eficazes para encontrar coleções de soluções diversas e de alto desempenho. No entanto, o MAP-Elites padrão requer um número massivo de avaliações no motor do jogo (SabberStone) para explorar o espaço de busca, tornando o processo ineficiente.
• Limitação de Modelos Surrogatos Offline: Abordagens anteriores que usavam modelos substitutos (surrogate models) treinados offline com dados rotulados aleatoriamente sofriam com a descoberta de "exemplos adversariais" (soluções de baixa qualidade que o modelo prevê erroneamente como boas) e não conseguiam generalizar bem para novas regiões do espaço de busca.

2. Metodologia: DSA-ME (Deep Surrogate Assisted MAP-Elites)

Os autores propõem o DSA-ME, um algoritmo de Diversidade de Qualidade baseado em modelo que utiliza um modelo substituto profundo (Deep Neural Network) treinado online para guiar a busca.

O algoritmo opera em dois loops interconectados (visualizados na Figura 1 do artigo):

• Loop Interno (Inner Loop):
  • Utiliza o MAP-Elites para explorar o espaço de busca, mas avalia os candidatos diretamente no modelo substituto profundo (e não no motor do jogo).
  • O modelo substituto prevê o objetivo (diferença de vida média) e as métricas de comportamento (número médio de cartas na mão e duração média do jogo).
  • Este loop gera um arquivo diversificado de "elites" (soluções promissoras) segundo a previsão do modelo.
• Loop Externo (Outer Loop):
  • Seleciona as elites do arquivo do modelo substituto e as avalia no motor real do jogo (SabberStone).
  • Essas avaliações geram dados rotulados de "verdade terrestre" (ground-truth).
  • Esses novos dados são adicionados a um buffer de treinamento para re-treinar o modelo substituto, melhorando sua precisão iterativamente.
  • As elites validadas são adicionadas ao arquivo final de "verdade terrestre".

Inovações Técnicas:

• Treinamento Online: Diferente de modelos estáticos, o modelo é continuamente atualizado com dados gerados pela própria busca do MAP-Elites. Isso permite que o modelo aprenda a corrigir seus próprios erros e explore regiões complexas do espaço de busca que seriam ignoradas por modelos treinados aleatoriamente.
• Rede Neural Profunda: Utiliza uma MLP (Multilayer Perceptron) capaz de lidar com espaços de busca de alta dimensão e discretos (centenas de cartas), superando as limitações de modelos Gaussianos (como usados no SAIL) que falham em dimensões altas.
• Codificação Bag-of-Cards: Os decks são codificados como vetores inteiros representando a frequência de cada carta (0, 1 ou 2 cópias).
• Dados Auxiliares (Ancillary Data): O estudo investigou se incluir dados adicionais (como dano total, mana gasta, etc.) ajudaria na representação interna, mas os resultados mostraram que isso não melhorou o desempenho neste contexto específico.

3. Contribuições Principais

1. Novo Algoritmo MBQD: Introdução do DSA-ME, um algoritmo de Diversidade de Qualidade baseado em modelo que mantém um modelo substituto profundo online.
2. Eficiência de Amostragem: Demonstração de que o uso de um modelo substituto treinado online reduz drasticamente o número de simulações de jogo necessárias para encontrar decks de alta qualidade e diversificados.
3. Superioridade sobre Baselines: O método supera tanto o MAP-Elites sem modelo (model-free) quanto modelos substitutos treinados offline e modelos lineares.
4. Análise de Representação: Evidência de que a iteração entre o loop interno (exploração no modelo) e o loop externo (validação no jogo) cria um ciclo virtuoso onde a diversidade dos dados melhora o modelo, e o modelo melhora a busca.

4. Resultados Experimentais

Os experimentos foram realizados no jogo Hearthstone (classe Ladron/Rogue) usando o simulador SabberStone. Foram comparados quatro métodos: MAP-Elites (sem modelo), LSA-ME (modelo linear), Offline DSA-ME (modelo profundo treinado offline) e DSA-ME (modelo profundo treinado online).

• Métricas de Desempenho: O DSA-ME obteve os melhores resultados em todas as métricas principais:
  • QD-Score (Pontuação de Diversidade e Qualidade): 338.52 (DSA-ME) vs. 276.23 (LSA-ME) e 136.89 (MAP-Elites puro).
  • Percentual de Células Preenchidas (Diversidade): 31.86% (DSA-ME) vs. 27.89% (LSA-ME).
  • Diferença Média de Vida (Qualidade): 22.30 (DSA-ME) vs. 20.07 (LSA-ME).
  • Taxa de Vitória Máxima: 98.4% (DSA-ME).
• Análise de Hipóteses:
  • H1 (Modelos vs. Sem Modelo): Confirmada. Modelos substitutos melhoraram significativamente a busca.
  • H2 (Online vs. Offline vs. Linear): Confirmada. O DSA-ME (online profundo) superou o Offline DSA-ME e o LSA-ME. Curiosamente, o modelo profundo treinado offline performou pior que o modelo linear, indicando que dados aleatórios não são suficientes para treinar redes profundas complexas para esta tarefa.
  • H3 (Dados Auxiliares): Rejeitada. A adição de dados auxiliares (ancillary data) não melhorou o desempenho e, em alguns casos, degradou os resultados, sugerindo que a representação "Bag-of-Cards" simples pode não capturar nuances suficientes para beneficiar dados extras ou que o modelo de baixa fidelidade não consegue aproveitar essas informações.

5. Significado e Conclusão

O trabalho estabelece um novo estado da arte (SOTA) para a montagem automática de decks no Hearthstone usando abordagens de Diversidade de Qualidade.

• Impacto no Design de Jogos: A metodologia oferece uma ferramenta poderosa para designers de jogos testarem o equilíbrio (balancing) de cartas e decks, permitindo a geração rápida de estratégias variadas (agressivas vs. controladoras) sem a necessidade de simulações exaustivas para cada candidato.
• Avanço em IA Generativa: O estudo demonstra que a combinação de algoritmos evolutivos (MAP-Elites) com aprendizado de máquina profundo (Surrogate Models) em um ciclo de treinamento online é uma estratégia superior para espaços de busca complexos e estocásticos, superando abordagens puramente evolutivas ou modelos estáticos.
• Limitações Identificadas: O artigo aponta que a fidelidade do modelo substituto e a qualidade da codificação das cartas (que ignora atributos como custo de mana e texto da carta) são gargalos que impedem o uso eficaz de dados auxiliares, sugerindo direções futuras para modelos de simulação de alta fidelidade.

Em resumo, o DSA-ME resolve o problema de custo computacional na busca de conteúdo de jogos, criando um ciclo onde a busca gera dados para melhorar o modelo, e o modelo guia a busca para soluções mais inovadoras e eficientes.