PaperlayerView exact revision on arXiv

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

CCG belief states are too large for sound enumeration-based search, motivating sampled unsound search in LoCM. The paper builds an imitation-trained policy-and-value agent with rules-consistent world sampling and evaluates it under the official referee and timer. It achieves a 51.35% win rate against ByteRL over 10,000 pre-registered games, with search contributing +24.6 points over the raw policy and improving resistance to a published attack. The study is limited to the battle phase, exceeds the competition memory cap, and depends on hardware including GPU parallelism.

  • Problem

    CCGs create belief states too large for sound enumeration-based search, leaving limited evidence about practical search in this setting.

  • Method

    The agent combines imitation-trained policy and value networks with beam search over worlds sampled from rules-consistent opponent-deck priors.

  • Results

    51.35% win rate against ByteRL over 10,000 pre-registered games, with search adding +24.6 points over the same network’s raw policy.

  • Takeaways & Limitations

    In LoCM, unsound decision-time search produces a stronger agent and better resistance to the published best-response attack than ByteRL.

  • Takeaways & Limitations

    The evaluation covers only the battle phase, exceeds the competition memory cap, and may be constrained by GPU and hardware availability.

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

Collectible card games combine hidden information with enormous state spaces, making sound enumeration-based search difficult. This paper argues that LoCM has structural properties favorable to unsound search and develops an efficient policy-and-value engine to test it.

  • Motivation: CCGs hide hand and deck contents while card order creates combinatorially large state spaces.Player actions can also reveal hidden information about the hand.
  • LoCM setting: LoCM simplifies agent development while retaining CCG challenges, and this study evaluates its battle phase with fixed, identical decks.Version 1.5 uses 120 randomly generated cards and 30-card decks with at most two copies of each card.
  • Motivation: ByteRL, LoCM’s leading policy, abandons both training-time and decision-time search in favor of a recurrent policy evaluation.The policy evaluates the action history and current state directly at decision time.
  • Research gap: Sound imperfect-information methods require state enumeration, while sampling methods are too slow to converge across CCG-scale state spaces.These constraints motivate investigating theoretically unsound perfect-information Monte Carlo search.
  • Approach: LoCM exhibits high leaf correlation, near-.5 bias, and strong disambiguation, supporting exploration of unsound search in this game.The authors build a fast engine with imitation-trained feed-forward policy and value networks plus rules-filtered consistent-world sampling.

II. RELATED WORK

Prior LoCM agents established strong performance without inference-time search, while a best-response attack substantially defeated ByteRL. These results frame search and robustness as open questions for the paper’s agent.

  • LoCM agents: ByteRL won both COG 2022 tracks using industrial-scale training and no search at inference.This establishes the competition champion as a strong no-search baseline.
  • Robustness: Haluška and Schmid defeated ByteRL with an approximately 90% win rate using a best-response attack.The result provides prior evidence that ByteRL is vulnerable to targeted exploitation.

B. Sound Search in Imperfect-Information Games

Sound imperfect-information search depends on enumerable belief states, which CCGs lack, so the paper uses sampled determinized search and validates its implementation against the official engine for certified results.

  • Sound Search in Imperfect-Information Games: Sound methods such as ReBeL and Student of Games resolve subgames over explicit belief distributions and require enumerable states.LoCM has approximately 2^101 hidden states at battle start, making enumeration infeasible.
  • Determinized Search: PIMC samples W worlds, searches each with perfect-information methods, and aggregates their results despite strategy fusion and non-locality.Prior work found these defects need not impair play in every game structure, motivating measurement in LoCM.
  • Determinized Search: Sampled beliefs avoid enumerating every consistent state, allowing search where sound methods cannot operate.The paper also studies whether this search configuration improves defenses against exploitative strategies.
  • Implementation: A new Rust engine simulates 443× more games per second than gym-locm and supports efficient, distribution-controlled determinization.This speed makes runtime search and imitation training more feasible.
  • Validation: Certified results use the official competition engine and referee, while the agent’s reimplemented engine performs search using only partially observable information.This separates headline matchup claims from dependence on the new engine’s correctness.

A. Observation and Action Encoding

The agent adopts ByteRL’s state and action representation for supervised imitation while replacing its recurrent architecture with feed-forward networks and searching complete turns over sampled opponent worlds.

  • A. Observation and Action Encoding: The networks use ByteRL’s per-card atoms and action space but are feed-forward over the current state rather than recurrent.They only observe the acting player’s cards.
  • A. Observation and Action Encoding: Because players complete a full turn before passing, the agent uses beam search over plans that terminate with a pass.It then samples W opponent worlds from priors over the remaining hand and deck, including draft-based and uniform mixtures.

C. Training

Training uses behavior-cloned policy-and-value networks, jointly refined with teacher self-play data under the battle-phase evaluation protocol.

  • C. Training: All networks use dual policy and value heads initialized by behavior cloning.The policy uses teacher-action cross-entropy, while the value head regresses game outcomes.
  • C. Training: The main training lines use ByteRL self-play or a strictly separate NeteaseOPD-trained line.NeteaseOPD is the runner-up policy used for the separate training line.
  • C. Training: Evaluation fixes identical decks and varies only battle-phase play between the agents.Both players enter battle with identical decks, while the first player alternates across games.
  • C. Training: The official-referee mode gives the agent partially observable data and a 200 ms move timer after the first move.The agent reconstructs the game using its engine and must respond through the competition protocol.
  • C. Training: Certified runs use an isolated AWS g5.2xlarge, and hardware strength affects the runtime search budget.The paper notes that different hardware configurations could improve or hurt the agent.

