Unsound Search with Policy and Value Networks in Legends of Code and Magic

Dustin Rubin

cs.AISep 6, 2026

Unsound Search with Policy and Value Networks in Legends of Code and Magic

Authors: Dustin Rubin

Organizations: Georgia Institute of Technology Atlanta, Georgia, USA

Abstract

Decision-time search in perfect and imperfect information games with enumerable belief states are effective methods for game AI. Collectible card games are imperfect information games with large belief states. Legends of Code and Magic is a collectible card game competition where the belief states are $2^{101}$ . The Legends of Code and Magic (LoCM) champion, ByteRL, plays with no search. Other works claim sound enumeration-based search is unusable in the genre due to the number of belief states. We measured three previously defined properties that predict where theoretically unsound perfect information Monte Carlo's defects are cheap and found LoCM sits in the favorable region. Starting with imitation learning of the runner-up policy, NeteaseOPD, we created a policy and value feed-forward network. Our agent searches over worlds sampled from a prior over the opponent's deck built from the runner-up's drafts. Using our strictest configuration in the battle phase we beat ByteRL with a win percentage of 51.35% 95% CI [50.37, 52.33], over 10,000 pre-registered games using the LoCM official referee and time limit. Search is not a minor factor on the matchup between our agent and ByteRL. Without search this agent scores 26.8% and adding search adds +24.6 points. Unsound search in imperfect information games could be exploitable. We replicate a published best-response attack against ByteRL. We then apply the same attack protocol to two search configurations of our agent, and each one resists it better than ByteRL at every iteration. In LoCM unsound search gives us a stronger and more resilient agent.

Figures & tables

Fig. 1: Figure A shows the uplift of decision time search on our imitation learned NeteaseOPD policy certified on the official referee within the time limit. a is the certified win rate of our most restrictive agent vs ByteRL with and without search with the zoom in showing the CI is above 50%. The other diagrams show the empirical factors that support PIMC working well in LoCM. Disambiguation shows the number of consistent states shrinking as actions are taken, leaf correlation shows determinizations not flipping the outcome and also shows minimal bias.

Fig. 2: Here we explore varying (a) plan beam width and (b) worlds sampled as beam search raises it continues to improve. Worlds sampled saturates at around 32.

Defense	h2h vs. ByteRL	converged	peak
ByteRL (no search)	$\sim$ 50	90.1	97.0
plan search, $W{=}16$	50.5	61.9	65.0
plan search, $W{=}64$	56.6	69.3	74.5

TABLE I: Converged exploitability (250-iteration PPO best response, this is the mean of last five evaluations) and head-to-head strength. The head-to-head numbers are internal runs at

W{=}64

for both rows, with the uniform belief for the first and the runner-up prior for the second. The exploitability runs use

W{=}16

and

W{=}64

with the opponent’s list known, so compare within a column and not across.

Fig. 3: Best-response attack win rate over 250 PPO iterations and the three defenders. The attack on ByteRL reaches 90% within 50 iterations, while both search configurations hold the attacker. The defenses run at

W{=}16

64

which is far below the certified budget.

Explore similar work

Mar 3, 2026

Valet: A Standardized Testbed of Traditional Imperfect-Information Card Games

AI algorithms for imperfect-information games are typically compared using performance metrics on individual games, making it difficult to assess robustness across game choices. Card games are a natural domain for imperfect information due to hidden hands and stochastic draws. To facilitate comparative research on imperfect-information game-playing algorithms and game systems, we introduce Valet, a diverse and comprehensive testbed of 21 traditional imperfect-information card games. These games span multiple genres, cultures, player counts, deck structures, mechanics, winning conditions, and methods of hiding and revealing information. To standardize implementations across systems, we encode the rules of each game in RECYCLE, a card game description language. We empirically characterize each game's branching factor and duration using random simulations, reporting baseline score distributions for a Monte Carlo Tree Search player against random opponents to demonstrate the suitability of Valet as a benchmarking suite.

Mark Goadrich, Achille Morenville, Éric Piette

Hendrix College, Conway AR 72032, USA · ICTEAM, UCLouvain, Louvain-la-Neuve, Belgium

Imperfect-Information Games AI Agent Benchmarks Benchmark Design

Ask PDF

Sep 27, 2026

Modular Discovery of General Game-Playing Algorithms with Large Language Models

General Game Playing across arbitrary games from rules alone remains challenging due to differing algorithmic requirements across game classes and strict decision-time constraints. Rather than hand-designing search heuristics for specific domains, can we leverage Large Language Models (LLMs) to discover general game-playing algorithms? Because language models can propose and refactor structured code, they provide an expressive proposal engine for exploring the space of algorithmic designs. We introduce a multi-agent LLM meta-learning system to co-evolve game-agnostic procedural search mechanisms in C++ alongside domain heuristics synthesized directly from game rules. Controlling the compute budget, we benchmark the discovered mechanisms across more than 400 diverse environments, including OpenSpiel training and held-out games, procedural simulation engines, and games with deep neural policy-value representations trained via PPO. Evaluated via AlphaRank stationary distributions and Soft Condorcet Optimization (SCO) against 15 established MCTS baselines, the discovered search mechanisms consistently achieve top-tier ratings and pairwise ballot majorities over most baselines across independent evolutionary runs, generalizing to unseen human-designed and procedurally synthesized games and remaining competitive with baselines on frozen neural network representations.

Zun Li, John Schultz, Marc Lanctot +1

Google DeepMind · Work done while at Google DeepMind

Game-Playing Agents Automated Algorithm Discovery Multi-Agent LLMs

Ask PDF

Jul 6, 2026

Predicting Drafted Deck Strength for "Magic: the Gathering"

Many real-world games do not admit a fixed, compact rule set: instead, their dynamics are defined by interactions among a large and often evolving collection of game pieces, making general-purpose policy learning impractical. Magic: the Gathering (MTG) exemplifies this setting, where the cards themselves define and alter gameplay rules, strategic constraints, and long-term outcomes, while the pool of available cards is ever-changing. We study Draft, a constrained deck-building format of MTG in which eight players make 39-45 sequential selections from semi-random packs to construct a 40-card deck under partial information. By isolating the card selection process from gameplay, Draft provides a tractable yet non-trivial setting for studying decision-making driven by combinatorial card synergies. We propose an encoder-based model that produces set-contextualized card embeddings to encode the draft decision sequence, with a consistent improvement over linear baselines on large-scale real-world data, establishing a first learned benchmark for outcome prediction in MTG Draft. Our code is available at github.com/akulen/MtGDraftEncoder.

Tomas Rigaux, Hisashi Kashima

Grad. School of Informatics Kyoto University Kyoto, Japan

Representation Learning

Ask PDF