🤖 AI

Domain-Independent Game Abstraction using Word Embedding Techniques

This paper proposes a domain-independent game abstraction method that leverages natural language processing word embedding techniques to represent and cluster game actions, demonstrating its effectiveness in reducing game complexity despite not surpassing specialized, domain-specific algorithms.

Original authors: Juho Kim, Tuomas Sandholm

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Juho Kim, Tuomas Sandholm

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a massive, incredibly complex puzzle, like a game of poker or chess. The problem is that the number of possible moves is so huge (like trying to count every grain of sand on a beach) that even the smartest computers can't solve it all at once.

To fix this, game experts use a trick called game abstraction. Think of this like grouping similar puzzle pieces together. Instead of treating every single grain of sand as unique, you group them into buckets: "wet sand," "dry sand," "shell fragments," etc. This shrinks the puzzle down to a manageable size so a computer can solve it, and then you can use that solution to play the real, giant game.

The problem with most existing methods is that they are like specialized chefs. A poker chef knows exactly how to group poker hands because they know the rules of poker inside and out. But if you ask that same chef to group moves in a video game or a board game they've never seen, they are stuck. They need to learn the new rules from scratch every time.

The Paper's Big Idea: The "Universal Translator"

The authors, Juho Kim and Tuomas Sandholm, propose a new way to group these moves that doesn't need to know the specific rules of the game. They borrow a tool from the world of language, called Word Embeddings.

Here is the analogy:

Words are Moves: Imagine every possible move in a game is a "word."
Gameplay is a Story: Imagine a record of many games played is a "book" or a "corpus" of text.

In language, computers can learn that the word "king" is similar to "queen" because they often appear in similar sentences (like "The king and queen sat on the throne"). The computer turns these words into mathematical coordinates (vectors). Words with similar meanings end up close together in this mathematical space.

The authors asked: Can we do this with game moves?
They fed records of games (like chess or poker) into these language models. The model learned that a move like "Pawn captures Queen" is mathematically similar to "Bishop captures Rook" because they often happen in similar situations, even if the model doesn't "know" what a pawn or a bishop is.

What They Found (The "Magic" of the Method)

It Understands Strategy Without Being Taught:
When they looked at the mathematical map of these moves, they saw something amazing. Moves that are strategically similar (like capturing a piece to promote a pawn) were clustered right next to each other. It's as if the computer, just by reading the "story" of the game, figured out which moves are cousins without anyone telling it the rules.
It Works with "Pre-Trained" Brains:
They also tried using massive, pre-trained AI models (like the ones behind Google or OpenAI) that have read millions of books and articles. Even though these models were trained on general text, not game rules, they could still group game moves effectively.
- The Catch: To use these giant models, you still have to describe the moves in plain English (e.g., "The bishop takes the pawn on b5"). So, it's not perfectly independent of human input, but it's much easier than writing a custom algorithm for every new game.
The Results: Good, But Not the Best:
They tested this on poker games.
- Better than Random: Their method was much better than just randomly grouping moves.
- Worse than Specialists: However, it didn't beat the "specialized chefs" (algorithms built specifically for poker). The poker experts still know the game better than the universal translator.

The Bottom Line

This paper introduces a domain-independent way to shrink giant games. Instead of building a custom tool for every new game you encounter, you can use a "universal translator" (word embeddings) to automatically group similar moves together.

The Pros: You don't need to be an expert in the game to use it. You just need a log of how the game is played.
The Cons: It's a generalist tool. It works well, but it won't beat a tool built specifically for that one game.

Think of it like this: If you need to organize a library, a specialist librarian who knows every book by heart will organize it perfectly. This new method is like using a smart robot that has read every book in the world but doesn't know the specific library's layout. The robot will do a great job grouping similar books together, but it won't be quite as perfect as the human expert who knows the specific rules of that library. Still, for a robot that knows nothing about the library beforehand, it's a surprisingly good job.

Technical Summary: Domain-Independent Game Abstraction using Word Embedding Techniques

Problem Statement

Many real-world games, including complex imperfect-information games like two-player no-limit Texas hold'em, possess game trees too large to be solved directly by existing techniques (e.g., containing $\approx 10^{165}$ nodes). Game abstraction is the standard approach to mitigate this, shrinking the game size by merging similar states or actions while preserving strategic properties. Solutions derived from the abstracted game are then "lifted" back to the original game to yield approximate solutions.

