JSON-Bag: A generic game trajectory representation

Technical Summary: JSON-Bag: A Generic Game Trajectory Representation

Problem Statement
Defining features and representations for games, along with corresponding distance or similarity metrics, is foundational for game analysis tasks such as optimizing agent strength, modeling human playstyles, and automated game design. Traditionally, these representations rely on hand-crafted features requiring significant domain knowledge or deep learning models that necessitate further feature engineering. Existing distance metrics, such as Euclidean distance and cosine similarity, are often applied to these manually defined vectors. The authors propose a method to generically represent game trajectories without relying on domain-specific feature engineering, enabling the comparison of game logs across diverse tabletop games using a unified, data-driven approach.

Methodology
The paper introduces the JSON Bag-of-Tokens model (JSON-Bag). This method represents game trajectories by tokenizing their JSON descriptions.

• Tokenization: A game trajectory is formed by concatenating the JSON of individual game states. Tokens are defined as atomic components (non-dictionary, non-list values) identified by their path from the root (e.g., .playerResources[0].Wood.2). The authors experiment with both ordered and unordered tokenization modes depending on the game's mechanics (e.g., unordered for card hands, ordered for grid positions).
• Representation: Similar to the "bag-of-words" model in Natural Language Processing (NLP), a JSON-Bag is a collection of token-occurrence count pairs. These counts are normalized to sum to 1, interpreting the JSON-Bag as a probabilistic model of the game trajectory, where token frequency represents the probability of generating that token during gameplay.
• Distance Metric: To measure similarity between these probabilistic models, the authors employ the Jensen-Shannon Distance (JSD), a symmetric and bounded metric derived from the Jensen-Shannon divergence.
• Classification Approaches:
  1. Prototype-based Nearest Neighbor Search (P-NNS): A prototype for a class is defined as the average JSON-Bag of all trajectories in that class. Classification is performed by finding the closest prototype using JSD.
  2. Random Forest (RF): Individual token-frequency pairs are treated as features and fed into a Random Forest classifier to evaluate the model's ability to automatically extract features without manual selection.

Experimental Setup
The approach was evaluated on six tabletop games implemented in the TAG framework: 7 Wonders, Dominion, Sea Salt and Paper, Can't Stop, Connect4, and Dots and boxes. The authors categorized Connect4 and Dots and boxes as "sparse" games due to their limited unique game components compared to the others.
Three classification tasks were performed for each game:

1. Agent Classification: Distinguishing between Random, One-step-look-ahead (OSLA), and three variants of Monte Carlo Tree Search (MCTS) agents.
2. Parameter Classification: Identifying different game parameter sets (e.g., grid size, card values).
3. Seed Classification: Identifying the random number generator seeds used to initialize games.

Key Results

• P-NNS Performance: JSON-Bag with JSD outperformed a baseline using hand-crafted features and Euclidean distance in the majority of tasks. It successfully distinguished OSLA and Random agents from MCTS variants in most games. However, performance degraded on "sparse" games (Connect4, Dots and boxes) and specific tasks like classifying Dominion seeds, likely due to the limited information content in sparse JSON descriptions or the high role of randomness in Dominion.
• Sample Efficiency: In N-shot classification experiments, JSON-Bag prototypes demonstrated high sample efficiency. For "easy" tasks (where classes have obvious differences), accurate classification was achieved with as few as 5 samples per class.
• Random Forest Improvement: When JSON-Bag tokens were used as features for a Random Forest classifier, accuracy significantly improved on tasks where P-NNS underperformed, particularly on sparse games and complex parameter classification. This suggests JSON-Bag effectively captures features that can be leveraged by models capable of learning complex interactions.
• Correlation with Policy Distance: The JSD between JSON-Bag prototypes of different agent classes was found to be highly correlated (Pearson coefficients ranging from 0.62 to 0.97) with the actual policy distance between those agents. This validates the metric as a proxy for behavioral difference without requiring hand-crafted features.
• JSON-Char: An ablation study tokenizing individual characters of the JSON string (JSON-Char) yielded surprisingly competitive results, suggesting the semantic structure of JSON itself carries significant signal.

Significance and Contributions
The paper claims four main contributions:

1. Generic Representation: It provides a domain-agnostic method to represent game trajectories using only JSON descriptions, eliminating the need for manual feature engineering or game-specific serialization logic beyond standard JSON conversion.
2. Probabilistic Similarity: It demonstrates that game trajectory similarity can be effectively evaluated using the probabilistic interpretation of JSON-Bags combined with the information-theoretic JSD metric.
3. Sample Efficiency and Feature Extraction: It shows that JSON-Bag prototypes are sample-efficient for representing trajectory classes and that the model possesses an inherent ability to extract features suitable for machine learning algorithms like Random Forest.
4. Behavioral Correlation: It establishes a strong correlation between the JSD of JSON-Bag prototypes and the actual policy distance between agents, validating its utility for playstyle clustering and novelty search without relying on domain-specific metrics.

Limitations
The authors acknowledge that JSON-Bag struggles with "sparse" games where serialized state data lacks informative unique components or where spatial relationships (e.g., grid coordinates) are critical. In such cases, the tokenization method may treat distinct but semantically similar values (like different turn counts) as entirely different tokens, losing information. The paper suggests that refining tokenization strategies (e.g., pairing coordinates or binning numerical values) could address these limitations.