Counterfactual regret minimization solver for two-player zero-sum incomplete-information games in rust. This is a rust library and binary for computing approximate nash-equilibria of two-player zero-sum incomplete-information games.
To use the library part of this crate, add the following to your Cargo.toml.
toml
[dependencies]
cfr = { version = "0.1.0", default-features = false }
Then implement
[IntoGameNode]((https://docs.rs/cfr/latest/cfr/trait.IntoGameNode.html), for
a type that represents a node in your game tree (or alternatively can generate
new nodes).
Finally execute:
rust
use cfr::{Game, IntoGameNode};
struct MyData { ... }
impl IntoGameNode for MyData { ... }
let game = Game::from_root(...)?;
let strategies = game.solve_external();
let info = strategies.get_info();
let regret = info.regret();
let [player_one, player_two] = strategies.as_named();
This package can also be used as a binary with a few different input formats. install it with
bash
$ cargo install cfr
Solving a game will produce the expected utility to player one, as well as the regrets and the strategy found in json format.
bash
$ cfr -i game_file
{
"expected_one_utility": 0.05555555727916178,
"player_one_regret": 1.186075528125663e-06,
"player_two_regret": 8.061797025377127e-05,
"regret": 8.061797025377127e-05,
"player_one_strategy": { ... },
"player_two_regret": { ... }
}
The command line tool can interpret a custom json dsl, and
gambit .efg files.
The DSL is defined by:
bison
node ::= terminal || chance || player
terminal ::= { "terminal": <number> }
chance ::= {
"chance": {
"infoset"?: <string>,
"outcomes": {
"<named outcome>": { "prob": <number>, "state": node },
...
}
}
}
player ::= {
"player": {
"player_one": <bool>,
"infoset": <string>,
"actions": { "<named action>": node, ... }
}
}
A minimal example highlighting all types of nodes, but of an uninteresting game is:
json
{
"chance": {
"outcomes": {
"single": {
"prob": 1.0,
"state": {
"player": {
"player_one": true,
"infoset": "none",
"actions": {
"only": {
"terminal": 0.0
}
}
}
}
}
}
}
}
In this game there's a 100% chance of the "single" outcome, followed by a
move by player one where they have information "none" and only have one
action: "only". After selecting that action, they get payoff 0.
The gambit format follows the standard gambit extensive form game format, with some mild restrictions.
This section has more details on errors the command line might return.
This error occurs when the json doesn't match the expected format for reading. See JSON Format for details on the specification, and make sure that the json you're providing matches that specification.
This error occurs when the gambit file can't be parsed. There should be more info about exactly where the error occured. See gambit format for more details on the format.
The game file couldn't be parsed by any known game format. In order to get more
detailed errors regarding the parsing failure, try rerunning again with
--input-format <format> to get more precise errors
Gambit .efg files don't require naming infosets, but cfr requires string
names for every infoset. It will default to useing the string version of the
infoset number, but this will fail if that infoset name is already taken. For
example:
...
p 1 1 "2" { ... } 0
p 1 2 { ... } 0
...
will throw this error as long as a name for infoset 2 isn't defined elsewhere.
Counterfactual regret minimization only works on constant sum games. Since
gambit files define payoffs independently, this verifies that the range of the
sum of every profile is less than 0.1% of the range of the of the payoffs for a
single player. If you encounter this error, cfr will not for this game.
This error occurs if there were problems with the game specification that made
creating a compact game impossible. See the documentation of
GameError for more
details.
The error occured if there were problems solving it. This should only happen if
you requested too many threads, or the threads couldn't be spawned. See the
documentation of
SolveError for more
details.
Hash, Ord, or Clone and use the most performant
option given the trait bounds. This doesn't seem particularly useful and
would be a lot of work, so it's omitted for now.