Counterfactual Regret Minimization (CFR) Explained

Counterfactual regret minimization (CFR) is the algorithm family behind most strong poker AI. It plays a game against itself many times, tracks how much it regrets each choice, and shifts toward choices it regrets not having made. This page explains CFR poker training in plain terms: regret matching, information sets, the average strategy, and the variants (MCCFR, Linear CFR, CFR+) used in practice.

The idea in one paragraph

Regret is simple. After you act, you ask: how much better would I have done with a different action? If an alternative would have won more, you have positive regret for it. CFR keeps a running total of that regret for every action at every decision point, and plays actions in proportion to their positive regret. Over many iterations, the players' average strategy approaches a Nash equilibrium in two-player zero-sum games. The original method is from Zinkevich, Johanson, Bowling and Piccione, "Regret Minimization in Games with Incomplete Information" (NeurIPS 2007).

The word "counterfactual" matters. The regret at a decision is weighted by the probability that the other players and chance (the deck) would have led you there, while ignoring your own probability of reaching it. This lets every decision point learn on its own, which is what makes the method scale to a game as large as poker.

Regret matching: a worked example

Regret matching is the rule CFR applies at each decision point. Rock-paper-scissors is the smallest honest example. Payoffs are +1 for a win, 0 for a tie, -1 for a loss. Track cumulative regret for (Rock, Paper, Scissors), all starting at zero. With no positive regret, you play uniformly: 1/3 each.

Iteration 1. You play Rock, and the opponent plays Paper. You lose (-1). Had you played Paper, you would have tied (0). Had you played Scissors, you would have won (+1). Regret for an action is its payoff minus the payoff you got: Rock (-1) - (-1) = 0, Paper 0 - (-1) = +1, Scissors (+1) - (-1) = +2. Cumulative regret is (0, 1, 2).

Iteration 2. Normalize the positive regrets: total 3, so the strategy is (0, 1/3, 2/3). Say you sample Scissors, and the opponent plays Rock. You lose (-1). Paper would have won (+1) and Rock would have tied (0). Regrets this round: Rock 0 - (-1) = +1, Paper +1 - (-1) = +2, Scissors 0. Cumulative regret is now (1, 3, 2).

Iteration 3. Total positive regret is 6, so the strategy is (1/6, 3/6, 2/6), about (0.17, 0.50, 0.33). The strategy has moved toward Paper because the opponent has played Paper and Rock. The average strategy over iterations 1 and 2 is the mean of (1/3, 1/3, 1/3) and (0, 1/3, 2/3), which is (1/6, 1/3, 1/2). Against a fixed opponent the play chases a best response. In self-play, both sides do this at once, and it is the averages, not the latest strategies, that converge to equilibrium.

Information sets and the average strategy

Poker is a game of hidden information, so a player cannot tell which exact game state they are in. An information set groups every state a player cannot distinguish: your own hole cards, the public board cards, and the betting history. CFR stores one regret table and one strategy per information set, and the action probabilities live there.

Two details trip people up. First, the latest strategy can cycle and oscillate. Only the average strategy, weighted over iterations, carries the convergence guarantee. That is what a trained bot plays. Second, the guarantee holds for two-player zero-sum games. With three or more players there is no such guarantee, yet Pluribus showed that CFR-style self-play still produces strong six-player play. See the poker AI history for how this fits into the wider field.

The full poker tree is far too large to visit, so games are shrunk by abstraction. Card abstraction puts similar hands into the same bucket. Action abstraction limits bets to a short menu of sizes. The Pluribus paper used both, and so does SHARINGAN-2.

Sampling variants: MCCFR

Vanilla CFR walks the whole game tree each iteration. That is impossible for no-limit hold'em. Monte Carlo CFR (MCCFR, Lanctot, Waugh, Zinkevich and Bowling, NeurIPS 2009) samples part of the tree instead and corrects for the sampling so regrets stay unbiased in expectation. Two common forms:

