regret

A game-agnostic implementation of the Counterfactual Regret Minimization (CFR) family for imperfect-information extensive-form games, written in Rust.

There is nothing about poker, dice, or cards in the core. You bring a game that implements the Game trait and the trainer learns a strategy (Profile). It covers the modern CFR / Monte-Carlo CFR (MCCFR) literature and works for any number of players and any payoff structure.

The reference games (Kuhn Poker, Rock-Paper-Scissors, Matching Pennies, Goofspiel, Liar's Dice, Leduc Hold'em, N-player Kuhn, and so on) live in a separate crate. They are worked examples of the Game trait, kept out of this one so regret stays general.

The wiki is the long-form documentation: Getting started, Implementing a game, Training, and the rest.

---

Quick start

Add the crate (and, for the example below, the reference games):

[dependencies]
regret = "2.2.1"
regret-games = { git = "https://github.com/sqlongithub/regret" }

Train against the bundled Kuhn Poker, check the result, and save it:

use regret::prelude::*;
use regret_games::kuhn::KuhnAction;
use regret_games::KuhnPoker;

let game = KuhnPoker::new();

// One call runs the recommended defaults (external-sampling MCCFR + DCFR+).
let profile = Profile::train(game.clone(), 20_000);

// For a 2-player zero-sum game, exploitability is a hard Nash proof: it tends
// to 0 as the profile approaches equilibrium. Pass the analytic Nash value
// (Kuhn: [-1/18, 1/18]).
let expl = exploitability_2p_zerosum(&game, &profile, [-1.0 / 18.0, 1.0 / 18.0]).unwrap();
assert!(expl < 0.01);

// Read the strategy at a decision node (deal the Jack to player 0, Queen to 1).
let mut node = game.clone();
node.step(&KuhnAction::Deal(0, 1)).unwrap();
println!("{}", profile.pretty(&node, 0)); // e.g. "C: 0.667, B: 0.333"

// Versioned binary checkpoint.
profile.save("kuhn.cfr").unwrap();
let loaded = Profile::<KuhnPoker>::load("kuhn.cfr").unwrap();

For a specific algorithm, regret variant, seed, or pruning, use the Trainer builder instead of Profile::train; train returns a Result so it can report a malformed game:

use regret::prelude::*;
use regret_games::KuhnPoker;

let mut trainer = Trainer::new(KuhnPoker::new())
    .algorithm(Algorithm::ExternalSampling) // the workhorse for large games
    .regret(RegretVariant::default())       // DCFRPlus (3/2, 4)
    .seed(0xABCD);

trainer.train(20_000).unwrap();
let profile = trainer.profile();

To write your own game, implement Game for your type. See the Implementing a game guide for the trait, the correctness contract, and chance semantics, and examples/ for runnable demos (cargo run --example debug).

---

Algorithms

An algorithm is composed from two separable pieces:

• a sampling scheme (Algorithm), how each iteration's trajectory is sampled, and
• a regret / averaging schedule (RegretVariant), how regret and the average strategy are accumulated.

Sampling schemes (MCCFR)

Algorithm	Reference	Notes
ExternalSampling	Lanctot et al. 2009, Monte Carlo Sampling for Regret Minimization in Extensive Games	Samples opponents + chance, traverses every action of the investigating player. The default for large games.
ChanceSampling	Gibson et al. 2012, Generalized Sampling and Variance in CFR	Samples chance only; full traversal of all players.
OutcomeSampling	Lanctot et al. 2009	Samples a single full trajectory with importance weighting. Memory-light.
FullTree	Zinkevich et al. 2007	Exact, full-tree CFR every iteration. Reference baseline for small games.

Regret / averaging variants

Variant	Reference	Default params
Vanilla	Zinkevich et al. 2007, Regret Minimization in Games with Incomplete Information	n/a
CFRPlus	Tammelin 2014, Solving Large Imperfect-Information Games Using CFR+	zero-floor regrets, linear avg weight
LinearCFR	Brown & Sandholm 2019, Solving Imperfect-Information Games via Discounted Regret Minimization	weight t
DCFR	Brown & Sandholm 2019	(α, β, γ) = (3/2, 0, 2)
DCFRPlus (CFR-D+, default)	Xu et al. 2022 (AAAI AutoCFR)	(α, γ) = (3/2, 4); single discount exponent, CFR+ floor (no β)
PDCFRPlus (predictive)	Xu et al. 2024, IJCAI (arXiv:2404.13891)	(α, γ) = (2.3, 5)

