12 papers
When Are We Near Nash? Certifying Solutions in General-Sum Games
Boning Li, Longbo Huang
Heuristic solvers for general-sum extensive-form games produce a stream of iterates, and practice reports the NashGap of the returned profile. We ask what a solver can know about i…
Why Alternation Speeds Up Counterfactual Regret Minimization?
Boning Li, Longbo Huang
Solving imperfect-information games at scale rests on counterfactual regret minimization with the regret matching (RM) update, and a seemingly minor implementation choi…
GPU-CFR: 80x Faster Counterfactual Regret Minimization by Compiling the Game to Static Dataflow and CUDA Graph Replay
Boning Li, Longbo Huang
Counterfactual regret minimization (CFR) is one of the few large numerical workloads that still runs faster on CPUs than on GPUs. Each iteration sweeps a game tree with up to billi…
Abstraction Agent
Boning Li, Longbo Huang
Information abstraction, which groups strategically similar private states into a tractable number of buckets, is essential for scaling game-solving algorithms to large imperfect-i…
ICM Out! Better Tournament Strategy from Computed Continuations, vs. Solvers and LLMs
Boning Li, Longbo Huang
The Independent Chip Model (ICM) converts tournament chips into reference prize equity, and policies are routinely constructed against those values. Because ICM reads only stack si…
Solver-Guided Reasoning for Mixed-Equilibrium Strategies
Han Wang, Philippe Beardsell, Boning Li +4
Reasoning in large language models (LLMs) is often grounded in human text, human demonstrations, and human-generated rationales. For equilibrium reasoning in complex games, however…
AV-AIVAT: 74x Cheaper Agent Evaluation with Certified Anytime-Valid Stopping in Imperfect-Information Games
Boning Li, Yu Chen, Longbo Huang
Deciding which of two agents is stronger means playing games until skill outweighs luck, and every game costs money, model inference, or expert time. Since the number of games need…
Agents That Certify Their Own Exploits: Confidence-Scheduled Restricted Responses for Safe Opponent Exploitation
Boning Li, Longbo Huang
An agent playing a Nash-equilibrium strategy in a two-player zero-sum imperfect-information game secures the game value but forfeits the additional value offered by a flawed oppone…
Correlated Chance Sampling for Monte Carlo Counterfactual Regret Minimization
Boning Li, Yu Chen, Longbo Huang
Monte Carlo Counterfactual Regret Minimization (MCCFR) repeatedly allocates chance outcomes while its strategy evolves, yet standard sampling draws those outcomes independently on…
PokerSkill: LLMs Can Play Expert-Level Poker without Training or Solvers
Boning Li, Baoxiang Wang, Longbo Huang
Poker is a landmark challenge for artificial intelligence. The dominant approach relies on equilibrium solvers built on counterfactual regret minimization, requiring millions of co…
Real-Time Parallel Counterfactual Regret Minimization
Boning Li, Longbo Huang
Counterfactual Regret Minimization (CFR) is the dominant algorithmic family for solving large imperfect-information games, underpinning breakthroughs such as Libratus and Pluribus…
RL-CFR: Improving Action Abstraction for Imperfect Information Extensive-Form Games with Reinforcement Learning
Boning Li, Zhixuan Fang, Longbo Huang
Effective action abstraction is crucial in tackling challenges associated with large action spaces in Imperfect Information Extensive-Form Games (IIEFGs). However, due to the vast…