Source-linked AI summary

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

Dustin Rubin

arXiv:2609.06816v1cs.AI

TL;DR

Sound search methods face scalability limits in collectible card games with huge belief spaces. This paper applies sampled-world unsound search with learned policy and value networks, reporting a 51.35% win rate against ByteRL over 10,000 pre-registered games.

  • Problem

    Sound search for imperfect-information collectible card games is limited by state enumeration, while sound sampling methods are too slow with high state counts.

    Source: §I · p. 2
  • Method

    The authors measured LoCM’s PIMC-relevant structure and built a policy/value agent using imitation-trained policies and decision-time search over consistency-filtered sampled beliefs.

    Source: §I · p. 2, B. Corpora · p. 3, §VII · p. 5
  • Results

    51.35% [50.37, 52.33] win rate against ByteRL over 10,000 pre-registered games; the raw policy scored 26.8%, with search adding 24.6 points.

    Source: A. Certified Results Against ByteRL · p. 4
  • Takeaways & Limitations

    In LoCM, measured game structure places PIMC defects in a regime where they are cheap, supporting unsound search as a practical option.

    Source: §I · p. 2, §VII · p. 5

    Evaluation covers only the battle phase, exceeds the competition memory cap, and measures exploitability once per defense; certified-agent exploitability was unmeasured.

    Source: E. Limitations · p. 5

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper evaluates sampled, theoretically unsound search in LoCM, where measured game-tree properties support exploring PIMC. Its runner-up-imitation agent beats ByteRL within the official time limit and resists a replicated best-response attack better than ByteRL at every iteration.

I. INTRODUCTION

  • CCGs combine hidden hands and decks with combinatorially many states; LoCM 1.5 uses a pool of 120 randomly generated cards to build 30-card decks with at most two copies each [3].The paper evaluates the battle phase in isolation, with fixed, identical decks for both players, while studying assumptions about the opponent's deck list.Source: §I · p. 1
  • The runner-up-imitation agent with sampled search beats ByteRL within the official time limit, with its certified win-rate confidence interval above 50%.The figure describes the certified comparison as within the official referee and time limit; the introduction says the agent beats the champion.Source: Figure 1 · p. 1, §I · p. 2
  • Sound enumeration-based methods ReBeL and Student of Games are intractable for CCGs, while Monte Carlo CFR, is too slow to converge with many states.PIMC is theoretically unsound because of strategy fusion and non-locality, although empirical work found its defects may not impair correct play in some game structures.Source: §I · p. 2
  • The search agent resists a replicated best-response attack better than ByteRL at every iteration.The paper applies the published attack protocol to ByteRL and its new policy.Source: §I · p. 2
  • The authors measured high leaf correlation, bias near .5, and strong disambiguation in LoCM, properties they say support PIMC search.They build a faster-than-gym-locm engine, imitation-trained feed-forward policy and value networks, and rule-filtered sampling of consistent worlds.Source: §I · p. 2

II. RELATED WORK

This section situates the work among LoCM agents, sound imperfect-information search, and determinized search, then describes how sampled-belief search and robustness evaluation relate to prior work.

A. Agents for Legends of Code and Magic

  • ByteRL [4] won both COG 2022 tracks with industrial-scale training and no inference-time search, while Haluška and Schmid [15] beat it at ∼90% with a best-response attack.Classic search won competitions under the fixed 1.2 rules, while learning agents took over in version 1.5; gym-locm provided battle-phase RL baselines. LoCM cards are procedurally generated, requiring agents to generalize over card properties [3].Source: A. Agents for Legends of Code and Magic · p. 2

B. Sound Search in Imperfect-Information Games

  • Sound-search methods such as DeepStack, ReBeL, and Student of Games resolve subgames over enumerable belief distributions, but LoCM has ∼2^101 battle-start states.Prior work explicitly called enumeration-based search unusable for LoCM [15]; ByteRL’s reason for omitting training-time search was sample throughput [4].Source: B. Sound Search in… · p. 2

C. Determinized Search

  • PIMC determinizes into worlds and aggregates perfect-information searches, risking strategy fusion and non-locality despite strong play in bridge and skat.Determinized search has been used in MtG, Hearthstone, and LoCM, but those works were not evaluated against a scaled-RL state-of-the-art agent; this work measures LoCM structures associated with lower defect costs. Search partly resists adversarial policies in Go, while poker’s LBR probe against DeepStack is the closest imperfect-information evidence.Source: C. Determinized Search · p. 2

D. Relation to Prior Work

  • Sampled-belief search avoids enumerating all consistent states, allowing it to operate where sound search cannot, and this work replicates and extends an exploitability study to examine search defenses.Source: D. Relation to Prior Work · p. 2

III. METHOD

