Kuhn Poker & CFR

1. Recap: From RPS to Poker

In Chapter 1, we built regret matching for Rock-Paper-Scissors — a normal-form game with one simultaneous decision. We showed that two regret-matching players converge to Nash Equilibrium, and we introduced exploitability as a convergence metric.

Poker is fundamentally different. It's an extensive-form game:

• Sequential: Players act in turns, not simultaneously
• Hidden information: Each player sees their own cards but not the opponent's
• Tree structure: The game unfolds through a tree of decision points

To handle this, we need a way to run regret matching at every decision point in the tree, coordinating updates across the entire game. That algorithm is Counterfactual Regret Minimization (CFR).

We'll develop it using Kuhn Poker — the smallest poker game that captures bluffing, value betting, and positional advantage.

2. Kuhn Poker: The Simplest Real Poker Game

Despite its simplicity, Kuhn Poker has several features that make it a perfect teaching tool:

• Small enough to solve analytically (we know the exact Nash Equilibrium)
• Large enough to exhibit bluffing, value betting, and position effects
• Has 12 information sets — small enough to inspect every one
• Introduced by Harold Kuhn in 1950, the same era as Nash's equilibrium theorem

3. The Game Tree

The game tree shows every possible sequence of actions. Each path from root to leaf is a history — a complete record of how the hand played out.

We'll use a compact notation: c = check/fold (pass), b = bet/call.

History	Meaning	Terminal?	Pot
cc	Both check → showdown	Yes	2 (1+1)
cb	P1 checks, P2 bets → P1 must act	No	—
cbc	P1 checks, P2 bets, P1 folds	Yes	P1 loses 1
cbb	P1 checks, P2 bets, P1 calls → showdown	Yes	4 (2+2)
bc	P1 bets, P2 folds	Yes	P2 loses 1
bb	P1 bets, P2 calls → showdown	Yes	4 (2+2)

Here's the full game tree visualized. Player 1 nodes are blue, Player 2 nodes are purple, and terminal nodes are green:

There are 5 terminal histories and 4 decision points. But with 3 possible card deals per player (and 2 possible opponent cards for each), the full tree has 6 × 5 = 30 terminal states. This is small enough to enumerate completely — no sampling or abstraction needed.

4. Information Sets

In Kuhn Poker, the information sets are:

Player 1's Information Sets (6 total)

Info Set	Situation	Actions	Possible Opponent Cards
J:	Holding Jack, opening action	Check / Bet	Q or K
Q:	Holding Queen, opening action	Check / Bet	J or K
K:	Holding King, opening action	Check / Bet	J or Q
J:cb	Holding Jack, checked, P2 bet	Fold / Call	Q or K
Q:cb	Holding Queen, checked, P2 bet	Fold / Call	J or K
K:cb	Holding King, checked, P2 bet	Fold / Call	J or Q

Player 2's Information Sets (6 total)

Info Set	Situation	Actions	Possible Opponent Cards
J:c	Holding Jack, P1 checked	Check / Bet	Q or K
Q:c	Holding Queen, P1 checked	Check / Bet	J or K
K:c	Holding King, P1 checked	Check / Bet	J or Q
J:b	Holding Jack, P1 bet	Fold / Call	Q or K
Q:b	Holding Queen, P1 bet	Fold / Call	J or K
K:b	Holding King, P1 bet	Fold / Call	J or Q

5. The CFR Algorithm

CFR was introduced by Zinkevich et al. (2007). The core idea is elegantly simple:

If you strip away the terminology, CFR is doing the same thing as Chapter 1 at every info set — accumulate regrets, derive strategy from positive regrets, report the average. The new ingredient is the counterfactual value and reach probabilities.

6. Counterfactual Values & Reach Probabilities

In a game tree, we can't simply compute "EV of action Rock against opponent's strategy" like we did in RPS. We need to account for the fact that reaching an information set depends on both players' strategies and the chance node (card deal).

Worked Example

Consider Player 1 at info set Q: (holding Queen, opening action). The opponent could have Jack or King, each equally likely. Suppose Player 2's current strategy at J:b is [Fold=1.0, Call=0.0] and at K:b is [Fold=0.0, Call=1.0].

If Player 1 bets:

• vs Jack: P2 folds → P1 wins 1 chip
• vs King: P2 calls → showdown, P1 loses 2 chips

Counterfactual value of betting = 1 · (+1) + 1 · (−2) = −1
(Both opponents have reach probability 1 since no player actions precede this node.)

If Player 1 checks, the game continues to Player 2's info set (J:c or K:c), and the value depends on Player 2's check/bet strategy there.

7. Implementation Walkthrough

The entire CFR algorithm for Kuhn Poker fits in a single recursive function. Let's walk through the key pieces.

Data Structures

We need just two dictionaries, mapping each info set to an array of size 2 (one per action):

# Per info set: cumulative regrets and strategy sums
cumulative_regret = {}   # info_set -> [regret_pass, regret_bet]
strategy_sum = {}        # info_set -> [sum_pass, sum_bet]

Get Strategy (Same as Chapter 1)

def get_strategy(info_set):
    # Identical to Chapter 1 — normalize positive regrets
    regret = cumulative_regret[info_set]
    positive = np.maximum(regret, 0)
    total = positive.sum()
    if total > 0:
        return positive / total
    return np.array([0.5, 0.5])  # uniform if no positive regrets

