5D Library › Imperfect-Information Stochastic Games, Bayesian Hand-Reading and Counterfactual Regret Minimisation in Four-Player Tile Dynamics · 中文

Chapter 6. Solving the Game, and the Money

This chapter has two parts. The first deals with how to solve the game, and reports two negative results; the second deals with how much to stake, and corrects a popular claim.

Part one: regret minimisation

Two-player zero-sum: where the theorem holds

Evidence

Regret matching and counterfactual regret minimisation. Hart and Mas-Colell proved that a simple adaptive procedure, regret matching, leads to correlated equilibrium (Hart and Mas-Colell 2000). Zinkevich, Johanson, Bowling and Piccione extended it to imperfect-information extensive-form games as counterfactual regret minimisation (CFR): in a two-player zero-sum game the average strategy converges to a Nash equilibrium (Zinkevich et al. 2008). The method underpins a sequence of later results: the solution of heads-up limit hold’em (Bowling et al. 2015), DeepStack (Moravčík et al. 2017) and Libratus (Brown and Sandholm 2018).

The book verifies that guarantee on a toy game that can be solved exactly — Kuhn’s one-card poker (Kuhn 1950).

Calculation

# Chapter 6. Counterfactual regret minimisation where it is guaranteed to
# work: a two-player zero-sum game. The toy game is the standard one-card
# betting game (Kuhn's game), an abstraction of "commit or fold with private
# information" small enough to solve exactly and large enough to have a
# non-trivial mixed equilibrium. Zinkevich and colleagues' result is that
# regret matching on counterfactual regrets converges, in the AVERAGE
# strategy, to a Nash equilibrium of a two-player zero-sum game. The program
# demonstrates that by computing exact exploitability, which falls toward
# zero. Programme p08 then removes the two-player condition. Standard library
# only; exact tree traversal, no sampling.
import math
from itertools import permutations

CARDS = [0, 1, 2]
ACTIONS = "pb"
NAMES = {0: "J", 1: "Q", 2: "K"}

class Node:
    def __init__(self):
        self.regret = [0.0, 0.0]
        self.strategy_sum = [0.0, 0.0]

    def strategy(self):
        r = [max(0.0, x) for x in self.regret]
        s = math.fsum(r)
        return [0.5, 0.5] if s <= 0 else [x / s for x in r]

    def average(self):
        s = math.fsum(self.strategy_sum)
        return [0.5, 0.5] if s <= 0 else [x / s for x in self.strategy_sum]

nodes = {}

def is_terminal(history):
    if len(history) < 2:
        return False
    return history[-1] == "p" or history[-2:] == "bb"

def terminal_util(history, cards):
    """Utility for the player who would act next at this terminal history,
    i.e. the
    standard Kuhn convention: the value is for `player = len(history) % 2`."""
    player = len(history) % 2
    opp = 1 - player
    higher = cards[player] > cards[opp]
    if history[-1] == "p":
        if history == "pp":
            return 1 if higher else -1
        return 1                      # the opponent folded to a bet
    return 2 if higher else -2        # double bet

def cfr(cards, history, p0, p1):
    """Returns the utility of `history` for the player about to act."""
    if is_terminal(history):
        return terminal_util(history, cards)
    player = len(history) % 2
    key = (cards[player], history)
    node = nodes.setdefault(key, Node())
    strat = node.strategy()
    util = [0.0, 0.0]
    node_util = 0.0
    for i, a in enumerate(ACTIONS):
        if player == 0:
            util[i] = -cfr(cards, history + a, p0 * strat[i], p1)
        else:
            util[i] = -cfr(cards, history + a, p0, p1 * strat[i])
        node_util += strat[i] * util[i]
    reach_opp = p1 if player == 0 else p0
    reach_self = p0 if player == 0 else p1
    for i in range(2):
        node.regret[i] += reach_opp * (util[i] - node_util)
        node.strategy_sum[i] += reach_self * strat[i]
    return node_util

# A best response must be measurable with respect to the responder's OWN
# information, so it cannot depend on the opponent's card. The tree is small
# enough to enumerate every deterministic strategy of the responder: each
# player has 6 information sets (3 cards x 2 histories at which they act),
# hence 2^6 = 64 pure strategies.
INFOSETS = {0: [(c, h) for h in ("", "pb") for c in CARDS],
            1: [(c, h) for h in ("b", "p") for c in CARDS]}

def value_for_p0(cards, history, strat0, strat1):
    """Expected value to player 0, both players following given strategy
    maps."""
    if is_terminal(history):
        u = terminal_util(history, cards)
        return u if len(history) % 2 == 0 else -u
    player = len(history) % 2
    probs = (strat0 if player == 0 else strat1)[(cards[player], history)]
    return math.fsum(
        probs[i] * value_for_p0(cards, history + a, strat0, strat1)
        for i, a in enumerate(ACTIONS)
    )

def pure_strategies(player):
    sets = INFOSETS[player]
    for mask in range(1 << len(sets)):
        yield {k: ([1.0, 0.0] if (mask >> i) & 1 == 0 else [0.0, 1.0])
               for i, k in enumerate(sets)}

def full(avg, player):
    """avg restricted to one player's information sets, defaulting to
    uniform."""
    return {k: avg.get(k, [0.5, 0.5]) for k in INFOSETS[player]}

def exploitability(avg):
    """Best-response value for each player against the other's average
    strategy.
    At equilibrium the two sum to zero (the game's value cancels)."""
    deals = list(permutations(CARDS, 2))
    s0, s1 = full(avg, 0), full(avg, 1)
    best0 = max(
        math.fsum(value_for_p0(c, "", p, s1) for c in deals) / len(deals)
        for p in pure_strategies(0)
    )
    best1 = max(
        math.fsum(-value_for_p0(c, "", s0, p) for c in deals) / len(deals)
        for p in pure_strategies(1)
    )
    return best0 + best1

def game_value(avg):
    deals = list(permutations(CARDS, 2))
    s0, s1 = full(avg, 0), full(avg, 1)
    return math.fsum(value_for_p0(c, "", s0, s1) for c in deals) / len(deals)

if __name__ == "__main__":
    deals = list(permutations(CARDS, 2))
    print(
        "Two-player zero-sum one-card betting game: 6 deals, 12 information"
        " sets."
    )
    print(
        "Exploitability = best-response value for p0 plus that for p1; it is"
        " zero"
    )
    print("exactly at equilibrium and positive otherwise.\n")
    print("   iterations   exploitability   value to player 0")
    marks = {1, 10, 100, 1000, 10000, 100000}
    ex = []
    for it in range(1, 100001):
        for cards in deals:
            cfr(cards, "", 1.0, 1.0)
        if it in marks:
            avg = {k: v.average() for k, v in nodes.items()}
            ex.append(exploitability(avg))
            print("   {:10d} {:16.6f} {:19.6f}"
                  .format(it, ex[-1], game_value(avg)))
    print("   (the game's known value to player 0 is -1/18 = {:.6f})"
          .format(-1.0 / 18.0))
    print("   exploitability falls from {:.3f} to {:.4f}"
          .format(ex[0], ex[-1]))

    avg = {k: v.average() for k, v in nodes.items()}
    print("\nAverage strategy (P(pass), P(bet)):")
    for key in sorted(avg, key=lambda k: (len(k[1]), k[1], k[0])):
        card, hist = key
        print("   card {}, history '{:3s}' -> pass {:.3f}, bet {:.3f}"
              .format(NAMES[card], hist or "-", avg[key][0], avg[key][1]))

    jb = avg[(0, "")][1]
    print(
        "\nThe known equilibria of this game have the first player betting"
        " the worst"
    )
    print(
        "card (J) at a rate alpha in [0, 1/3] and betting K at 3 x alpha."
        " Here the"
    )
    print(
        "average strategy bets J at {:.3f} and K at {:.3f}, a ratio of"
        " {:.2f},".format(
            jb, avg[(2, "")][1], avg[(2, "")][1] / jb if jb else float("nan")
        )
    )
    print(
        "against the predicted 3.00, and exploitability falls toward zero."
        " That is"
    )
    print("Zinkevich and colleagues' guarantee in action.")
    print(
        "\nWhat the guarantee rests on: TWO players and ZERO sum."
        " Programme p08"
    )
    print("removes the first condition and shows what survives.")
