CS Paper Radar

PokaiTrainer: Scaling Equilibrium Search to Competitive Pokémon VGC

Max Yu

cs.LG cs.AIcs.GT ·submitted 2026-08-29 11:11 UTC · v2

Abstract

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. No prior Pokémon agent performs equilibrium search, and whether it scales to this regime was open; we show that it does, and report what it 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. PokaiTrainer adapts Student of Games to this scale and trains it by self-play over hundreds of human teams. Each decision is solved by counterfactual regret minimization as a Bayesian matrix game over public belief states, subgames grow under an explicit compute budget, and value targets are harvested from the interior of every solve and grounded by realized outcomes. The strength is in the search. The network's policy alone loses even to a shallow heuristic search. PokaiTrainer is, to our knowledge, the first VGC agent rated on the live Showdown ladder. Under open team sheets it wins 59% of 150 best-of-three sets against a human field averaging ${\sim}1320$ Elo, holds a 1350-1400 Elo band, and at its peak reached 1492 Elo, entering the format's top 500.

Comment
25 pages, 4 figures, 9 tables. v2: title and abstract revised; adds decoupled-UCT and local best response equilibrium-quality experiments

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.AI ·2026-09-06 ·Dustin Rubin
similarity 0.64
Abstract · 6 pages, 3 figures, 1 table. Also available as a Zenodo preprint, doi:10.5281/zenodo.22547763

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.

0.18

Beating the Pool, Not the Game: A White-Box Equilibrium Agent for Language-Based Economic Games

cs.RO ·2026-11-07 ·Sudhanshu Srivastava, Faisal Aqlan
similarity 0.63
Abstract

We describe sudsho, a rule-based agent for the GLEE Competition that plays bargaining, negotiation, and persuasion with zero inference-time LLM calls. Games are scored as payoff percentiles against an empirical pool of prior play on the same configuration, so pool percentiles set our demand targets while clamped equilibrium shares bound demands and acceptance. Every move is a deterministic function of the visible state (persuasion mixing aside), so alignment is verified by replaying the post-freeze move log through the policy. Across 117,280 games the agent reached an overall rating of 2056 at $0 inference cost, and the account, ranked by its best agent (a same-policy replica), placed 26th of 71 ranked accounts. A replay against three frozen snapshots of the opponent pool credits the pool-aware clamp with 274 to 330 points of mean per-game bargaining rating, an effect that holds where logged opponent decisions fix the replay.

0.10

Porimon: An LLM-Based Pokémon Battle Agent Enhanced by Long/Short-Term Knowledge Augmented Generation

cs.AI ·2026-09-26 ·Dongyin Zhuo, Fengjunjie Pan, Nenad Petrovic, Alois Knoll
published similarity 0.62
Abstract · 6 pages, 5 figures, accepted by FLLM 2026

In this paper, we use Pokémon Battles as a case study to investigate how to improve the performance of LLM-based agents in tasks that require opponent-aware planning without additional fine-tuning. We propose Long/Short-Term Knowledge Augmented Generation (LSTKAG), a mechanism that enables LLM-based agents to leverage past states of the current task and retrieve experience summaries from similar previous task instances based on the current state. Based on LSTKAG, we design Porimon, an LLM-based agent structure for Pokémon Battles. For optimization, we introduce an external API for precise damage calculation and more detailed information about the game. We conduct tournament-like evaluation experiments comprising 15,000 battles for hyperparameter optimization, ablation studies, and performance evaluation. The results indicate that Porimon-based players with hyperparameter optimization significantly outperform players based on PokéLLMon, an LLM-based agent structure proposed in previous research, and the rule-based heuristic player. Furthermore, our ablation study shows that Porimon variants outperform the one without extension in game information retrieval, which shows the contribution of that extension. However, the current experiment results are inconclusive regarding the contribution of Long-Term KAG. These results suggest that introducing external resources, information from previous states of the current task, and experience summaries from similar previous task instances could elevate the performance of LLM-based agents designed for tasks requiring opponent-aware planning.

0.45

Bayesian Replicator Dynamics and the Inversion of Strict Dominance in Bimatrix Games

cs.GT cs.MA ·2026-10-26 ·Jaime Ruiz-Serra, Nihat Ay, Michael Harré
similarity 0.61
Abstract · 18 pages, 3 figures

Replicator dynamics, the central model of evolutionary game theory, describe populations evolving under selection and agents learning by trial and error. They also admit a third use: continuous-time Bayesian inference, in which an agent planning against an opponent accumulates evidence for each candidate strategy. Here we show that this use divides all two-player games into two classes. With the standard expected-utility payoff, the dynamics can be expressed as Bayesian updating only in games (with any number of actions) where no player has a dominant strategy. The logarithmic payoff of Ay and Erb (2005) admits the Bayesian representation in every game. Coordination, anti-coordination, and cyclic games share qualitative dynamics under both payoff definitions, with equilibria displaced and selection thresholds shifted. In contrast, the flows of every game with a dominant strategy are reversed between the payoff definitions, with the strictly dominant strategy eliminated under logarithmic payoffs. Cooperation therefore emerges in the Prisoner's Dilemma, and games of common interest converge to mutual defection. For two-action games the classification is complete and rests on an exact Hamiltonian structure shared by both payoff definitions. The structure gives a behavioural test: cycles in the classic Matching Pennies game have amplitude-independent period (isochronous) under logarithmic payoffs, but not under expected utility. Logarithmic evidence integration thus determines which strategic outcomes dynamical selection can reach, wherever learning approximates Bayesian updating.