The CFR Traversal

def cfr(cards, history, reach_0, reach_1):
    # Base case: terminal node
    if is_terminal(history):
        return terminal_payoff(cards, history)  # from P0's perspective

    player = len(history) % 2
    info_set = cards[player] + ":" + history
    strategy = get_strategy(info_set)

    # Recurse into each action
    action_values = [0.0, 0.0]
    node_value = 0.0
    for action in [0, 1]:  # 0=pass, 1=bet
        if player == 0:
            action_values[action] = cfr(cards, history + action_char,
                                        reach_0 * strategy[action], reach_1)
        else:
            action_values[action] = cfr(cards, history + action_char,
                                        reach_0, reach_1 * strategy[action])
        node_value += strategy[action] * action_values[action]

    # Update regrets (weighted by OPPONENT's reach)
    opponent_reach = reach_1 if player == 0 else reach_0
    for action in [0, 1]:
        regret = action_values[action] - node_value
        if player == 1:
            regret = -regret  # P1 values are negated (zero-sum)
        cumulative_regret[info_set][action] += opponent_reach * regret

    # Accumulate strategy (weighted by OWN reach)
    my_reach = reach_0 if player == 0 else reach_1
    strategy_sum[info_set] += my_reach * strategy

    return node_value

Training Loop

for iteration in range(num_iterations):
    # Traverse tree for every possible deal
    for p0_card in [J, Q, K]:
        for p1_card in [J, Q, K]:
            if p0_card != p1_card:
                cfr([p0_card, p1_card], "", 1.0, 1.0)

Each iteration traverses the full tree for all 6 possible deals. This is vanilla CFR — no sampling. For larger games, Monte Carlo CFR (MCCFR) samples deals instead of enumerating them, trading variance for speed.

8. The Nash Equilibrium of Kuhn Poker

Unlike RPS (which has a unique Nash Equilibrium), Kuhn Poker has a family of equilibria parameterized by a single value α ∈ [0, 1/3].

All values of α give the same game value. CFR may converge to any equilibrium in this family.

9. Poker Concepts in Miniature

The Kuhn Poker equilibrium is a microcosm of real poker strategy. Let's unpack the key concepts.

9.1 Bluffing

Player 1 bets with Jack (the worst hand) with probability α. This is a pure bluff — the only way to win with Jack is to make the opponent fold. But why does the equilibrium include bluffing at all?

If Player 1 never bluffed, Player 2 would know every bet means King and would always fold. Then Player 1 would never get value from Kings. By bluffing sometimes with Jack, Player 1 forces Player 2 to call sometimes, which extracts value from King bets.

9.2 The Bluff-to-Value Ratio

Notice: P1 bluffs with probability α and value bets with probability 3α. The ratio is 1:3 (bluff : value). This is not arbitrary — it's calibrated to make Player 2 indifferent to calling with Queen.

When facing a bet, Player 2 with Queen risks 1 chip to win a pot of 3 chips (the 2 antes + 1 bet). The pot odds are 3:1, so Player 2 needs the bet to be a bluff at least 1/4 of the time. With P1 bluffing α and value betting 3α, the bluff frequency is α / (α + 3α) = 1/4 — exactly the pot odds.

9.3 Position

The game value is −1/18 for Player 1. Acting first is a disadvantage in Kuhn Poker (and in most poker variants). Player 2 gets to see Player 1's action before deciding, which provides valuable information.

This mirrors real poker: the button (last to act post-flop) has a significant strategic advantage. In the solver output, you'll see this reflected in the asymmetric equilibrium strategies.

9.4 Indifference

At Nash Equilibrium, Player 2 with Queen is indifferent to calling or folding when facing a bet — both actions give the same expected value. Similarly, Player 1's bluff and value bet frequencies are set to make Player 2 indifferent. This is a defining property of mixed-strategy Nash Equilibria: you mix between actions only when they're equally good.

10. Interactive Demo: Play Kuhn Poker

Before we look at the solver output, play a few hands of Kuhn Poker against the Nash Equilibrium strategy. You'll be Player 1 (first to act). Try bluffing, try value betting — and see how the equilibrium responds. Your long-run EV should approach −1/18 ≈ −0.056 per hand (the positional disadvantage).

11. Interactive Demo: CFR Training

Watch CFR learn the Nash Equilibrium of Kuhn Poker in real time. The chart shows exploitability dropping toward zero as strategies converge.

12. Interactive Demo: Equilibrium Explorer

Explore how the strategies at each information set change as CFR converges. Run the training first, then inspect each info set.

13. Bridge to Larger Games

Kuhn Poker has 12 information sets. Real poker has billions. How does CFR scale?

12.1 Monte Carlo CFR (MCCFR)

Vanilla CFR traverses the entire tree every iteration. In NLHE, this is impossible. MCCFR samples random deals and traverses only those branches, giving unbiased regret estimates with much less work per iteration.

12.2 CFR+

Instead of allowing negative cumulative regrets (which slow convergence), CFR+ floors regrets at zero after each iteration. This was used to essentially solve Heads-Up Limit Hold'em.

12.3 Abstraction

For NLHE, the game tree is too large even for MCCFR. Abstraction groups similar hands into "buckets" (card abstraction) and limits the bet sizes (action abstraction), reducing the tree to a tractable size. Chapter 4 will cover this.

14. References