# Two-player zero-sum one-card betting game: 6 deals, 12 information sets.
# Exploitability = best-response value for p0 plus that for p1; it is zero
# exactly at equilibrium and positive otherwise.
#
#    iterations   exploitability   value to player 0
#             1         0.666667           -0.020833
#            10         0.182288           -0.035974
#           100         0.046601           -0.054715
#          1000         0.013010           -0.055178
#         10000         0.002972           -0.055531
#        100000         0.001265           -0.055554
#    (the game's known value to player 0 is -1/18 = -0.055556)
#    exploitability falls from 0.667 to 0.0013
#
# Average strategy (P(pass), P(bet)):
#    card J, history '-  ' -> pass 0.780, bet 0.220
#    card Q, history '-  ' -> pass 1.000, bet 0.000
#    card K, history '-  ' -> pass 0.337, bet 0.663
#    card J, history 'b  ' -> pass 1.000, bet 0.000
#    card Q, history 'b  ' -> pass 0.664, bet 0.336
#    card K, history 'b  ' -> pass 0.000, bet 1.000
#    card J, history 'p  ' -> pass 0.668, bet 0.332
#    card Q, history 'p  ' -> pass 1.000, bet 0.000
#    card K, history 'p  ' -> pass 0.000, bet 1.000
#    card J, history 'pb ' -> pass 1.000, bet 0.000
#    card Q, history 'pb ' -> pass 0.445, bet 0.555
#    card K, history 'pb ' -> pass 0.000, bet 1.000
#
# The known equilibria of this game have the first player betting the worst
# card (J) at a rate alpha in [0, 1/3] and betting K at 3 x alpha. Here the
# average strategy bets J at 0.220 and K at 0.663, a ratio of 3.01,
# against the predicted 3.00, and exploitability falls toward zero. That is
# Zinkevich and colleagues' guarantee in action.
#
# What the guarantee rests on: TWO players and ZERO sum. Programme p08
# removes the first condition and shows what survives.

The result is textbook. Exploitability falls from 0.667 to 0.0013; the game value converges to −0.055554-0.055554 against the known value to the first player of −1/18=−0.055556-1/18 = -0.055556; and the average strategy’s ratio of betting the worst card to betting the best is 3.01 against the 3.00 the equilibrium family predicts.

Note

Exploitability must be computed over information sets. The first implementation of this calculation in the writing of this book let the best response “see” both cards, and exploitability then stalled well above zero. A best response must be measurable with respect to the responder’s own information, so the program enumerates the responder’s 64 pure strategies (6 information sets, 2 actions each). The error is worth recording: it does not make the program fail, it only makes the convergence look as though it had.

Three players: the first negative result

The guarantee holds only for two-player zero-sum games, and that dividing line is much older than CFR.

Evidence

The line between two-player zero-sum and everything else is an old one. Robinson proved that an iterative method of solving a game — fictitious play — converges to the game’s value in two-player zero-sum games (Robinson 1951); Shapley then gave a non-zero-sum example in which the same iteration cycles forever and never converges (Shapley 1964). So “there is a theorem inside two-player zero-sum and none outside it” is not a peculiar weakness of CFR but a limit shared by this whole class of iterative methods.

So what happens with three?

Calculation

# Chapter 6. The same algorithm with three players, where the guarantee does
# not hold. Regret matching converges to a Nash equilibrium in two-player
# zero-sum games; with three or more players the convergence proof does not
# apply, and the average strategy need not be an equilibrium. Abou Risk and
# Szafron applied CFR to three-player poker empirically and reported that it
# produces strong agents without the guarantee. This program runs the same
# machinery on a three-player one-card game and measures exploitability
# properly (best response over each player's own information sets, by
# enumeration). The result to look for is NOT divergence but a FLOOR:
# exploitability falls and then stops, at a level the two-player version
# passes straight through. Standard library only; exact traversal.
import math
from itertools import permutations

CARDS = [0, 1, 2, 3]
ACTIONS = "pb"
NAMES = {0: "J", 1: "Q", 2: "K", 3: "A"}
N = 3

def is_terminal(history):
    return len(history) >= N

def payoffs(history, cards):
    """Three players each pass or bet once, in order. Each bettor stakes 1.
    The
    highest card among the bettors takes the pot of bets; if nobody bets,
    everyone
    scores 0. Zero sum across the three by construction."""
    bettors = [i for i in range(N) if history[i] == "b"]
    out = [0.0] * N
    if not bettors:
        return out
    pot = len(bettors)
    winner = max(bettors, key=lambda i: cards[i])
    for i in bettors:
        out[i] -= 1.0
    out[winner] += pot
    return out

class Node:
    def __init__(self):
        self.regret = [0.0, 0.0]
        self.strategy_sum = [0.0, 0.0]

    def strategy(self):
        r = [max(0.0, x) for x in self.regret]
        s = math.fsum(r)
        return [0.5, 0.5] if s <= 0 else [x / s for x in r]

    def average(self):
        s = math.fsum(self.strategy_sum)
        return [0.5, 0.5] if s <= 0 else [x / s for x in self.strategy_sum]

nodes = {}

def cfr(cards, history, reach):
    """reach: list of per-player reach probabilities. Returns the payoff
    vector."""
    if is_terminal(history):
        return payoffs(history, cards)
    player = len(history)
    key = (cards[player], history)
    node = nodes.setdefault(key, Node())
    strat = node.strategy()
    utils = []
    node_util = [0.0] * N
    for i, a in enumerate(ACTIONS):
        r2 = list(reach)
        r2[player] *= strat[i]
        u = cfr(cards, history + a, r2)
        utils.append(u)
        for j in range(N):
            node_util[j] += strat[i] * u[j]
    counterfactual = 1.0
    for j in range(N):
        if j != player:
            counterfactual *= reach[j]
    for i in range(2):
        node.regret[i] += counterfactual * (
            utils[i][player] - node_util[player]
        )
        node.strategy_sum[i] += reach[player] * strat[i]
    return node_util

INFOSETS = {
    p: [
        (c, h)
        for h in (
            "".join(x)
            for x in __import__("itertools").product(ACTIONS, repeat=p)
        )
        for c in CARDS
    ]
    for p in range(N)
}

def value_vec(cards, history, strats):
    if is_terminal(history):
        return payoffs(history, cards)
    player = len(history)
    probs = strats[player][(cards[player], history)]
    out = [0.0] * N
    for i, a in enumerate(ACTIONS):
        sub = value_vec(cards, history + a, strats)
        for j in range(N):
            out[j] += probs[i] * sub[j]
    return out

def pure_strategies(player):
    sets = INFOSETS[player]
    for mask in range(1 << len(sets)):
        yield {k: ([1.0, 0.0] if (mask >> i) & 1 == 0 else [0.0, 1.0])
               for i, k in enumerate(sets)}

def full(avg, player):
    return {k: avg.get(k, [0.5, 0.5]) for k in INFOSETS[player]}

DEALS = list(permutations(CARDS, N))