Pruning and variance reduction come from Pruning: Safe (regret-based, Brown & Sandholm 2015/2019) and Probabilistic (Pluribus-style, with a warm-up).

Multi-chance sampling (re-roll chance K times and average) is a first-class option via Trainer::chance_samples(K).

Action abstraction

Abstraction is opt-in. The core solver never needs it, and the happy path is just Trainer::new(game).train(n) as in Quick start. Many real games have far more actions than you can solve exactly, so an abstraction collapses strategically-similar actions into one, shrinking the action space (and the strategy table) at some cost to solution quality. To use one, implement the Abstraction trait, which returns the reduced legal actions for a state, and wrap a [Game] in Abstracted<G, A>. Only legal_actions changes; every other method is delegated unchanged, so the solver needs no knowledge of the abstraction.

use regret::prelude::*;
use regret_games::KuhnPoker;

// `Identity` keeps every action, so `Abstracted<G, Identity>` behaves exactly
// like the wrapped game; this is the case the convergence tests pin down. A
// real abstraction returns a strict subset of `legal_actions` instead.
let game = Abstracted::new(KuhnPoker::new(), Identity);
let profile = Trainer::new(game).train(8_000).unwrap().profile();

External sampling on deep games. ExternalSampling is the workhorse for large games, but its variance grows with tree depth and the number of sequential chance nodes, so it converges more slowly on deep games such as Goofspiel with many rounds. Reach for FullTree (exact) or ChanceSampling there, or raise chance_samples. It still converges on 2-player zero-sum games; it just needs more iterations on deep trees.

---

