Expand description
§Little Sorry
Regret minimization algorithms for finding Nash equilibrium strategies in imperfect-information games.
§Available Algorithms
All algorithms implement the RegretMinimizer trait:
| Type | Algorithm | Key Property |
|---|---|---|
CfrPlusRegretMatcher | CFR+ | Regret clipping at zero |
DiscountedRegretMatcher | DCFR | Configurable time-based discounting |
DcfrPlusRegretMatcher | DCFR+ | DCFR discounting + CFR+ clipping |
LinearCfrRegretMatcher | Linear CFR | Linear time-weighted regrets |
PcfrPlusRegretMatcher | PCFR+ | Predictive future regret estimates |
PdcfrPlusRegretMatcher | PDCFR+ | DCFR+ discounting + predictive updates |
§Quick Start
use little_sorry::{CfrPlusRegretMatcher, RegretMinimizer};
let mut matcher = CfrPlusRegretMatcher::new(3);
for _ in 0..1000 {
matcher.update_regret(&[1.0, -0.5, 0.2]);
}
let strategy = matcher.best_weight();
assert!((strategy.iter().sum::<f32>() - 1.0).abs() < 1e-6);§Batched, storage-generic matchers
For large or concurrent solves, BatchedMatcher owns many information sets
(“rows”) that advance on one shared iteration clock, so a rule’s
time-dependent factors are computed once per batch rather than once per row.
It is generic over both the update rule (one of Dcfr, DcfrPlus,
LinearCfr, PcfrPlus, PdcfrPlus) and the cell backend (Local
for zero-overhead single-threaded use, Atomic for lock-free concurrent
updates through a shared reference). Swapping either is a one-type change.
The solved average strategy reads out the same way for every rule and can be
exported compactly with quantize_dist / dequantize_dist:
use little_sorry::{BatchedMatcher, Dcfr, DiscountParams, Local};
use little_sorry::{dequantize_dist, quantize_dist};
// One node owning 8 abstraction classes over 3 actions.
let node = BatchedMatcher::<Dcfr, Local>::new(8, 3, DiscountParams::RECOMMENDED);
let mut expected = [0.0; 8];
for _ in 0..1000 {
// The caller supplies values from whatever layout it holds.
node.update_batch(|action, _row| [1.0, -0.5, 0.2][action], &mut expected);
}
let mut probs = [0.0; 3];
node.average_into(0, &mut probs); // normalized average strategy, any rule
let codes = quantize_dist::<u16>(&probs); // compact on-disk form
let reloaded = dequantize_dist::<u16>(&codes); // decodes AND renormalizes
assert!((reloaded.iter().sum::<f32>() - 1.0).abs() < 1e-6);The memory layout is a third type parameter (F32Full by default). Swap it
to cut footprint without changing the API:
use little_sorry::{BatchedMatcher, Dcfr, DiscountParams, Local, HalfStrategy};
// f32 regret + u16 average strategy — ~25% smaller, same f32-facing API.
let node = BatchedMatcher::<Dcfr, Local, HalfStrategy>::new(8, 3, DiscountParams::RECOMMENDED);
node.seed(|action, _row| [10.0, 0.0, 0.0][action], 100); // warm-start row regret
let mut probs = [0.0; 3];
node.average_into(0, &mut probs);
assert!((probs.iter().sum::<f32>() - 1.0).abs() < 1e-6);Re-exports§
pub use cfr_plus::CfrPlusRegretMatcher;pub use dcfr::DiscountedRegretMatcher;pub use dcfr_plus::DcfrPlusRegretMatcher;pub use discount::DiscountParams;pub use linear_cfr::LinearCfrRegretMatcher;pub use pcfr_plus::PcfrPlusRegretMatcher;pub use pdcfr_plus::PdcfrPlusRegretMatcher;pub use regret_minimizer::RegretMinimizer;pub use batched_matcher::BatchedMatcher;pub use batched_matcher::Scratch;pub use lane::F32Full;pub use lane::F32Regret;pub use lane::F32SumStrategy;pub use lane::HalfBoth;pub use lane::HalfRegret;pub use lane::HalfStrategy;pub use lane::Int16Regret;pub use lane::Layout;pub use lane::RegretLane;pub use lane::StrategyLane;pub use lane::U16AvgStrategy;pub use quantize::FixedWidth;pub use quantize::dequantize_dist;pub use quantize::quantize_dist;pub use rules::Dcfr;pub use rules::DcfrPlus;pub use rules::LinearCfr;pub use rules::PcfrPlus;pub use rules::PdcfrPlus;pub use rules::PlusDiscount;pub use storage::Atomic;pub use storage::Local;pub use update_rule::UpdateRule;pub use cfr_plus::CfrPlusRegretMatcher as RegretMatcher;
Modules§
- batched_
matcher - A matcher owning many information sets over a pluggable cell backend.
- cfr_
plus - CFR+ regret minimization implementation.
- dcfr
- Discounted CFR (DCFR) implementation.
- dcfr_
plus - DCFR+ (Discounted CFR+) implementation.
- discount
- Discount parameter configurations for DCFR variants.
- lane
- Pluggable lane stores for regret and strategy accumulation.
- linear_
cfr - Linear CFR implementation.
- pcfr_
plus - PCFR+ (Predictive CFR+) implementation.
- pdcfr_
plus - PDCFR+ (Predictive Discounted CFR+) implementation.
- quantize
- Fixed-point export codec for normalized strategies.
- regret_
minimizer - Trait definition and shared helpers for regret minimization algorithms.
- rules
- The concrete regret-update rules.
- storage
- Pluggable accumulator storage.
- update_
rule - The algorithm abstraction shared by the batched matcher.