The method combines a reimplemented LoCM engine, behavior-cloned policy and value networks, and decision-time search over sampled opponent worlds. The networks use ByteRL’s state and action encoding, while certified results were run through the official competition engine and referee.

III. METHOD

  • The Rust engine simulates 443× more games per second than reference gym-locm and enables controlled determinization to remove impossible states and apply priors over opponent hands.Certified numbers use the official competition engine and referee, while the agent searches in an isolated process using only its available information; extensive tests compare game behavior across engines.Source: §III · pp. 2–3

A. Observation and Action Encoding

  • The networks adopt ByteRL’s state and action encoding, including its per-card atoms and action space, to simplify supervised behavior cloning on self-play games.Unlike ByteRL’s LSTM, the networks are feed-forward and see only their own player’s cards.Source: A. Observation and Action Encoding · p. 3

B. Search

  • The certified agents combine learned policy and value networks with beam search over turns, scoring plans after sampled opponent reply turns and choosing the plan with the highest average value.The certified configuration uses beam 24, seven expansions, and up to 384 worlds under a 185 ms budget within the 200 ms timer; the opponent-hand prior varies across tested distributions.Source: B. Search · p. 3

C. Training

  • Networks are dual-head policy-and-value models initialized by behavior cloning, with policy cross-entropy and value-outcome regression trained jointly on self-play data.The study trains separate lines based on ByteRL self-play and on runner-up NeteaseOPD teaching without ByteRL play; headline agents are not trained or fine-tuned against ByteRL.Source: C. Training · p. 3

IV. EXPERIMENTAL SETUP

The experiments evaluate LoCM battle play under internal and official-referee protocols, with certified runs using predefined configurations, game counts, and seed blocks. The setup also specifies imitation-learning corpora, a best-response attack protocol, and measurements of game structure.

A. Game and Protocol

  • The study used LoCM 1.5 under COG 2022 rules and evaluated only battle play, with identical ByteRL-drafted decks for both players and alternating first player.The internal harness had no clock for ablations and search-depth tests; official-referee runs used isolated processes, partially observable inputs, and the competition protocol. Seeds were disjoint across tests.Source: A. Game and Protocol · p. 3

B. Corpora

  • The imitation-learning data comprised 80k ByteRL self-play games, 36k used for training, and 126k NeteaseOPD self-play games.NeteaseOPD was the COG 2022 runner-up; its published policy also generated the belief prior for play, while temperature-sampled early self-play decisions were excluded from value targets.Source: B. Corpora · p. 3

C. Certification

  • Certified games used the official referee, a 200 ms move timer after the first move, disjoint seed blocks, and configurations and game counts chosen before certification.Every move stayed within the timer; win-rate intervals were Wilson 95% CIs, and estimates suggested 1,000 games could vary by ±3 points. Certified runs used an AWS g5.2xlarge; hardware could affect search runtime and results.Source: C. Certification · p. 3, A. Game and Protocol · p. 3

D. Attack Protocol

  • 97.0% peak and 90.1% converged win rates against ByteRL replicated the published attack’s 90.4% converged rate.Following [15], the attacker was fine-tuned against a frozen defense on a fixed pool of 32 decks; search defenses played with the opponent’s list known, and results used the mean of the last five runs after convergence.Source: D. Attack Protocol · pp. 3–4

E. Game-Structure Measurement

  • Game-structure measurements used the NeteaseOPD-trained network without search, 32 fixed decks, and 600 self-play games.The study measured log2 consistent hidden-state counts, leaf correlation by comparing winners from two uniformly sampled consistent worlds, and bias as the first player’s win frequency near terminal outcomes, where 0.5 indicates no lean.Source: E. Game-Structure Measurement · p. 4

V. RESULTS

Under the strictest test, search beats ByteRL with an evenly balanced 10,000-game evaluation, and search also improves resistance to a best-response attack. Results further show that plan-evaluation budget, opponent-deck beliefs, and training data affect strength, while greater model size and search depth do not.

A. Certified Results Against ByteRL

  • 51.35% [50.37, 52.33] over 10,000 pre-registered games beats ByteRL, while policy argmax scores 26.8%, making search worth 24.6 points.The strictest test removes exact opponent-deck knowledge and uses the NeteaseOPD prior mixed 50/50 with a uniform distribution; games were evenly split by first player. With the opponent’s deck known and a ByteRL-trained policy, search reaches 60.4% over 500 certified games.Source: A. Certified Results Against ByteRL · p. 4

B. Search Budget Ablations

  • Strength rises as candidate-plan beam size grows from 12 to 96, but more than 32 worlds or greater depth adds no performance; evaluating plans supplies most search value.The results suggest that generating and evaluating a full turn plan is a main driver of search’s performance gain.Source: B. Search Budget Ablations · p. 4