While significant advances have been made in game abstraction over the last two decades, most prior work is domain-specific, heavily relying on the game of poker. These techniques often require calculating poker-specific metrics (e.g., expected hand strength, equities) or constructing specialized data structures like signal trees, which necessitate deep, game-specific knowledge. Consequently, these methods do not generalize easily to other settings without extensive manual analysis of the target game. Existing general-purpose techniques often suffer from scalability issues or require full enumeration of terminal nodes, which is infeasible for large games.

Methodology

The authors propose a domain-independent approach to game abstraction that leverages word embedding techniques from Natural Language Processing (NLP). The core hypothesis is that game actions can be treated analogously to words in a language, and gameplay data can be treated as a corpus.

Action Representation: Each distinct action in the game is assigned a unique token.
Corpus Construction: Gameplay data (sequences of actions) is compiled into a corpus. This data can be derived from human gameplay or synthetic data generated by a known strategy profile.
Embedding Generation:
- Custom Training: The authors utilize GloVe (Global Vectors for Word Representation) to train static vectors on the action corpus.
- Foundational Models: The authors also explore using pre-trained foundational embedding models (from OpenAI and Google Gemini) to generate embeddings for actions represented as human-readable text.
Clustering: Once actions are represented as real-valued vectors, the k-means clustering algorithm is applied to group actions with similar vector representations. In the context of game abstraction, actions with similar vector representations are assumed to have isomorphic subgame trees or similar strategic implications.
Evaluation: The quality of the resulting abstraction is measured by calculating the exploitability of the Nash equilibrium derived from the abstract game when lifted back to the original game. The size of the abstraction is quantified by the number of sequences and the number of non-zeros (NNZs) in the utility matrix.

Key Contributions

The paper's contributions are primarily empirical and structured in two parts:

Interpretability of Action Embeddings:
- The authors demonstrate that action embeddings generated via word embedding techniques capture deep strategic considerations. In experiments with Chess and Kuhn Poker, actions with similar strategic properties (e.g., pawn promotions, check patterns, or cards of similar strength) clustered closely together in the vector space.
- This interpretability holds even when using foundational embedding models trained on general, multi-domain corpora, provided the actions can be represented as common-sense text.
- The study highlights that while foundational models require a textual representation of actions (weakening the claim of pure domain-independence), this requirement is significantly simpler than developing specialized abstraction algorithms for specific games.
Performance Quantification:
- The authors evaluated the technique on 256-Kuhn Poker and 13-Leduc Hold'em.
- They compared their method against a random baseline and a specialized hand-bucketing algorithm (tailored for poker).
- Results showed that the proposed technique consistently outperformed the random baseline, producing effective abstractions where the exploitability decreased as the abstraction size increased.
- However, the technique did not outperform the specialized hand-bucketing baseline, which is expected given the domain-independent nature of the proposed method versus the domain-specific optimization of the baseline.

Results

Chess Observational Study: Nearest neighbors of specific chess moves (e.g., exd8=Q) in the embedding space correctly identified moves with similar tactical attributes (e.g., other pawn promotions, checks, or captures), despite the model being unaware of the specific notation symbols (like + for check or x for capture).
Poker Observational Study: In 256-Kuhn poker, hole cards of similar ordinal strength clustered tightly. In Texas Hold'em, foundational models grouped hands by strength (e.g., AsAh near other Ace pairs) and suit relevance.
Abstraction Quality:
- In 256-Kuhn Poker, the GloVe-based abstraction yielded lower exploitability than the random baseline but higher exploitability than the hand-bucketing baseline.
- In 13-Leduc Hold'em, abstractions using OpenAI and Google Gemini embeddings also outperformed the random baseline. The Gemini embeddings produced more tightly concentrated exploitability results, suggesting higher consistency.
- In all cases, increasing the granularity of the abstraction (more clusters) generally improved the quality of the lifted solution for the proposed method and the specialized baseline, but not consistently for the random baseline.

Significance and Claims

The paper claims that word embedding techniques offer a viable, domain-independent pathway to game abstraction. The primary significance lies in the ability to generate effective abstractions without requiring:

Extensive analysis of the game's specific topology.
Domain-specific metrics (like hand strength calculators).
Specialized data structures like signal trees.

The authors contend that while the technique does not surpass specialized algorithms tailored to specific games (such as poker), it provides a robust general-purpose alternative that avoids the "chicken-and-egg" problem of needing a solved strategy to generate training data, as human gameplay data can be used directly. Furthermore, the technique can serve as a competitive baseline for developing specialized algorithms in the future.

The paper concludes modestly, acknowledging a tradeoff between generality and solution quality. It suggests that while foundational models require a textual representation of actions (limiting absolute domain independence), the effort to create such representations is minimal compared to developing game-specific abstraction methodologies. Future work is suggested at the intersection of computer games and information retrieval.