JSON-Bag: A generic game trajectory representation

Resumo Técnico: JSON-Bag: Uma Representação Genérica de Trajetórias de Jogos

Declaração do Problema
Definir características e representações para jogos, juntamente com métricas de distância ou similaridade correspondentes, é fundamental para tarefas de análise de jogos, como otimização da força de agentes, modelagem de estilos de jogo humanos e design automatizado de jogos. Tradicionalmente, essas representações dependem de características criadas manualmente, exigindo conhecimento significativo de domínio, ou de modelos de aprendizado profundo que necessitam de engenharia de características adicional. Métricas de distância existentes, como distância euclidiana e similaridade cosseno, são frequentemente aplicadas a esses vetores definidos manualmente. Os autores propõem um método para representar genericamente trajetórias de jogos sem depender de engenharia de características específica de domínio, permitindo a comparação de registros de jogos em diversos jogos de tabuleiro usando uma abordagem unificada e orientada por dados.

Metodologia
O artigo introduz o modelo Bolsa de Tokens JSON (JSON-Bag). Este método representa trajetórias de jogos tokenizando suas descrições em JSON.

• Tokenização: Uma trajetória de jogo é formada pela concatenação do JSON de estados individuais do jogo. Os tokens são definidos como componentes atômicos (valores que não são dicionários nem listas) identificados por seu caminho a partir da raiz (por exemplo, .playerResources[0].Wood.2). Os autores experimentam modos de tokenização ordenada e desordenada, dependendo das mecânicas do jogo (por exemplo, desordenado para mãos de cartas, ordenado para posições em grade).
• Representação: Semelhante ao modelo "bolsa de palavras" em Processamento de Linguagem Natural (PLN), uma Bolsa JSON é uma coleção de pares de ocorrência-contagem de tokens. Essas contagens são normalizadas para somar 1, interpretando a Bolsa JSON como um modelo probabilístico da trajetória do jogo, onde a frequência do token representa a probabilidade de gerar esse token durante o jogo.
• Métrica de Distância: Para medir a similaridade entre esses modelos probabilísticos, os autores empregam a Distância de Jensen-Shannon (JSD), uma métrica simétrica e limitada derivada da divergência de Jensen-Shannon.
• Abordagens de Classificação:
  1. Busca de Vizinho Mais Próximo Baseada em Protótipos (P-NNS): Um protótipo para uma classe é definido como a média das Bolsas JSON de todas as trajetórias nessa classe. A classificação é realizada encontrando o protótipo mais próximo usando a JSD.
  2. Random Forest (RF): Pares individuais de frequência de token são tratados como características e alimentados em um classificador Random Forest para avaliar a capacidade do modelo de extrair características automaticamente sem seleção manual.

Configuração Experimental
A abordagem foi avaliada em seis jogos de tabuleiro implementados no framework TAG: 7 Wonders, Dominion, Sea Salt and Paper, Can't Stop, Connect4 e Dots and boxes. Os autores categorizaram Connect4 e Dots and boxes como jogos "esparços" devido aos seus componentes de jogo únicos limitados em comparação com os outros.
Três tarefas de classificação foram realizadas para cada jogo:

1. Classificação de Agentes: Distinção entre agentes Aleatórios, de Olhada de Um Passo (OSLA) e três variantes de Busca em Árvore de Monte Carlo (MCTS).
2. Classificação de Parâmetros: Identificação de diferentes conjuntos de parâmetros de jogo (por exemplo, tamanho da grade, valores de cartas).
3. Classificação de Sementes: Identificação das sementes do gerador de números aleatórios usadas para inicializar os jogos.

Principais Resultados

• Desempenho do P-NNS: A Bolsa JSON com JSD superou uma linha de base usando características criadas manualmente e distância euclidiana na maioria das tarefas. Ela distinguiu com sucesso agentes OSLA e Aleatórios das variantes MCTS na maioria dos jogos. No entanto, o desempenho degradou em jogos "esparços" (Connect4, Dots and boxes) e em tarefas específicas como classificar sementes do Dominion, provavelmente devido ao conteúdo de informação limitado em descrições JSON esparsas ou ao alto papel da aleatoriedade no Dominion.
• Eficiência de Amostra: Em experimentos de classificação N-shot, os protótipos de Bolsa JSON demonstraram alta eficiência de amostra. Para tarefas "fáceis" (onde as classes têm diferenças óbvias), a classificação precisa foi alcançada com tão poucos quanto 5 amostras por classe.
• Melhoria com Random Forest: Quando os tokens da Bolsa JSON foram usados como características para um classificador Random Forest, a precisão melhorou significativamente em tarefas onde o P-NNS teve desempenho inferior, particularmente em jogos esparsos e classificação complexa de parâmetros. Isso sugere que a Bolsa JSON captura efetivamente características que podem ser aproveitadas por modelos capazes de aprender interações complexas.
• Correlação com Distância de Política: A JSD entre protótipos de Bolsa JSON de diferentes classes de agentes foi encontrada altamente correlacionada (coeficientes de Pearson variando de 0,62 a 0,97) com a distância de política real entre esses agentes. Isso valida a métrica como um proxy para diferença comportamental sem exigir características criadas manualmente.
• JSON-Char: Um estudo de ablação tokenizando caracteres individuais da string JSON (JSON-Char) produziu resultados surpreendentemente competitivos, sugerindo que a estrutura semântica do JSON em si carrega sinal significativo.

Significado e Contribuições
O artigo reivindica quatro contribuições principais:

1. Representação Genérica: Fornece um método agnóstico de domínio para representar trajetórias de jogos usando apenas descrições JSON, eliminando a necessidade de engenharia de características manual ou lógica de serialização específica de jogo além da conversão JSON padrão.
2. Similaridade Probabilística: Demonstra que a similaridade de trajetórias de jogos pode ser efetivamente avaliada usando a interpretação probabilística de Bolsas JSON combinada com a métrica JSD baseada em teoria da informação.
3. Eficiência de Amostra e Extração de Características: Mostra que protótipos de Bolsa JSON são eficientes em amostras para representar classes de trajetórias e que o modelo possui uma capacidade inerente de extrair características adequadas para algoritmos de aprendizado de máquina como Random Forest.
4. Correlação Comportamental: Estabelece uma forte correlação entre a JSD de protótipos de Bolsa JSON e a distância de política real entre agentes, validando sua utilidade para agrupamento de estilos de jogo e busca de novidade sem depender de métricas específicas de domínio.

Limitações
Os autores reconhecem que a Bolsa JSON luta com jogos "esparços" onde dados de estado serializados carecem de componentes únicos informativos ou onde relações espaciais (por exemplo, coordenadas de grade) são críticas. Nesses casos, o método de tokenização pode tratar valores distintos, mas semanticamente semelhantes (como diferentes contagens de turno), como tokens completamente diferentes, perdendo informações. O artigo sugere que refinar estratégias de tokenização (por exemplo, emparelhando coordenadas ou agrupando valores numéricos) poderia abordar essas limitações.