Table of Contents
- Motivation: What Do Poker Solvers Actually Do?
- Normal-Form Games & the Payoff Matrix
- Pure vs. Mixed Strategies
- Nash Equilibrium & the Minimax Theorem
- Regret: The Key Concept
- The Regret Matching Algorithm
- Convergence Guarantees
- Exploitability: Measuring Distance from Nash
- Interactive Demo: Convergence in Self-Play
- Interactive Demo: Exploiting a Fixed Opponent
- Interactive Demo: Play RPS Against the Bot
- Bridge to Poker: From Normal-Form to Extensive-Form
- References & Further Reading
1. Motivation: What Do Poker Solvers Actually Do?
Tools like PIOsolver and GTO Wizard have transformed competitive poker. At their core, they compute Nash Equilibrium strategies — strategy profiles where neither player can improve their expected value by unilaterally deviating. A player following a Nash Equilibrium strategy is guaranteed to not lose in expectation, no matter what the opponent does.
But how do you find a Nash Equilibrium in a game as complex as No-Limit Hold'em, which has on the order of 10160 game states? The answer is a family of algorithms built on a single, elegant primitive: regret matching.
This chapter develops regret matching from first principles using Rock-Paper-Scissors — a game simple enough to verify by hand, yet rich enough to illustrate every concept we'll need. By the end of this chapter, you will understand the exact mechanism that poker solvers use at every decision point in the game tree.
2. Normal-Form Games & the Payoff Matrix
A normal-form game (also called a strategic-form game) is defined by:
- A finite set of players (here, 2)
- A finite set of actions for each player
- A utility function mapping each action profile to a real-valued payoff for each player
In Rock-Paper-Scissors, both players simultaneously choose one of three actions: Rock (R), Paper (P), or Scissors (S). The payoffs from Player 1's perspective are given by the following matrix:
Rows = Player 1's action | Columns = Player 2's action | Cell = Player 1's payoff
RPS is a two-player zero-sum game: Player 2's payoff is always the negative of Player 1's. This zero-sum property is critical — it guarantees that Nash Equilibria exist and can be computed via linear programming (or, as we'll see, regret matching).
3. Pure vs. Mixed Strategies
Example: σ = [0.4, 0.35, 0.25] means play Rock 40% of the time, Paper 35%, and Scissors 25%.
Every pure strategy is a special case of a mixed strategy (e.g., "always Rock" = [1, 0, 0]). The set of all mixed strategies is a simplex — a triangle in the case of three actions.
Expected Value Under Mixed Strategies
When Player 1 plays mixed strategy σ and Player 2 plays mixed strategy τ, Player 1's expected value is:
where A is the payoff matrix. For example, if Player 1 plays [0.5, 0.5, 0] (50/50 Rock/Paper) and Player 2 plays [1, 0, 0] (always Rock):
4. Nash Equilibrium & the Minimax Theorem
EV(σ*, τ*) ≥ EV(σ, τ*) for all strategies σ of Player 1
EV(σ*, τ*) ≤ EV(σ*, τ) for all strategies τ of Player 2
(The second inequality is flipped because Player 2 is minimizing in a zero-sum game.)
John Nash proved in 1950 that every finite game has at least one Nash Equilibrium (possibly in mixed strategies). For RPS, the unique Nash Equilibrium is:
Against this strategy, every action yields expected value 0. No deviation can improve on this — you can verify by computing the EV of each pure action against [1/3, 1/3, 1/3]:
EV(Paper) = (+1)·(1/3) + 0·(1/3) + (-1)·(1/3) = 0
EV(Scissors) = (-1)·(1/3) + (+1)·(1/3) + 0·(1/3) = 0
The minimax theorem guarantees that Nash Equilibria exist in all two-player zero-sum games and can be computed. This is the theoretical foundation upon which all poker solvers rest: heads-up poker is a two-player zero-sum game, so its Nash Equilibrium is guaranteed to exist and is computable.
About this paper
This landmark paper single-handedly founded modern game theory. Von Neumann proved that in any finite two-player zero-sum game, there exists a pair of optimal mixed strategies and a well-defined game value. The original proof used a sophisticated topological argument; a simpler version via Brouwer's fixed-point theorem followed in 1937.
Von Neumann considered the minimax theorem essential to the entire field: "As far as I can see, there could be no theory of games without that theorem. I thought there was nothing worth publishing until the Minimax Theorem was proved." The paper introduced the concept of mixed (randomized) strategies and established the mathematical framework that would later be developed into the comprehensive theory presented in his 1944 book with Morgenstern.
Read the paper (Springer) →About this paper
One of the most influential papers in mathematics and economics — and remarkably, it is only one page long. Nash proved that every finite game with any number of players has at least one equilibrium point in mixed strategies. The proof uses Kakutani's fixed-point theorem in an elegant argument that fits on a single printed page.
While Von Neumann's minimax theorem covered only two-player zero-sum games, Nash's generalization applies to any number of players and any payoff structure. The concept of a "Nash Equilibrium" became foundational across economics, political science, evolutionary biology, and computer science. Nash received the 1994 Nobel Prize in Economics for this work.
Read the paper (PNAS) →5. Regret: The Key Concept
Now we arrive at the central concept. Intuitively, regret for an action answers: "How much better would I have done if I had always played this action instead of what I actually played?"
Regret can be positive (we would have done better) or negative (we would have done worse). If our strategy is already optimal against the opponent, all regrets are zero.
Worked Example
Suppose we play σ = [0.5, 0.3, 0.2] and the opponent plays τ = [0.7, 0.2, 0.1].
Step 1: Compute EV of each pure action against τ:
EV(Paper) = (+1)(0.7) + 0(0.2) + (−1)(0.1) = +0.6
EV(Scissors) = (−1)(0.7) + (+1)(0.2) + 0(0.1) = −0.5
Step 2: Compute EV of our mixed strategy:
Step 3: Compute regrets:
r(Paper) = +0.6 − 0.03 = +0.57 (would have done much better)
r(Scissors) = −0.5 − 0.03 = −0.53 (would have done worse)
The only positive regret is for Paper — which makes sense, since the opponent heavily favors Rock. Regret matching will increase our probability of playing Paper next iteration.
6. The Regret Matching Algorithm
Regret matching was introduced by Hart and Mas-Colell (2000) as a simple procedure for learning in games. The algorithm is remarkably simple:
At each iteration t = 1, 2, 3, ...:
-
Compute strategy from regrets:
Let R+(a) = max(Rt-1(a), 0)
If Σ_a R+(a) > 0:
σt(a) = R+(a) / Σ_a R+(a)
Else:
σt(a) = 1/|A| (uniform) - Play strategy σt, observe opponent's strategy τt.
-
Update cumulative regrets:
For each action a:
Rt(a) = Rt-1(a) + [EV(a, τt) − EV(σt, τt)]
Output: The average strategy σ̄ = (1/T) Σt=1..T σt
This is why solvers like PIOsolver report the average strategy as the solution. The distinction is easy to miss but absolutely essential to understand correctly.
Implementation
The algorithm requires only two arrays per player, both of size |A| (number of actions):
cumulative_regret[a]— the running sum of regretsstrategy_sum[a]— the running sum of strategies (for computing the average)
def get_strategy(cumulative_regret):
# Clip negative regrets to zero
positive = np.maximum(cumulative_regret, 0)
total = positive.sum()
if total > 0:
return positive / total
else:
return np.ones(NUM_ACTIONS) / NUM_ACTIONS
def update_regrets(my_strategy, opponent_strategy, cumulative_regret):
# EV of each pure action against opponent
action_evs = PAYOFF @ opponent_strategy
# EV of our mixed strategy
strategy_ev = my_strategy @ action_evs
# Accumulate regrets
cumulative_regret += action_evs - strategy_ev
Note the separation of concerns: get_strategy is a pure function that converts
regrets to a strategy. Strategy accumulation happens separately in the training loop.
This avoids the subtle bug of double-accumulating the strategy sum if multiple code paths
call get_strategy.
About this paper
This paper introduced the regret matching algorithm studied in this chapter. Hart and Mas-Colell showed that if players adjust their strategies with probabilities proportional to their accumulated regret for not having played alternative actions, then the empirical distribution of play converges to the set of correlated equilibria of the game.
The elegance of regret matching lies in its simplicity: each player needs only to track a single number per action (cumulative regret), and the strategy update is a straightforward normalization. Despite this simplicity, the procedure has strong convergence guarantees. In two-player zero-sum games, when both players use regret matching, their average strategies converge to a Nash Equilibrium — the specific property exploited by all CFR-based poker solvers.
Read the paper (Econometrica) →7. Convergence Guarantees
Why does regret matching work? The key theoretical result connects cumulative regret to Nash Equilibrium:
As T → ∞, the average strategy converges to Nash Equilibrium at rate O(1/√T).
This O(1/√T) rate means you need 4x the iterations to halve the exploitability. For RPS with 3 actions and payoffs in [-1, +1]:
| Iterations | Upper Bound on Exploitability | Typical Observed |
|---|---|---|
| 100 | 0.346 | ~0.10 |
| 1,000 | 0.110 | ~0.03 |
| 10,000 | 0.035 | ~0.01 |
| 100,000 | 0.011 | ~0.002 |
In practice, convergence is often faster than the theoretical worst case. The connection to Blackwell's approachability theorem (1956) provides a deeper understanding of why this works: regret matching can be viewed as a special case of Blackwell's procedure for approaching a convex set in vector-valued payoff space.
About this paper
Blackwell extended Von Neumann's minimax theorem from scalar payoffs to vector-valued payoffs. In the scalar case, a player can guarantee a certain expected payoff. Blackwell asked: when payoffs are vectors in Rd, can a player guarantee that the average payoff vector converges to a target set?
He proved the approachability theorem: a closed convex set S is "approachable" by a player if and only if for every opponent strategy, there exists a counter-strategy whose expected payoff lies in S. The proof is constructive — at each step, project the running average onto S and play optimally for the resulting halfspace game. Regret matching is a special case: the "target set" is the non-positive orthant of regret space, and Blackwell's procedure becomes exactly the regret-matching update rule.
Read the paper (Project Euclid) →8. Exploitability: Measuring Distance from Nash
How do we measure how close a strategy is to Nash Equilibrium? The answer is exploitability — the maximum expected value an opponent can achieve by best-responding to our strategy.
Solvers typically report this as a fraction of the pot: "converged to 0.3% of pot" means the exploitability is 0.3% of the pot size.
9. Interactive Demo: Convergence in Self-Play
This demo runs two regret-matching players against each other, starting from biased initial strategies. Watch how both players' average strategies converge toward [1/3, 1/3, 1/3] and exploitability drops toward 0.
Self-Play Convergence
10. Interactive Demo: Exploiting a Fixed Opponent
When the opponent plays a fixed (non-adaptive) strategy, regret matching converges to the best response — the pure action with the highest EV. This illustrates a crucial concept for poker: against a non-equilibrium opponent, the optimal counter-strategy deviates from Nash. This is the theoretical basis of exploitative play.
Best Response to a Fixed Opponent
Set the opponent's fixed strategy and watch regret matching find the best response.
11. Interactive Demo: Play RPS Against the Bot
Now it's your turn. Play Rock-Paper-Scissors against a regret-matching bot. At first, it plays randomly. But as you play more rounds, it learns your tendencies and adapts. Can you stay unpredictable enough to avoid being exploited?
You vs. Regret-Matching Bot
In a poker solver, this same process runs at every decision point simultaneously. Both "players" adapt to each other until neither can improve — that's Nash Equilibrium.
12. Bridge to Poker: From Normal-Form to Extensive-Form
Rock-Paper-Scissors is a normal-form game: a single simultaneous decision with no hidden information and no sequential play. Poker is an extensive-form game: it unfolds over time through a tree of decisions, with hidden information (private cards) and multiple betting rounds.
The leap from this chapter to a poker solver requires three conceptual extensions:
11.1 Game Trees & Sequential Decisions
In poker, decisions happen in sequence: Player 1 might bet, then Player 2 decides to call, raise, or fold. This creates a game tree where each node is a decision point. Instead of one regret-matching instance, we'll need one at every decision node.
11.2 Information Sets
A player can't distinguish between game states that look identical from their perspective. If you hold A♠K♥, you can't tell whether the opponent holds Q♠J♠ or 7♦2♣. All states that are indistinguishable to a player are grouped into an information set. Regret matching operates at the information-set level, not at individual game states.
11.3 Counterfactual Values
In a game tree, we can't simply use expected values — we need counterfactual values. The counterfactual value of reaching an information set assumes the player tries to reach it (probability 1 for their own actions) while all other players play according to their current strategies. This "what if I tried to get here?" framing is the "counterfactual" in Counterfactual Regret Minimization (CFR).
In Chapter 2, we'll implement full CFR for Kuhn Poker — a 3-card poker game with a tractable game tree that still exhibits bluffing, value betting, and positional advantage.
About this paper
This is the paper that introduced Counterfactual Regret Minimization (CFR) — the algorithm that powers every modern poker solver. The key insight is a decomposition: overall regret in an extensive-form game can be bounded by the sum of counterfactual regrets at individual information sets. This means you can minimize regret independently at each decision point using simple regret matching, then combine the guarantees.
The practical impact was immediate. CFR could solve poker game abstractions with up to 1012 states — two orders of magnitude larger than previous methods based on linear programming. Strategies produced by CFR were used in the 2007 Annual Computer Poker Competition. The paper spawned an entire family of algorithms (CFR+, MCCFR, Discounted CFR) that remain the state of the art for imperfect-information game solving.
Read the paper (NeurIPS) →13. References & Further Reading
About this paper
This landmark paper single-handedly founded modern game theory. Von Neumann proved that in any finite two-player zero-sum game, there exists a pair of optimal mixed strategies and a well-defined game value — the minimax theorem. His original proof used a sophisticated topological argument; a simpler proof via Brouwer's fixed-point theorem followed in 1937, and Jean Ville provided an even more elegant convexity-based proof in 1938.
Von Neumann considered this result essential to the entire field: "As far as I can see, there could be no theory of games without that theorem." The paper introduced mixed (randomized) strategies and established the mathematical framework that would later be developed into the comprehensive theory presented in his 1944 book with Morgenstern, Theory of Games and Economic Behavior.
Read the paper (Springer) →About this paper
One of the most influential papers in the history of mathematics and economics — and remarkably, it is only one page long. Nash proved that every finite game with any number of players has at least one equilibrium point in mixed strategies. The proof applies Kakutani's fixed-point theorem to the "countering" correspondence: the set of best responses to any strategy profile is convex and varies continuously, so a fixed point must exist.
While Von Neumann's minimax theorem covered only two-player zero-sum games, Nash's generalization applies to any number of players and any payoff structure. The "Nash Equilibrium" concept became foundational across economics, political science, evolutionary biology, and computer science. Nash received the 1994 Nobel Prize in Economics for this work.
Read the paper (PNAS, free access) →About this paper
Blackwell extended Von Neumann's minimax theorem from scalar payoffs to vector-valued payoffs. He defined a set S as "approachable" if a player can force the time-averaged payoff vector to converge to S regardless of the opponent's actions, and proved the approachability theorem: a closed convex set is approachable if and only if for every opponent strategy, there exists a counter-strategy whose expected payoff vector lies in S.
The proof is constructive: at each step, project the running average onto S and play optimally for the resulting halfspace game. Regret matching turns out to be a special case — the "target set" is the non-positive orthant of regret space, and Blackwell's procedure becomes exactly the regret-matching update. This connection provides the deepest theoretical explanation for why regret matching converges.
Read the paper (Project Euclid, free access) →About this paper
This paper introduced regret matching — the algorithm at the heart of this chapter and every poker solver. Hart and Mas-Colell showed that if players adjust their strategies with probabilities proportional to their positive regret for not having played alternative actions, the empirical distribution of play converges to the set of correlated equilibria. The procedure requires tracking only one number per action (cumulative regret), making it remarkably simple.
In two-player zero-sum games specifically, when both players use regret matching, their average strategies converge to a Nash Equilibrium. This property is what CFR-based poker solvers exploit: run regret matching at every information set simultaneously, and the overall average strategy profile converges to Nash. The paper has over 1,300 citations and remains one of the most popular algorithms in game-theoretic applications.
Read the paper (Econometrica) →About this paper
The paper that introduced Counterfactual Regret Minimization (CFR) — the direct ancestor of all modern poker solvers. The key contribution is a decomposition theorem: overall regret in an extensive-form game can be bounded by the sum of counterfactual regrets at each information set. This means you can run simple regret matching independently at each decision point, and the combination converges to Nash Equilibrium.
The practical impact was immediate and dramatic. CFR could solve poker game abstractions with up to 1012 states — two orders of magnitude larger than the linear programming methods used previously. Strategies generated by CFR were used in the 2007 Annual Computer Poker Competition and Man-vs-Machine Championship. The paper spawned a family of variants (CFR+, MCCFR, Discounted CFR) that remain the state of the art.
Read the paper (NeurIPS, PDF) →About this paper
This paper announced that Heads-Up Limit Texas Hold'em — a game with 3.19 × 1014 information sets — had been "essentially weakly solved." Their program Cepheus plays so close to the game-theoretic optimum that it cannot be statistically distinguished from perfect play over a human lifetime of poker. This was the first imperfect-information game played competitively by humans to be solved.
The breakthrough came from CFR+, a variant of CFR invented by Oskari Tammelin that floors negative regrets to zero at each step (rather than allowing them to accumulate). This seemingly minor change dramatically accelerates convergence — CFR+ solved the game using 4,800 CPUs over 68 days. The paper also formally confirmed the conventional poker wisdom that the dealer holds a significant strategic advantage.
Read the paper (Science) →About this paper
Pluribus was the first AI to defeat elite human professionals at six-player no-limit Texas Hold'em — the most popular form of poker played worldwide. When pitted against five top professionals including Darren Elias (most World Poker Tour titles) and Chris Ferguson (six WSOP bracelets), Pluribus achieved a win rate of approximately 5 big blinds per 100 hands over 10,000 hands.
Technically, Pluribus uses Monte Carlo CFR for self-play training to produce a "blueprint" strategy, then performs real-time search during play. Remarkably, it uses no neural networks — its strategy comes entirely from CFR. It trained in just 8 days on a 4-core server with less than 512 GB of RAM (compared to millions of core-hours for other game-playing AIs). The paper also revealed surprising strategic findings: Pluribus frequently used "donk bets" — a move traditionally considered weak by human players.
Read the paper (Science) →