B. Corpora

The corpora combine large-scale self-play from leading policies with preregistered certification and a converged best-response attack protocol.

  • B. Corpora: 80k ByteRL self-play games and 126k NeteaseOPD self-play games generate imitation-learning data.Of the ByteRL games, 36k are used for training; NeteaseOPD also supplies the belief prior.
  • B. Corpora: Certification uses uninterrupted cloud execution, disjoint seed blocks, Wilson 95% confidence intervals, and preregistered game counts.The protocol accounts for substantial variance at 1,000 games before fixing the certification configuration and sample size.
  • B. Corpora: The attack protocol fine-tunes a policy against a frozen defense on a fixed pool of 32 decks with the opponent’s list known.Each attack runs to convergence, verified by a plateau through oscillation.
  • B. Corpora: ByteRL reaches a 97.0% peak attack win rate and a 90.1% replicated converged rate.The replicated converged rate is close to the paper’s reported 90.4%.

E. Game-Structure Measurement

The study measures structural properties of LoCM’s hidden-state game and evaluates search against ByteRL under different information assumptions.

  • E. Game-Structure Measurement: Game-structure measurements use NeteaseOPD self-play without search across 32 fixed decks and 600 games.The measurements quantify disambiguation, leaf correlation, and first-player bias from sampled consistent worlds.
  • E. Game-Structure Measurement: 51.35% [50.37, 52.33] is the certified win rate over 10,000 games for strict search against ByteRL.The configuration uses NeteaseOPD self-play and a 50/50 mixture of the NeteaseOPD prior with a uniform distribution.
  • E. Game-Structure Measurement: 26.8% is the corresponding policy-argmax win rate, while search adds +24.6 points.The results include an even split of games by first player, despite a first-player advantage.

B. Search Budget Ablations

Search strength rises with wider plan beams and better opponent priors, while additional worlds, depth, and model size provide limited gains at the tested settings.

  • B. Search Budget Ablations: Candidate-plan beam size from 12 to 96 continues to increase strength.The accompanying search-budget figure also reports continued improvement as beam search raises its width.
  • B. Search Budget Ablations: More search depth does not increase agent quality, and most search value is gained immediately by evaluating plans.The authors connect the gain to generating a full plan for the turn and evaluating its result.
  • B. Search Budget Ablations: Win rate is 50.5 with a uniform assumption, 56.6 with the runner-up prior, and 59.6 with the exact opponent list.These results show performance increasing as the opponent-deck assumption becomes more informed.
  • B. Search Budget Ablations: Quadrupling training data moves win rate 8 points for both 2.5M- and 10M-parameter models.Model size does not appear to contribute at this game level and imitation-learning setting.

E. Exploitability

Search substantially reduces exploitability against the replicated best-response attack: ByteRL reaches 90% attacker win rate quickly, while both search configurations hold the attacker. This robustness was measured with reduced search budgets rather than the official certification budget.

  • 21 to 28 points: adding search cuts ByteRL’s converged exploitability by 21 to 28 points.The exploitability test used W=16/64, below the search available under the certification time limit.
  • High leaf correlation supports search because consistent hidden worlds tend to agree on the winner.The paper also reports that world samples saturate at 32, suggesting this sample size is already predictive for action selection.
  • 90%: the attack on ByteRL reaches 90% win rate within 50 PPO iterations, while both search configurations hold the attacker.The defenses use W=16/64, far below the certified budget.

B. Decision-Time Compute Under the Competition Limits

Decision-time computation provides a clear advantage under the competition clock, but the agent exceeds the competition’s memory cap and therefore could not qualify as an official entry. The evidence also cautions that imitation fidelity and head-to-head strength do not directly establish robustness.

  • 200 ms: the competition caps decision-time computation at 200 ms and 256 MB RAM, while training compute is uncapped.The agent competes within the clock but exceeds the memory limit.
  • ∼0.9 GB: the agent peaks at about 0.9 GB memory with search, versus the 256 MB competition cap.Its no-search runtime still peaks at ∼535 MB, while ByteRL peaks at ∼37 MB.
  • 28 points: closely matched agents can differ by 28 points against a best-response learner.Thus head-to-head playing strength does not translate directly to robustness against best-response attacks.
  • Large game counts are required to measure the agent’s minor edge because the observed win rate has a ±3 margin over 1,000 games.The study therefore uses a pre-registered certification protocol with large competitions.

E. Limitations

The evaluation is limited to LoCM’s battle phase and a small deck set, while the agent exceeds the competition memory cap and exploitability was only sampled once per defense. The paper presents broader CCG generalization as future work.

  • The study evaluates only the battle phase, not the draft phase, and its memory usage exceeds the competition cap.GPU support in the official competition is also unclear, creating a hardware-scope limitation.
  • Exploitability is measured with one run per defense, and the certified agent’s exploitability is not measured.The paper states that the certified agent’s exploitability is likely higher.
  • The structured PIMC efficacy measurements cover only 32 decks.The authors identify testing generalization to stronger play in other CCGs as future work.
  • The reported evaluation gives the agent a favorable setup by allowing ByteRL to draft both decks while using a belief prior from the runner-up’s drafting choices.The agent is not trained against ByteRL or conditioned on its play.
  • Decision-time search over sampled beliefs is presented as a practical approach where sound search cannot extend, but the conclusion is scoped to LoCM.The paper attributes the practical advantage partly to a rules engine that supplies card-interaction consequences and consistent hidden worlds at decision time.
Loading 2609.06816v1…