Counterfactual Regret Minimization

Introduction

In chess both players see the whole board. In poker you see your own cards and nothing else, and that single fact changes everything. The right move depends on what your opponent holds, which you can only infer from how they have played — and they know you are inferring, so they play to mislead you. Games like this are called imperfect-information games, and for decades they resisted the search techniques that conquered chess and Go, such as Monte Carlo tree search: you cannot evaluate a position you cannot see.

The way out is game theory. In a two-player zero-sum game, a Nash equilibrium strategy guarantees at least the value of the game against any opponent. It does not try to read minds; it is simply impossible to exploit. And one of the oldest results in the field says that such a strategy must bluff. John von Neumann analysed simplified poker in Theory of Games and Economic Behavior (1944, with Oskar Morgenstern), and Harold Kuhn's 1950 paper "A simplified two-person poker" solved the three-card game you can play with below: in every equilibrium the first player sometimes bets with the worst card. Bluffing is not a psychological trick bolted onto good play — it is good play.

The question is how to compute such a strategy when the game has billions of situations. The answer that won was surprisingly humble: play against yourself many times and keep track of your regrets.

Regret. After $T$ rounds of a repeated game, the regret for never having played action $a$ is

R^T(a) = \sum_{t=1}^{T} \Big( u\big(a, \sigma_{-i}^t\big) - u\big(\sigma^t\big) \Big),

how much better you would have done by always playing $a$ while the opponent did what they actually did. Regret matching (Sergiu Hart and Andreu Mas-Colell, Econometrica, 2000) chooses the next strategy in proportion to the positive part of these regrets:

\sigma^{T+1}(a) = \frac{R^{T,+}(a)}{\sum_b R^{T,+}(b)}, \qquad x^+ = \max(x, 0),

falling back to uniform when no regret is positive. It is a no-regret rule: the average regret $R^T/T$ goes to zero. And there is a classic link between learning and equilibrium: in a two-player zero-sum game, if both players have average regret at most $\varepsilon$ , then their average strategies form a $2\varepsilon$ -Nash equilibrium. Self-play of two no-regret learners therefore converges, on average, to an equilibrium — the same idea behind online convex optimization and multi-armed bandits.

Counterfactual regret. Poker is not a one-shot game; it is a tree of decisions where you do not know which node you are in. The nodes you cannot tell apart form an information set $I$ (in Kuhn poker: "I hold the queen, I checked, and now face a bet"). In 2007 Martin Zinkevich, Michael Johanson, Michael Bowling and Carmelo Piccione (NIPS 2007, "Regret Minimization in Games with Incomplete Information") had the key idea: run a separate regret matcher at every information set, using as payoff the counterfactual value

v_i(\sigma, I) = \sum_{h \in I} \pi_{-i}^{\sigma}(h) \sum_{z \text{ terminal}} \pi^{\sigma}(h \to z)\, u_i(z),

the value of reaching $I$ weighted only by the probability that the opponent and chance get there — as if player $i$ had tried to reach it. The counterfactual regret of action $a$ accumulates $v_i(\sigma^t_{I \to a}, I) - v_i(\sigma^t, I)$ . They proved that the player's total regret is bounded by the sum of these local positive regrets, so driving every local regret to zero drives the whole strategy toward equilibrium.

initialise regret[I][a] = 0 and strategySum[I][a] = 0 for every info set I
repeat T times:
    for each player i:
        walk the whole game tree with the current strategy
          sigma(I) = regret matching on regret[I]
        at each info set I of player i:
            v[a]  = value of taking action a           (for each a)
            v_I   = sum_a sigma(I)[a] * v[a]
            regret[I][a]      += reach_opponent_and_chance * (v[a] - v_I)
            strategySum[I][a] += reach_i * sigma(I)[a]
output the AVERAGE strategy: strategySum normalised per info set

The last line matters: the current strategy can oscillate forever, but the average strategy converges. The demo below shows both.

Try It: Watch CFR Discover the Bluff

Kuhn poker is the smallest game that still has the essence of poker. There are three cards, J < Q < K. Each player antes 1 chip and gets one card. Player 1 may check or bet 1; if player 1 checks, player 2 may check (showdown) or bet; whoever faces a bet may call (showdown for 2 chips) or fold. Each player has just six information sets — the whole game has twelve.

The demo runs genuine CFR over the full tree, and after each batch it computes the exploitability of the average strategy exactly: how much a perfect best-responder could win against it, averaged over the two seats.

<!-- CFR demo: a real Counterfactual Regret Minimization solver for Kuhn poker, plus a regret-matching panel for rock-paper-scissors. -->
<h3>1 · Solve Kuhn poker with CFR</h3>
<p class="hint">Kuhn poker: three cards (J &lt; Q &lt; K), each player antes 1 chip and gets one card, one bet of 1 chip is allowed. The solver below runs genuine CFR self-play over all 12 information sets. Press the buttons and watch the <b>exploitability</b> of the average strategy fall, the game value approach <b>−1/18</b> for player 1, and the J-bluff appear on its own.</p>
<div class="row">
  <label for="algo">Algorithm:</label>
  <select id="algo">
    <option value="cfr">Vanilla CFR (2007)</option>
    <option value="cfrplus">CFR+ (2014)</option>
  </select>
</div>
<div class="btns">
  <button id="b1" type="button">+1 iteration</button>
  <button id="b100" type="button">+100</button>
  <button id="b1000" type="button">+1000</button>
  <button id="brun" type="button">Run to 20,000</button>
  <button id="breset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>
<div class="lbl">Exploitability of the average strategy (log–log)</div>
<canvas id="plot" width="340" height="150" aria-label="Exploitability versus iterations on a log-log scale"></canvas>
<div class="legend"><span class="sw solid"></span>exploitability <span class="sw dash"></span>reference slope 1/√T</div>
<div class="stats" id="stats"></div>
<div class="alpha" id="alpha"></div>
<div class="tblwrap">
  <table class="strat">
    <thead><tr><th>Information set</th><th>Action</th><th>Learned P</th><th>Nash (for this α)</th></tr></thead>
    <tbody id="tbody"></tbody>
  </table>
</div>
<hr>
<!-- Second panel: plain regret matching on rock-paper-scissors, drawn on the probability simplex. -->
<h3>2 · Regret matching in rock-paper-scissors</h3>
<p class="hint">The building block of CFR on a one-shot game. Each player plays in proportion to its positive regrets. In self-play the current strategy (orange) keeps circling, but the <b>average</b> strategy (blue) spirals into the Nash equilibrium (1/3, 1/3, 1/3). Against a rock-heavy opponent, regret matching discovers paper.</p>
<div class="row">
  <label for="mode">Opponent:</label>
  <select id="mode">
    <option value="self">Self-play (another regret matcher)</option>
    <option value="fixed">Fixed bot: 50% rock, 25% paper, 25% scissors</option>
  </select>
</div>
<div class="btns">
  <button id="r10" type="button">+10 rounds</button>
  <button id="r1000" type="button">+1000 rounds</button>
  <button id="rreset" type="button" class="ghost">New random start</button>
</div>
<canvas id="simplex" width="240" height="210" aria-label="Strategy of player A on the rock-paper-scissors simplex"></canvas>
<div class="legend"><span class="dot cur"></span>current strategy <span class="dot avg"></span>average strategy</div>
<div class="stats" id="rstats"></div>
<div class="note" id="rnote"></div>

