5D Library › 四人不完全信息随机博弈、贝叶斯读牌与反事实遗憾最小化 · English
第六章 博弈的解与钱
本章分两部分。前半部分处理「怎么解这个博弈」,并报告两个否定结果;后半部分处理「押多少钱」,并修正一处流行说法。
第一部分 遗憾最小化
两人零和:定理成立的地方
证据
遗憾匹配与反事实遗憾最小化。 Hart 与 Mas-Colell 证明了一个简单的适应过程(遗憾匹配)导向相关均衡 (Hart and Mas-Colell 2000)。Zinkevich、Johanson、Bowling 与 Piccione 把它推广到不完全信息的扩展式博弈,给出反事实遗憾最小化(CFR):在两人零和博弈中,平均策略收敛到纳什均衡 (Zinkevich et al. 2008)。这一方法是此后一系列结果的基础:单挑限注德州扑克的求解 (Bowling et al. 2015)、DeepStack (Moravčík et al. 2017) 与 Libratus (Brown and Sandholm 2018)。
本书在一个可以精确求解的玩具博弈——Kuhn 的一张牌扑克 (Kuhn 1950)——上验证这个保证。
推导
# 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.结果是教科书式的。可利用度从 0.667 降到 0.0013;博弈值收敛到 ,而该博弈对先手的已知值是 ;平均策略用最差牌下注的比例与用最好牌下注的比例之比为 3.01,而均衡族预测的是 3.00。
注
可利用度必须按信息集算。 本书第一次实现这个计算时,让最优反应「看得见」双方的牌,于是可利用度停在远高于零的位置不动。一个最优反应必须对回应方自己的信息可测,所以程序枚举的是回应方的 64 个纯策略(6 个信息集、每个 2 个行动)。这一处错误值得写出来:它不会使程序报错,只会使收敛看起来失败。
三人:第一个否定结果
保证只对两人零和成立,而这条分界线比 CFR 老得多。
证据
两人零和与其余之间的分界线是旧的。 Robinson 证明了一种迭代解法(虚拟对局,fictitious play)在两人零和博弈中收敛到博弈值 (Robinson 1951);Shapley 随后给出一个非零和的例子,其中同一迭代永远绕圈而不收敛 (Shapley 1964)。所以「在两人零和里有定理、出了这个范围没有」这件事并非 CFR 的特有缺陷,而是这一整类迭代方法共同的界限。
那么三人会怎样?
推导
# 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.本书的第一个否定结果是:在这个三人玩具博弈上,同一算法照样把可利用度压到 。 也就是说,它找到了非常接近均衡的东西。
这必须照实报告:「没有收敛定理」不等于「算法会失败」。Abou Risk 与 Szafron 把 CFR 用于三人扑克,得到有竞争力的代理,而同样没有保证 (Abou Risk and Szafron 2010);Brown 与 Sandholm 的六人扑克结果也是在没有多人保证的情况下取得的 (Brown and Sandholm 2019)。缺的是保证,不一定是结果。
第二个否定结果:本书没有工作例
多人博弈还有另一个问题,而它不随算法收敛而消失。在两人零和博弈中,均衡策略保证至少拿到博弈值,无论对手怎么打。多人博弈中没有这条保证。
本书想给这件事一个工作例,于是构造了四种简单的对手偏离。结果是:没有一种把玩家压到均衡值以下——每一种都让玩家更好,因为在那个博弈里乱下注是亏的,偏离者自己付钱。
所以
本书没有一个展示多人「无价值保证」现象的工作例,并且不假装有。
能确定的只有两件事,而要分开说:一件是哪些定理存在——两人零和的价值保证没有多人对应物,这与任何具体博弈无关;另一件是在某个具体博弈里这个缺口是否咬人——这是经验问题,而在本书的玩具博弈里它没有咬人。对手联盟的完整最小化(约 个策略组合)未算,所以更强的偏离可能存在而本书没有找到。
注
为什么把两个否定结果都写出来。 按第 33 本的立场,无论结果支持还是不支持作者的框架都照实写。本章原本的写作意图是「展示多人博弈里 CFR 不可靠」,而两次尝试都没有支持那个说法。保留失败的尝试比替换成一个更戏剧化的例子诚实,而且它给出一个更准确的结论:多人博弈的问题是没有保证,不是方法无效。
对本书的后果
两点。第一,用这类方法训练出的代理可以很强而不可证明不可被利用,而「强」是相对于它训练时的对手而言的。第二,既然保证缺失,有用的问题就是对在场的对手的最优反应,这是一个关于对手总体的经验问题而不是定理。第八章因此预注册一个针对固定对手池的策略比较,并且不作任何关于均衡的主张。
混合:虚实的形式内容
推导
# 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.这是一个 零和博弈,有唯一的混合均衡:以 0.1667 的概率打有价值的那张牌。A 段的要点是:两个确定性策略都比混合差——总是打价值牌值 ,总是打安全牌值 ,而均衡混合值 。混合优于任何一个纯选择,这在单人决策问题里不可能,在博弈里是常态。
B 段给出损失曲线:在均衡处有一个折点,两侧线性上升。所以「总是出奇」与「从不出奇」同样错,而正确的比例不是品味问题——它由支付矩阵唯一决定。第七章与《孙子》并读的正是这一点。
C 段给出这个论证的上界,而它比通常的说法窄。矩阵假设对手能观察到足够多的手数来估计玩家的混合比例。而第八章的程序 p11 说明,估计一个小差别需要数千手。所以对一个只看了几百手的对手,确定性策略事实上不可被利用——没有足够的数据去读它。混合的论证因此是有条件的,而在休闲牌桌上那个条件通常不成立。
第二部分 钱
凯利,与一处流行说法的修正
证据
凯利准则。 Kelly 证明按最大化财富对数的比例下注,使长期增长率几乎必然最大 (Kelly 1956);Breiman 给出了更一般的结果 (Breiman 1961);MacLean、Thorp 与 Ziemba 的文集收集了理论与实践 (MacLean, Thorp, and Ziemba 2011)。Peters 把这一类问题放进非遍历性的框架 (Peters 2019)。第 19 本整本书讨论这一主题,这里只取这个博弈特有的两处。
这个博弈有两个特点改变答案。一是它在点数上零和而在金钱上负和(抽水)。二是结果不是两路赌注,而是一个分布,所以凯利比例要解 ,不能用教科书的 。
推导
# 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.三个结果。
抽水决定有没有赢家。 在本书的示意分布中,优势在每手抽水 0.0128 个买入处消失;而抽水 0.005(只占优势的 39%)就使最优注码降低 40%,抽水 0.010 使它降低 79%。注码对抽水比对优势本身敏感得多。
两路公式有错误的符号。 把这个分布当作「两成的时候赢」代入 得 ,而正确值是 。赢的时候赢得多,所以胜率低于一半与有优势完全相容;用两路公式会得出「不该下注」的结论。
增长率曲线在最优点附近近乎对称。 这是对流行说法的修正。半凯利保 75.3% 的增长率,1.5 倍凯利保 75.7%——下得太少与下得太多的代价相差不到半个百分点;只有到 2 倍凯利才塌到 3.7%。所以
「增长率曲线在上方陡降」不是降低注码的好理由,因为在任何人会选择的范围内它两边差不多。
真正的理由:优势要估计
推导
# 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.A 段给出标准误:即使 1,000 手也只把优势定到自身的四分之一左右;100 手则几乎没有信息。
B 段与 C 段给出结论。在 100 手的样本上,任何分数凯利都优于按估计值下的全凯利:0.75 倍凯利为 ,全凯利为 ,而只有 0.25 倍凯利的增长率为正()。这一优势随样本增大而收窄,在所计算的范围内并不反转——到 5,000 手时 0.75 倍凯利(0.000353)与全凯利(0.000330)已持平到三位有效数字。所以
降低注码的理由不是曲线形状,而是优势必须估计,而小样本的估计会把注码推进曲线确实塌陷的那一段。
D 段写明这个计算仍然乐观:它估计的是一个固定分布的均值,形状已知。真实的优势随对手、规则与玩家自己的进步而变,所以它不是一个被估计的固定量,而是一个移动的量。
破产
推导
# 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.三个杠杆不等权:资金与注码以指数进入破产概率,优势只以线性进入。所以就「不破产」这一目的而言,注码小比打得好更有效——但这是关于存活的陈述,不是关于赚钱的陈述,因为注码小也把收益等比例缩小。
C 段把抽水放回去:一旦抽水抵消优势,破产概率是 1。在零或负漂移下,有界的资金必然被从上方触及。这就是「抽水不是小额扣减而是决定有没有赢家」的精确含义。
假说 · 尚未验证
作者的假说(尚未确立): 在本书讨论的这类牌桌上,扣除抽水后的长期优势为正的玩家比例低于一成。什么样的结果能证明它是错的: 在一个记录完整、抽水已知的平台上,取足够长的个人序列(按第八章程序 p11,每人数千手以上),若扣除抽水后优势显著为正的玩家比例的 95% 置信区间下限超过 0.10,则本假说错。注意本假说是可以用现有平台数据检验的,而本书没有这样的数据。
本章小结
反事实遗憾最小化在两人零和博弈上确实收敛:本书验证可利用度从 0.667 降到 0.0013、博弈值收敛到 (理论 )、最差牌与最好牌的下注比为 3.01(理论 3.00);并记下一处不会报错的实现陷阱——最优反应必须按信息集算。随后是两个否定结果:在三人玩具博弈上同一算法照样把可利用度压到 ,所以「没有定理」不等于「会失败」;而本书构造的四种对手偏离没有一种把玩家压到均衡值以下,所以本书没有展示多人无价值保证现象的工作例,也不假装有。混合优于任何纯策略是定理,但它要求对手有足够观察量,而那需要数千手,所以这个论证是有条件的。钱的部分修正三处:抽水决定有没有赢家(优势在 0.0128 处消失,抽水 0.010 使注码降 79%);两路凯利公式在这里符号相反;增长率曲线在最优点附近近乎对称,所以降低注码的理由是优势要估计而非曲线形状——在 100 手样本上 0.75 倍凯利确实更好。最后,破产的三个杠杆中资金与注码以指数进入,优势只以线性进入。
参考文献
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).