def exploitability(avg):
    """Sum over players of (best response value - value under the average
    profile).
    Zero if and only if the profile is a Nash equilibrium."""
    strats = [full(avg, p) for p in range(N)]
    base = [0.0] * N
    for c in DEALS:
        v = value_vec(c, "", strats)
        for j in range(N):
            base[j] += v[j] / len(DEALS)
    total = 0.0
    for p in range(N):
        best = -9e9
        for pure in pure_strategies(p):
            s2 = list(strats)
            s2[p] = pure
            val = math.fsum(value_vec(c, "", s2)[p] for c in DEALS) / len(
                DEALS
            )
            best = max(best, val)
        total += best - base[p]
    return total

if __name__ == "__main__":
    print(
        "Three-player one-card game: {} cards, {} deals, each player acts"
        " once.".format(len(CARDS), len(DEALS))
    )
    print(
        "Payoffs are zero sum across the three. Exploitability is the sum"
        " over"
    )
    print(
        "players of what each could gain by deviating; it is zero exactly at"
        " a Nash"
    )
    print("equilibrium.\n")
    print("   iterations   exploitability")
    marks = {1, 10, 100, 1000, 10000, 100000}
    hist = {}
    for it in range(1, 100001):
        for cards in DEALS:
            cfr(cards, "", [1.0] * N)
        if it in marks:
            avg = {k: v.average() for k, v in nodes.items()}
            e = exploitability(avg)
            hist[it] = e
            print("   {:10d} {:16.6f}".format(it, e))

    print(
        "\nIn THIS game exploitability does fall to {:.6f}, so the"
        " algorithm has".format(hist[100000])
    )
    print(
        "found something very close to an equilibrium. That has to be"
        " reported as"
    )
    print(
        "it is: the absence of a convergence theorem for three or more"
        " players does"
    )
    print(
        "NOT mean the algorithm fails. Abou Risk and Szafron's three-player"
        " poker"
    )
    print(
        "agents were likewise strong without a guarantee. What is missing"
        " is the"
    )
    print("assurance, not necessarily the result.")

    print(
        "\nBut there is a different multiplayer problem, and it does not go"
        " away when"
    )
    print(
        "the algorithm converges. In a two-player zero-sum game, playing an"
    )
    print(
        "equilibrium strategy GUARANTEES at least the game's value,"
        " whatever the"
    )
    print(
        "opponent does. With three players that guarantee is false: the"
        " other two"
    )
    print("can, between them, hold a player below their equilibrium payoff.")

    avg = {k: v.average() for k, v in nodes.items()}
    strats = [full(avg, p) for p in range(N)]
    eq_val = math.fsum(value_vec(c, "", strats)[0] for c in DEALS) / len(
        DEALS
    )
    print(
        "\n   player 0's payoff under the converged profile: {:+.6f}".format(
            eq_val
        )
    )

    # A few named, simple joint deviations by the other two. Player 0 does NOT
    # change strategy in any of these rows: only the opponents differ.
    def always(action):
        return lambda sets: {k: ([1.0, 0.0] if action == "p" else [0.0, 1.0])
                             for k in sets}

    def threshold(cut):
        """Bet only with a card at or above `cut`."""
        return lambda sets: {k: ([0.0, 1.0] if k[0] >= cut else [1.0, 0.0])
                             for k in sets}

    PROFILES = [("the converged profile", None),
                ("both always pass", always("p")),
                ("both always bet", always("b")),
                ("both bet only K or A", threshold(2)),
                ("both bet Q or better", threshold(1))]
    print(
        "\n   player 0 keeps the converged strategy throughout; only the"
        " other two"
    )
    print("   change. Player 0's payoff:")
    print(
        "   opponents' joint behaviour          player 0   the pair, combined"
    )
    rows = []
    for label, maker in PROFILES:
        if maker is None:
            s = strats
        else:
            s = [strats[0], maker(INFOSETS[1]), maker(INFOSETS[2])]
        v0 = math.fsum(value_vec(c, "", s)[0] for c in DEALS) / len(DEALS)
        vp = math.fsum(value_vec(c, "", s)[1] + value_vec(c, "", s)[2]
                       for c in DEALS) / len(DEALS)
        rows.append((label, v0, vp))
        print("   {:34s} {:+9.4f} {:19.4f}".format(label, v0, vp))

    worst = min(rows[1:], key=lambda r: r[1])
    print(
        "\n   A NEGATIVE result, reported as such. None of these four"
        " deviations"
    )
    print(
        "   leaves player 0 worse off than the converged profile does: the"
        " worst is"
    )
    print("   '{}' at {:+.4f}, against {:+.4f} under the converged"
          .format(worst[0], worst[1], eq_val))
    print("   profile.")
    print(
        "   Every other deviation makes player 0 BETTER off, because in this"
        " game"
    )
    print(
        "   betting loosely is simply a losing move and the deviators pay"
        " for it."
    )
    print(
        "\n   So this toy game does NOT exhibit the failure it was built to"
        " look for."
    )
    print(
        "   That has to be said plainly rather than glossed over, and it"
        " sharpens"
    )
    print("   what the multiplayer problem actually is:")
    print(
        "     * The two-player zero-sum GUARANTEE - that an equilibrium"
        " strategy"
    )
    print(
        "       secures at least the game's value against every opponent -"
        " has no"
    )
    print(
        "       multiplayer counterpart. That is a statement about which"
        " theorems"
    )
    print("       exist, and it is true regardless of this game.")
    print(
        "     * Whether the guarantee's absence BITES in a particular game"
        " is a"
    )
    print(
        "       separate, empirical question. Here it did not bite. The book"
        " does"
    )
    print(
        "       not have a worked example in which it does, and does not"
        " pretend to."
    )
    print(
        "\n   The full minimisation over the pair's joint strategies is not"
        " computed:"
    )
    print(
        "   player 2 alone has 2^16 pure strategies, so the pair's product is"
        " about"
    )
    print(
        "   1.7 x 10^7 profiles, and a coalition might find something these"
        " four"
    )
    print(
        "   simple profiles do not. That search is left open rather than"
        " claimed."
    )

    print("\nTwo consequences for the four-player game of this book.")
    print("1. An agent trained this way can be strong without being provably")
    print(
        "   unexploitable, and 'strong' is relative to the opponents it"
        " trained"
    )
    print(
        "   against. Abou Risk and Szafron's three-player poker agents were"
    )
    print(
        "   competitive while carrying no guarantee, which is the right"
        " expectation"
    )
    print(
        "   to hold - neither the confidence of a theorem nor the suspicion"
        " that the"
    )
    print("   method must fail.")
    print(
        "2. Because the guarantee is missing, the useful question is a best"
        " response"
    )
    print(
        "   to the opponents actually present, which is empirical rather than"
    )
    print(
        "   theoretical. Chapter 8 accordingly pre-registers a comparison of"
    )
    print(
        "   policies against a FIXED opponent pool and makes no claim about"
    )
    print("   equilibrium at all.")
