Crate cfr 

Counterfactual Regret (CFR) is a library for finding an approximate nash equilibrium in two-player zero-sum games of incomplete information with perfect recall, such as poker etc., using discounted¹ monte carlo² counterfactual regret minimization³.

Usage

To use the command line tool, see documentation on github, or use cfr --help.

To use this as a rust library, implement the Game trait for your extensive form game – a state machine that classifies each state as terminal, chance, or player and yields its child states by index. See the trait for the contracts of implementation, and the kuhn_poker example for a full game. There are then two ways to solve: for games small enough to fit in memory, build a GameTree with GameTree::from_game and call GameTree::solve (exact, with regret bounds); for games whose tree is too large to fit in memory, drive LazySolver directly, which keeps only a per-infoset regret table. You can get equilibrium utilities and regret from Strategies::get_info.

Examples

Once Game is implemented for your game, you solve for equilibria like:

impl Game for MyGame {
    // ...
}
// small game: materialize the tree and solve it exactly
let game = GameTree::from_game(MyGame::Start).unwrap();
let (strats, reg_bounds) = game.solve(
    SolveMethod::External,
    100,  // number of iterations
    0.0,  // early termination regret
    1,    // number of threads
    SolveParams::default(), // advanced options
).unwrap();
// get named versions, i.e. exportable version
let named = strats.as_named();
// compute regret and other values
let strat_info = strats.get_info();
let regret = strat_info.regret();

---

1. Brown, Noam, and Tuomas Sandholm. “Solving imperfect-information games via discounted regret minimization.” Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 33. No. 01. (2019) ↩

2. Lanctot, Marc, et al. “Monte Carlo sampling for regret minimization in extensive games.” Advances in neural information processing systems 22 (2009). ↩

3. Zinkevich, Martin, et al. “Regret minimization in games with incomplete information.” Advances in neural information processing systems 20 (2007). ↩

Structs

Digest

A fixed-size rolling hash of an append-only history, usable as a cheap, allocation-free Game::Infoset key.

GameTree

A compact game representation

History

A persistent, append-only history usable as a Game::Infoset key.

LazySolver

An external-sampling MCCFR solver over a Game, with DCFR discounting and regret-based pruning.

NamedStrategyActionIter

An iterator over named actions and assiciated probabilities

NamedStrategyIter

An iterator over named information sets of a strategy.

RegretBound

Regret bound produced by solving a game

RegretParams

Advanced parameters for regret calculation

SolveParams

Tuning knobs for a solve that aren’t part of the regret-matching math. Every field has a sensible default, so override one at a time with struct-update syntax: SolveParams { check_interval: 1000, ..Default::default() }.

Strategies

A compact strategy for both players

StrategiesInfo

Information about the regret and utility of a specific strategy profile

Enums

GameError

Errors that result from game definition errors

NodeType

Which kind of node a Game state is, with the data needed to enumerate its children.

PlayerNum

An enum indicating a player

SolveError

Errors that result from problems solving

SolveMethod

The method to use for finding approximate equilibria

StratError

Errors that result from incompatible strategy representation

Traits

Game

A two-player zero-sum game of imperfect information, expressed as a state machine.

Moves

A lazy, indexable sequence of the legal moves at a player node.

Outcomes

A lazy, indexable sequence of chance outcomes, each a (probability, next state) pair.