Research map / Learning theory and algorithms / Submodular and game algorithms

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

NeurIPS 2026 · Learning theory and algorithms › Submodular and game algorithms · approach: Opponent modeling and subgame solving · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Adapts the KGW LLM watermark to game-playing strategies in perfect-information extensive-form games, seeding by observation hash and adding hardness-based utility shifts, and validates on UCI chess engine matches.

Problem

Detecting unauthorized use of AI game-playing agents (e.g., cheating in online chess, IP protection, data cleaning) by embedding a detectable watermark in their strategies without degrading quality.

Approach

Treat a strategy profile like an LLM: partition available actions into green/red lists seeded by the observation hash, add a hardness bonus to green-action expected utilities (with a compensating shift on red ones), and play the argmax; also watermark returned expected utilities and bound the expected-utility loss.

Key results

• Watermarked Stockfish 17.1 (gamma=0.25, delta=0.5 centipawn) showed Elo difference +24.4±31.0 vs original, with LOI 6.3%, so no significant strength loss across six engines.
• Watermarked engines crossed the z=4 detection threshold early: Dragon after 1 round, asmFish 9 and Stockfish 17.1 after 2 rounds.
• Detection AUC per round averaged roughly 0.7-0.8; increasing delta to 10 raised AUC to 0.962 but reduced strength (Elo -88.7).

Surprising findings

• Watermarked Stockfish 17.1 measured with a positive Elo difference (+24.4), and several watermarked engines outperformed originals within noise.
• Hashing the observation rather than the last action was needed to avoid a bypass, and the paper argues that SynthID-style watermarks fail because solutions give pure distributions.

Limitations

• Detection AUC per single round is only about 0.7-0.8, so multiple games are needed for reliable detection.
• Theoretical loss bound relies on independence and constant green-selection probability assumptions; the deterministic bound scales linearly with number of actions.
• Expected-utility watermark must be deployed privately, and attacks such as observation perturbation are only argued informally.

Experimental setup

Datasets: Stockfish chess books dataset (8-move opening positions)

Benchmarks: UCI engine matches (100 games each)

Metrics: Elo difference likelihood of being weaker (LOI) z-score AUC draw count

Baselines: asmFish 9 Dragon Ethereal 14.40 PlentyChess 7.0.0 Stash v37.0 Stockfish 17.1

Builds on: KGW watermark AlphaZero Hoeffding's inequality

Closest papers by meaning

• No Free Lunch in LLM Watermarking: Trade-offs in Watermarking Design Choices (NeurIPS 2024 · similarity 0.85)
• Unbiased Watermark for Large Language Models (ICLR 2024 · similarity 0.85)
• Watermark Stealing in Large Language Models (ICML 2024 · similarity 0.84)
• Can Watermarking Large Language Models Prevent Copyrighted Text Generation and Hide Training Data? (AAAI 2025 · similarity 0.84)
• Discovering Spoofing Attempts on Language Model Watermarks (ICML 2025 · similarity 0.83)
• Mastering Board Games by External and Internal Planning with Language Models (ICML 2025 · similarity 0.83)