PaperlayerView exact revision on arXiv

Source-linked AI summary

PokaiTrainer: Scaling Belief-State Search to Competitive Pokémon VGC

Max Yu

arXiv:2608.29197v1cs.LGcs.AIcs.GT

TL;DR

VGC violates the tractability assumptions behind prior decision-time equilibrium search through simultaneous actions, wide stochastic outcomes, and hidden information. The paper builds an exact-outcome engine and adapts Student of Games to belief-state search under compute budgets, achieving 59% wins across 150 live ladder sets against a field averaging ∼1320 Elo. The results show that belief-state equilibrium search can scale to this combination of game properties, while exposing unresolved calibration and evaluation boundaries.

  • Problem

    VGC combines simultaneous joint actions, wide stochastic outcome distributions, and hidden reserves and stat allocations, leaving it unclear whether belief-state equilibrium search can scale to the format.

  • Method

    PokaiTrainer adapts Student of Games with Bayesian matrix-game solving over public belief states, exact chance enumeration, compute-budgeted subgames, and self-play training.

  • Results

    59% of 150 live best-of-three sets were won against a human field averaging ∼1320 Elo, with the agent reaching a 1350–1400 Elo band and briefly entering the top 500.

  • Takeaways & Limitations

    Belief-state equilibrium search scales to VGC’s simultaneous moves, wide chance nodes, and hidden information when paired with an engine that enumerates chance and a solver that budgets its subgame.

  • Takeaways & Limitations

    Training leaves early-game value optimism unresolved, and the evaluation covers Open Team Sheets while closed-sheet play remains future work.

Abstract

from arXiv · show

Decision-time equilibrium search carried poker to superhuman play, but it has so far relied on tractable subgames: a handful of actions per decision, chance confined to card deals, one player moving at a time. Competitive Pokémon in its official doubles format (VGC) breaks all three assumptions at once. Both players act simultaneously from joint menus in the hundreds, each joint action resolves to hundreds of stochastic outcomes, and the opponent's reserves and stat allocations are hidden. We set out to build a strong VGC agent and report what that took. PokaiEngine, our Rust battle engine, enumerates a joint action's full weighted outcome distribution in one pass, at ${\sim}99\%$ parity with Pokémon Showdown and a fraction of the cost of sampling it. On top of the engine, PokaiTrainer adapts Student of Games to this scale, solving every decision as a Bayesian matrix game over public belief states and growing subgames under an explicit compute budget. On the live Showdown best-of-three ladder, the agent wins 59% of 150 sets against a human field averaging ${\sim}1320$ Elo. It settles into a 1350-1400 Elo band, and at its peak briefly entered the format's top 500.

1 INTRODUCTION

VGC challenges equilibrium search with simultaneous, wide, stochastic decisions and hidden information. PokaiTrainer addresses this through an adapted Student of Games pipeline and achieves competitive ladder performance, while leaving clear scope and training limitations.

  • VGC combines simultaneous turns, hundreds to thousands of joint actions, hundreds of stochastic outcomes, and hidden information, exceeding prior tractable equilibrium-search settings.
  • PokaiEngine exactly enumerates joint-action outcomes, while PokaiTrainer solves Bayesian matrix games over public belief states with incrementally budgeted subgames.
  • 59% of 150 best-of-three sets were won against a human field averaging ∼1320 Elo, with performance settling into a 1350–1400 Elo band and briefly reaching the top 500.
  • Search supplies the strength: the policy network alone loses to shallow heuristic search, whereas the same network under full search beats both.
  • Evaluation uses Open Team Sheets; closed sheets remain future work, and the authors claim no algorithmic novelty beyond their system adaptations.

2 BACKGROUND

VGC is a two-player zero-sum game whose simultaneous actions, hidden configuration details, stochastic outcomes, and mechanical breadth make decision-time equilibrium search demanding. These properties motivate belief-state search with approximate equilibrium methods.

  • VGC is a two-player zero-sum game where each player brings six customized Pokémon, reveals the team, selects four, and controls two active Pokémon at a time.
  • Simultaneous commitments create matrix-game incentives: Protect, switching, and attacks can counter one another, making deterministic play exploitable.
  • Open Team Sheets still hide stat spreads and reserve choices, while closed sheets hide additional team configuration information.
  • Moves can miss, critically strike, trigger secondary effects, and draw damage from 16 uniform multipliers, with up to four moves resolving per turn.
  • The game’s breadth of species, moves, abilities, items, and power-up mechanics shifts the burden toward learning interaction-specific knowledge on demand.
  • The proposed toolkit targets approximate equilibrium play using CFR and depth-limited search rooted at public belief states with learned value returns.

3 THE POKAIENGINE

