Deep Surrogate Assisted MAP-Elites for Automated Hearthstone Deckbuilding

1. Problema: Generación de Contenido de Calidad y Diversidad

El trabajo aborda el desafío de generar automáticamente contenido de videojuegos que sea tanto de alta calidad (alto rendimiento) como diverso (estrategias variadas). El caso de estudio es la construcción automática de mazos en el juego de cartas coleccionables Hearthstone.

• Desafíos específicos:
  • Espacio de búsqueda masivo: Con miles de cartas, el número de combinaciones posibles de mazos es astronómico ($\approx 1.42 \times 10^{35}$ para los conjuntos básicos).
  • Costo de evaluación: Evaluar un mazo candidato requiere ejecutar cientos de partidas (el estudio usa 200) contra oponentes diversos debido a la alta varianza estocástica del juego (estados iniciales aleatorios, acciones probabilísticas).
  • Limitaciones de métodos anteriores: El algoritmo de Diversidad de Calidad (QD) MAP-Elites ha demostrado ser efectivo para encontrar mazos diversos, pero sufre de una baja eficiencia de muestreo porque requiere evaluaciones directas y costosas en el motor del juego para cada candidato.

2. Metodología: DSA-ME (Deep Surrogate Assisted MAP-Elites)

Los autores proponen DSA-ME, un algoritmo de optimización de diversidad de calidad basado en modelos que combina MAP-Elites con un modelo sustituto (surrogate model) profundo entrenado en línea.

Arquitectura del Algoritmo

El sistema opera mediante dos bucles interconectados (ver Figura 1 del artículo):

1. Bucle Interno (Exploración Barata):

   • Utiliza un modelo sustituto de red neuronal profunda (MLP) para predecir los resultados de las partidas (objetivo y medidas) sin ejecutar el motor del juego real.
   • Ejecuta el algoritmo MAP-Elites sobre este modelo sustituto para generar un archivo (archive) diverso de mazos candidatos prometedores.
   • Este bucle es computacionalmente barato y rápido.

2. Bucle Externo (Validación y Aprendizaje):

   • Toma los mazos "élite" (los mejores candidatos) generados en el bucle interno.
   • Evalúa estos mazos en el simulador real SabberStone (ejecutando 200 partidas por mazo) para obtener datos de "verdad fundamental" (ground-truth).
   • Actualización del Modelo: Los datos reales obtenidos se añaden a un búfer de entrenamiento para reentrenar el modelo sustituto en línea.
   • Actualización del Archivo Real: Los mazos evaluados se añaden al archivo final de verdad fundamental.

Ciclo de Retroalimentación

La clave de DSA-ME es la interacción dinámica:

• MAP-Elites explora el espacio de búsqueda usando el modelo sustituto, descubriendo regiones donde el modelo podría estar equivocado (ejemplos adversarios).
• La evaluación en el simulador real corrige estos errores y proporciona datos de alta calidad.
• El modelo sustituto se reentrena con estos nuevos datos, mejorando su precisión y guiando a MAP-Elites hacia soluciones más prometedoras en la siguiente iteración.

Representación y Medidas

• Codificación: Los mazos se codifican como vectores enteros ("Bag-of-Cards") que representan la frecuencia de cada carta (0, 1 o 2 copias).
• Objetivo: Maximizar la diferencia promedio de salud al final de la partida (proxy de porcentaje de victorias).
• Medidas (Ejes de Diversidad):
  1. Número promedio de cartas en mano (indica control vs. agresividad).
  2. Número promedio de turnos (duración de la partida).

3. Contribuciones Clave