/* Layout and colors. Colors live in CSS variables so the canvases can follow light/dark mode. */
* { box-sizing: border-box; }
:root { --ink: #1f2933; --muted: #5b6774; --line: #cfd8e1; --bg2: #f3f6f9; --main: #1d3557; --accent: #e63946; --ref: #8a96a3; --good: #2a9d8f; --bar: #457b9d; --cur: #f4a261; }
body { font-family: system-ui, sans-serif; color: var(--ink); margin: 0; }
h3 { font-size: 1rem; margin: .2rem 0 .3rem; }
hr { border: 0; border-top: 1px solid var(--line); margin: 1rem 0 .6rem; }
.hint { font-size: .86rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; font-size: .9rem; margin: .3rem 0; }
select { font: 14px system-ui, sans-serif; padding: .25rem .4rem; border-radius: 6px; border: 1px solid var(--line); background: var(--bg2); color: var(--ink); }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin: .35rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid var(--main); background: var(--main); color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--main); }
.status { font-size: .9rem; font-weight: 600; margin: .35rem 0; min-height: 1.4em; line-height: 1.35; }
.lbl { font-size: .76rem; font-weight: 700; text-transform: uppercase; letter-spacing: .04em; color: var(--muted); margin: .4rem 0 .25rem; }
canvas { width: 100%; max-width: 340px; border: 1px solid var(--line); border-radius: 6px; display: block; }
#simplex { max-width: 240px; }
.legend { font-size: .78rem; color: var(--muted); margin: .25rem 0; display: flex; align-items: center; gap: .3rem; flex-wrap: wrap; }
.sw { display: inline-block; width: 18px; height: 0; border-top: 2px solid var(--main); margin-left: .4rem; }
.sw.dash { border-top: 2px dashed var(--ref); }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; margin-left: .4rem; }
.dot.cur { background: var(--cur); }
.dot.avg { background: var(--main); }
.stats { font: 12px ui-monospace, monospace; color: var(--muted); margin: .3rem 0; line-height: 1.5; }
.alpha { font-size: .85rem; margin: .3rem 0 .5rem; line-height: 1.4; }
.note { font-size: .84rem; color: var(--muted); line-height: 1.4; }
.tblwrap { overflow-x: auto; }
table.strat { border-collapse: collapse; width: 100%; font-size: .8rem; }
.strat th, .strat td { border-bottom: 1px solid var(--line); padding: .25rem .3rem; text-align: left; vertical-align: middle; }
.strat th { color: var(--muted); font-weight: 700; }
.strat td.num { font: 12px ui-monospace, monospace; white-space: nowrap; }
.bar { display: inline-block; width: 46px; height: 8px; background: var(--bg2); border: 1px solid var(--line); border-radius: 4px; vertical-align: middle; margin-right: 4px; overflow: hidden; }
.bar i { display: block; height: 100%; background: var(--bar); }
.strat tr.p2 td:first-child { color: var(--good); }
@media (prefers-color-scheme: dark) {
  /* Dark-mode palette. */
  :root { --ink: #e3e8ee; --muted: #a7b3c0; --line: #36495d; --bg2: #1f2a36; --main: #9fc5e8; --accent: #ff6b6b; --ref: #8796a6; --good: #6fd3c4; --bar: #7fb3d8; --cur: #f4b26a; }
  button { color: #111; }
  button.ghost { color: var(--main); }
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Counterfactual Regret Minimization on Kuhn poker. Cards: 0 = J, 1 = Q, 2 = K. Actions: p = pass (check/fold), b = bet (bet/call).
// An information set is the acting player's card plus the public history, e.g. '1pb' = player 1 holds Q, checked, and now faces a bet.
// Each iteration walks the full game tree for all 6 deals, updates counterfactual regrets and accumulates the average strategy.
const CARD = ['J', 'Q', 'K'];
const DEALS = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]];
// The 12 information sets: 6 for player 1 (opening, or after check-bet) and 6 for player 2 (after a check, or after a bet).
const P1_KEYS = ['0', '1', '2', '0pb', '1pb', '2pb'];
const P2_KEYS = ['0p', '1p', '2p', '0b', '1b', '2b'];
const KEYS = P1_KEYS.concat(P2_KEYS);
let R = {}, S = {}, sigma = {}, iter = 0, plus = false, hist = [], timer = null;

function isTerminal(h) { return h === 'pp' || h === 'bp' || h === 'bb' || h === 'pbp' || h === 'pbb'; }
// Net chips won by player 1 at a terminal history (ante 1, bet 1).
function payoff1(h, c1, c2) {
  const win = c1 > c2 ? 1 : -1;
  if (h === 'pp') return win;
  if (h === 'bp') return 1;
  if (h === 'pbp') return -1;
  return 2 * win;
}
function toAct(h) { return h.length % 2; }

function resetCFR() {
  R = {}; S = {};
  for (const k of KEYS) { R[k] = [0, 0]; S[k] = [0, 0]; }
  iter = 0; hist = [];
}
// Regret matching: play each action in proportion to its positive regret; uniform if none is positive.
function regretMatch(r) {
  let z = 0; const p = r.map((x) => { const y = Math.max(x, 0); z += y; return y; });
  return z > 0 ? p.map((y) => y / z) : r.map(() => 1 / r.length);
}
function snapshot() { for (const k of KEYS) sigma[k] = regretMatch(R[k]); }
function avgStrat(k) { const s = S[k], z = s[0] + s[1]; return z > 0 ? [s[0] / z, s[1] / z] : [0.5, 0.5]; }

// Recursive CFR. p0, p1 = reach probabilities of each player; u = the player whose regrets we update; w = weight for the average.
// Returns the expected payoff of player 1 below history h under the current strategy profile.
function cfr(h, c, p0, p1, u, w) {
  if (isTerminal(h)) return payoff1(h, c[0], c[1]);
  const pl = toAct(h), k = c[pl] + h, s = sigma[k];
  const v = [0, 0]; let node = 0;
  for (let a = 0; a < 2; a++) {
    const nh = h + (a ? 'b' : 'p');
    v[a] = pl === 0 ? cfr(nh, c, p0 * s[a], p1, u, w) : cfr(nh, c, p0, p1 * s[a], u, w);
    node += s[a] * v[a];
  }
  if (pl === u) {
    const sign = pl === 0 ? 1 : -1;
    const opp = pl === 0 ? p1 : p0, own = pl === 0 ? p0 : p1;
    for (let a = 0; a < 2; a++) {
      R[k][a] += (opp / 6) * sign * (v[a] - node);   // counterfactual regret, weighted by the opponent's (and chance's) reach
      S[k][a] += w * own * s[a];                     // average strategy, weighted by own reach
    }
  }
  return node;
}

function pass(u, w) {
  for (const d of DEALS) cfr('', d, 1, 1, u, w);
  // CFR+: clip regrets at zero after each pass (regret-matching+).
  if (plus) for (const k of (u === 0 ? P1_KEYS : P2_KEYS)) R[k] = R[k].map((x) => Math.max(x, 0));
}
function iterate() {
  iter++;
  if (plus) { snapshot(); pass(0, iter); snapshot(); pass(1, iter); }
  else { snapshot(); pass(0, 1); pass(1, 1); }
}

// Exact expected value of a profile: f0 and f1 map an information set to [P(pass), P(bet)].
function ev(h, c, f0, f1) {
  if (isTerminal(h)) return payoff1(h, c[0], c[1]);
  const pl = toAct(h), s = (pl === 0 ? f0 : f1)(c[pl] + h);
  return s[0] * ev(h + 'p', c, f0, f1) + s[1] * ev(h + 'b', c, f0, f1);
}
function value(f0, f1) { let t = 0; for (const d of DEALS) t += ev('', d, f0, f1); return t / 6; }
// Best response by brute force: each player has only 2^6 = 64 pure strategies, so try them all.
function pure(keys, mask) { return (k) => { const i = keys.indexOf(k); return (mask >> i) & 1 ? [0, 1] : [1, 0]; }; }
function bestResponses() {
  let br1 = -Infinity, br2 = -Infinity;
  for (let m = 0; m < 64; m++) {
    br1 = Math.max(br1, value(pure(P1_KEYS, m), avgStrat));
    br2 = Math.max(br2, -value(avgStrat, pure(P2_KEYS, m)));
  }
  return { br1, br2, expl: (br1 + br2) / 2 };
}
function record() { const b = bestResponses(); hist.push({ t: iter, e: Math.max(b.expl, 1e-9) }); return b; }
function shouldRecord() { return iter <= 20 || iter % Math.ceil(iter / 40) === 0; }
function runN(n) { for (let i = 0; i < n; i++) { iterate(); if (shouldRecord()) record(); } }

// User interface: plot, strategy table, buttons.
const $ = (id) => document.getElementById(id);
function css(v) { return getComputedStyle(document.documentElement).getPropertyValue(v).trim(); }
function setStatus(t) { $('status').textContent = t; }
const fmt = (x, d) => (Math.abs(x) < 5e-4 ? 0 : x).toFixed(d);

function drawPlot() {
  const cv = $('plot'), g = cv.getContext('2d'), W = cv.width, H = cv.height;
  g.clearRect(0, 0, W, H);
  const pad = { l: 34, r: 8, t: 8, b: 20 };
  const xmax = Math.max(10, iter), lx = (t) => pad.l + (Math.log10(t) / Math.log10(xmax)) * (W - pad.l - pad.r);
  const es = hist.map((p) => p.e);
  const ymax = Math.log10(Math.max(0.5, ...es)), ymin = Math.min(-3, Math.floor(Math.log10(Math.min(1, ...es))));
  const ly = (e) => pad.t + ((ymax - Math.log10(e)) / (ymax - ymin)) * (H - pad.t - pad.b);
  g.strokeStyle = css('--line'); g.fillStyle = css('--muted'); g.font = '10px system-ui, sans-serif'; g.lineWidth = 1;
  for (let y = Math.ceil(ymin); y <= Math.floor(ymax); y++) {
    g.beginPath(); g.moveTo(pad.l, ly(10 ** y)); g.lineTo(W - pad.r, ly(10 ** y)); g.stroke();
    g.fillText('1e' + y, 2, ly(10 ** y) + 3);
  }
  for (let x = 1; x <= xmax; x *= 10) g.fillText(String(x), lx(x) - 3, H - 5);
  if (!hist.length) return;
  // Dashed reference curve proportional to 1/√T, anchored at the first point.
  const c0 = hist[0].e * Math.sqrt(hist[0].t);
  g.setLineDash([4, 4]); g.strokeStyle = css('--ref'); g.beginPath();
  for (let i = 0; i <= 40; i++) { const t = Math.pow(xmax, i / 40); const y = c0 / Math.sqrt(t); i ? g.lineTo(lx(t), ly(y)) : g.moveTo(lx(t), ly(y)); }
  g.stroke(); g.setLineDash([]);
  g.strokeStyle = css('--main'); g.lineWidth = 2; g.beginPath();
  hist.forEach((p, i) => (i ? g.lineTo(lx(p.t), ly(p.e)) : g.moveTo(lx(p.t), ly(p.e))));
  g.stroke();
}

function rowsSpec(a) {
  const third = 1 / 3;
  return [
    ['0', "P1 holds %c%, acts first", "bet", 1, a], ['1', "P1 holds %c%, acts first", "bet", 1, 0], ['2', "P1 holds %c%, acts first", "bet", 1, Math.min(1, 3 * a)],
    ['0pb', "P1 holds %c%, checked, faces a bet", "call", 1, 0], ['1pb', "P1 holds %c%, checked, faces a bet", "call", 1, Math.min(1, a + third)], ['2pb', "P1 holds %c%, checked, faces a bet", "call", 1, 1],
    ['0p', "P2 holds %c%, P1 checked", "bet", 2, third], ['1p', "P2 holds %c%, P1 checked", "bet", 2, 0], ['2p', "P2 holds %c%, P1 checked", "bet", 2, 1],
    ['0b', "P2 holds %c%, P1 bet", "call", 2, 0], ['1b', "P2 holds %c%, P1 bet", "call", 2, third], ['2b', "P2 holds %c%, P1 bet", "call", 2, 1]
  ];
}
function drawTable() {
  const a = avgStrat('0')[1];
  const tb = $('tbody'); tb.innerHTML = '';
  for (const [k, label, act, pl, th] of rowsSpec(a)) {
    const p = avgStrat(k)[1];
    const tr = document.createElement('tr'); if (pl === 2) tr.className = 'p2';
    const td1 = document.createElement('td'); td1.textContent = i18nFmt(label, { c: CARD[+k[0]] });
    const td2 = document.createElement('td'); td2.textContent = act;
    const td3 = document.createElement('td'); td3.className = 'num';
    const bar = document.createElement('span'); bar.className = 'bar'; const fill = document.createElement('i'); fill.style.width = (p * 100).toFixed(1) + '%'; bar.appendChild(fill);
    td3.appendChild(bar); td3.appendChild(document.createTextNode(fmt(p, 3)));
    const td4 = document.createElement('td'); td4.className = 'num'; td4.textContent = fmt(th, 3);
    tr.append(td1, td2, td3, td4); tb.appendChild(tr);
  }
  $('alpha').textContent = i18nFmt("Learned α = P(P1 bets with J) = %a% — a pure bluff. Equilibria form a family with α ∈ [0, 1/3]: K should bet 3α (learned %k%, theory %k3%) and Q should call a bet with α + 1/3 (learned %q%, theory %q3%).", { a: fmt(a, 3), k: fmt(avgStrat('2')[1], 3), k3: fmt(Math.min(1, 3 * a), 3), q: fmt(avgStrat('1pb')[1], 3), q3: fmt(Math.min(1, a + 1 / 3), 3) });
}
function drawKuhn() {
  const last = hist.length ? hist[hist.length - 1] : null;
  const v = iter ? value(avgStrat, avgStrat) : 0;
  $('stats').textContent = i18nFmt("iteration %t% · exploitability %e% chips/hand · value for P1 %v% (theory −1/18 ≈ −0.0556)", { t: iter, e: last ? last.e.toExponential(2) : '—', v: fmt(v, 4) });
  drawPlot(); drawTable();
}
function stopRun() { if (timer) { clearInterval(timer); timer = null; } $('brun').textContent = "Run to 20,000"; }
function doReset() {
  stopRun(); plus = $('algo').value === 'cfrplus'; resetCFR(); drawKuhn();
  setStatus(plus ? "CFR+ selected: regrets are clipped at zero, updates alternate, the average is weighted linearly. Compare the slope with vanilla CFR." : "Regrets are zero, so both players start uniformly at random. Press a button to iterate.");
}
function afterBatch() { if (!hist.length || hist[hist.length - 1].t !== iter) record(); drawKuhn(); setStatus(i18nFmt("Done: %t% iterations. The table shows the average strategy, which is what converges to equilibrium.", { t: iter })); }
$('b1').onclick = () => { stopRun(); runN(1); afterBatch(); };
$('b100').onclick = () => { stopRun(); runN(100); afterBatch(); };
$('b1000').onclick = () => { stopRun(); runN(1000); afterBatch(); };
$('breset').onclick = doReset;
$('algo').onchange = doReset;
$('brun').onclick = () => {
  if (timer) { stopRun(); setStatus(i18nFmt("Paused at iteration %t%.", { t: iter })); return; }
  $('brun').textContent = "Pause"; setStatus("Running self-play…");
  timer = setInterval(() => {
    runN(Math.max(1, Math.floor(iter / 25)));
    drawKuhn();
    if (iter >= 20000) { stopRun(); afterBatch(); }
  }, 40);
};

// Regret matching (Hart & Mas-Colell, 2000) on rock-paper-scissors with exact expected payoffs.
// Index 0 = rock, 1 = paper, 2 = scissors; u(i, j) is the payoff of i against j.
const FIXED = [0.5, 0.25, 0.25];
const u = (i, j) => (i === j ? 0 : (i - j + 3) % 3 === 1 ? 1 : -1);
let rA, rB, sA, sB, rt, trail, rpsMode = 'self', gainSum = 0;
function rpsReset() {
  rpsMode = $('mode').value;
  const rnd = () => [0, 1, 2].map(() => Math.round(Math.random() * 6));
  rA = rnd(); rB = rnd(); sA = [0, 0, 0]; sB = [0, 0, 0]; rt = 0; gainSum = 0;
  trail = [{ c: regretMatch(rA), a: regretMatch(rA) }];
  drawRPS();
}
function rpsStep() {
  const pA = regretMatch(rA), pB = rpsMode === 'self' ? regretMatch(rB) : FIXED;
  const uA = [0, 1, 2].map((i) => pB[0] * u(i, 0) + pB[1] * u(i, 1) + pB[2] * u(i, 2));
  const vA = pA[0] * uA[0] + pA[1] * uA[1] + pA[2] * uA[2];
  for (let i = 0; i < 3; i++) { rA[i] += uA[i] - vA; sA[i] += pA[i]; }
  gainSum += vA;
  if (rpsMode === 'self') {
    const uB = [0, 1, 2].map((j) => pA[0] * u(j, 0) + pA[1] * u(j, 1) + pA[2] * u(j, 2));
    const vB = pB[0] * uB[0] + pB[1] * uB[1] + pB[2] * uB[2];
    for (let j = 0; j < 3; j++) { rB[j] += uB[j] - vB; sB[j] += pB[j]; }
  }
  rt++;
}
function rpsAvg() { const z = sA[0] + sA[1] + sA[2]; return z > 0 ? sA.map((x) => x / z) : regretMatch(rA); }
function rpsRun(n) { for (let i = 0; i < n; i++) { rpsStep(); if (rt <= 200 || rt % 5 === 0) trail.push({ c: regretMatch(rA), a: rpsAvg() }); } if (trail.length > 600) trail = trail.slice(-600); drawRPS(); }
// Draw the strategy simplex: each corner is a pure strategy, the center is the Nash equilibrium.
function drawRPS() {
  const cv = $('simplex'), g = cv.getContext('2d'), W = cv.width, H = cv.height;
  g.clearRect(0, 0, W, H);
  const V = [[W / 2, 18], [20, H - 22], [W - 20, H - 22]];
  const pt = (p) => [p[0] * V[0][0] + p[1] * V[1][0] + p[2] * V[2][0], p[0] * V[0][1] + p[1] * V[1][1] + p[2] * V[2][1]];
  g.strokeStyle = css('--line'); g.lineWidth = 1; g.beginPath(); g.moveTo(...V[0]); g.lineTo(...V[1]); g.lineTo(...V[2]); g.closePath(); g.stroke();
  g.fillStyle = css('--muted'); g.font = '11px system-ui, sans-serif'; g.textAlign = 'center';
  g.fillText("Rock", V[0][0], V[0][1] - 6); g.fillText("Paper", V[1][0] + 8, V[1][1] + 15); g.fillText("Scissors", V[2][0] - 8, V[2][1] + 15);
  const cen = pt([1 / 3, 1 / 3, 1 / 3]); g.beginPath(); g.arc(cen[0], cen[1], 3, 0, 7); g.fill();
  const line = (key, col, wdt) => { g.strokeStyle = col; g.lineWidth = wdt; g.beginPath(); trail.forEach((q, i) => { const p = pt(q[key]); i ? g.lineTo(p[0], p[1]) : g.moveTo(p[0], p[1]); }); g.stroke(); };
  g.globalAlpha = 0.55; line('c', css('--cur'), 1); g.globalAlpha = 1; line('a', css('--main'), 2);
  const last = trail[trail.length - 1], pc = pt(last.c), pa = pt(last.a);
  g.fillStyle = css('--cur'); g.beginPath(); g.arc(pc[0], pc[1], 4, 0, 7); g.fill();
  g.fillStyle = css('--main'); g.beginPath(); g.arc(pa[0], pa[1], 5, 0, 7); g.fill();
  const f3 = (p) => p.map((x) => x.toFixed(2)).join(', ');
  $('rstats').textContent = i18nFmt("round %t% · current (R, P, S) = (%c%) · average = (%a%) · mean payoff of A = %g%", { t: rt, c: f3(last.c), a: f3(last.a), g: (rt ? gainSum / rt : 0).toFixed(3) });
  $('rnote').textContent = rpsMode === 'self' ? "Self-play: the current strategy orbits forever, but the average converges to (1/3, 1/3, 1/3) and the mean payoff to 0 — the value of the game." : "Against 50% rock the best response is pure paper, worth 0.25 per round. Regret matching finds it: the mean payoff climbs toward 0.25.";
}
$('r10').onclick = () => rpsRun(10);
$('r1000').onclick = () => rpsRun(1000);
$('rreset').onclick = rpsReset;
$('mode').onchange = rpsReset;

doReset();
rpsReset();
if (window.matchMedia) window.matchMedia('(prefers-color-scheme: dark)').addEventListener?.('change', () => { drawKuhn(); drawRPS(); });

<!-- CFR demo: a real Counterfactual Regret Minimization solver for Kuhn poker, plus a regret-matching panel for rock-paper-scissors. -->
<h3>1 · Solve Kuhn poker with CFR</h3>
<p class="hint">Kuhn poker: three cards (J &lt; Q &lt; K), each player antes 1 chip and gets one card, one bet of 1 chip is allowed. The solver below runs genuine CFR self-play over all 12 information sets. Press the buttons and watch the <b>exploitability</b> of the average strategy fall, the game value approach <b>−1/18</b> for player 1, and the J-bluff appear on its own.</p>
<div class="row">
  <label for="algo">Algorithm:</label>
  <select id="algo">
    <option value="cfr">Vanilla CFR (2007)</option>
    <option value="cfrplus">CFR+ (2014)</option>
  </select>
</div>
<div class="btns">
  <button id="b1" type="button">+1 iteration</button>
  <button id="b100" type="button">+100</button>
  <button id="b1000" type="button">+1000</button>
  <button id="brun" type="button">Run to 20,000</button>
  <button id="breset" type="button" class="ghost">Reset</button>
</div>
<div class="status" id="status"></div>
<div class="lbl">Exploitability of the average strategy (log–log)</div>
<canvas id="plot" width="340" height="150" aria-label="Exploitability versus iterations on a log-log scale"></canvas>
<div class="legend"><span class="sw solid"></span>exploitability <span class="sw dash"></span>reference slope 1/√T</div>
<div class="stats" id="stats"></div>
<div class="alpha" id="alpha"></div>
<div class="tblwrap">
  <table class="strat">
    <thead><tr><th>Information set</th><th>Action</th><th>Learned P</th><th>Nash (for this α)</th></tr></thead>
    <tbody id="tbody"></tbody>
  </table>
</div>
<hr>
<!-- Second panel: plain regret matching on rock-paper-scissors, drawn on the probability simplex. -->
<h3>2 · Regret matching in rock-paper-scissors</h3>
<p class="hint">The building block of CFR on a one-shot game. Each player plays in proportion to its positive regrets. In self-play the current strategy (orange) keeps circling, but the <b>average</b> strategy (blue) spirals into the Nash equilibrium (1/3, 1/3, 1/3). Against a rock-heavy opponent, regret matching discovers paper.</p>
<div class="row">
  <label for="mode">Opponent:</label>
  <select id="mode">
    <option value="self">Self-play (another regret matcher)</option>
    <option value="fixed">Fixed bot: 50% rock, 25% paper, 25% scissors</option>
  </select>
</div>
<div class="btns">
  <button id="r10" type="button">+10 rounds</button>
  <button id="r1000" type="button">+1000 rounds</button>
  <button id="rreset" type="button" class="ghost">New random start</button>
</div>
<canvas id="simplex" width="240" height="210" aria-label="Strategy of player A on the rock-paper-scissors simplex"></canvas>
<div class="legend"><span class="dot cur"></span>current strategy <span class="dot avg"></span>average strategy</div>
<div class="stats" id="rstats"></div>
<div class="note" id="rnote"></div>

/* Layout and colors. Colors live in CSS variables so the canvases can follow light/dark mode. */
* { box-sizing: border-box; }
:root { --ink: #1f2933; --muted: #5b6774; --line: #cfd8e1; --bg2: #f3f6f9; --main: #1d3557; --accent: #e63946; --ref: #8a96a3; --good: #2a9d8f; --bar: #457b9d; --cur: #f4a261; }
body { font-family: system-ui, sans-serif; color: var(--ink); margin: 0; }
h3 { font-size: 1rem; margin: .2rem 0 .3rem; }
hr { border: 0; border-top: 1px solid var(--line); margin: 1rem 0 .6rem; }
.hint { font-size: .86rem; color: var(--muted); margin: 0 0 .5rem; line-height: 1.45; }
.row { display: flex; align-items: center; gap: .5rem; flex-wrap: wrap; font-size: .9rem; margin: .3rem 0; }
select { font: 14px system-ui, sans-serif; padding: .25rem .4rem; border-radius: 6px; border: 1px solid var(--line); background: var(--bg2); color: var(--ink); }
.btns { display: flex; gap: .4rem; flex-wrap: wrap; margin: .35rem 0; }
button { font: 600 13px system-ui, sans-serif; padding: .4rem .7rem; border: 1px solid var(--main); background: var(--main); color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: transparent; color: var(--main); }
.status { font-size: .9rem; font-weight: 600; margin: .35rem 0; min-height: 1.4em; line-height: 1.35; }
.lbl { font-size: .76rem; font-weight: 700; text-transform: uppercase; letter-spacing: .04em; color: var(--muted); margin: .4rem 0 .25rem; }
canvas { width: 100%; max-width: 340px; border: 1px solid var(--line); border-radius: 6px; display: block; }
#simplex { max-width: 240px; }
.legend { font-size: .78rem; color: var(--muted); margin: .25rem 0; display: flex; align-items: center; gap: .3rem; flex-wrap: wrap; }
.sw { display: inline-block; width: 18px; height: 0; border-top: 2px solid var(--main); margin-left: .4rem; }
.sw.dash { border-top: 2px dashed var(--ref); }
.dot { display: inline-block; width: 10px; height: 10px; border-radius: 50%; margin-left: .4rem; }
.dot.cur { background: var(--cur); }
.dot.avg { background: var(--main); }
.stats { font: 12px ui-monospace, monospace; color: var(--muted); margin: .3rem 0; line-height: 1.5; }
.alpha { font-size: .85rem; margin: .3rem 0 .5rem; line-height: 1.4; }
.note { font-size: .84rem; color: var(--muted); line-height: 1.4; }
.tblwrap { overflow-x: auto; }
table.strat { border-collapse: collapse; width: 100%; font-size: .8rem; }
.strat th, .strat td { border-bottom: 1px solid var(--line); padding: .25rem .3rem; text-align: left; vertical-align: middle; }
.strat th { color: var(--muted); font-weight: 700; }
.strat td.num { font: 12px ui-monospace, monospace; white-space: nowrap; }
.bar { display: inline-block; width: 46px; height: 8px; background: var(--bg2); border: 1px solid var(--line); border-radius: 4px; vertical-align: middle; margin-right: 4px; overflow: hidden; }
.bar i { display: block; height: 100%; background: var(--bar); }
.strat tr.p2 td:first-child { color: var(--good); }
@media (prefers-color-scheme: dark) {
  /* Dark-mode palette. */
  :root { --ink: #e3e8ee; --muted: #a7b3c0; --line: #36495d; --bg2: #1f2a36; --main: #9fc5e8; --accent: #ff6b6b; --ref: #8796a6; --good: #6fd3c4; --bar: #7fb3d8; --cur: #f4b26a; }
  button { color: #111; }
  button.ghost { color: var(--main); }
}

const i18nFmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Counterfactual Regret Minimization on Kuhn poker. Cards: 0 = J, 1 = Q, 2 = K. Actions: p = pass (check/fold), b = bet (bet/call).
// An information set is the acting player's card plus the public history, e.g. '1pb' = player 1 holds Q, checked, and now faces a bet.
// Each iteration walks the full game tree for all 6 deals, updates counterfactual regrets and accumulates the average strategy.
const CARD = ['J', 'Q', 'K'];
const DEALS = [[0, 1], [0, 2], [1, 0], [1, 2], [2, 0], [2, 1]];
// The 12 information sets: 6 for player 1 (opening, or after check-bet) and 6 for player 2 (after a check, or after a bet).
const P1_KEYS = ['0', '1', '2', '0pb', '1pb', '2pb'];
const P2_KEYS = ['0p', '1p', '2p', '0b', '1b', '2b'];
const KEYS = P1_KEYS.concat(P2_KEYS);
let R = {}, S = {}, sigma = {}, iter = 0, plus = false, hist = [], timer = null;

function isTerminal(h) { return h === 'pp' || h === 'bp' || h === 'bb' || h === 'pbp' || h === 'pbb'; }
// Net chips won by player 1 at a terminal history (ante 1, bet 1).
function payoff1(h, c1, c2) {
  const win = c1 > c2 ? 1 : -1;
  if (h === 'pp') return win;
  if (h === 'bp') return 1;
  if (h === 'pbp') return -1;
  return 2 * win;
}
function toAct(h) { return h.length % 2; }

function resetCFR() {
  R = {}; S = {};
  for (const k of KEYS) { R[k] = [0, 0]; S[k] = [0, 0]; }
  iter = 0; hist = [];
}
// Regret matching: play each action in proportion to its positive regret; uniform if none is positive.
function regretMatch(r) {
  let z = 0; const p = r.map((x) => { const y = Math.max(x, 0); z += y; return y; });
  return z > 0 ? p.map((y) => y / z) : r.map(() => 1 / r.length);
}
function snapshot() { for (const k of KEYS) sigma[k] = regretMatch(R[k]); }
function avgStrat(k) { const s = S[k], z = s[0] + s[1]; return z > 0 ? [s[0] / z, s[1] / z] : [0.5, 0.5]; }

// Recursive CFR. p0, p1 = reach probabilities of each player; u = the player whose regrets we update; w = weight for the average.
// Returns the expected payoff of player 1 below history h under the current strategy profile.
function cfr(h, c, p0, p1, u, w) {
  if (isTerminal(h)) return payoff1(h, c[0], c[1]);
  const pl = toAct(h), k = c[pl] + h, s = sigma[k];
  const v = [0, 0]; let node = 0;
  for (let a = 0; a < 2; a++) {
    const nh = h + (a ? 'b' : 'p');
    v[a] = pl === 0 ? cfr(nh, c, p0 * s[a], p1, u, w) : cfr(nh, c, p0, p1 * s[a], u, w);
    node += s[a] * v[a];
  }
  if (pl === u) {
    const sign = pl === 0 ? 1 : -1;
    const opp = pl === 0 ? p1 : p0, own = pl === 0 ? p0 : p1;
    for (let a = 0; a < 2; a++) {
      R[k][a] += (opp / 6) * sign * (v[a] - node);   // counterfactual regret, weighted by the opponent's (and chance's) reach
      S[k][a] += w * own * s[a];                     // average strategy, weighted by own reach
    }
  }
  return node;
}

function pass(u, w) {
  for (const d of DEALS) cfr('', d, 1, 1, u, w);
  // CFR+: clip regrets at zero after each pass (regret-matching+).
  if (plus) for (const k of (u === 0 ? P1_KEYS : P2_KEYS)) R[k] = R[k].map((x) => Math.max(x, 0));
}
function iterate() {
  iter++;
  if (plus) { snapshot(); pass(0, iter); snapshot(); pass(1, iter); }
  else { snapshot(); pass(0, 1); pass(1, 1); }
}

// Exact expected value of a profile: f0 and f1 map an information set to [P(pass), P(bet)].
function ev(h, c, f0, f1) {
  if (isTerminal(h)) return payoff1(h, c[0], c[1]);
  const pl = toAct(h), s = (pl === 0 ? f0 : f1)(c[pl] + h);
  return s[0] * ev(h + 'p', c, f0, f1) + s[1] * ev(h + 'b', c, f0, f1);
}
function value(f0, f1) { let t = 0; for (const d of DEALS) t += ev('', d, f0, f1); return t / 6; }
// Best response by brute force: each player has only 2^6 = 64 pure strategies, so try them all.
function pure(keys, mask) { return (k) => { const i = keys.indexOf(k); return (mask >> i) & 1 ? [0, 1] : [1, 0]; }; }
function bestResponses() {
  let br1 = -Infinity, br2 = -Infinity;
  for (let m = 0; m < 64; m++) {
    br1 = Math.max(br1, value(pure(P1_KEYS, m), avgStrat));
    br2 = Math.max(br2, -value(avgStrat, pure(P2_KEYS, m)));
  }
  return { br1, br2, expl: (br1 + br2) / 2 };
}
function record() { const b = bestResponses(); hist.push({ t: iter, e: Math.max(b.expl, 1e-9) }); return b; }
function shouldRecord() { return iter <= 20 || iter % Math.ceil(iter / 40) === 0; }
function runN(n) { for (let i = 0; i < n; i++) { iterate(); if (shouldRecord()) record(); } }

// User interface: plot, strategy table, buttons.
const $ = (id) => document.getElementById(id);
function css(v) { return getComputedStyle(document.documentElement).getPropertyValue(v).trim(); }
function setStatus(t) { $('status').textContent = t; }
const fmt = (x, d) => (Math.abs(x) < 5e-4 ? 0 : x).toFixed(d);

function drawPlot() {
  const cv = $('plot'), g = cv.getContext('2d'), W = cv.width, H = cv.height;
  g.clearRect(0, 0, W, H);
  const pad = { l: 34, r: 8, t: 8, b: 20 };
  const xmax = Math.max(10, iter), lx = (t) => pad.l + (Math.log10(t) / Math.log10(xmax)) * (W - pad.l - pad.r);
  const es = hist.map((p) => p.e);
  const ymax = Math.log10(Math.max(0.5, ...es)), ymin = Math.min(-3, Math.floor(Math.log10(Math.min(1, ...es))));
  const ly = (e) => pad.t + ((ymax - Math.log10(e)) / (ymax - ymin)) * (H - pad.t - pad.b);
  g.strokeStyle = css('--line'); g.fillStyle = css('--muted'); g.font = '10px system-ui, sans-serif'; g.lineWidth = 1;
  for (let y = Math.ceil(ymin); y <= Math.floor(ymax); y++) {
    g.beginPath(); g.moveTo(pad.l, ly(10 ** y)); g.lineTo(W - pad.r, ly(10 ** y)); g.stroke();
    g.fillText('1e' + y, 2, ly(10 ** y) + 3);
  }
  for (let x = 1; x <= xmax; x *= 10) g.fillText(String(x), lx(x) - 3, H - 5);
  if (!hist.length) return;
  // Dashed reference curve proportional to 1/√T, anchored at the first point.
  const c0 = hist[0].e * Math.sqrt(hist[0].t);
  g.setLineDash([4, 4]); g.strokeStyle = css('--ref'); g.beginPath();
  for (let i = 0; i <= 40; i++) { const t = Math.pow(xmax, i / 40); const y = c0 / Math.sqrt(t); i ? g.lineTo(lx(t), ly(y)) : g.moveTo(lx(t), ly(y)); }
  g.stroke(); g.setLineDash([]);
  g.strokeStyle = css('--main'); g.lineWidth = 2; g.beginPath();
  hist.forEach((p, i) => (i ? g.lineTo(lx(p.t), ly(p.e)) : g.moveTo(lx(p.t), ly(p.e))));
  g.stroke();
}

function rowsSpec(a) {
  const third = 1 / 3;
  return [
    ['0', "P1 holds %c%, acts first", "bet", 1, a], ['1', "P1 holds %c%, acts first", "bet", 1, 0], ['2', "P1 holds %c%, acts first", "bet", 1, Math.min(1, 3 * a)],
    ['0pb', "P1 holds %c%, checked, faces a bet", "call", 1, 0], ['1pb', "P1 holds %c%, checked, faces a bet", "call", 1, Math.min(1, a + third)], ['2pb', "P1 holds %c%, checked, faces a bet", "call", 1, 1],
    ['0p', "P2 holds %c%, P1 checked", "bet", 2, third], ['1p', "P2 holds %c%, P1 checked", "bet", 2, 0], ['2p', "P2 holds %c%, P1 checked", "bet", 2, 1],
    ['0b', "P2 holds %c%, P1 bet", "call", 2, 0], ['1b', "P2 holds %c%, P1 bet", "call", 2, third], ['2b', "P2 holds %c%, P1 bet", "call", 2, 1]
  ];
}
function drawTable() {
  const a = avgStrat('0')[1];
  const tb = $('tbody'); tb.innerHTML = '';
  for (const [k, label, act, pl, th] of rowsSpec(a)) {
    const p = avgStrat(k)[1];
    const tr = document.createElement('tr'); if (pl === 2) tr.className = 'p2';
    const td1 = document.createElement('td'); td1.textContent = i18nFmt(label, { c: CARD[+k[0]] });
    const td2 = document.createElement('td'); td2.textContent = act;
    const td3 = document.createElement('td'); td3.className = 'num';
    const bar = document.createElement('span'); bar.className = 'bar'; const fill = document.createElement('i'); fill.style.width = (p * 100).toFixed(1) + '%'; bar.appendChild(fill);
    td3.appendChild(bar); td3.appendChild(document.createTextNode(fmt(p, 3)));
    const td4 = document.createElement('td'); td4.className = 'num'; td4.textContent = fmt(th, 3);
    tr.append(td1, td2, td3, td4); tb.appendChild(tr);
  }
  $('alpha').textContent = i18nFmt("Learned α = P(P1 bets with J) = %a% — a pure bluff. Equilibria form a family with α ∈ [0, 1/3]: K should bet 3α (learned %k%, theory %k3%) and Q should call a bet with α + 1/3 (learned %q%, theory %q3%).", { a: fmt(a, 3), k: fmt(avgStrat('2')[1], 3), k3: fmt(Math.min(1, 3 * a), 3), q: fmt(avgStrat('1pb')[1], 3), q3: fmt(Math.min(1, a + 1 / 3), 3) });
}
function drawKuhn() {
  const last = hist.length ? hist[hist.length - 1] : null;
  const v = iter ? value(avgStrat, avgStrat) : 0;
  $('stats').textContent = i18nFmt("iteration %t% · exploitability %e% chips/hand · value for P1 %v% (theory −1/18 ≈ −0.0556)", { t: iter, e: last ? last.e.toExponential(2) : '—', v: fmt(v, 4) });
  drawPlot(); drawTable();
}
function stopRun() { if (timer) { clearInterval(timer); timer = null; } $('brun').textContent = "Run to 20,000"; }
function doReset() {
  stopRun(); plus = $('algo').value === 'cfrplus'; resetCFR(); drawKuhn();
  setStatus(plus ? "CFR+ selected: regrets are clipped at zero, updates alternate, the average is weighted linearly. Compare the slope with vanilla CFR." : "Regrets are zero, so both players start uniformly at random. Press a button to iterate.");
}
function afterBatch() { if (!hist.length || hist[hist.length - 1].t !== iter) record(); drawKuhn(); setStatus(i18nFmt("Done: %t% iterations. The table shows the average strategy, which is what converges to equilibrium.", { t: iter })); }
$('b1').onclick = () => { stopRun(); runN(1); afterBatch(); };
$('b100').onclick = () => { stopRun(); runN(100); afterBatch(); };
$('b1000').onclick = () => { stopRun(); runN(1000); afterBatch(); };
$('breset').onclick = doReset;
$('algo').onchange = doReset;
$('brun').onclick = () => {
  if (timer) { stopRun(); setStatus(i18nFmt("Paused at iteration %t%.", { t: iter })); return; }
  $('brun').textContent = "Pause"; setStatus("Running self-play…");
  timer = setInterval(() => {
    runN(Math.max(1, Math.floor(iter / 25)));
    drawKuhn();
    if (iter >= 20000) { stopRun(); afterBatch(); }
  }, 40);
};

// Regret matching (Hart & Mas-Colell, 2000) on rock-paper-scissors with exact expected payoffs.
// Index 0 = rock, 1 = paper, 2 = scissors; u(i, j) is the payoff of i against j.
const FIXED = [0.5, 0.25, 0.25];
const u = (i, j) => (i === j ? 0 : (i - j + 3) % 3 === 1 ? 1 : -1);
let rA, rB, sA, sB, rt, trail, rpsMode = 'self', gainSum = 0;
function rpsReset() {
  rpsMode = $('mode').value;
  const rnd = () => [0, 1, 2].map(() => Math.round(Math.random() * 6));
  rA = rnd(); rB = rnd(); sA = [0, 0, 0]; sB = [0, 0, 0]; rt = 0; gainSum = 0;
  trail = [{ c: regretMatch(rA), a: regretMatch(rA) }];
  drawRPS();
}
function rpsStep() {
  const pA = regretMatch(rA), pB = rpsMode === 'self' ? regretMatch(rB) : FIXED;
  const uA = [0, 1, 2].map((i) => pB[0] * u(i, 0) + pB[1] * u(i, 1) + pB[2] * u(i, 2));
  const vA = pA[0] * uA[0] + pA[1] * uA[1] + pA[2] * uA[2];
  for (let i = 0; i < 3; i++) { rA[i] += uA[i] - vA; sA[i] += pA[i]; }
  gainSum += vA;
  if (rpsMode === 'self') {
    const uB = [0, 1, 2].map((j) => pA[0] * u(j, 0) + pA[1] * u(j, 1) + pA[2] * u(j, 2));
    const vB = pB[0] * uB[0] + pB[1] * uB[1] + pB[2] * uB[2];
    for (let j = 0; j < 3; j++) { rB[j] += uB[j] - vB; sB[j] += pB[j]; }
  }
  rt++;
}
function rpsAvg() { const z = sA[0] + sA[1] + sA[2]; return z > 0 ? sA.map((x) => x / z) : regretMatch(rA); }
function rpsRun(n) { for (let i = 0; i < n; i++) { rpsStep(); if (rt <= 200 || rt % 5 === 0) trail.push({ c: regretMatch(rA), a: rpsAvg() }); } if (trail.length > 600) trail = trail.slice(-600); drawRPS(); }
// Draw the strategy simplex: each corner is a pure strategy, the center is the Nash equilibrium.
function drawRPS() {
  const cv = $('simplex'), g = cv.getContext('2d'), W = cv.width, H = cv.height;
  g.clearRect(0, 0, W, H);
  const V = [[W / 2, 18], [20, H - 22], [W - 20, H - 22]];
  const pt = (p) => [p[0] * V[0][0] + p[1] * V[1][0] + p[2] * V[2][0], p[0] * V[0][1] + p[1] * V[1][1] + p[2] * V[2][1]];
  g.strokeStyle = css('--line'); g.lineWidth = 1; g.beginPath(); g.moveTo(...V[0]); g.lineTo(...V[1]); g.lineTo(...V[2]); g.closePath(); g.stroke();
  g.fillStyle = css('--muted'); g.font = '11px system-ui, sans-serif'; g.textAlign = 'center';
  g.fillText("Rock", V[0][0], V[0][1] - 6); g.fillText("Paper", V[1][0] + 8, V[1][1] + 15); g.fillText("Scissors", V[2][0] - 8, V[2][1] + 15);
  const cen = pt([1 / 3, 1 / 3, 1 / 3]); g.beginPath(); g.arc(cen[0], cen[1], 3, 0, 7); g.fill();
  const line = (key, col, wdt) => { g.strokeStyle = col; g.lineWidth = wdt; g.beginPath(); trail.forEach((q, i) => { const p = pt(q[key]); i ? g.lineTo(p[0], p[1]) : g.moveTo(p[0], p[1]); }); g.stroke(); };
  g.globalAlpha = 0.55; line('c', css('--cur'), 1); g.globalAlpha = 1; line('a', css('--main'), 2);
  const last = trail[trail.length - 1], pc = pt(last.c), pa = pt(last.a);
  g.fillStyle = css('--cur'); g.beginPath(); g.arc(pc[0], pc[1], 4, 0, 7); g.fill();
  g.fillStyle = css('--main'); g.beginPath(); g.arc(pa[0], pa[1], 5, 0, 7); g.fill();
  const f3 = (p) => p.map((x) => x.toFixed(2)).join(', ');
  $('rstats').textContent = i18nFmt("round %t% · current (R, P, S) = (%c%) · average = (%a%) · mean payoff of A = %g%", { t: rt, c: f3(last.c), a: f3(last.a), g: (rt ? gainSum / rt : 0).toFixed(3) });
  $('rnote').textContent = rpsMode === 'self' ? "Self-play: the current strategy orbits forever, but the average converges to (1/3, 1/3, 1/3) and the mean payoff to 0 — the value of the game." : "Against 50% rock the best response is pure paper, worth 0.25 per round. Regret matching finds it: the mean payoff climbs toward 0.25.";
}
$('r10').onclick = () => rpsRun(10);
$('r1000').onclick = () => rpsRun(1000);
$('rreset').onclick = rpsReset;
$('mode').onchange = rpsReset;

doReset();
rpsReset();
if (window.matchMedia) window.matchMedia('(prefers-color-scheme: dark)').addEventListener?.('change', () => { drawKuhn(); drawRPS(); });

Result

Console

What to look for:

The value converges to −1/18. Acting first is a disadvantage: in equilibrium player 1 loses $1/18 \approx 0.0556$ chips per hand.
The bluff appears by itself. Nobody told the algorithm to bet with the jack, the card that can never win a showdown. Yet the learned probability of that bet settles somewhere between $0$ and $1/3$ — a bluff.
There is a whole family of equilibria. Kuhn showed that player 1's optimal strategies form a one-parameter family: bet the jack with probability $\alpha \in [0, 1/3]$ , bet the king with probability $3\alpha$ , always check the queen, and after check–bet call with the queen with probability $\alpha + 1/3$ . Reset and rerun with the other algorithm: you may land on a different $\alpha$ , but the relations between the rows still hold. Player 2's equilibrium strategy, by contrast, is unique: bluff-bet the jack $1/3$ of the time after a check, call a bet with the queen $1/3$ of the time.
CFR versus CFR+. On the log–log plot vanilla CFR roughly follows the dashed $1/\sqrt{T}$ line; CFR+ drops much faster.
Rock-paper-scissors shows the engine in isolation: the current strategy cycles around the triangle, the average spirals into the centre.

The Real Complexity

Measuring progress: exploitability. For a strategy profile $\bar\sigma = (\bar\sigma_1, \bar\sigma_2)$ of a two-player zero-sum game, define

\varepsilon(\bar\sigma) = \tfrac12 \Big( \max_{\sigma_1'} u_1(\sigma_1', \bar\sigma_2) + \max_{\sigma_2'} u_2(\bar\sigma_1, \sigma_2') \Big) \ge 0 .

It is zero exactly at a Nash equilibrium and measures how much a perfect opponent could win. Poker researchers report it in milli-big-blinds per game (mbb/g).

Convergence rate. With regret matching at each information set, Zinkevich et al. proved that player $i$ 's average regret after $T$ iterations satisfies

\frac{R_i^T}{T} \le \frac{\Delta_i \, |\mathcal{I}_i| \sqrt{|A_i|}}{\sqrt{T}},

where $\Delta_i$ is the payoff range, $|\mathcal{I}_i|$ the number of information sets and $|A_i|$ the maximum number of actions. So exploitability falls like $O(1/\sqrt{T})$ , and reaching $\varepsilon$ takes $O(1/\varepsilon^2)$ iterations. Two caveats: the guarantee is for the average strategy (the current one need not converge), and the constant grows with the size of the game.

Cost per iteration. Vanilla CFR walks the whole game tree: $O(|H|)$ time per iteration, where $|H|$ is the number of histories. Memory is two tables (cumulative regret and strategy sum), one entry per information-set–action pair: $O\big(\sum_I |A(I)|\big)$ , linear in the strategy representation and much smaller than the tree when information sets are large.

The exact alternative. Two-player zero-sum extensive games can also be solved exactly by a linear program of polynomial size using the sequence form (Koller, Megiddo and von Stengel, 1994; von Stengel, 1996). In theory that is better — polynomial time, not $1/\varepsilon^2$ . In practice LP solvers need memory far beyond the tree for big games, while CFR streams through it with tiny state, which is why CFR-family methods solved the record-size poker games.

The variants that made it scale.

CFR+ (Oskari Tammelin, 2014): clip cumulative regrets at zero after every update (regret-matching $^+$ ), alternate the players' updates and weight later iterations more in the average. Its worst-case bound is still $O(1/\sqrt{T})$ , but in practice it converges far faster, often looking closer to $O(1/T)$ — exactly what the demo's plot shows.
Monte Carlo CFR (Lanctot, Waugh, Zinkevich and Bowling, NIPS 2009): sample chance outcomes or opponent actions instead of walking the full tree. Each iteration becomes much cheaper while regrets stay unbiased in expectation.
Discounted and linear CFR (Brown and Sandholm, AAAI 2019): down-weight early, bad iterations.
Deep CFR (Brown, Lerer, Gross and Sandholm, ICML 2019): replace the regret tables with neural networks trained on sampled regrets, so information sets never need to be enumerated.

Abstraction and subgame solving. Heads-up no-limit Texas hold'em has on the order of $10^{161}$ decision points, far too many for any table. Practical systems solve a coarser abstraction (similar hands and bet sizes bucketed together) to get a "blueprint", then refine it during play by re-solving the subgame actually reached — with care, because naively re-solving a subgame of an imperfect-information game can make the strategy more exploitable.

Where the guarantees stop. Everything above relies on two-player zero-sum structure. In general-sum or multiplayer games, no-regret self-play converges only to the weaker set of (coarse) correlated equilibria, and computing a Nash equilibrium is PPAD-complete even for two-player general-sum games. The six-player poker bot Pluribus works extremely well, but it has no equilibrium guarantee — its success is empirical.

Where It Matters

CFR turned poker, a long-standing grand challenge for AI, into a series of milestones:

2007 — abstractions of limit hold'em. The original paper already solved abstracted heads-up limit Texas hold'em games with up to $10^{12}$ states, two orders of magnitude beyond previous methods.
2015 — Cepheus. Using CFR+, Michael Bowling, Neil Burch, Michael Johanson and Oskari Tammelin computed a strategy for the full game of heads-up limit Texas hold'em with exploitability below 1 mbb/g and announced in Science that the game is "essentially weakly solved": its remaining edge is so small that it could not be beaten with statistical confidence even over a human lifetime of play.
2017 — DeepStack. Matej Moravčík and colleagues (Science, 2017) combined CFR-style re-solving at every decision with deep neural networks that estimate the value of the rest of the game — a kind of learned intuition — and beat professional players at heads-up no-limit hold'em.
2017 — Libratus. Noam Brown and Tuomas Sandholm's bot played 120,000 hands of heads-up no-limit over 20 days in January 2017 against four top professionals and won decisively, about 14.7 big blinds per 100 hands (Science, published online December 2017). It combined an MCCFR blueprint, safe nested subgame solving and a self-improver that patched holes the humans found.
2019 — Pluribus. Brown and Sandholm (Science, 2019) beat elite professionals at six-player no-limit hold'em. Its blueprint was computed by MCCFR self-play in eight days on a single 64-core server — about 144 US dollars of cloud compute.

The ideas spread beyond cards. Regret minimization is a general tool for any setting with hidden information and strategic opponents: negotiation and auctions, security and patrolling games, the Colonel Blotto-style resource-allocation games of military planning, and multi-agent research in general. Later work merged CFR with the self-play and search of AlphaGo: ReBeL (Brown et al., NeurIPS 2020) and Student of Games (Schmid et al., 2023) use one algorithm for both perfect- and imperfect-information games, bridging the gap with reinforcement learning.

Conclusion

Counterfactual Regret Minimization rests on a disarmingly human idea: after every hand, ask "how much better would I have done if I had played differently here?", and lean toward the moves you regret not making. Done at every information set, against a copy of yourself, the average of everything you played becomes a strategy no one can exploit.

Nothing in the algorithm mentions deception, yet the Kuhn demo learns to bet the jack — the card that can never win a showdown — because an equilibrium has to keep the opponent guessing. Von Neumann's 1944 insight that bluffing is part of rational play reappears as a number on a screen. That is the real lesson of CFR: in games of hidden information, the right goal is not to read your opponent, but to become unreadable.

Comments

Loading comments...

https://www.kipuhub.com/en/article/counterfactual-regret-minimization/Content licensed under CC BY-NC 4.0.

Cookies & privacy

How AI learned to bluff at poker