• Outcome sampling follows a single path of play per iteration. Updates are cheap, but noisy.
• External sampling samples chance events and the opponents' actions, but tries every action for the player being updated. Updates cost more but are far less noisy. Pluribus used this form.

Because each iteration touches only a sliver of the tree, a blueprint needs enormous numbers of iterations. SHARINGAN-2's blueprint was trained for 1.83e11 external-sampling iterations on CPU servers. Sampling is what turns an impossible computation into a rented-server job.

Discounting and pruning: Linear CFR and CFR+

Early iterations are played with bad strategies, and plain CFR carries that early regret forever. Two fixes helped a great deal:

• CFR+ (Tammelin, 2014) resets negative cumulative regret to zero ("regret-matching+") and uses a weighted average. It powered Cepheus, which essentially solved heads-up limit hold'em.
• Linear CFR and Discounted CFR (Brown and Sandholm, AAAI 2019) weight iteration t in proportion to t, so later, better iterations count more. Pluribus applied Linear CFR discounting in the early part of training.

Pruning skips actions whose cumulative regret is very negative, since they are unlikely to be worth playing. It saves time on most iterations. The usual rule is to revisit pruned actions every so often, and not to prune on the final betting round. SHARINGAN-2 prunes negative-regret actions on 95% of iterations and never on the river.

A minimal sketch

The structure below is the core of external-sampling MCCFR for one player. It is a sketch for understanding, not the production Rust code.

def traverse(h, player):
    if terminal(h):    return payoff(h, player)
    if chance(h):      return traverse(sample_chance(h), player)
    I = infoset(h)
    sigma = regret_matching(regret[I])      # positive regrets, normalized
    if actor(h) == player:
        v = {a: traverse(h + a, player) for a in actions(h)}
        ev = sum(sigma[a] * v[a] for a in actions(h))
        for a in actions(h):
            regret[I][a] += v[a] - ev       # (+ discounting / pruning here)
        return ev
    a = sample(sigma)                       # opponent: sample one action
    strategy_sum[I] += sigma                # accumulate the average strategy
    return traverse(h + a, player)

How blueprints use it in Pluribus and SHARINGAN-2

CFR is used offline to compute a blueprint: a full strategy for the abstracted game. Pluribus computed its blueprint in 8 days on a 64-core server with MCCFR (external sampling), Linear CFR discounting early on, and negative-regret pruning. At play time it ran depth-limited real-time search on top of that blueprint, which the Pluribus article covers in detail.

The open reproduction follows the same recipe. SHARINGAN-2 pairs an MCCFR blueprint (preflop in 169 lossless classes, 200 buckets per postflop street) with turn and river search. The training details are in the SHARINGAN-2 write-up and the open-source Pluribus page, and the code is on GitHub. If you want to know how bots like these get scored fairly, read measuring poker bot skill.

FAQ

What is counterfactual regret minimization?

An iterative self-play algorithm for imperfect-information games. It tracks, for every information set, how much better each action would have done than the one taken, and plays actions in proportion to positive regret. The average strategy approaches a Nash equilibrium in two-player zero-sum games.

What is regret matching?

The rule used at each decision point in CFR: keep cumulative regret per action, and choose each action with probability proportional to its positive regret. If no regret is positive, play uniformly.

What is the difference between CFR and MCCFR?

CFR visits the entire game tree each iteration. Monte Carlo CFR samples parts of the tree, such as chance events and opponent actions, which makes each iteration far cheaper while keeping regret estimates unbiased in expectation.

What are Linear CFR and CFR+?

Both speed up convergence. CFR+ floors negative cumulative regret at zero and was used to solve heads-up limit hold'em. Linear CFR weights iteration t by t so that later iterations count more; Pluribus used it early in training.

Does CFR work for six-player poker?

There is no convergence guarantee with three or more players. In practice, CFR-style self-play still produced a bot that beat elite professionals in Pluribus, so it works well empirically.

Why do poker bots play the average strategy?

The latest iterate can oscillate. The convergence guarantee applies to the strategy averaged across iterations, so that average is the one deployed.