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 against the known value to the first player of ; 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 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.
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 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 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 , always discarding the safe tile , and the equilibrium mix . 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
Kelly, and one popular claim corrected
Evidence
The Kelly criterion. Kelly showed that staking in proportion to the maximisation of expected logarithmic wealth maximises the almost-sure long-run growth rate (Kelly 1956); Breiman gave more general results (Breiman 1961); MacLean, Thorp and Ziemba’s collection gathers theory and practice (MacLean, Thorp, and Ziemba 2011). Peters places this class of problem in the framework of non-ergodicity (Peters 2019). Volume 19 is devoted to the subject; only the two features peculiar to this game are taken here.
Two features change the answer. The game is zero-sum in points but negative-sum in money (the fee). And the outcome is not a two-way bet but a distribution, so the Kelly fraction requires solving rather than using the textbook .
Calculation
# Chapter 6. Kelly staking at a four-person table, with the correction nobody
# makes. Kelly's criterion maximises the expected logarithm of wealth, which
# maximises the almost-sure long-run growth rate. Volume 19 derives it; this
# program applies it to the structure of this game, where two features change
# the answer:
# 1. The game among the players is zero sum in POINTS, but a table fee, rake
# or commission makes it negative sum in MONEY. A negative-sum game has a
# smaller optimal stake and, past a point, none at all.
# 2. The outcome is not a two-way bet. A four-person hand has a distribution
# of results, and Kelly for a general discrete distribution requires
# solving E[X / (1 + fX)] = 0 numerically rather than using the textbook
# (p - q) formula.
# Standard library only; exact root finding by bisection.
import math
# Illustrative per-hand point outcomes for one player, in units of the buy-in,
# as a discrete distribution. These are shaped to look like a real score
# distribution (frequent small losses, occasional large wins) but they are not
# measured.
EDGE_FREE = [(+0.90, 0.155), (+0.30, 0.110), (-0.10, 0.450), (-0.35, 0.225),
(-0.60, 0.060)]
def normalise(dist):
s = math.fsum(p for _, p in dist)
return [(x, p / s) for x, p in dist]
def mean(dist):
return math.fsum(x * p for x, p in dist)
def apply_rake(dist, rake):
"""A fee of `rake` units of the buy-in is charged per hand, win or
lose."""
return [(x - rake, p) for x, p in dist]
def log_growth(f, dist):
"""E[log(1 + f X)]; -inf if any outcome would ruin the bankroll."""
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, hi=None):
"""Maximise E[log(1 + f X)] over f in [0, f_max) by bisection on the
derivative
E[X / (1 + f X)], which is decreasing in f."""
worst = min(x for x, _ in dist)
f_max = (1.0 / -worst) if worst < 0 else 1e6
if hi is None:
hi = f_max * 0.999999
# derivative at f = 0 is E[X]
d0 = math.fsum(p * x for x, p in dist)
if d0 <= 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
if __name__ == "__main__":
base = normalise(EDGE_FREE)
print(
"Illustrative per-hand outcome distribution for one player, in"
" buy-ins:"
)
print(" outcome probability")
for x, p in base:
print(" {:+7.2f} {:13.2f}".format(x, p))
print(
" mean (the player's edge before any fee): {:+.4f} buy-ins per hand"
.format(mean(base))
)
print("\nA. The effect of a table fee. Kelly fraction and growth rate:")
print(
" fee per hand mean outcome Kelly fraction growth rate per"
" hand"
)
for rake in (0.000, 0.005, 0.010, 0.020, 0.030, 0.040):
d = apply_rake(base, rake)
f = kelly_fraction(d)
print(" {:12.3f} {:14.4f} {:16.4f} {:22.6f}"
.format(rake, mean(d), f, log_growth(f, d) if f > 0 else 0.0))
# the fee at which the edge vanishes
lo, hi = 0.0, 1.0
for _ in range(80):
mid = 0.5 * (lo + hi)
if mean(apply_rake(base, mid)) > 0:
lo = mid
else:
hi = mid
print(
"\n The edge vanishes at a fee of {:.4f} buy-ins per hand, and at"
" or above".format(hi)
)
print(
" that the Kelly fraction is exactly zero: the correct stake in a"
)
print(
" negative-sum game with no edge is nothing at all. Note how"
" FAST the"
)
print(
" Kelly fraction falls - a fee of {:.3f}, which is only {:.0%}"
" of the".format(0.005, 0.005 / mean(base))
)
print(
" edge-free mean, already cuts the optimal stake by {:.0%}, and a"
" fee of".format(
1 - kelly_fraction(apply_rake(base, 0.005)) / kelly_fraction(base)
)
)
print(
" {:.3f} cuts it by {:.0%}. The stake is far more sensitive to"
" the fee".format(
0.010,
1
- kelly_fraction(apply_rake(base, 0.010)) / kelly_fraction(base),
)
)
print(" than the edge itself is.")
print(
"\nB. Why the textbook formula does not apply. For a two-way bet at"
" even"
)
print(
"money, Kelly is f = p - q. Treating this distribution as 'win 20 %"
" of the"
)
print("time' and applying that formula gives:")
p_win = math.fsum(p for x, p in base if x > 0)
print(" p - q = {:.2f} - {:.2f} = {:+.2f}".format(p_win, 1 - p_win,
2 * p_win - 1))
print(" against the correct value of {:.4f} for the full distribution."
.format(kelly_fraction(base)))
print(
" The two-way formula is not merely imprecise here, it has the"
" WRONG SIGN,"
)
print(
" because the outcomes are not symmetric: the wins are larger"
" than the"
)
print(
" losses, so a win rate below a half is perfectly compatible with"
" an edge."
)
print("\nC. Fractional Kelly, which is what the growth curve justifies:")
f_star = kelly_fraction(base)
g_star = log_growth(f_star, base)
print(
" fraction of Kelly stake growth rate share of maximum growth"
)
for frac in (0.25, 0.50, 0.75, 1.00, 1.25, 1.50, 2.00):
f = f_star * frac
g = log_growth(f, base)
print(" {:18.2f} {:7.4f} {:13.6f} {:24.1%}"
.format(frac, f, g, g / g_star if g_star else 0.0))
half = log_growth(0.5 * f_star, base) / g_star
onehalf = log_growth(1.5 * f_star, base) / g_star
dbl = log_growth(2.0 * f_star, base) / g_star
print(
"\n Read that table carefully, because it does not say what the"
" usual"
)
print(
" argument for fractional Kelly says. Near the optimum the curve is"
" very"
)
print(
" nearly SYMMETRIC: half-Kelly keeps {:.0%} of the growth and"
" one-and-a-".format(half)
)
print(
" half Kelly keeps {:.0%}, which is essentially the same"
" penalty for".format(onehalf)
)
print(
" staking too little and too much. The collapse only appears"
" further out:"
)
print(" at double Kelly the growth rate is {:.1%} of the maximum."
.format(dbl))
print(
"\n So the growth curve alone is NOT a good argument for"
" deliberately"
)
print(
" staking under Kelly: it penalises both directions about equally"
" over"
)
print(
" the range anyone would plausibly choose. The real argument is"
" different,"
)
print(
" and it is the subject of the next programme: the Kelly fraction"
" has to"
)
print(
" be ESTIMATED, estimation error is asymmetric in its"
" consequences, and"
)
print(
" overestimating the edge pushes the stake into the region"
" where the"
)
print(" curve does collapse.")
# Illustrative per-hand outcome distribution for one player, in buy-ins:
# outcome probability
# +0.90 0.15
# +0.30 0.11
# -0.10 0.45
# -0.35 0.23
# -0.60 0.06
# mean (the player's edge before any fee): +0.0128 buy-ins per hand
#
# A. The effect of a table fee. Kelly fraction and growth rate:
# fee per hand mean outcome Kelly fraction growth rate per hand
# 0.000 0.0128 0.0696 0.000439
# 0.005 0.0078 0.0418 0.000161
# 0.010 0.0027 0.0147 0.000020
# 0.020 -0.0073 0.0000 0.000000
# 0.030 -0.0173 0.0000 0.000000
# 0.040 -0.0273 0.0000 0.000000
#
# The edge vanishes at a fee of 0.0128 buy-ins per hand, and at or above
# that the Kelly fraction is exactly zero: the correct stake in a
# negative-sum game with no edge is nothing at all. Note how FAST the
# Kelly fraction falls - a fee of 0.005, which is only 39% of the
# edge-free mean, already cuts the optimal stake by 40%, and a fee of
# 0.010 cuts it by 79%. The stake is far more sensitive to the fee
# than the edge itself is.
#
# B. Why the textbook formula does not apply. For a two-way bet at even
# money, Kelly is f = p - q. Treating this distribution as 'win 20 % of the
# time' and applying that formula gives:
# p - q = 0.27 - 0.73 = -0.47
# against the correct value of 0.0696 for the full distribution.
# The two-way formula is not merely imprecise here, it has the WRONG SIGN,
# because the outcomes are not symmetric: the wins are larger than the
# losses, so a win rate below a half is perfectly compatible with an edge.
#
# C. Fractional Kelly, which is what the growth curve justifies:
# fraction of Kelly stake growth rate share of maximum growth
# 0.25 0.0174 0.000193 44.0%
# 0.50 0.0348 0.000330 75.3%
# 0.75 0.0522 0.000412 93.8%
# 1.00 0.0696 0.000439 100.0%
# 1.25 0.0870 0.000412 93.9%
# 1.50 0.1044 0.000332 75.7%
# 2.00 0.1392 0.000016 3.7%
#
# Read that table carefully, because it does not say what the usual
# argument for fractional Kelly says. Near the optimum the curve is very
# nearly SYMMETRIC: half-Kelly keeps 75% of the growth and one-and-a-
# half Kelly keeps 76%, which is essentially the same penalty for
# staking too little and too much. The collapse only appears further out:
# at double Kelly the growth rate is 3.7% of the maximum.
#
# So the growth curve alone is NOT a good argument for deliberately
# staking under Kelly: it penalises both directions about equally over
# the range anyone would plausibly choose. The real argument is different,
# and it is the subject of the next programme: the Kelly fraction has to
# be ESTIMATED, estimation error is asymmetric in its consequences, and
# overestimating the edge pushes the stake into the region where the
# curve does collapse.Three results.
The fee decides whether there is a winner. In this book’s illustrative distribution the edge vanishes at a fee of 0.0128 buy-ins a hand; a fee of 0.005, only 39 % of the edge, already cuts the optimal stake by 40 %, and 0.010 cuts it by 79 %. The stake is far more sensitive to the fee than to the edge itself.
The two-way formula has the wrong sign. Treating this distribution as “wins two times in ten” and applying gives , while the correct value is . The wins are larger than the losses, so a win rate below a half is entirely compatible with an edge; the two-way formula would conclude that one should not bet at all.
The growth curve is nearly symmetric about the optimum. This corrects the popular claim. Half-Kelly keeps 75.3 % of the growth rate and 1.5× Kelly keeps 75.7 % — the same penalty, to within half a percentage point, for staking too little and too much; only at 2× Kelly does it collapse to 3.7 %. So
“the growth curve falls off a cliff above the optimum” is not a good reason to shade the stake down, because over any range anyone would plausibly choose it is about equally punishing in both directions.
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 against full Kelly’s , and only 0.25 Kelly is positive at all (). 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 against the theoretical , 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 , 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
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).