PokaiEngine replaces single-path replay with exact chance forking, compact branch handling, and batched execution. Validation shows high behavioral parity, faster simulation, and better outcome-distribution coverage than practical sampling.

  • A single-path engine exposes joint-action outcome distributions only through repeated replay, allowing moderately likely compounded outcomes to be missed.
  • Search mode forks every chance event and returns the full weighted outcome distribution in one pass without sampling variance.
  • Optimizations: Branching that changes values without changing behavior remains within one state, while forks are reserved for categorical divergences such as knock-outs or speed-order changes.
  • Optimizations: Probability-floor pruning and merging identical outcomes further control the number of enumerated states.
  • Validation: ∼99% behavioral parity with Showdown was obtained after fixing four bugs revealed by exhaustive comparison across 500 random turns.
  • Validation: 26× faster simulation was achieved in Compute mode, resolving median turns in 0.08 ms versus Showdown’s 2.0 ms.
  • Validation: 17% of outcome mass was missed by 256 samples on the branchiest probe, where exhaustive enumeration found 960 distinct outcomes.

4 METHOD

PokaiTrainer adapts Student of Games to VGC’s simultaneous, stochastic, imperfect-information setting by solving Bayesian matrix games over public belief states. It grows subgames under compute budgets and trains networks from search and self-play targets.

  • Core architecture: PokaiTrainer adapts ReBeL and Student of Games with CFR over public belief states, value-network leaves, incremental subgame growth, and self-play retraining.The paper frames these changes as adaptations to simultaneous joint actions, wide chance nodes, and VGC’s data demands rather than a new algorithm.
  • Belief representation: Public belief states pair observable battle state with a posterior over opponent lineups, while hidden stat spreads are represented as mixtures inside each world.The model treats the agent’s own hidden configuration as known to both players, an explicit approximation.
  • Core architecture: Each decision is a Bayesian matrix game in which chance samples a hidden world, both seats choose simultaneously, and the engine resolves their joint action into weighted successors.Seat 1 uses one strategy, while the privately informed opponent uses a world-specific strategy; the value network returns one value per world.
  • Decision types: Team preview solves 90 bring-and-lead options per side, then uses the opponent’s bring marginal and revealed leads to seed the initial belief.The resulting belief supplies the hidden-information state for later solves.
  • Decision types: Turn menus contain roughly 10^2 joint options per side, so policy-weighted shortlists cap both players’ matrices while reserving capacity for switches and gimmick actions.Opponent actions are aligned across worlds by identity and scored with belief-weighted priors.
  • Budgeted search: Subgames expand by a PUCT-like selection rule until a compute budget binds, with cost scaled by belief width and cheaper mid-turn or forced-switch nodes.Expansion interleaves continuation selection with regret updates rather than counting nodes alone.
  • Inference and learning: Opponent stat beliefs are updated by re-branching observed turns through the exact engine, while a shared transformer supplies policy priors and per-world values.Training starts from behavior cloning, then mixes solver backups with realized outcomes for the played world and pure solver targets elsewhere.

5 EXPERIMENTS

Experiments evaluate a behavior-cloned, search-based agent across controlled eval16 matches, training extensions, deployment-time search variants, and live Showdown ladder sets. Performance is strongest when search is scaled carefully, but training gains plateau and early-game value optimism persists.

  • Setup: The reported agent uses a 256-wide, 6-layer transformer initialized from 122,804 human replays and searches up to 15 worlds with budgeted PUCT expansion.Evaluation uses 663 public team pastes for self-play and a hand-picked 16-team pool spanning primary archetypes.
  • Setup: The evaluation protocol combines 256-game eval16 cells, larger 1,024-game close calls, fixed opponents, and live best-of-three ladder runs.Checkpoint comparisons use the average strategy, while ladder play samples at temperature 0.5.
  • Training run: Eight further rounds at B=16 reached 50.8% against round 32, while a B=32 continuation reached 48.1%, showing diminishing training returns.A B=64 extension briefly reached 54.5% against round 32 before giving back its gains; round 32 remains the evaluated checkpoint.
  • Limitations: Evaluation is limited to Open Team Sheets, excludes Illusion, and withholds closed-sheet evaluation as future work.The paper also notes that trained checkpoints are unlikely to be released while the trained format remains active.
  • Limitations: The remaining defect is early-game value optimism, which neither additional rounds nor deeper self-play solves correct.Solved root values are better calibrated than the seeding network overall, but the live and certified-position defect remains unexplained.
  • Training run: Search carries strength: GREEDY beats every raw policy head at 71% pooled, while every search agent beats its own policy head.The authors identify encoder and compute, rather than target construction, as the clear training-side drivers of strength.
  • Deployment search: Deployment scaling rewards deeper, sharper child solves: solves reaching at least three turns rise from 18% to 56%, while the winning shapes cost 4–6× native wall clock.Wider menus alone dilute CFR convergence, whereas child-menu widening combined with budget and more CFR iterations improves direct-play results.
  • Human evaluation: The agent wins 59% of 150 live ladder sets against a human field averaging ∼1320 Elo, settling into a 1350–1400 Elo band after briefly entering the top 500.Across two 75-set runs, native deployment won 58.7% and scaled deployment 60.0%; the scaled run’s game win rate was 56.0%.

