Subgames

Subgames and blueprints

Safe subgame solving takes a game, picks a node h (a sequence of actions from the root), and re-solves just the subtree rooted at h against a blueprint: a fixed "rest of the game" strategy. Composing the solved subgame over the blueprint yields a full-game strategy that, for 2-player zero-sum games, is a Nash equilibrium whenever the blueprint is.

Use Subgame::at

Subgame::at(game, blueprint, path) builds the subgame for the node reached by path (a sequence of actions from the game root). It computes the opponent o and V_o(h) from the blueprint automatically, so you never have to supply them. It returns Result and reports an error (it does not panic) when path is not a valid action sequence or does not end at a decision node.

Subgame::new(inner, blueprint, opponent, v_o) and DepthLimitedSubgame::new exist but are not the first thing to reach for. They take an inner game that the caller has already stepped to the subgame root, plus a hand-supplied opponent and v_o, with no path resolution. A wrong v_o or opponent silently produces a subgame that solves to the wrong strategy. Subgame::at removes that footgun; reach for new only when you already hold the stepped state and the correct root value. DepthLimitedSubgame mirrors both: prefer DepthLimitedSubgame::at, use ::new only with a pre-stepped state.

Safe subgame solving (2-player zero-sum)

The textbook transformation (Brown & Sandholm, Safe and Nested Subgame Solving, IJCAI 2017) keeps the composed strategy a Nash equilibrium even though the subgame is solved in isolation. The subgame is solved for both players, but the opponent's terminal payoff at every leaf z is replaced by

u'_o(z) = u_o(z) + (π̂_o(z) − 1) · V_o(h)

where o is the player not to act at the subgame root, π̂_o(z) is o's blueprint reach from h to z, and V_o(h) is o's expected payoff of the subgame root under the blueprint. The V_o(h) term injects the opponent's outside reach so the isolated solve agrees with the full-game best response.

Subgame is a thin Game wrapper that starts already stepped to h, tracks π̂_o(z) incrementally, and applies the shift at terminals. It forwards infoset_key verbatim, so the strategies it learns live under the real game's information-set keys and compose directly via compose_profiles.

Blueprint variant and idempotency

This is the footgun the codebase warns about. Strict safe-subgame idempotency (re-solving a near-Nash blueprint and composing it back keeps the strategy near the blueprint) is guaranteed only for CFR-family blueprints: RegretVariant::DCFR / RegretVariant::CFRPlus. The canonical choice is RegretVariant::dcfr(1.5, 0.0, 2.0).

RegretVariant::default() is DCFRPlus { alpha: 1.5, gamma: 4.0 }. Its heavy t^γ average-strategy weighting can leave the fresh re-solve in a different (still-Nash) equilibrium, so the composed strategy drifts away from the blueprint even though exploitability stays low. A DCFRPlus blueprint is accepted (never hard-rejected). It yields a valid, if not strictly idempotent, result. Use the CFR-family variant if you rely on idempotency.

Enumerable-chance precondition

Every full-tree walk in this module (continuation_value, subgame root resolution, Blueprint::train_abstracted lifting) requires enumerable chance: every chance node must return Some from chance_outcomes. Games that draw chance via sample_chance are not supported on this path; attempting it returns a typed RegretError. Inside a Game impl the contract is a clear panic, never a wrong answer.

Depth-limited subgames

DepthLimitedSubgame solves only down to max_depth plies, replacing deeper nodes with their continuation value under the blueprint (the Libratus / DeepStack real-time re-solving trick). With max_depth ≥ the true game depth it is exactly Subgame. Smaller max_depth trades solution quality for a large per-iteration speed-up. Truncation leaves are memoized per distinct leaf, so each leaf's continuation value is computed once.

The truncation has a limitation. Each truncation leaf holds a single expected continuation value; it is not a table indexed by the full set of reachable states. There is no "multi-valued states" extension.

Compositional solving

TerminalFn is a caller-supplied closure consulted at every terminal history of a subgame solve; returning Some(payoffs) overrides the literal terminal_returns (the safe opponent-payoff shift is still applied on top). This wires an already-solved successor subgame's values into a parent solve, building a finite DAG of subgames ordered by a decreasing potential. No bespoke back-induction driver is needed. Cross-level resolution is the caller's responsibility: the closure may read a value table computed at any layer.

Entry points: solve_subgame (and solve_subgame_plain), solve_subgame_depth_limited, solve_subgame_with_terminal_fn, solve_subgame_depth_limited_with_terminal_fn, and the Blueprint methods.

compose_profiles(base, override_sub) overlays the solved subtree's information sets onto the blueprint; everything else of the base is untouched.

Blueprint

Blueprint<G> wraps a profile used as the fixed outside strategy. It stores a bare Profile<G>, not an Arc.

Blueprint::train(game, iters, variant, chance_samples, seed): trains a concrete blueprint with a given variant. Pick a CFR-family variant when you need idempotent re-solving.

Blueprint::from_profile(profile) / into_profile(): wrap an existing profile, or recover the bare Profile<G> the blueprint holds.

Blueprint::profile(): returns the bare Profile<G> the blueprint wraps.

Blueprint::solve_subgame(...) / compose(sub): solve over the blueprint and overlay the solved subtree back onto it.

Blueprint::train_abstracted(abstraction, ...): trains on an Abstracted game and lifts the result back to a real-action Profile. Use this when the full game is too large to train directly. See Abstraction.

check_invariants(solved, game, invariant) validates a solved subgame profile: normalized finite distributions, per-infoset arity matches the real game's legal_actions count, then a caller invariant closure.