# Three-player one-card game: 4 cards, 24 deals, each player acts once.
# Payoffs are zero sum across the three. Exploitability is the sum over
# players of what each could gain by deviating; it is zero exactly at a Nash
# equilibrium.
#
#    iterations   exploitability
#             1         0.440683
#            10         0.044804
#           100         0.004479
#          1000         0.000448
#         10000         0.000045
#        100000         0.000004
#
# In THIS game exploitability does fall to 0.000004, so the algorithm has
# found something very close to an equilibrium. That has to be reported as
# it is: the absence of a convergence theorem for three or more players does
# NOT mean the algorithm fails. Abou Risk and Szafron's three-player poker
# agents were likewise strong without a guarantee. What is missing is the
# assurance, not necessarily the result.
#
# But there is a different multiplayer problem, and it does not go away when
# the algorithm converges. In a two-player zero-sum game, playing an
# equilibrium strategy GUARANTEES at least the game's value, whatever the
# opponent does. With three players that guarantee is false: the other two
# can, between them, hold a player below their equilibrium payoff.
#
#    player 0's payoff under the converged profile: +0.000001
#
#    player 0 keeps the converged strategy throughout; only the other two
#    change. Player 0's payoff:
#    opponents' joint behaviour          player 0   the pair, combined
#    the converged profile                +0.0000             -0.0000
#    both always pass                     +0.0000              0.0000
#    both always bet                      +0.5000             -0.5000
#    both bet only K or A                 +0.1667             -0.1667
#    both bet Q or better                 +0.3333             -0.3333
#
#    A NEGATIVE result, reported as such. None of these four deviations
#    leaves player 0 worse off than the converged profile does: the worst is
#    'both always pass' at +0.0000, against +0.0000 under the converged
#    profile.
#    Every other deviation makes player 0 BETTER off, because in this game
#    betting loosely is simply a losing move and the deviators pay for it.
#
#    So this toy game does NOT exhibit the failure it was built to look for.
#    That has to be said plainly rather than glossed over, and it sharpens
#    what the multiplayer problem actually is:
#      * The two-player zero-sum GUARANTEE - that an equilibrium strategy
#        secures at least the game's value against every opponent - has no
#        multiplayer counterpart. That is a statement about which theorems
#        exist, and it is true regardless of this game.
#      * Whether the guarantee's absence BITES in a particular game is a
#        separate, empirical question. Here it did not bite. The book does
#        not have a worked example in which it does, and does not pretend to.
#
#    The full minimisation over the pair's joint strategies is not computed:
#    player 2 alone has 2^16 pure strategies, so the pair's product is about
#    1.7 x 10^7 profiles, and a coalition might find something these four
#    simple profiles do not. That search is left open rather than claimed.
#
# Two consequences for the four-player game of this book.
# 1. An agent trained this way can be strong without being provably
#    unexploitable, and 'strong' is relative to the opponents it trained
#    against. Abou Risk and Szafron's three-player poker agents were
#    competitive while carrying no guarantee, which is the right expectation
#    to hold - neither the confidence of a theorem nor the suspicion that the
#    method must fail.
# 2. Because the guarantee is missing, the useful question is a best response
#    to the opponents actually present, which is empirical rather than
#    theoretical. Chapter 8 accordingly pre-registers a comparison of
#    policies against a FIXED opponent pool and makes no claim about
#    equilibrium at all.

The book’s first negative result is that on this three-player toy game the same algorithm drives exploitability to 4×10−64\times10^{-6} as well. That is, it finds something very close to an equilibrium.

This has to be reported as it is: “no convergence theorem” does not mean “the algorithm fails”. Abou Risk and Szafron applied CFR to three-player poker and obtained competitive agents, likewise without a guarantee (Abou Risk and Szafron 2010); Brown and Sandholm’s six-player poker result was also obtained without a multiplayer guarantee (Brown and Sandholm 2019). What is missing is the assurance, not necessarily the result.

Exploitability against iterations for the two-player zero-sum game (solid, program p07) and the three-player game (dashed, program p08), on log-log axes. The values plotted are those the two programs print. The three-player game has no convergence theorem, and here it falls further than the two-player one.

The second negative result: the book has no worked example

Multiplayer games have another problem, and it does not go away when the algorithm converges. In a two-player zero-sum game an equilibrium strategy guarantees at least the game’s value, whatever the opponent does. With more than two players there is no such guarantee.

The book wanted a worked example of this, and constructed four simple opponent deviations. The result is that none of them held the player below the equilibrium value — every one left the player better off, because in that game loose betting simply loses and the deviators pay for it.

So

the book has no worked example of the multiplayer “no value guarantee” phenomenon, and does not pretend to.

Only two things can be stated, and they must be stated separately. One is about which theorems exist: the two-player zero-sum value guarantee has no multiplayer counterpart, and that is true regardless of any particular game. The other is about whether the gap bites in some particular game, which is an empirical question — and in this book’s toy game it did not. The full minimisation over the opponents’ coalition (about 1.7×1071.7\times10^{7} strategy profiles) was not computed, so a stronger deviation may exist that the book did not find.

Note

Why both negative results are printed. Following Volume 33’s position, results are reported whether or not they support the author’s framework. This chapter was written intending to show that CFR is unreliable in multiplayer games, and two attempts failed to support that. Keeping the failed attempts is more honest than substituting a more dramatic example, and it yields a more accurate conclusion: the multiplayer problem is the absence of a guarantee, not the failure of the method.

Consequences for this book

Two. First, an agent trained this way can be strong without being provably unexploitable, and “strong” is relative to the opponents it trained against. Second, since the guarantee is missing, the useful question is a best response to the opponents actually present, which is an empirical question about a population of opponents rather than a theorem. Chapter 8 therefore pre-registers a comparison against a fixed opponent pool and makes no claim about equilibrium at all.

Mixing: the formal content of the orthodox and the unorthodox

Calculation

# Chapter 6. Why a predictable policy loses: the exploitability of a
# deterministic strategy, computed exactly. This is the formal content of the
# classical insistence on combining the orthodox and the unorthodox, and it is
# a theorem rather than an
# aphorism: in a game where the opponent can observe and adapt, any
# deterministic policy has a best response that beats it, while a suitably
# mixed policy does not. The setting is a repeated discard game reduced to its
# essentials: a player holds a safe tile and a valuable tile and must choose
# which to discard; an opponent chooses which to guard. Payoffs are a 2x2
# zero-sum matrix with a unique mixed equilibrium.
import math

# rows: the discarder's choice; columns: the opponent's guess
# payoff to the discarder
A = [[-2.0, +3.0],      # discard the valuable tile: caught -2, through +3
     [+0.5, -0.5]]      # discard the safe tile: small gain or small loss

def value_against(p, q):
    """p = P(row 0), q = P(column 0)."""
    return (p * q * A[0][0] + p * (1 - q) * A[0][1]
            + (1 - p) * q * A[1][0] + (1 - p) * (1 - q) * A[1][1])

def best_response_q(p):
    """The opponent minimises; returns (q, value)."""
    v0 = value_against(p, 1.0)
    v1 = value_against(p, 0.0)
    return (1.0, v0) if v0 <= v1 else (0.0, v1)

def equilibrium():
    """Unique mixed equilibrium of a 2x2 game with no saddle point."""
    a, b = A[0]
    c, d = A[1]
    p = (d - c) / (a - b - c + d)
    q = (d - b) / (a - b - c + d)
    return p, q, value_against(p, q)