What CFR guarantees (and what it doesn't)

• 2-player zero-sum: the average strategy is guaranteed to converge to a Nash equilibrium, and analytics::exploitability_2p_zerosum is a hard proof that goes to 0.
• N > 2 or non-zero-sum: self-play still runs, and best_response / exploitability give a quality signal, not a Nash proof. Don't read a low exploitability number here as convergence. This is why the API hands back per-player best responses (analytics::best_responses) instead of a single exploitability figure the theory doesn't support.

---

Testing & analytics

Run cargo test-fast for a much faster test pass on multi-core machines: it serializes the libtest harness (avoiding nested parallelism with the library's own rayon pool) and runs in release. Plain cargo test is unchanged; cargo test -- --ignored runs the slow convergence suite.

tests/convergence.rs trains the library against analytic equilibria and the full reference-game test bed: Matching Pennies, Rock-Paper-Scissors, Kuhn Poker (all four sampling schemes), N-player Kuhn (KuhnN, including the 3-player case), Goofspiel (sequential chance), Liar's Dice (an N-player constant-sum game), a constant-sum 2-player game (payoff-sum invariance), and N-player zero-sum / general-sum toys. The 2-player zero-sum games assert exploitability → 0 to a tight tolerance; N-player and general-sum games assert that per-player best responses are finite, stable, and within the game's payoff range. The suite also checks the action-abstraction wrapper (Abstracted<G, Identity>).

Built-in analytics (regret::analytics): exact best response, per-player best responses, and exploitability. exploitability_2p_zerosum is a hard Nash proof for 2-player zero-sum games only; the exploitability_zerosum helper for N-player zero-sum games (and per-player best_responses generally) is a quality signal, not a Nash proof. For games too large to afford the exact full-tree traversal, regret::sampled provides a sampled best response / exploitability estimator that reports a confidence interval instead of an exact figure (see its module docs on the statistical trade-off).

---

Parallelism

With the default parallel feature, each training call launches one independent serial run per rayon worker. Each worker runs the full iteration budget on a distinct seed, and the resulting average-strategy accumulators are summed and normalized. That gives you a valid profile, reduces the variance of independent runs, and takes roughly one worker's wall-clock time. The reason for the full budget per worker rather than a split is that the average-strategy weight grows with t under discounting, so splitting would only reflect iters/workers of convergence.

Averaging caveat (N > 2 / non-zero-sum). Averaging independent runs is exact for 2-player zero-sum games: the equilibrium set is convex, so the average of equilibria is itself an equilibrium. For N > 2 or general-sum games it is only a variance-reduction heuristic, not a theoretically justified combination, and must not be read as a Nash proof.

The rayon sharding lives only inside the tabular Trainer (src/trainer/): each worker runs a full serial iteration on its own seed and the average-strategy accumulators are summed. Two parts of the library are single-threaded and do not use rayon:

• the DeepTrainer (neural-net tabular approximation, src/deep/), and
• regret::subgame re-solving (Blueprint training + solve_subgame*).

If you need parallelism in those paths today, run several independent processes and ensemble/average their output profiles (valid for 2p zero-sum; a variance-reduction heuristic otherwise, per the caveat above).

---

Performance & benchmarks

benches/suite.rs is a dependency-free benchmark (harness = false, so it runs on stable Rust) that reports, per game/algorithm: wall-clock time and iterations/sec, plus iterations-to-target-exploitability (how many iterations until exploitability drops below 0.05). Run it with:

cargo bench --all-features

Measured on a release build with thin-LTO — AMD Ryzen 5 5600, 32 GB DDR4-3200, Windows 11 (your machine will differ; the CI bench job prints live numbers on every push to main):

Game / algorithm	it/s	reaches exploit < 0.05 in
Kuhn / ExternalSampling	~33k	~5k iterations
Kuhn / FullTree	~18k	~500 iterations
Rock-Paper-Scissors / External	~118k	~17k iterations
Goofspiel(2) / ExternalSampling	~5.6k	~8k iterations
Goofspiel(3) / FullTree	~630	(0.07 at 3k, deeper tree, raise budget)
Liar's Dice 2p1d / External	~2.2k	~1.3k iterations

Peak working set for the full suite above: ~4.4 MB (release build).

The pattern to take away: external sampling is fast per iteration but needs more iterations on flat or deep games (RPS, Goofspiel, Liar's Dice); FullTree is exact and converges in far fewer iterations, but each iteration is expensive on larger trees.

---

Cross-library benchmarks

benchmarks/ benchmarks regret against other CFR libraries on Kuhn Poker through three purely quantitative lenses:

1. Raw throughput — iterations/sec (single-threaded, fixed 20k-iteration budget).
2. Convergence at a fixed iteration count — exploitability (NashConv/2) after exactly 20,000 iterations.
3. Convergence at a fixed training time — exploitability after 30 s of wall-clock training.

All harnesses run sequentially (no CPU contention) under one shared contract; the numbers below are produced and saved (padded, aligned) by python benchmarks/run_benchmarks.py, which writes benchmarks/results/latest.txt (+ latest.csv). The harnesses, the native OpenSpiel C++ build, and full caveats are in benchmarks/README.md.

Measured on a release build, AMD Ryzen 5 5600, 32 GB DDR4-3200, Windows 11 (single-threaded; your machine will differ):

Library	Backend	it/s (20k)	exploit @ 20k iters	iters @ 30s	it/s @ 30s	exploit @ 30s train
regret	ExternalSampling (MCCFR, DCFR+)	62,161	5.14e-02	2,131,000	71,020	5.87e-02
regret	FullTree (exact CFR+)	40,561	1.08e-03	1,344,000	44,797	1.32e-04
OpenSpiel	CFR+ (Python)	928	6.68e-06	30,049	1,002	8.64e-06
OpenSpiel	CFR+ (pyspiel C++)	16,697	6.68e-06	551,269	18,375	5.77e-07
cfrainbow	VanillaCFR	3,701	1.13e-04	106,781	3,559	3.07e-05
cfrainbow	CFRPlus	3,613	9.63e-06	104,783	3,493	3.25e-06
cfrainbow	DiscountedCFR	2,882	1.57e-05	96,958	3,232	4.70e-06
openCFR	CFRPlus	2,398	6.30e-05	70,858	2,366	2.40e-05
openCFR	VanillaCFR	2,591	1.63e-03	77,295	2,581	7.72e-04

Reading it. regret and OpenSpiel's C++ CFR+ are the throughput leaders (~45k–86k it/s in the fixed-time window). OpenSpiel's CFR+ (both backends) reaches the tightest exploitability floor — ~1e-6 within 20k iterations and 30 s alike, because Kuhn is tiny. regret's exact-CFR+ (FullTree) is ~2.5× faster per iteration than OpenSpiel's C++ CFR+ but converges more gradually on this 12-information-set game. The pure-Python libraries (cfrainbow, openCFR) land at ~3k–4k it/s, with their CFR+ variants reaching ~1e-5–1e-6. regret's ExternalSampling is the fastest per second but, run single-threaded, is high-variance (its exploitability bounces; the default parallel build averages independent worker runs and converges much faster — see the in-library table above).

Caveats. Each library defines an "iteration" in its own terms (regret's ExternalSampling re-rolls chance 4× per iteration; openCFR's CFR+ counts a single-player alternating traversal per iteration), so cross-library it/s is approximate. Exploitability is reported consistently as NashConv/2 for all four libraries, and benchmarks/verify_games.py confirms every library plays the same standard Kuhn (12 info sets, uniform-random exploitability 11/24 ≈ 0.458333), so the convergence columns are directly comparable. Kuhn implementations differ slightly between libraries (e.g. openCFR builds its own tree) but were verified to agree on the standard rules. All numbers are single-threaded and reproducible via python benchmarks/run_benchmarks.py.

---

Subgame solving and blueprint abstraction

[regret::subgame] provides safe subgame solving (Brown & Sandholm, IJCAI 2017): take a game, pick a node h, and re-solve just the subtree rooted at h against a fixed blueprint [Profile], composing the refined strategy back over the blueprint so the result stays a Nash equilibrium of the full game. It also ships [Blueprint], which trains a (optionally abstraction-reduced) blueprint and lifts it back to a real-action profile. Both are exercised by the convergence suite (tests/convergence.rs, the subgame_* tests).

// In Cargo.toml: regret-games = "2"
use regret::prelude::*;
use regret::subgame::{Blueprint, solve_subgame};
use regret_games::KuhnPoker;

let game = KuhnPoker::new();
// Use a CFR-family variant (not the DCFR+ default) for the blueprint: strict
// safe-subgame idempotency needs it, since DCFR+'s `t^γ` averaging can pull a
// later re-solve to a different (still-Nash) equilibrium.
let variant = RegretVariant::dcfr(1.5, 0.0, 2.0);
let bp = Blueprint::train(game.clone(), 30_000, variant, 1, 0);
let path = &[regret_games::kuhn::KuhnAction::Deal(0, 1)];
// Safe solving returns `Result` (no panic on a bad path) and takes an
// explicit `Algorithm`, so `chance_samples` is meaningful for sampled schemes.
let solved = solve_subgame(
    &game, path, bp.profile(), 20_000,
    variant, Algorithm::FullTree, 1, 7,
).expect("valid subgame path");
let composed = bp.compose(&solved); // refined strategy over the blueprint

Scope and limitations

The solver covers the full-game CFR / MCCFR setting end to end: the four sampling schemes, every regret/averaging schedule above, action abstraction via [Abstraction], safe subgame solving (static, depth-limited, and nested) with blueprint abstraction, parallel ensemble training, variance-reduction sampling (VarianceReduction::ControlVariate), and both exact and sampled analytics (regret::sampled, including non-enumerable chance and the opt-in f32-tables and Game::caches_transpositions paths).

Two known limitations:

• Exact analytics do not scale. analytics::* best response and exploitability are full-tree traversals, cheap only for small and medium games. On the large games external/outcome sampling exists for, use the sampled estimator in regret::sampled, which reports a confidence interval instead of an exact figure (see Analytics for its statistical limits). Calibrating posterior_samples on very deep games still needs manual tuning.
• Accumulator tables use a mutex per shard. The current sharded design has low contention in practice; a lock-free table would only matter at very high core counts.