💻 computer science

Watermarking Game-Playing Agents in Perfect-Information Extensive-Form Games

This paper introduces a method to watermark game-playing agents in perfect-information extensive-form games by adapting LLM watermarking techniques, demonstrating that the approach allows for reliable detection of unauthorized AI use with negligible impact on strategy quality.

Original authors: Juho Kim, Fei Fang, Tuomas Sandholm

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Juho Kim, Fei Fang, 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 have a super-smart chess robot that never makes a mistake. It's so good that it could beat the world champion. But now, imagine someone is using this robot to cheat in online chess tournaments. How do you prove, "Hey, this player isn't human; they are using our specific robot"?

This is the problem the paper solves. The authors created a way to "watermark" game-playing AI, similar to how you might put a hidden serial number on a banknote to prove it's real.

Here is the breakdown of their idea using simple analogies:

1. The Big Idea: Turning a Game into a Secret Code

The researchers realized that playing a game (like chess) is very similar to writing a story.

Writing a story: An AI picks the next word based on what came before.
Playing a game: An AI picks the next move based on the current board.

Just as writers have "green lists" of words they prefer, the authors gave the game AI a secret "Green List" of moves and a "Red List" of moves.

The Trick: The AI is programmed to slightly prefer moves on the Green List. It doesn't change its strategy enough to make it a bad player, but it does change it just enough to leave a hidden statistical signature.
The Result: If you watch the AI play 20 or 30 games, you can run a math test (like a detective counting clues) to see if the player is favoring the "Green List" moves more often than random chance would allow. If they are, you know they are using that specific watermarked AI.

2. The "Magic" of the Green List

Think of the Green List like a subtle nudge.

Imagine you are walking through a forest (the game). Normally, you might take any path.
The watermark is like a gentle breeze that pushes you slightly toward the "Green" paths.
If you walk 100 steps, you might not notice the breeze. But if a detective watches you walk 1,000 steps, they will notice you took 25% more Green paths than a random walker would. That's the watermark.

3. The Trade-off: Strength vs. Detectability

The paper asks: "Does this nudge make the robot play worse?"

The Answer: Not really. The authors tested this on six famous chess engines (including the world-famous Stockfish).
The Analogy: It's like asking a professional basketball player to shoot slightly more often with their left hand because it's "in the secret code." They might miss a few more shots than usual, but they are still a pro. The paper found that the watermarked robots were just as strong as the original ones; the difference was so small it was basically noise.
The Catch: If you make the "nudge" too strong (trying to make the watermark easier to spot), the robot starts playing worse. You have to balance how easy it is to catch the cheater with how well the robot plays.

4. Why This is Harder Than Just Text

The paper points out a key difference between writing text and playing games:

Text: If an AI writes a sentence, you can't easily go back and change a word without rewriting the whole paragraph.
Games: In a game, you can't "undo" a move. Once you move a pawn, it's gone. This actually helps the watermark! A cheater can't just "edit" the game history to remove the secret code. They have to play the game move-by-move, and every move they make leaves a tiny fingerprint.

5. The "Black Box" Problem (The Utility Issue)

Sometimes, users of these AI engines don't just want to know what move to make; they want to know how good that move is (the score).

The Problem: If the AI tells you, "Move A is worth 5 points," a smart cheater could just ignore the secret code and pick the move with the highest score, bypassing the watermark.
The Solution: The authors created a second layer of protection. They also "nudge" the score numbers slightly. If the watermark is public, a cheater could undo this. So, the paper suggests keeping the scoring system secret (private) so the cheater can't reverse-engineer the trick.

6. The Results: Catching Cheaters Fast

The authors ran experiments where they pitted the watermarked chess engines against the normal ones.

Performance: The watermarked engines played almost exactly as well as the originals.
Detection: They found that they could detect the watermark with high confidence after just a few games (sometimes as few as one or two rounds).
Conclusion: You can put a hidden, unremovable ID tag on a game-playing AI without making it any dumber, and you can catch cheaters very quickly.

Summary

This paper is about putting a hidden, unerasable fingerprint on game-playing AI. It works by subtly biasing the AI to pick certain moves, creating a statistical pattern that proves the AI's identity. The best part? The AI doesn't get any dumber doing it, and you can catch the cheater after just a handful of games.

Technical Summary: Watermarking Game-Playing Agents in Perfect-Information Extensive-Form Games

Problem Statement
The rapid advancement of artificial intelligence has produced superhuman agents for games such as chess, Go, and poker. While these agents demonstrate superior performance, their unauthorized use in competitive environments (e.g., online cheating) and the potential for intellectual property (IP) theft (e.g., code plagiarism or model distillation) present significant challenges. Existing watermarking techniques for Large Language Models (LLMs), which encode hidden signals to verify output sources, offer a potential solution. However, direct application of LLM watermarking to game-playing agents is non-trivial due to structural differences: game-playing involves sequential actions by multiple players, requires the preservation of strategic quality (expected utility), and often necessitates the disclosure of estimated utilities alongside action recommendations. Furthermore, unlike text generation where offline post-processing attacks are possible, game-playing constraints (e.g., inability to undo moves, presence of observers) limit attackers to online, single-step manipulations.