if __name__ == "__main__":
    print("Zero-sum 2x2 discard game, payoff to the discarder:")
    print("                    opponent guards valuable   guards safe")
    print("   discard valuable {:23.1f} {:13.1f}".format(A[0][0], A[0][1]))
    print("   discard safe     {:23.1f} {:13.1f}".format(A[1][0], A[1][1]))

    p_eq, q_eq, v_eq = equilibrium()
    print(
        "\nEquilibrium: discard the valuable tile with probability {:.4f};"
        .format(p_eq)
    )
    print(
        "the opponent guards it with probability {:.4f}; game value {:+.4f}."
        .format(q_eq, v_eq)
    )

    print("\nA. Value of a policy when the opponent BEST RESPONDS to it:")
    print(
        "   P(discard valuable)   opponent's response   value to the"
        " discarder"
    )
    for p in (0.0, 0.2, 0.4, p_eq, 0.6, 0.8, 1.0):
        q, v = best_response_q(p)
        lab = "guard valuable" if q == 1.0 else "guard safe"
        star = "  <- equilibrium" if abs(p - p_eq) < 1e-9 else ""
        print("   {:19.4f}   {:21s} {:+12.4f}{}".format(p, lab, v, star))

    print("\n   Both deterministic policies are the worst rows in the table:")
    print(
        "   always discarding the valuable tile is worth {:+.2f}, always"
        " discarding".format(best_response_q(1.0)[1])
    )
    print(
        "   the safe tile is worth {:+.2f}, and the equilibrium mix is worth"
        " {:+.2f}.".format(best_response_q(0.0)[1], v_eq)
    )
    print(
        "   The mix is better than EITHER pure choice, which is impossible"
        " in a"
    )
    print("   one-player decision problem and routine in a game.")

    print(
        "\nB. The cost of being read, as a function of how predictable the"
        " policy is."
    )
    print(
        "Suppose the opponent detects the discarder's mix with error e, i.e."
        " they"
    )
    print(
        "best-respond to p + e rather than to p. At the equilibrium the"
        " discarder"
    )
    print(
        "is indifferent, so small errors cost nothing; away from it they"
        " cost:"
    )
    print("   P(discard valuable)   loss relative to the equilibrium value")
    for p in sorted((0.0, 0.1, 0.2, 0.3, p_eq, 0.5, 0.7, 1.0)):
        _, v = best_response_q(p)
        print("   {:19.4f} {:38.4f}".format(p, v_eq - v))

    print(
        "\n   The loss curve has a kink at the equilibrium and rises"
        " linearly on"
    )
    print(
        "   either side. That is the formal shape of the classical"
        " doctrine: the"
    )
    print(
        "   unorthodox has value only in a particular proportion to the"
        " orthodox,"
    )
    print(
        "   and both 'always surprise' and 'never surprise' are equally"
        " wrong."
    )
    print(
        "   The proportion is not a matter of taste: it is {:.4f} here, and"
        " it is".format(p_eq)
    )
    print("   determined entirely by the payoff matrix.")

    print(
        "\nC. What changes in the real game, and it is not small. The matrix"
        " above"
    )
    print(
        "   assumes the opponent observes enough to estimate the discarder's"
        " mix."
    )
    print(
        "   Programme p11 showed that estimating a small difference takes"
        " thousands"
    )
    print(
        "   of hands, so against an opponent who sees a few hundred, a"
        " deterministic"
    )
    print(
        "   policy is NOT in fact exploitable - there is not enough data to"
        " read it."
    )
    print(
        "   The argument for mixing is therefore conditional on the opponent"
        " having"
    )
    print(
        "   enough observations, and at a casual table they usually do not."
        " This is"
    )
    print(
        "   the honest version of the doctrine, and it is narrower than the"
        " usual"
    )
    print("   statement of it.")

    print(
        "\nD. Against a four-player table the matrix itself is the wrong"
        " model:"
    )
    print(
        "   three opponents observe the same discards, and what is"
        " unexploitable"
    )
    print(
        "   against one may feed another (p06, p08). The 2x2 game is used"
        " here only"
    )
    print(
        "   to show that mixing can beat both pure choices, which is a point"
        " about"
    )
    print("   games as such and does not depend on the number of players.")
# Zero-sum 2x2 discard game, payoff to the discarder:
#                     opponent guards valuable   guards safe
#    discard valuable                    -2.0           3.0
#    discard safe                         0.5          -0.5
#
# Equilibrium: discard the valuable tile with probability 0.1667;
# the opponent guards it with probability 0.5833; game value +0.0833.
#
# A. Value of a policy when the opponent BEST RESPONDS to it:
#    P(discard valuable)   opponent's response   value to the discarder
#                 0.0000   guard safe                 -0.5000
#                 0.2000   guard valuable             +0.0000
#                 0.4000   guard valuable             -0.5000
#                 0.1667   guard safe                 +0.0833  <- equilibrium
#                 0.6000   guard valuable             -1.0000
#                 0.8000   guard valuable             -1.5000
#                 1.0000   guard valuable             -2.0000
#
#    Both deterministic policies are the worst rows in the table:
#    always discarding the valuable tile is worth -2.00, always discarding
#    the safe tile is worth -0.50, and the equilibrium mix is worth +0.08.
#    The mix is better than EITHER pure choice, which is impossible in a
#    one-player decision problem and routine in a game.
#
# B. The cost of being read, as a function of how predictable the policy is.
# Suppose the opponent detects the discarder's mix with error e, i.e. they
# best-respond to p + e rather than to p. At the equilibrium the discarder
# is indifferent, so small errors cost nothing; away from it they cost:
#    P(discard valuable)   loss relative to the equilibrium value
#                 0.0000                                 0.5833
#                 0.1000                                 0.2333
#                 0.1667                                 0.0000
#                 0.2000                                 0.0833
#                 0.3000                                 0.3333
#                 0.5000                                 0.8333
#                 0.7000                                 1.3333
#                 1.0000                                 2.0833
#
#    The loss curve has a kink at the equilibrium and rises linearly on
#    either side. That is the formal shape of the classical doctrine: the
#    unorthodox has value only in a particular proportion to the orthodox,
#    and both 'always surprise' and 'never surprise' are equally wrong.
#    The proportion is not a matter of taste: it is 0.1667 here, and it is
#    determined entirely by the payoff matrix.
#
# C. What changes in the real game, and it is not small. The matrix above
#    assumes the opponent observes enough to estimate the discarder's mix.
#    Programme p11 showed that estimating a small difference takes thousands
#    of hands, so against an opponent who sees a few hundred, a deterministic
#    policy is NOT in fact exploitable - there is not enough data to read it.
#    The argument for mixing is therefore conditional on the opponent having
#    enough observations, and at a casual table they usually do not. This is
#    the honest version of the doctrine, and it is narrower than the usual
#    statement of it.
#
# D. Against a four-player table the matrix itself is the wrong model:
#    three opponents observe the same discards, and what is unexploitable
#    against one may feed another (p06, p08). The 2x2 game is used here only
#    to show that mixing can beat both pure choices, which is a point about
#    games as such and does not depend on the number of players.

This is a 2×22\times2 zero-sum game with a unique mixed equilibrium: discard the valuable tile with probability 0.1667. The point of section A is that both deterministic policies are worse than the mix — always discarding the valuable tile is worth −2.00-2.00, always discarding the safe tile −0.50-0.50, and the equilibrium mix +0.0833+0.0833. The mix beats either pure choice, which is impossible in a single-agent decision problem and routine in a game.

Section B gives the loss curve: it has a kink at the equilibrium and rises linearly on either side. So “always surprise” and “never surprise” are equally wrong, and the correct proportion is not a matter of taste — it is determined uniquely by the payoff matrix (0.1667 here). Chapter 7 reads the Sunzi beside exactly this.

Section C gives the upper bound on that argument, and it is narrower than the usual statement. The matrix assumes the opponent observes enough to estimate the player’s mix. Program p11 in Chapter 8 shows that estimating a small difference takes thousands of hands. So against an opponent who has seen a few hundred, a deterministic policy is in fact not exploitable — there are not enough data to read it. The argument for mixing is therefore conditional, and at a casual table the condition usually does not hold.

Part two: the money

The real reason: the edge is estimated

Calculation