6 RELATED WORKS

The paper situates PokaiTrainer within equilibrium search, Pokémon agents, and simultaneous-move game research. Its contribution is to test whether decision-time equilibrium search can scale to VGC’s joint actions, hidden information, and stochastic transitions.

  • Equilibrium search: Equilibrium search advanced imperfect-information games from poker competition to superhuman play through depth-limited public-belief subgames, learned leaf values, and self-play.ReBeL and Student of Games exemplify this modern recipe.
  • Pokémon agents: Earlier Pokémon systems used heuristics, scripted or search-based singles agents, determinization, or offline learning rather than equilibrium search in VGC.Foul Play is the closest cited system, using a Rust engine and sampled hidden sets with independent MCTS per sample.
  • Simultaneous-move games: DeepNash reached expert-level Stratego without decision-time search, leaving open whether search pays off in simultaneous-move imperfect-information games.The paper also notes that standard decoupled UCT can converge to exploitable strategies, motivating regret-based alternatives.

7 LIMITATIONS AND CONCLUSION

The paper finds that belief-state equilibrium search scales to VGC within mapped limits, while identifying unresolved team inference, limited generalization, value-calibration, and compute-scaling boundaries.

  • Limitations: Closed team sheets expand hidden uncertainty from stat spreads to complete builds, and inferring those sets remains unsolved in this framework.The hidden space includes moves, items, abilities, and spreads jointly.
  • Limitations: Team construction is out of scope, while online play only partially exercises generalization across diverse opponent archetypes.Self-play rates teams, providing a signal for a future team-builder search.
  • Limitations: The reported run uses roughly 250 L40S-hours of self-play and ∼15 A100-hours of retraining, far below the compute of predecessor milestones.The paper states that diminishing returns at this scale do not establish the recipe’s ceiling.
  • Limitations: Early-game value optimism persists because realized outcomes are noisy labels drawn from hundreds of possible outcomes per turn.Deeper solves mask rather than fix this calibration defect.

REPRODUCIBILITY STATEMENT

The reproducibility statement describes planned releases while noting that release timing and terms are being coordinated with Showdown administrators.

  • Reproducibility statement: The authors intend to release PokaiEngine and PokaiTrainer, subject to coordination with Showdown administrators.The stated concern is that public release could put proficient bots on the live ladder.

USE OF LARGE LANGUAGE MODELS

The authors disclose Claude’s use as a coding and writing assistant and retain responsibility for the system, experiments, code review, reported numbers, and report content.

  • Use of large language models: Claude was used for coding, evaluation tooling, and drafting and editing, while the authors designed, reviewed, verified, and assumed responsibility for the work.The authors verified every reported number against logged artifacts.

A.1 SYSTEM ARCHITECTURE AND BACKENDS

The system architecture uses a shared battle abstraction across local, offline, and live backends, with compact belief-state representations and batched computation across outcome branches.

  • Backends: A shared battle abstraction exposes local engine play, an offline Showdown process, and the live Showdown ladder as interchangeable backends.These backends operate under one seat-view surface.
  • State representation: HP damage rolls and hidden stat spreads are represented as in-state distributions to compact uncertain battle states.Different Pokémon’s spreads are treated as statistically independent for this compaction.
  • Branch sharing: Shared damage modifiers are computed once per batch, while status-, stage-, and spread-dependent work remains per state.Batches group attributes that rarely diverge across a turn’s forks.

B METHOD DETAILS

PokaiTrainer extends belief-state equilibrium search to VGC by representing decisions as Bayesian matrix games and adapting state encoding, hidden-stat inference, sampling, and compute-budgeted solving. The method combines public-belief subgames, exact engine outcomes, learned leaf values, and incremental supervision.

  • Relation to ReBeL and Student of Games: PokaiTrainer follows ReBeL and Student of Games while adapting their recipe to VGC’s simultaneous actions, wide chance nodes, and hidden stat spreads.The adaptations are presented as domain-driven changes rather than a new algorithm.
  • Budgeted solve: Figure 4’s budgeted solve roots a subgame at public belief state β, places matrix games at decision nodes, and uses exact outcome batches, leaf values, and PUCT expansion.Turn-node payoff matrices are weighted by belief and solved jointly by CFR.
  • State representation: The encoder represents rosters, battle state, hidden opponent information, field state, phase commitments, and stat-belief quantiles in a shared tokenized position.Opponent calculated stats are masked, while belief summaries include phase-and-queue information and quantiles over hidden spreads.
  • Interior-row sampling and weighting: Interior supervision samples rows proportional to reach under the average strategy and discounts backups that rely more heavily on leaf-network pricing.Horvitz–Thompson sampling preserves reach weighting in expectation, while the in-tree fraction controls the discount.
  • Hidden stat belief machinery: The hidden-build model assumes independent per-Pokémon spreads and uses corpus or fallback candidates, with closed-sheet inference identified as a future extension.The current candidate menus are built for open sheets; closed sheets require a Bayesian team-paste corpus model instead.
  • Hidden stat belief machinery: Hidden stat beliefs are updated from observed actions, public outcomes, and move-order signatures by re-branching the engine across candidate spreads.Likelihood floors prevent surprising observations from eliminating candidates outright, while contradiction handling rebuilds inconsistent worlds.

