How the solver actually works

Minimax and alpha-beta assume you can look at a position and evaluate it. Poker denies you that. The value of your situation depends on a card you cannot see, so there is no position to evaluate — only a probability distribution over positions.

Two consequences follow, and both break classical search:

• Decisions cannot be made locally. Your play with the Queen depends on how often you bluff the Jack, because that is what makes your bets credible. Subgames do not decompose the way they do in chess.
• The optimal strategy is randomised. Any deterministic strategy in Kuhn poker is heavily exploitable — a deterministic bet is a readable bet. The answer is a set of frequencies, not a set of moves.

Kuhn poker is small enough to solve as a linear program. Real poker is not: the LP scales with the number of game states, and heads-up limit hold'em has about 10¹⁴. CFR is the method that scales, and it needs nothing but the ability to walk the tree.

An information set I is a set of game states the acting player cannot tell apart. In Kuhn poker it is exactly “my card + the betting so far”. There are 12.

The key bookkeeping is the reach probability — how likely a state was to occur — split into three independent factors:

Splitting them is the whole trick. Everything below hinges on being able to divide out a player's own contribution to reaching a decision.

The counterfactual value of an information set weights each state by how likely the opponent and chance were to produce it, deliberately excluding the player's own probability of getting there:

Why exclude your own reach? Because otherwise a rarely-visited decision would look unimportant simply because your current strategy avoids it — and you would never discover that it is avoided precisely because you play it badly. Dividing out your own probability makes each information set improvable on its own terms.

Counterfactual regret is then the obvious question: how much better would always taking action a have been?

Play each action in proportion to how much positive regret it has accumulated. Actions you wish you had taken more get taken more.

That is the entire learning rule. No gradients, no neural network, no opponent model. Just: count what you wish you had done, and do more of it.

Two results combine, and neither is obvious on its own:

• Regret matching is a no-regret algorithm. Average regret at each information set decays like O(1/√T).
• Folk theorem for zero-sum games. If both players' average overall regret is below ε, their average strategies form a 2ε-Nash equilibrium.

So minimising a purely local, greedy, per-decision quantity yields a global equilibrium of the entire game. The formal guarantee:

One recursive tree walk carries both reach probabilities down and returns values back up. Chance is enumerated exactly — all six deals every iteration — rather than sampled, which removes Monte-Carlo variance entirely.

def _walk(self, deal, history, reach0, reach1, chance,
          updating_player, regret_weight, average_weight):
    # returns the expected value to Player 0
    if is_terminal(history):
        return terminal_utility(history, deal)

    player   = current_player(history)
    node     = self.nodes[info_set_key(deal[player], history)]
    strategy = node.strategy          # FROZEN for this iteration

    # average strategy accumulates weighted by OWN reach
    own = reach0 if player == 0 else reach1
    node.strategy_sum += own * chance * average_weight * strategy

    # recurse, threading each player's reach separately
    action_values = [self._walk(deal, history + a, ...) for a in ACTIONS]
    node_value = dot(strategy, action_values)

    # regret uses the OPPONENT's reach - the counterfactual weight
    sign = 1.0 if player == 0 else -1.0
    counterfactual = (reach1 if player == 0 else reach0) * chance
    for i in range(NUM_ACTIONS):
        regret = sign * (action_values[i] - node_value)
        node.regret_delta[i] += counterfactual * regret * regret_weight

    return node_value

Both of these were real bugs in this solver's first version. Individually each looks harmless and still converges to the correct strategy — they simply drag CFR+ back to vanilla's 1/√T rate. Fixing them moved exploitability at 50,000 iterations from 1.0×10⁻³ to 5.8×10⁻⁶. Both are now pinned by regression tests.

“The strategy stopped changing” proves nothing — a solver can converge confidently to a non-equilibrium. The real question is what a perfect adversary could win:

The subtle part of computing a best response is that the maximisation must happen at the information set, not at individual game states. A best responder still cannot see the private card, so it must commit to one action across every deal consistent with what it observes. Taking a max at each state separately silently grants clairvoyance and reports exploitability that is too high.

The most misunderstood property of a Nash strategy, and the most interesting measured result in this project: an equilibrium does not try to win.

It guarantees you cannot lose more than the game value against any opponent. But against a specific flawed opponent it frequently earns exactly zero, because equilibrium play makes the opponent indifferent — every option they have is worth the same, so their bad habits cost them nothing against it.

That trade — safety versus maximum value — is the real subject of the tournament table on the Solver page, and it is why both agents are reported side by side rather than picking one number to headline.