Implementing a game

Implementing a game (the Game trait)

A game is an imperfect-information extensive-form game with a fixed number of players, perfect recall (each player's information sets partition histories such that every history in a set has the same observations for that player), and terminal payoffs returned as a per-player vector.

The solver only knows how to walk the tree; it imposes no game-specific logic. Implement Game for your game type and the trainer does the rest.

pub trait Game: Clone + Debug + Send + Sync {
    type Action: Action;
    fn num_players(&self) -> usize;
    fn is_terminal(&self) -> bool;
    fn is_chance(&self) -> bool;
    fn player_to_act(&self) -> PlayerToAct;
    fn chance_outcomes(&self) -> Option<Vec<(Self::Action, f64)>> { None }
    fn sample_chance(&self, rng: &mut Rng) -> Result<(Self::Action, f64), GameError>;
    fn nash_value(&self) -> Option<[f64; 2]> { None }
    fn legal_actions(&self) -> Vec<Self::Action>;
    fn step(&mut self, action: &Self::Action) -> Result<(), GameError>;
    fn terminal_returns(&self) -> Vec<f64>;
    fn infoset_key(&self, player: usize) -> Vec<u8>;
    // plus buffer-reuse variants legal_actions_into / infoset_key_into
    // and provided methods validate / state_hash / caches_transpositions
}

Action must be Clone + Eq + Hash + Debug + Display + Send + Sync. Strategies are serialized by action index (aligned to legal_actions order), so no Serialize bound is imposed on the caller's action type.

Implementors must be cheaply cloneable: the trainer clones state to explore alternative actions rather than mutating and undoing. If cloning is expensive, use a small cursor representation (indices into a precomputed tree).

A conforming implementation

[regret-games](Reference-games) ships worked implementations. KuhnPoker in regret-games/src/kuhn.rs is the smallest complete example: two players, a single chance deal from a 3-card deck, a one-round bet/call/fold sequence, and a showdown. Reading it covers most of what an implementation needs to get right. The parts worth noting:

• KuhnPoker is Clone with a tiny footprint (two dealt cards, a betting history, and pot contributions), so cloning per explored action is free.
• infoset_key returns the player's own card plus the public betting history. Two histories that differ only in the opponent's card return the same key for that player, which is exactly the perfect-recall condition.
• legal_actions returns a fixed, deterministic order for each node type (Check, Bet or Call, Fold). That order indexes the regret and average-strategy vectors, so it must be stable across every history in an information set.
• chance_outcomes enumerates all six ordered card pairs with probability 1/6, because the chance space is small and materializable.
• nash_value returns Some([-1.0/18.0, 1.0/18.0]), the known analytic equilibrium value.

The correctness contract

Trainer::new runs the contract check unconditionally in every build profile, not just under debug_assertions. A subtly-wrong game therefore surfaces the error immediately, before any training runs. The contract is:

• is_terminal and is_chance are never both true.
• At a terminal node, terminal_returns returns one finite payoff per player and step returns an error.
• At a chance node, either chance_outcomes returns Some with non-empty, non-negative, sum-to-1 probabilities and legal_actions is empty, or it returns None (non-enumerable chance) and the node is driven by sample_chance.
• At a decision node, legal_actions is non-empty, contains no duplicates, and chance_outcomes is None.
• infoset_key returns identical keys for histories the player cannot distinguish (perfect recall) and distinct keys otherwise.
• The order of legal_actions is the canonical action order used to index the regret/average vectors; it must be deterministic and identical for every history in the same information set.

Chance: enumerable vs non-enumerable

chance_outcomes returns Some for a small, materializable chance space (a die roll, a single card deal). The exact analytics (best response, value walk, subgame continuation values) only enumerate chance when this is Some.

For a combinatorial or too-large-to-materialize chance space (many dice, a full card deal, large player counts), return None and override sample_chance to draw one outcome directly. The default sample_chance enumerates chance_outcomes and samples from it, so existing games need no extra code. Override only when enumeration is the bottleneck. The returned probability must be finite, non-negative, and consistent in expectation with the distribution chance_outcomes advertises.

Transposition caching

state_hash (default: an observable-position hash) is not a valid transposition key in general. Two states with the same observable position can expose different best-response values whenever some player cannot observe the true history. The library therefore only memoizes on it when a game opts in via caches_transpositions() == true, which defaults to false.

Override state_hash to a true transposition key (identical exactly when the cacheable value is identical) and return true from caches_transpositions only when you have separately proven it is safe. Games with genuine repeated subtrees (symmetric positions) then benefit without silently corrupting history-blind games.

nash_value

Override for games whose 2-player zero-sum equilibrium value is known in closed form: Kuhn poker [-1/18, 1/18], RPS / Matching Pennies [0, 0]. This lets the exploitability dispatcher pick the tightest metric. It is hard-wired to two players and returns [f64; 2]. For any other shape, return None. Using it for N-player or general-sum values is undefined.

Validation

validate (also validate::validate_game) walks 256 random trajectories under a fixed seed. It checks node-type invariants, chance-probability validity, step acceptance, and that every history sharing an information-set key reports the same ordered legal_actions (the check most likely to catch a real perfect-recall regression). It is a random probe, not an exhaustive traversal. A violation confined to a deep, narrow, or low-probability subtree may be missed. Call validate_game_with with a larger budget for games with subtle corner cases.

validate does not prove perfect recall in the strong sense: that two indistinguishable histories truly share a key and two distinguishable ones truly differ. That depends on game semantics no checker can see. The legal_actions stability check catches the large majority of perfect-recall regressions in practice.

Common mistakes

• Breaking perfect recall. infoset_key must return the same key for every history a player cannot distinguish and a different key otherwise. A wrong key merges or splits information sets and produces a silently wrong strategy. validate only checks that histories with the same key agree on legal_actions; it cannot verify the key itself is semantically correct.
• Unstable action ordering. The order of legal_actions indexes the regret and average vectors. If two histories in the same information set return legal_actions in different orders, the strategy is indexed inconsistently. Keep the order deterministic and identical within each information set.
• Choosing the wrong chance representation. Use enumerable chance_outcomes only when the chance space is small and materializable. For large or combinatorial chance, return None and implement sample_chance; otherwise enumeration becomes the training bottleneck.
• Enabling transposition caching without a safe key. Overriding state_hash without proving it is a true transposition key silently corrupts best-response values in any game where a player is history-blind. Leave caches_transpositions at its default false unless you have verified safety.
• Returning nash_value for the wrong game shape. It is hard-wired to two players and returns [f64; 2]. Return None for N-player or general-sum games; supplying a value for them is undefined and misleads the exploitability dispatcher.