0.23

Why Alternation Speeds Up Counterfactual Regret Minimization?

cs.GT ·2026-10-15 ·Boning Li, Longbo Huang
theory similarity 0.61
Abstract · 34 pages, 8 figures

Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching$^{+}$ (RM$^{+}$) update, and a seemingly minor implementation choice accounts for much of its practical speed: alternating the two players' updates, so that the second player responds to the strategy the first player just produced. A widely repeated intuition explains why: seeing the opponent's fresh strategy should act like optimism. We treat this intuition as a testable hypothesis about deterministic two-player zero-sum self-play dynamics and find that its canonical additive form fails an information-matched test. On an analytic witness family we compare alternating RM$^{+}$ against a one-sided predictive RM$^{+}$ that receives the same information channel each round and differs only in where the fresh signal enters, a persistent regret state versus a transient prediction term. Our main result is a dichotomy theorem that reduces trajectory separation to the recurrence of exact-vertex play by the predictive dynamics: under an interior-band assumption on the alternating iterate, either vertex times recur and the profile distance is at least, infinitely often, an explicit constant that our measurements nearly attain, or they terminate. Across the tested self-play regimes, any correct explanation of the alternation speedup must reproduce a staleness cost present at the smallest tested stale fraction, an advantage that persists across seven orders of payoff conditioning, regime crossings of the optimism family, and a measured per-perturbation cost of weakening the injection path that is far steeper for staleness than for partial persistence.

0.40

Regularized policy gradient with learned mixtures of Gaussians for games with continuous actions

cs.MA cs.GT ·2026-09-29 ·Ondřej Kubíček, Viliam Lisý, Tuomas Sandholm
similarity 0.60
Abstract

Most successes of superhuman game-playing algorithms are in games with discrete actions, yet in auctions, robotics, sports, or trading, actions are nearly continuous. Prior techniques either rely on expert-designed discretizations or are sample inefficient. We present a scalable policy-gradient algorithm for large sequential games with continuous or mixed discrete and continuous actions. It combines magnetic mirror descent with a mixture of Gaussians reparametrization, trained via self-play. We show that it approximates equilibrium in games where gradient descent fails. In sequential games, it outperforms neural fictitious self-play and matches or outperforms the final strategies of policy space response oracles with 3.5--5.5$\times$ fewer samples. In heads-up no-limit Texas hold'em, it performs on par with Slumbot.

0.19

Efficient Nash Equilibrium Computation for Cybersecurity Games

cs.GT cs.AI ·2026-09-16 ·Michael Lanier, David Farmer, Yevgeniy Vorobeychik
theory similarity 0.60
Abstract

Game-theoretic analyses of cyber defence often compute equilibria of games whose payoffs exist only as the output of a simulator. Iterative equilibrium-finding methods grow a set of attacker and defender policies and need the payoff of every attacker--defender pair, so they are bottlenecked by payoff estimation: each payoff costs many simulator runs. We introduce Regret-Weighted Payoff Sampling (RWPS), which spends a fixed simulation budget on the payoffs the equilibrium actually depends on and predicts the rest with a model trained on every payoff measured so far. Standard error bounds for estimated games are driven by the worst-estimated payoff, so they cannot credit an estimator that is inaccurate only where accuracy does not matter. We prove a bound that weights payoff errors by the opponent's equilibrium strategy, a certificate that can be computed from simulated payoffs alone, and a condition under which errors in the predicted payoffs cannot change either player's regret. On three synthetic general-sum games, one of them a Colonel Blotto game of military resource allocation, the new bounds are four to six times tighter than the standard one, and RWPS finds less exploitable equilibria than minimum-regret-first search, information-gain search and progressive sampling at the same budget. On two cyber-defence simulators, CyGym and a new game whose hosts are LLM agents exposed to prompt injection, it gives the least exploitable equilibria at the smallest budgets.

0.26

A Resource Allocation Tournament

cs.GT math.OCecon.TH ·2026-10-22 ·Adam Nathaniel, Refael Hassin
similarity 0.60
Abstract

We introduce and analyze a round-robin simultaneous resource allocation contest, motivated by sports leagues and other competitive environments where agents must distribute limited resources across multiple encounters. Players allocate resources in advance to matches against all opponents, and match outcomes are determined by relative allocations. We study two payoff schemes: total points, where players accumulate rewards for each win, and winner-takes-all, where only the tournament winner is rewarded. For three players, we provide complete equilibrium characterizations under both schemes. For four or more players, we show that the total points payoff admits Blotto-type equilibria, while the winner-takes-all payoff requires numerical and algorithmic analysis. To address this, we develop a best-response dynamics algorithm with stochastic inertia and use it to approximate equilibria in games with four and five players.

0.26