D TEAM STRENGTH AND POOL EFFECTS

Team evaluations show that measured strength depends strongly on the opponent pool, search depth, and team durability rather than on corpus ratings alone. The final agent’s reference and encoder comparisons also expose substantial effects from representation and compute choices.

  • Team-pool composition: Eval16 spans ranks 3–459 of 648 builds, with median rank 217, and its corpus ratings correlate weakly with round-robin ordering.The pool was chosen for archetype diversity rather than strength, and neither ordering predicts current ladder residuals reliably.
  • Elite round-robin: The 32-team elite round-robin uses a deepened deployment shape, with Win% measured over 93 games per team and cRk reflecting corpus-wide fit.The table compares strong builds under a consistent deep-search evaluation and preserves corpus rank as a separate axis.
  • Elite round-robin: The Mega Staraptor sand team won the elite round-robin, sweeping 16 of 31 opponents, while Mega Sceptile sand held 60.2% against the elite pool.The winner was a tournament-proven team, whereas the fourth-ranked corpus build was a less expected entrant near the top.
  • Human-meta strength: A tournament-winning surprise team finished last in the elite pool, showing that human-meta success and self-play search strength can diverge.Its gameplan relies on surprise against human expectations, which the self-play-trained search neither finds nor falls for.
  • Search depth and durability: Deeper deployment reshuffled team rankings: durable builds rose, while hyper offense fell, although search depth and opponent-pool effects remain confounded.For example, one rain team rose from 22nd to 8th and its sibling from 20th to 5th, while hyper offense fell from 8th to 21st.
  • Ladder evaluation: The top-eight ladder run achieved 56.3% set wins and 52.6% game wins over 142 sets, below both eval16 runs despite using stronger teams.Its first 81 sets reached 64.2% before the remaining 61 sets went 28–33, illustrating substantial single-account variation.
  • Reference agent and encoder lineage: Adding phase and queued-commitment summaries plus spread quantiles improved the encoder lineage, while parity with D1SW required raising the budget to 32.The measured phase-block contribution is confounded with search changes, but the deeper trunk added approximately 6 percentage points in one comparison.

E.3 TRAINING ABLATIONS

Training ablations find that inference-time expansion and shortlist design matter more reliably than most target or solver changes, while value-network quality remains the main bottleneck. The experiments are noisy at the available compute scale, so variants are retained mainly when they are not worse and offer practical advantages.

  • ±4–6pp resolving power makes most individual ablation effects indistinguishable from noise, so the study avoids claiming wins within that band.Campaign arms span two to seven rounds, with cells of 256–512 games.
  • Expansion and budget: 2× inference budget improved a midcampaign network by +4.3pp, whereas doubling data-generation budget did not move a plateaued lineage.Inference budget converted directly into performance, while additional training-generation budget showed no comparable movement in the reported rounds.
  • Expansion and budget: PUCT walks matched queue-mode performance while using roughly half the training rows per round and 8% less wall time per decision.The two variants were retained despite confounding from different hypothetical-fork counts because the walk reduced forced-switch plans and inference cost.
  • Interior rows: λint=0.15 rising to 0.25 was retained because interior-row weighting was cheap through 0.15, while higher weighting increased value-network error without improving later play.At λint=1, retraining cost +0.003–0.005 MSE and reduced corr(v, z) by 0.07; round-six play was flat across λint values.
  • Targets: The value network, not target construction, remains the binding constraint: most target and expansion levers stayed within a 256-game cell’s ±6pp parity band.The discrimination suite found that networks often selected the correct move under search without reliably separating certified wins from losses.
  • Menus and solver iterations: +16pp came from ranking opponent menus by belief-weighted policy prior rather than support count, also correcting early Protect omissions.The same network reached 57.8% versus 41.8% over 512 games, and attack-biased shortlists had omitted Protect on 48% of legal turns.
Loading 2608.29197v1…