Source-linked AI summary
Game-Agnostic Value Functions through Automatic JSON Feature Extraction
Dien Nguyen, Diego Perez-Liebana
TL;DR
The paper addresses the challenge of building useful game-playing value functions without hand-crafted, domain-specific features or expensive deep-learning models. It introduces JSON-Bag VF using JSON-Bag prototypes, Jensen-Shannon distance, and prototype nearest-neighbor search, then evaluates JSON-Bag OSLA across six tabletop games. JSON-Bag OSLA outperforms baseline OSLA in most games, while feature selection improves performance and is more important than prototype-tokenization.
Problem
Game-playing agents often require hand-crafted domain features or expensive deep-learning models, while JSON-Bag had only been tested on toy trajectory-classification problems.
Method
JSON-Bag VF trains value functions from winner-prediction prototypes using Jensen-Shannon distance and prototype nearest-neighbor search, with Random Forest and segmented feature selection.
Results
JSON-Bag OSLA outperforms baseline OSLA in most games, and feature selection improves performance while contributing more to agent score than prototype-tokenization.
Takeaways & Limitations
JSON-Bag can provide useful game features beyond scoring, although its benefit varies by game and feature selection is central to performance.
Takeaways & Limitations
JSON-Bag VF is tested only with simple OSLA agents, and the top-k feature-selection choice is arbitrary across games.
Abstract
from arXiv · showhide
JSON Bag-of-Tokens (JSON-Bag) is a recently proposed method to generically represent game trajectories by tokenizing their JSON descriptions. We introduce JSON-Bag VF, a game-agnostic approach to training value functions for game-playing agents using JSON-Bag prototypes. We show that this approach can be enhanced with Random Forest-based feature selection and a method to select game-stage-specific features. We evaluate JSON-Bag VF with One-step-look-ahead (JSON-Bag OSLA) on six tabletop games over different combinations of prototype-tokenization and feature selections. JSON-Bag OSLA outperforms baseline OSLA agents in most games. Our analysis also shows that feature selection significantly improves JSON-Bag VF and that feature selection is the most important factor in JSON-Bag VF performance, over prototype-tokenization.
I. INTRODUCTION
The paper extends JSON-Bag from toy trajectory classification to game-agnostic value functions, adding Random Forest feature selection and game-stage-specific selection. Evaluated with JSON-Bag OSLA across six tabletop games, it finds feature selection especially important for performance.
- JSON-Bag VF trains game-agnostic value functions from winner-prediction prototypes using Jensen-Shannon distance and prototype nearest-neighbor search.
- JSON-Bag OSLA significantly outperforms standard OSLA in four of six games, but underperforms in Sea Salt and Paper and Dots and Boxes.
- Random Forest-based feature selection improves JSON-Bag VF by retaining important tokens and reducing redundant features.
- Game-stage-specific selection segments trajectories and applies feature selection independently to each segment.
- Effect-size analysis identifies feature selection as more important to agent score than prototype-tokenization.
II. GAMES
The experiments use six tabletop games spanning drafting, deck-building, set collection, connection, grid-linking, and push-your-luck mechanics. Can’t Stop additionally involves deciding whether to stop or continue rolling while risking progress.
- 7 Wonders: 7 Wonders is a drafting game where players build civilizations, exchange cards, and buy resources for assigned wonders.
- Dominion: Dominion is a deck-building game centered on creating an engine to acquire victory-point cards, using the First Game setup.
- Sea Salt and Paper: Sea Salt and Paper is a set-collection game involving card combinations, scoring, and risky choices about ending rounds.
- Connect4: Connect4 requires players to drop pieces into a vertical grid and connect four in a row, column, or diagonal.
- Dots and Boxes: Dots and Boxes awards a point and another turn when a player completes a box by linking adjacent dots.
- Can’t Stop: Can’t Stop uses dice to advance along number tracks, requiring players to choose between stopping and risking continued progress.
III. JSON BAG-OF-TOKENS MODEL
JSON-Bag represents game trajectories as normalized token-frequency distributions derived from serialized game states. Class prototypes support distance-based classification, with Jensen-Shannon distance providing the comparison metric.
- A game trajectory is serialized as concatenated JSON game states, whose atomic components become path-based tokens.
- Ordered tokenization can encode list indices, while unordered tokenization omits positional information.
- Token occurrences are counted into token-occurrence pairs and normalized to sum to 1, forming a probability distribution for each trajectory.
- A positive integer suffix can expand a token into multiple instances, and the paper applies both ordered and unordered tokenization.
- A JSON-Bag prototype averages bags from one class to represent that class of trajectories for distance-based classification.
- Jensen-Shannon distance is the square root of Jensen-Shannon divergence and is a metric for comparing distributions.
- For distributions P and Q, the divergence uses the KL divergences from each distribution to their mixture M = (P + Q)/2.
IV. JSON-BAG AS VALUE FUNCTION (JSON-BAG VF)
JSON-Bag VF derives game-agnostic value estimates by comparing trajectory token distributions with winner-specific prototypes. It integrates distance-based confidence, Random Forest feature selection, and game-stage-specific feature selection, and can drive OSLA decisions.
- Value-function construction: Winner-specific JSON-Bag prototypes are formed by summing labeled trajectory bags, and prototype nearest-neighbor distances support winner prediction.The winning-player classification task labels full trajectories, then aggregates JSON-Bags for each player.
- Value-function construction: The value function converts relative Jensen-Shannon distances to player prototypes into scores, giving higher values to closer prototypes.The scores and Jensen-Shannon distances are bounded between 0 and 1, using linear normalization across player distances.
- Decision making: JSON-Bag OSLA maintains the current trajectory as a JSON-Bag and evaluates actions by rolling the state forward before valuing the resulting trajectory.The trajectory summary is updated at the beginning of the agent’s turn.
- Feature selection: Random Forest feature selection ranks tokens by Mean Decrease in Impurity and retains important features to reduce redundant-token noise.Each token is treated as a feature and its frequency as the feature value.
- Feature selection: Stage-specific selection segments trajectories and combines the top-k features selected from datasets ending at successive segments.The resulting feature list can contain more than k features, and segmentation may be customized for a game.
V. EXPERIMENTS
The experiments vary prototype-tokenization frequency and feature-selection strategy while testing JSON-Bag OSLA against scoring-based OSLA baselines. Evaluation uses self-play training data and repeated games across player positions.
- Experimental setup: Training data for each game consists of 1000 self-play games generated by tuned MCTS agents with a 128ms action-decision budget.JSON descriptions include every game state after a player ends their turn.
- Experimental factors: Prototype tokenization is compared using full-state, fixed-interval, and random state sampling strategies.Interval sampling uses f = n turns, while random sampling uses p = 1/n; terminal states are always included for interval sampling.
- Experimental factors: Feature selection is tested with k = 100 using non-segmented and four-segment trajectory datasets, producing six feature-selection variants across tokenization frequencies.Segmented selection combines top-k features from each trajectory segment.
- Evaluation protocol: Each game evaluates every tokenization–feature-selection pair with one JSON-Bag OSLA against baseline OSLA agents over 1000 games per player position.Baseline OSLA uses the game’s scoring system as its value function, and outcomes are coded -1, 0, or 1 for loss, draw, or win.
VI. RESULTS AND DISCUSSION
JSON-Bag OSLA improves substantially over scoring-based OSLA in four games but performs worse in two. Feature selection usually improves performance and explains more score variance than prototype-tokenization, while player position can still create large gaps.
- Performance across games: JSON-Bag OSLA significantly outperforms baseline OSLA in Dominion, 7 Wonders, Connect-4, and Can’t Stop, with or without feature selection.The result indicates that JSON-Bag encodes useful game features beyond game scoring in these games.
- Performance across games: JSON-Bag OSLA performs worse in Sea Salt and Paper and Dots and Boxes regardless of feature selection.The authors hypothesize that scoring is already sufficiently informative in these games, making other tokens comparatively noisy.
- Performance across games: In Sea Salt and Paper, JSON-Bag OSLA cannot infer current hand scores because those scores are not explicitly stored and require token interactions.This provides a game-specific explanation for the weaker result.
- Feature selection: Feature selection noticeably improves JSON-Bag OSLA in most cases, especially for Dominion and 7 Wonders.Dominion benefits from segmented selection, whereas 7 Wonders benefits from non-segmented selection despite its explicit game stages.
- Position effects: Some games show large score differences between the best and worst JSON-Bag OSLA player positions.Certain prototype–feature pairs have larger position gaps than baseline OSLA, motivating further investigation.
- Effect sizes: Feature selection is by far the most important factor in agent score for most games, while Can’t Stop shows equal contributions from feature selection and prototype-tokenization.The comparison uses η2 effect sizes to quantify variance explained by the two design choices.
VII. CONCLUSION
JSON-Bag VF provides a game-agnostic value-function approach using winner-prediction prototypes, JSD, P-NNS, and feature selection. Across six tabletop games, feature selection improved performance, while its contribution exceeded that of prototype tokenization; limitations remain in agent sophistication, feature-count selection, and game-state scoring.
- JSON-Bag VF trains game-agnostic value functions from winner-prediction prototypes using Jensen-Shannon distance and prototype nearest-neighbor search.
- Feature selection improves JSON-Bag VF performance across all six evaluated tabletop games.
- JSON-Bag OSLA outperforms baseline OSLA agents in all evaluated games except Sea Salt and Paper and Dots and Boxes.
- Effect-size analysis identifies feature selection as more important to agent score than prototype tokenization.
- The evaluation is limited to simple OSLA agents, leaving use with more sophisticated agents for future work.
- Top-k feature selection is arbitrary across games, and performance decreases when scoring is already strong or unclear in the game state.