C. Belief About the Opponent Deck

  • Win rate is 50.5 with a uniform opponent-deck assumption, 56.6 with the runner-up prior, and 59.6 when the exact list is known.Knowing the opponent’s exact list gives search a clear advantage.Source: C. Belief About the Opponent Deck · p. 4

D. Training Data and Model Size

  • Quadrupling training data raises win rate by 8 points for both 2.5M- and 10M-parameter models, while model size does not contribute to performance at this game level.Validation loss shows a capacity-by-data interaction, but it does not convert into wins; a smaller, faster, more parallelizable model may enable a larger search budget under time constraints.Source: D. Training Data and Model Size · p. 4

E. Exploitability

  • Adding search cuts converged exploitability by 21 to 28 points against the replicated ByteRL attack.Exploitability tests use W=16/64 with the opponent’s list known and a 250-iteration PPO best response; this is less search than the certification time limit permits, and certification resistance was not measured.Source: E. Exploitability · p. 4, Table I · p. 4

VI. DISCUSSION AND FUTURE WORK

The discussion argues that LoCM’s structure supports determinized search, while noting compute, memory, and evaluation limitations. It identifies broader CCG testing and sampled sound search as future directions.

A. Game Structure and Determinized Search

  • The three measured properties support PIMC in LoCM: play sharply reduces consistent worlds, bias is near neutral, leaf correlation is high, and 32 samples already guide action selection.The authors suggest strong disambiguation may generalize across CCGs, while the role of particular cards in deciding games may differ.Source: A. Game Structure and Determinized… · pp. 4–5

C. Imitation Fidelity, Head-to-Head Strength, and Robustness

  • The attack on ByteRL reaches 90% win rate within 50 PPO iterations, while both search configurations hold the attacker; imitation fidelity alone does not predict strength or robustness.The authors report that closely matched agents can differ by 28 points against a best-response learner, and that unsound search improves robustness even for an even policy. Defenses used W=16/64, below the certified budget; exploitability was measured in one run per defense, and the certified agent’s exploitability was not measured.Source: Figure 3 · p. 5, C. Imitation Fidelity, Head-to-Head… · p. 5, E. Limitations · p. 5

B. Decision-Time Compute Under the Competition Limits

  • Runtime search provides a clear advantage within the 200 ms clock limit, but memory peaks at ∼0.9 GB with search and ∼535 MB without it, exceeding the 256 MB cap.The champion peaks at ∼37 MB; the authors attribute much of their memory use to libtorch and note that unspecified hardware may not suit GPU-parallel search.Source: B. Decision-Time Compute Under the… · p. 5

D. Measuring a Small Margin

  • The authors created a certification protocol with a preregistered game count and large competitions because win-rate estimates varied by ±3 over 1,000 games.The protocol was intended to measure their small edge against ByteRL reliably.Source: D. Measuring a Small Margin · p. 5

E. Limitations

  • The study covers only the battle phase, exceeds the competition memory cap, and measures structured PIMC efficacy on just 32 decks.The authors also note uncertainty about GPU support in official competitions and that exploitability was evaluated in only one run per defense.Source: E. Limitations · p. 5

F. Future Work

  • Future work will test whether the algorithm generalizes to stronger play in other CCGs and compare sampled sound search variants.Source: F. Future Work · p. 5

VII. CONCLUSION

The agent’s final win rate was 51.35% over 10,000 pre-registered games without ByteRL data, and enabling search added +24.6 points over its raw policy. The conclusion attributes improved strength and attack resistance to decision-time search over sampled beliefs, supported by LoCM’s structure and rules engine.

VII. CONCLUSION

  • 51.35% win rate over 10,000 pre-registered games without ByteRL data, with search adding +24.6 points over the network’s raw policy.With the opponent’s deck known, determinized search over consistency-filtered beliefs achieved 60.4% against ByteRL under the official referee and clock.Source: §VII · p. 5
  • The attack beat ByteRL at 90.1% but converged to 62–69% against both search agents.The conclusion says decision-time compute buys robustness as well as strength.Source: §VII · p. 5
  • Evaluation choices tilted toward ByteRL: it drafted both decks, while the agent was not trained against ByteRL and used a prior from the runner-up’s drafts.The clock caps the resource the agent converts into playing strength.Source: §VII · p. 5
  • The rules engine supplies card-interaction consequences and consistent hidden worlds at decision time, avoiding work a policy would otherwise spend approximating.The conclusion says LoCM’s structure is measurably a setting where PIMC defects are cheap, making unsound search over sampled beliefs a practical route to strength and robustness where sound search cannot extend to.Source: §VII · p. 5
Loading 2609.06816v1…