Methodology
The authors adapt the Kirchenbauer-Green-Keen (KGW) watermark, a prominent LLM watermarking technique, to perfect-information extensive-form games (EFGs). The core methodology involves modifying the strategy profile $\sigma$ of a game-solving agent.

Adaptation of KGW to Strategy Profiles:
- Green/Red List Partitioning: For a given history $h$ , the available actions $A(h)$ are randomly partitioned into a "green list" $G$ (size $\gamma|A(h)|$ ) and a "red list" $R$ based on a pseudo-random number generator seeded by the hash of the current observation.
- Utility Distortion: Instead of modifying logits as in LLMs, the watermark modifies the (estimated) expected utilities $\vec{u}$ associated with actions. A hardness parameter $\delta$ is added to the utilities of actions in the green list, while a compensatory value of $-\gamma\delta/(1-\gamma)$ is subtracted from actions in the red list. This ensures the expected adjustment to the utility is zero, preserving the overall distribution in expectation.
- Action Selection: The agent selects the action with the maximum adjusted utility. As $\delta \to \infty$ , the agent is forced to choose only green-list actions; as $\delta \to 0$ , the watermark acts only as a tie-breaker.
Watermarking Expected Utilities:
- To address the need for users to see estimated utilities (not just actions), a parallel watermarking mechanism is applied to the utility values themselves. This prevents attackers from bypassing the watermark by simply selecting the action with the highest unmodified utility.
- Privacy Constraint: The paper notes that if expected utilities are returned to the user, the watermark must be deployed privately (with a secret key). If the hardness parameter $\delta$ is public, an attacker could mathematically reverse the utility adjustments to recover the true underlying model's values.
Detection Mechanism:
- Detection relies on a statistical test (z-score) comparing the observed frequency of green-list actions ( $n_G$ ) against the expected frequency ( $\gamma n$ ) under the null hypothesis that the player is unaware of the watermark.
- A high z-score indicates the presence of the watermark. The authors suggest a threshold of $z=4$ (approx. $3 \times 10^{-5}$ false positive rate).

Key Contributions

Initiation of Game-Playing Watermarking: The paper establishes the first framework for watermarking strategies in perfect-information EFGs, adapting LLM techniques to the domain of game theory.
Theoretical Bounds: The authors provide a theoretical analysis bounding the degradation in strategy quality. They prove that the total loss in expected utility ( $L$ ) incurred by the watermark is bounded by $L \le n\delta(1 + \gamma/(1-\gamma))$ , where $n$ is the number of actions. This demonstrates a tradeoff between detectability (higher $\delta$ ) and strategy quality.
Handling Utility Disclosure: The paper addresses the unique challenge of game-playing agents where users require estimated expected utilities, proposing a method to watermark these values without compromising the detection capability, provided the watermark is kept private.
Robustness Analysis: The authors argue that the nature of game-playing (sequential, observable, irreversible moves) inherently mitigates offline attack vectors common in text generation, limiting attackers to online, single-step manipulations which are less effective against the proposed scheme.

Experimental Results
The authors evaluated the framework by bootstrapping the watermark onto six popular Universal Chess Interface (UCI) engines: asmFish 9, Dragon, Ethereal 14.40, PlentyChess, Stash v37.0, and Stockfish 17.1.

Performance Impact: In matches of 100 rounds between watermarked and original engines, the Elo differences were negligible and within margins of error. For instance, Stockfish 17.1 showed a +24.4 Elo difference (statistically insignificant), and asmFish 9 showed -10.4. The likelihood of the watermarked engine being inferior (LOI) generally failed to reach 90% confidence, indicating the watermark does not significantly degrade playing strength.
Detectability: The watermark was detectable with high confidence after a small number of games. Most watermarked engines crossed the $z=4$ threshold within the first 2 to 9 rounds.
Parameter Ablation: Experiments varying the green-list size ( $\gamma$ ) and hardness ( $\delta$ ) revealed that $\gamma=0.25$ and $\delta=0.5$ centipawns offered an optimal balance. Increasing $\delta$ improved detection metrics (higher z-scores and Area Under the Curve) but significantly reduced engine strength (higher LOI).

Significance and Claims
The paper claims to initiate the study of watermarking game-playing strategies, demonstrating that robust, unique signatures can be embedded in game-playing agents without significantly compromising their performance. The authors assert that their method allows for the detection of unauthorized AI usage (e.g., cheating) or IP theft (e.g., distillation) using statistical tests on gameplay data. They emphasize that while there is a tradeoff between detectability and quality, the degradation in quality can be bounded and is often negligible in practice, especially when the underlying model already relies on heuristic estimates. The work highlights that game-playing presents a distinct setting from text generation, requiring specific adaptations regarding utility disclosure and the nature of adversarial attacks.