JSON-Bag: A generic game trajectory representation

Resumen Técnico: JSON-Bag: Una Representación Genérica de Trayectorias de Juego

Enunciado del Problema
Definir características y representaciones para juegos, junto con métricas de distancia o similitud correspondientes, es fundamental para tareas de análisis de juegos como la optimización de la fuerza de los agentes, el modelado de estilos de juego humanos y el diseño automatizado de juegos. Tradicionalmente, estas representaciones dependen de características creadas a mano que requieren un conocimiento de dominio significativo o de modelos de aprendizaje profundo que exigen una ingeniería de características adicional. Las métricas de distancia existentes, como la distancia euclidiana y la similitud del coseno, a menudo se aplican a estos vectores definidos manualmente. Los autores proponen un método para representar genéricamente las trayectorias de juego sin depender de la ingeniería de características específica del dominio, permitiendo la comparación de registros de juego entre diversos juegos de mesa mediante un enfoque unificado y basado en datos.

Metodología
El artículo introduce el modelo Bolsa de Tokens JSON (JSON-Bag). Este método representa las trayectorias de juego tokenizando sus descripciones JSON.

• Tokenización: Una trayectoria de juego se forma concatenando el JSON de los estados individuales del juego. Los tokens se definen como componentes atómicos (valores que no son diccionarios ni listas) identificados por su ruta desde la raíz (por ejemplo, .playerResources[0].Wood.2). Los autores experimentan con modos de tokenización ordenada y desordenada dependiendo de la mecánica del juego (por ejemplo, desordenada para manos de cartas, ordenada para posiciones en una cuadrícula).
• Representación: Similar al modelo "bolsa de palabras" en el Procesamiento del Lenguaje Natural (PLN), una JSON-Bag es una colección de pares de token-conteo de ocurrencias. Estos conteos se normalizan para sumar 1, interpretando la JSON-Bag como un modelo probabilístico de la trayectoria de juego, donde la frecuencia del token representa la probabilidad de generar ese token durante el juego.
• Métrica de Distancia: Para medir la similitud entre estos modelos probabilísticos, los autores emplean la Distancia Jensen-Shannon (JSD), una métrica simétrica y acotada derivada de la divergencia Jensen-Shannon.
• Enfoques de Clasificación:
  1. Búsqueda de Vecino Más Cercano basada en Prototipos (P-NNS): Un prototipo para una clase se define como el promedio de JSON-Bag de todas las trayectorias en esa clase. La clasificación se realiza encontrando el prototipo más cercano utilizando JSD.
  2. Random Forest (RF): Los pares individuales de frecuencia de token se tratan como características y se alimentan a un clasificador Random Forest para evaluar la capacidad del modelo de extraer características automáticamente sin selección manual.

Configuración Experimental
El enfoque se evaluó en seis juegos de mesa implementados en el marco TAG: 7 Wonders, Dominion, Sea Salt and Paper, Can't Stop, Connect4 y Dots and boxes. Los autores categorizaron a Connect4 y Dots and boxes como juegos "dispersos" debido a sus componentes únicos de juego limitados en comparación con los demás.
Se realizaron tres tareas de clasificación para cada juego:

1. Clasificación de Agentes: Distinguir entre agentes Aleatorios, de Búsqueda de un Paso Adelante (OSLA) y tres variantes de agentes de Búsqueda en Árbol Monte Carlo (MCTS).
2. Clasificación de Parámetros: Identificar diferentes conjuntos de parámetros de juego (por ejemplo, tamaño de la cuadrícula, valores de las cartas).
3. Clasificación de Semillas: Identificar las semillas del generador de números aleatorios utilizadas para inicializar los juegos.

Resultados Clave

• Rendimiento de P-NNS: JSON-Bag con JSD superó a una línea base que utilizaba características creadas a mano y distancia euclidiana en la mayoría de las tareas. Logró distinguir con éxito a los agentes OSLA y Aleatorios de las variantes MCTS en la mayoría de los juegos. Sin embargo, el rendimiento se degradó en juegos "dispersos" (Connect4, Dots and boxes) y en tareas específicas como la clasificación de semillas de Dominion, probablemente debido al contenido de información limitado en las descripciones JSON dispersas o al alto papel del azar en Dominion.
• Eficiencia de Muestra: En experimentos de clasificación N-shot, los prototipos JSON-Bag demostraron una alta eficiencia de muestra. Para tareas "fáciles" (donde las clases tienen diferencias obvias), se logró una clasificación precisa con tan solo 5 muestras por clase.
• Mejora con Random Forest: Cuando los tokens JSON-Bag se utilizaron como características para un clasificador Random Forest, la precisión mejoró significativamente en tareas donde P-NNS tuvo un rendimiento deficiente, particularmente en juegos dispersos y clasificación de parámetros complejos. Esto sugiere que JSON-Bag captura efectivamente características que pueden ser aprovechadas por modelos capaces de aprender interacciones complejas.
• Correlación con la Distancia de Política: Se encontró que la JSD entre los prototipos JSON-Bag de diferentes clases de agentes estaba altamente correlacionada (coeficientes de Pearson que oscilan entre 0.62 y 0.97) con la distancia de política real entre esos agentes. Esto valida la métrica como un proxy para la diferencia de comportamiento sin requerir características creadas a mano.
• JSON-Char: Un estudio de ablación que tokenizaba caracteres individuales de la cadena JSON (JSON-Char) arrojó resultados sorprendentemente competitivos, lo que sugiere que la estructura semántica del JSON en sí misma lleva una señal significativa.

Significado y Contribuciones
El artículo afirma cuatro contribuciones principales:

1. Representación Genérica: Proporciona un método agnóstico al dominio para representar trayectorias de juego utilizando solo descripciones JSON, eliminando la necesidad de ingeniería de características manual o lógica de serialización específica del juego más allá de la conversión JSON estándar.
2. Similitud Probabilística: Demuestra que la similitud de trayectorias de juego puede evaluarse efectivamente utilizando la interpretación probabilística de JSON-Bags combinada con la métrica JSD de teoría de la información.
3. Eficiencia de Muestra y Extracción de Características: Muestra que los prototipos JSON-Bag son eficientes en muestras para representar clases de trayectorias y que el modelo posee una capacidad inherente para extraer características adecuadas para algoritmos de aprendizaje automático como Random Forest.
4. Correlación de Comportamiento: Establece una fuerte correlación entre la JSD de los prototipos JSON-Bag y la distancia de política real entre agentes, validando su utilidad para el agrupamiento de estilos de juego y la búsqueda de novedad sin depender de métricas específicas del dominio.

Limitaciones
Los autores reconocen que JSON-Bag tiene dificultades con juegos "dispersos" donde los datos de estado serializados carecen de componentes únicos informativos o donde las relaciones espaciales (por ejemplo, coordenadas de cuadrícula) son críticas. En tales casos, el método de tokenización puede tratar valores distintos pero semánticamente similares (como diferentes conteos de turnos) como tokens completamente diferentes, perdiendo información. El artículo sugiere que refinar las estrategias de tokenización (por ejemplo, emparejar coordenadas o agrupar valores numéricos) podría abordar estas limitaciones.