# Chapter 6. Why the Kelly fraction should be shaded down: estimation error,
# not the shape of the growth curve. The previous programme showed the growth
# curve is nearly symmetric around the optimum for moderate deviations. This
# one shows that the ERROR in estimating the edge is not symmetric in its
# consequences, because the Kelly fraction is roughly proportional to the
# estimated edge while the loss from overbetting grows faster than the gain
# from underbetting once the stake is large.
# Procedure: the true edge is fixed; a player estimates it from n observed
# hands and stakes the Kelly fraction implied by the estimate; the program
# reports the realised long-run growth rate under the TRUE distribution.
# Synthetic; fixed seed.
import math
import random

OUTCOMES = [(+0.90, 0.155), (+0.30, 0.110), (-0.10, 0.450), (-0.35, 0.225),
            (-0.60, 0.060)]

def mean(dist):
    return math.fsum(x * p for x, p in dist)

def sd(dist):
    m = mean(dist)
    return math.sqrt(math.fsum(p * (x - m) ** 2 for x, p in dist))

def log_growth(f, dist):
    tot = 0.0
    for x, p in dist:
        v = 1.0 + f * x
        if v <= 0:
            return float("-inf")
        tot += p * math.log(v)
    return tot

def kelly_fraction(dist):
    worst = min(x for x, _ in dist)
    hi = (1.0 / -worst) * 0.999999 if worst < 0 else 1e6
    if mean(dist) <= 0:
        return 0.0
    lo = 0.0
    for _ in range(200):
        mid = 0.5 * (lo + hi)
        d = math.fsum(p * x / (1.0 + mid * x) for x, p in dist)
        if d > 0:
            lo = mid
        else:
            hi = mid
    return lo

def shift_to_mean(dist, target):
    """Same shape, shifted so the mean equals `target`."""
    d = mean(dist)
    return [(x + (target - d), p) for x, p in dist]

def sample_mean(dist, n, rng):
    cum, acc = [], 0.0
    for x, p in dist:
        acc += p
        cum.append((acc, x))
    tot = 0.0
    for _ in range(n):
        r = rng.random()
        for a, x in cum:
            if r <= a:
                tot += x
                break
    return tot / n

if __name__ == "__main__":
    true_dist = OUTCOMES
    mu, s = mean(true_dist), sd(true_dist)
    f_true = kelly_fraction(true_dist)
    g_true = log_growth(f_true, true_dist)
    print("True edge {:+.4f} buy-ins per hand, outcome s.d. {:.4f}."
          .format(mu, s))
    print("True Kelly fraction {:.4f}, maximum growth rate {:.6f} per hand.\n"
          .format(f_true, g_true))

    print("A. The standard error of the estimated edge, by sample size:")
    print(
        "   hands observed   s.e. of the edge   as a share of the true edge"
    )
    for n in (100, 500, 1000, 5000, 20000):
        se = s / math.sqrt(n)
        print("   {:14d} {:18.5f} {:28.1%}".format(n, se, se / mu))
    print(
        "\n   Even 1,000 hands leaves the edge known only to within about a"
        " quarter"
    )
    print("   of itself; 100 hands leaves it essentially unknown.")

    print(
        "\nB. Realised growth when the stake is set from an estimate. 4,000"
        " players"
    )
    print(
        "each observe n hands, estimate the edge, and stake the implied Kelly"
    )
    print("fraction for ever after:")
    rng = random.Random(1056)
    print("   hands   mean realised   share of   P(ruinous   P(stake = 0)")
    print("           growth          maximum    stake)")
    for n in (100, 500, 1000, 5000, 20000):
        gs, ruin, zero = [], 0, 0
        for _ in range(4000):
            est = sample_mean(true_dist, n, rng)
            d_est = shift_to_mean(true_dist, est)
            f = kelly_fraction(d_est)
            if f <= 0:
                zero += 1
                gs.append(0.0)
                continue
            g = log_growth(f, true_dist)
            if g == float("-inf"):
                ruin += 1
                gs.append(-1.0)
            else:
                gs.append(g)
        m = math.fsum(gs) / len(gs)
        print("   {:5d} {:14.6f} {:10.1%} {:11.3f} {:11.3f}"
              .format(n, m, m / g_true, ruin / 4000.0, zero / 4000.0))

    print("\nC. The same, but staking a FRACTION of the estimated Kelly:")
    print("   hands   full Kelly   0.75 Kelly   0.50 Kelly   0.25 Kelly")
    for n in (100, 500, 1000, 5000):
        row = []
        for frac in (1.0, 0.75, 0.50, 0.25):
            gs = []
            for _ in range(2000):
                est = sample_mean(true_dist, n, rng)
                f = kelly_fraction(shift_to_mean(true_dist, est)) * frac
                g = log_growth(f, true_dist) if f > 0 else 0.0
                gs.append(-1.0 if g == float("-inf") else g)
            row.append(math.fsum(gs) / len(gs))
        print(
            "   {:5d}".format(n) + "".join("{:13.6f}".format(v) for v in row)
        )

    print(
        "\n   At small samples the fractional stakes do BETTER than full"
        " Kelly on the"
    )
    print(
        "   estimate, and the advantage disappears as the sample grows. That"
        " is the"
    )
    print(
        "   argument for shading down, and note what it rests on: not the"
        " shape of"
    )
    print(
        "   the growth curve (p09 showed that is nearly symmetric) but the"
        " fact that"
    )
    print(
        "   the edge is estimated. A player who has not counted several"
        " thousand"
    )
    print(
        "   hands does not know their edge well enough to stake the full"
        " fraction,"
    )
    print("   and p11 shows how many hands 'knowing it' actually takes.")

    print(
        "\nD. A caution about what this does NOT model. The estimate here is"
        " of the"
    )
    print(
        "   MEAN of a fixed distribution, with the shape known. In reality"
        " the shape"
    )
    print(
        "   changes with the opponents, the rules and the player's own"
        " improvement,"
    )
    print(
        "   so the edge is not a fixed quantity being estimated but a moving"
        " one."
    )
    print("   Every number above is therefore optimistic.")
# True edge +0.0128 buy-ins per hand, outcome s.d. 0.4347.
# True Kelly fraction 0.0696, maximum growth rate 0.000439 per hand.
#
# A. The standard error of the estimated edge, by sample size:
#    hands observed   s.e. of the edge   as a share of the true edge
#               100            0.04347                       340.9%
#               500            0.01944                       152.5%
#              1000            0.01375                       107.8%
#              5000            0.00615                        48.2%
#             20000            0.00307                        24.1%
#
#    Even 1,000 hands leaves the edge known only to within about a quarter
#    of itself; 100 hands leaves it essentially unknown.
#
# B. Realised growth when the stake is set from an estimate. 4,000 players
# each observe n hands, estimate the edge, and stake the implied Kelly
# fraction for ever after:
#    hands   mean realised   share of   P(ruinous   P(stake = 0)
#            growth          maximum    stake)
#      100      -0.003323    -756.7%       0.000       0.397
#      500      -0.000341     -77.6%       0.000       0.245
#     1000       0.000031       7.0%       0.000       0.165
#     5000       0.000337      76.7%       0.000       0.020
#    20000       0.000414      94.2%       0.000       0.000
#
# C. The same, but staking a FRACTION of the estimated Kelly:
#    hands   full Kelly   0.75 Kelly   0.50 Kelly   0.25 Kelly
#      100    -0.003106    -0.001680    -0.000425     0.000121
#      500    -0.000353     0.000029     0.000188     0.000193
#     1000     0.000014     0.000199     0.000258     0.000190
#     5000     0.000330     0.000353     0.000306     0.000191
#
#    At small samples the fractional stakes do BETTER than full Kelly on the
#    estimate, and the advantage disappears as the sample grows. That is the
#    argument for shading down, and note what it rests on: not the shape of
#    the growth curve (p09 showed that is nearly symmetric) but the fact that
#    the edge is estimated. A player who has not counted several thousand
#    hands does not know their edge well enough to stake the full fraction,
#    and p11 shows how many hands 'knowing it' actually takes.
#
# D. A caution about what this does NOT model. The estimate here is of the
#    MEAN of a fixed distribution, with the shape known. In reality the shape
#    changes with the opponents, the rules and the player's own improvement,
#    so the edge is not a fixed quantity being estimated but a moving one.
#    Every number above is therefore optimistic.