1. Nuevo Algoritmo MBQD: Presentación de DSA-ME, un algoritmo de Diversidad de Calidad basado en modelos que utiliza redes neuronales profundas entrenadas en línea, superando las limitaciones de los modelos sustitutos estáticos o de baja dimensión (como los Procesos Gaussianos usados en SAIL).
2. Eficiencia de Muestreo: Demostración de que el entrenamiento en línea permite al algoritmo aprender de sus propios errores de exploración, reduciendo drásticamente el número de evaluaciones costosas necesarias en el motor del juego.
3. Análisis de Datos Auxiliares: Exploración de si incluir datos auxiliares (daño total, maná gastado, etc.) mejora el aprendizaje de representaciones internas, aunque los resultados mostraron que en este caso específico no mejoró el rendimiento.
4. Estado del Arte: Establecimiento de un nuevo récord de rendimiento en la construcción automática de mazos de Hearthstone utilizando enfoques de diversidad de calidad.

4. Resultados Experimentales

Los experimentos compararon DSA-ME contra tres líneas base:

• MAP-Elites puro (sin modelo sustituto).
• LSA-ME: MAP-Elites con un modelo sustituto lineal.
• Offline DSA-ME: MAP-Elites con un modelo profundo entrenado offline con datos aleatorios (sin reentrenamiento en línea).

Hallazgos principales (Tabla 1 del artículo):

• Rendimiento Superior: DSA-ME superó significativamente a todas las líneas base en todas las métricas:
  • Puntaje QD (Quality Diversity): 338.52 (DSA-ME) vs. 276.23 (LSA-ME) vs. 194.94 (Offline DSA-ME) vs. 136.89 (MAP-Elites).
  • Porcentaje de celdas llenas (Diversidad): 31.86% (DSA-ME) vs. 27.89% (LSA-ME).
  • Diferencia de salud máxima (Calidad): 22.30 (DSA-ME) vs. 20.07 (LSA-ME).
• Ventaja del Entrenamiento en Línea: El modelo "Offline DSA-ME" (entrenado solo con datos aleatorios) tuvo un rendimiento inferior incluso al modelo lineal (LSA-ME) en términos de QD-score. Esto demuestra que la capacidad de aprender de las soluciones exploradas por MAP-Elites es crucial.
• Precisión del Modelo: El modelo sustituto final logró predecir las medidas (turnos, tamaño de mano) con alta precisión, aunque con mayor error en el objetivo (salud). Sin embargo, las soluciones propuestas por el modelo permanecían en la misma región del espacio de búsqueda que la verdad fundamental, lo cual es suficiente para la optimización.
• Reinicialización: Se demostró que reiniciar el bucle interno de MAP-Elites en cada iteración (en lugar de continuar con el mismo archivo) es vital para cubrir huecos en el espacio de búsqueda y mejorar la diversidad.

Sobre los datos auxiliares: Contrario a la hipótesis inicial basada en aprendizaje auto-supervisado, añadir datos auxiliares (win rate, daño, etc.) no mejoró el rendimiento y en algunos casos lo empeoró. Los autores sugieren que la codificación "Bag-of-Cards" es demasiado simple para aprovechar estos datos adicionales o que el modelo de baja fidelidad no puede capturar el contexto necesario.

5. Significado e Impacto

• Para la Industria de Videojuegos: Proporciona una herramienta eficiente para los diseñadores de juegos para equilibrar juegos de cartas coleccionables (CCG) automatizando la búsqueda de mazos fuertes y diversos, identificando estrategias rotas o nichos no explorados.
• Avance en IA Evolutiva: DSA-ME demuestra que los modelos sustitutos profundos entrenados dinámicamente son superiores a los métodos tradicionales (offline o lineales) para problemas de optimización en espacios de alta dimensión y discretos.
• Eficiencia Computacional: Reduce la dependencia de simulaciones costosas, permitiendo que algoritmos de diversidad de calidad se apliquen a problemas más complejos donde la evaluación directa es prohibitiva.

En resumen, el paper presenta un marco robusto donde la exploración inteligente (MAP-Elites) y el aprendizaje adaptativo (Redes Neuronales en línea) se combinan para resolver un problema de optimización combinatoria complejo en el dominio de los videojuegos, logrando resultados de vanguardia en la generación de contenido.