Section A gives the standard error: even 1,000 hands pins the edge only to about a quarter of itself, and 100 hands leaves it essentially unknown.

Sections B and C give the conclusion. On a 100-hand sample every fractional stake beats full Kelly on the estimate: 0.75 Kelly gives −0.001680-0.001680 against full Kelly’s −0.003106-0.003106, and only 0.25 Kelly is positive at all (+0.000121+0.000121). The advantage narrows as the sample grows rather than reversing within the range computed — at 5,000 hands 0.75 Kelly (0.000353) and full Kelly (0.000330) are level to three significant figures. So

the reason to shade the stake down is not the shape of the curve but that the edge must be estimated, and a small-sample estimate pushes the stake into the region where the curve really does collapse.

Section D notes that this calculation is still optimistic: it estimates the mean of a fixed distribution whose shape is known. A real edge moves with the opponents, the rules and the player’s own improvement, so it is not a fixed quantity being estimated but a moving one.

Ruin

Calculation

# Chapter 6. Ruin, and the difference between a positive expectation and a
# safe one. Volume 19 treats non-ergodicity and Kelly in general; this
# programme does the specific calculation for a four-person table with a fee:
# given a bankroll of B buy-ins, a positive per-hand edge and a flat stake,
# what is the probability of going broke before reaching a target, and how
# does that change with the stake size? The point is that a positive
# expectation does not bound the risk of ruin, and that the stake size - not
# the edge - is what controls it.
import math
import random

OUTCOMES = [(+0.90, 0.155), (+0.30, 0.110), (-0.10, 0.450), (-0.35, 0.225),
            (-0.60, 0.060)]
FEE = 0.01

def dist_with_fee(fee=FEE):
    return [(x - fee, p) for x, p in OUTCOMES]

def mean(d):
    return math.fsum(x * p for x, p in d)

def sd(d):
    m = mean(d)
    return math.sqrt(math.fsum(p * (x - m) ** 2 for x, p in d))

def sampler(d):
    cum, acc = [], 0.0
    for x, p in d:
        acc += p
        cum.append((acc, x))
    def draw(rng):
        r = rng.random()
        for a, x in cum:
            if r <= a:
                return x
        return cum[-1][1]
    return draw

def ruin_probability(bankroll, stake, target, d, reps=20000, max_hands=200000,
                     seed=0):
    rng = random.Random(seed)
    draw = sampler(d)
    ruined = hit = 0
    for _ in range(reps):
        w = bankroll
        for _ in range(max_hands):
            w += stake * draw(rng)
            if w <= 0:
                ruined += 1
                break
            if w >= target:
                hit += 1
                break
        else:
            hit += 1                     # neither: counted as surviving
    return ruined / reps, hit / reps

def diffusion_ruin(bankroll, stake, d):
    """Classical approximation: for a random walk with drift mu and s.d. s per
    step,
    P(ever reaching 0 from x) = exp(-2 mu x / s^2) when mu > 0."""
    mu, s = mean(d) * stake, sd(d) * stake
    if mu <= 0:
        return 1.0
    return math.exp(-2.0 * mu * bankroll / (s * s))

if __name__ == "__main__":
    d = dist_with_fee()
    print("Per-hand outcome with a fee of {:.2f}: mean {:+.4f}, s.d. {:.4f}."
          .format(FEE, mean(d), sd(d)))
    print("A positive edge, so the expectation is favourable.\n")

    print("A. Probability of ever going broke, by bankroll and flat stake")
    print("(diffusion approximation, exact for the continuous limit):")
    print(
        "   bankroll (buy-ins)   stake 1.0   stake 0.5   stake 0.25  "
        " stake 0.1"
    )
    for B in (5, 10, 20, 50, 100):
        row = [diffusion_ruin(B, st, d) for st in (1.0, 0.5, 0.25, 0.1)]
        print(
            "   {:18d}".format(B) + "".join("{:12.4f}".format(v) for v in row)
        )

    print(
        "\n   Read along a row: HALVING the stake squares the survival odds,"
        " because"
    )
    print(
        "   the exponent is proportional to bankroll divided by stake. Read"
        " down a"
    )
    print(
        "   column: the same effect comes from doubling the bankroll. The"
        " edge"
    )
    print(
        "   itself appears only linearly in the exponent, so it is much the"
        " weakest"
    )
    print("   of the three levers.")

    print("\nB. Simulation check, bankroll 20 buy-ins, target 40:")
    print("   stake   simulated P(ruin)   diffusion P(ruin)")
    for st in (1.0, 0.5, 0.25):
        r, h = ruin_probability(
            20, st, 40, d, reps=4000, seed=1300 + int(st * 100)
        )
        print(
            "   {:5.2f} {:19.4f} {:19.4f}".format(
                st, r, diffusion_ruin(20, st, d)
            )
        )
    print(
        "\n   The simulation is run to a TARGET of 40 rather than for ever,"
        " so its"
    )
    print(
        "   ruin probabilities are lower than the diffusion figures, which"
        " assume"
    )
    print(
        "   an unbounded horizon. Both answer useful questions and they are"
        " not the"
    )
    print("   same question; quoting one for the other is a common error.")

    print("\nC. What the fee does to all of this:")
    print("   fee   mean per hand   P(ruin), bankroll 20, stake 0.5")
    for fee in (0.00, 0.01, 0.02, 0.04, 0.073, 0.10):
        dd = dist_with_fee(fee)
        m = mean(dd)
        pr = diffusion_ruin(20, 0.5, dd)
        print("   {:5.3f} {:15.4f} {:32.4f}".format(fee, m, pr))
    print(
        "\n   Once the fee removes the edge the ruin probability is 1: with"
        " zero or"
    )
    print(
        "   negative drift, a bounded bankroll is reached from above with"
        " certainty."
    )
    print(
        "   That is the sense in which a table fee is not a small deduction"
        " from a"
    )
    print(
        "   winning player's rate but the thing that decides whether there"
        " is a"
    )
    print("   winning player at all.")

    print(
        "\nD. The practical conclusion, and a limit on it. The three"
        " levers are"
    )
    print(
        "   bankroll, stake and edge, and the first two act exponentially"
        " while the"
    )
    print(
        "   edge acts linearly, so staking small matters more than playing"
        " well for"
    )
    print(
        "   the purpose of not going broke. That is a statement about"
        " SURVIVAL, not"
    )
    print(
        "   about earning: staking small also scales the winnings down. Kelly"
        " (p09,"
    )
    print(
        "   p10) is the formulation that trades the two off, and the honest"
        " summary"
    )
    print(
        "   of this chapter is that it requires an edge estimate nobody in"
        " this game"
    )
    print("   has yet measured to the precision p11 shows is needed.")
# Per-hand outcome with a fee of 0.01: mean +0.0027, s.d. 0.4347.
# A positive edge, so the expectation is favourable.
#
# A. Probability of ever going broke, by bankroll and flat stake
# (diffusion approximation, exact for the continuous limit):
#    bankroll (buy-ins)   stake 1.0   stake 0.5   stake 0.25   stake 0.1
#                     5      0.8646      0.7475      0.5587      0.2333
#                    10      0.7475      0.5587      0.3121      0.0544
#                    20      0.5587      0.3121      0.0974      0.0030
#                    50      0.2333      0.0544      0.0030      0.0000
#                   100      0.0544      0.0030      0.0000      0.0000
#
#    Read along a row: HALVING the stake squares the survival odds, because
#    the exponent is proportional to bankroll divided by stake. Read down a
#    column: the same effect comes from doubling the bankroll. The edge
#    itself appears only linearly in the exponent, so it is much the weakest
#    of the three levers.
#
# B. Simulation check, bankroll 20 buy-ins, target 40:
#    stake   simulated P(ruin)   diffusion P(ruin)
#     1.00              0.3498              0.5587
#     0.50              0.2355              0.3121
#     0.25              0.0905              0.0974
#
#    The simulation is run to a TARGET of 40 rather than for ever, so its
#    ruin probabilities are lower than the diffusion figures, which assume
#    an unbounded horizon. Both answer useful questions and they are not the
#    same question; quoting one for the other is a common error.
#
# C. What the fee does to all of this:
#    fee   mean per hand   P(ruin), bankroll 20, stake 0.5
#    0.000          0.0128                           0.0045
#    0.010          0.0027                           0.3121
#    0.020         -0.0073                           1.0000
#    0.040         -0.0273                           1.0000
#    0.073         -0.0602                           1.0000
#    0.100         -0.0872                           1.0000
#
#    Once the fee removes the edge the ruin probability is 1: with zero or
#    negative drift, a bounded bankroll is reached from above with certainty.
#    That is the sense in which a table fee is not a small deduction from a
#    winning player's rate but the thing that decides whether there is a
#    winning player at all.
#
# D. The practical conclusion, and a limit on it. The three levers are
#    bankroll, stake and edge, and the first two act exponentially while the
#    edge acts linearly, so staking small matters more than playing well for
#    the purpose of not going broke. That is a statement about SURVIVAL, not
#    about earning: staking small also scales the winnings down. Kelly (p09,
#    p10) is the formulation that trades the two off, and the honest summary
#    of this chapter is that it requires an edge estimate nobody in this game
#    has yet measured to the precision p11 shows is needed.

The three levers are not equally weighted: bankroll and stake enter the ruin probability exponentially and the edge only linearly. So for the purpose of not going broke, staking small is more effective than playing well — but that is a statement about survival and not about earning, because staking small scales the winnings down in proportion.

Section C puts the fee back: once the fee cancels the edge, the ruin probability is 1. With zero or negative drift a bounded bankroll is reached from above with certainty. That is the precise content of “a fee is not a small deduction but the thing that decides whether there is a winner”.

Hypothesis · not established

The author’s hypothesis (not established): at tables of the kind this book discusses, fewer than one player in ten has a positive long-run edge net of the fee. What would show it to be wrong: on a platform with complete records and a known fee, taking individual sequences long enough (by program p11, several thousand hands each), a lower bound above 0.10 on the 95 % confidence interval for the proportion of players with a significantly positive net edge would refute it. Note that this hypothesis is testable with data that exist, and that the book does not have such data.

Summary

Counterfactual regret minimisation does converge on two-player zero-sum games: this book verifies exploitability falling from 0.667 to 0.0013, the game value converging to −0.055554-0.055554 against the theoretical −1/18-1/18, and a worst-card to best-card betting ratio of 3.01 against 3.00; and it records an implementation trap that produces no error — a best response must be computed over information sets. Then two negative results: on the three-player toy game the same algorithm drives exploitability to 4×10−64\times10^{-6}, so “no theorem” does not mean “will fail”; and none of the four constructed opponent deviations held the player below the equilibrium value, so the book has no worked example of the multiplayer no-value-guarantee and does not pretend to. That a mix beats every pure strategy is a theorem, but it requires enough observation by the opponent, which takes thousands of hands, so the argument is conditional. The money part corrects three things: the fee decides whether there is a winner (the edge vanishes at 0.0128, and a fee of 0.010 cuts the stake by 79 %); the two-way Kelly formula has the wrong sign here; and the growth curve is nearly symmetric about the optimum, so the reason to shade down is that the edge is estimated rather than the curve’s shape — on a 100-hand sample 0.75 Kelly really is better. Finally, of the three levers on ruin, bankroll and stake enter exponentially and the edge only linearly.

References

Abou Risk, Nicholas, and Duane Szafron. 2010. “Using Counterfactual Regret Minimization to Create Competitive Multiplayer Poker Agents.” In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 159–66.
Bowling, Michael, Neil Burch, Michael Johanson, and Oskari Tammelin. 2015. “Heads-up Limit Hold’em Poker Is Solved.” Science 347 (6218): 145–49. https://doi.org/10.1126/science.1259433.
Breiman, Leo. 1961. “Optimal Gambling Systems for Favorable Games.” In Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1, 65–78. Berkeley: University of California Press.
Brown, Noam, and Tuomas Sandholm. 2018. “Superhuman AI for Heads-up No-Limit Poker: Libratus Beats Top Professionals.” Science 359 (6374): 418–24. https://doi.org/10.1126/science.aao1733.
———. 2019. “Superhuman AI for Multiplayer Poker.” Science 365 (6456): 885–90. https://doi.org/10.1126/science.aay2400.
Hart, Sergiu, and Andreu Mas-Colell. 2000. “A Simple Adaptive Procedure Leading to Correlated Equilibrium.” Econometrica 68 (5): 1127–50. https://doi.org/10.1111/1468-0262.00153.
Kelly, J. L. 1956. “A New Interpretation of Information Rate.” Bell System Technical Journal 35 (4): 917–26. https://doi.org/10.1002/j.1538-7305.1956.tb03809.x.
Kuhn, H. W. 1950. “A Simplified Two-Person Poker.” In Contributions to the Theory of Games, Volume i, edited by H. W. Kuhn and A. W. Tucker, 97–103. Princeton: Princeton University Press.
MacLean, Leonard C., Edward O. Thorp, and William T. Ziemba, eds. 2011. The Kelly Capital Growth Investment Criterion: Theory and Practice. Singapore: World Scientific.
Moravčík, Matej, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. 2017. “DeepStack: Expert-Level Artificial Intelligence in Heads-up No-Limit Poker.” Science 356 (6337): 508–13. https://doi.org/10.1126/science.aam6960.
Peters, Ole. 2019. “The Ergodicity Problem in Economics.” Nature Physics 15: 1216–21. https://doi.org/10.1038/s41567-019-0732-0.
Robinson, Julia. 1951. “An Iterative Method of Solving a Game.” Annals of Mathematics 54 (2): 296–301. https://doi.org/10.2307/1969530.
Shapley, Lloyd S. 1964. “Some Topics in Two-Person Games. The Example of Non-Convergent Fictitious Play Appears Here.” Advances in Game Theory, Annals of mathematics studies, 52: 1–28.
Zinkevich, Martin, Michael Johanson, Michael Bowling, and Carmelo Piccione. 2008. “Regret Minimization in Games with Incomplete Information. Presented at NIPS 2007.” In Advances in Neural Information Processing Systems 20, 1729–36. Curran Associates.

Fan, Y. (2026). Imperfect-Information Stochastic Games, Bayesian Hand-Reading and Counterfactual Regret Minimisation in Four-Player Tile Dynamics: From Markov Transitions of the Tile Pool and the Optimal Stopping of Defensive Folding to Kelly Allocation in a Multiplayer Game, with a Textual Examination of the Orthodox and the Unorthodox in the Classical Military Writers [四人不完全信息随机博弈、贝叶斯读牌与反事实遗憾最小化] (Version 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24020464 · Licensed under Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International (CC BY-NC-ND 4.0).