关于「博弈的解与钱」,《四人不完全信息博弈》给出的定量结论是什么?
结论:第六章在两人零和博弈上验证反事实遗憾最小化(可利用度从 0.667 降到 0.0013,博弈值 −0.055554,理论值 −1/18),并在三人博弈上诚实地报告两个否定结果:可利用度照样降到 4 × 10⁻⁶,四种简单偏离也没能把玩家压到均衡值以下。凯利增长率曲线在最优点附近近乎对称(半凯利保 75.3%、1.5 倍凯利保 75.7%),所以降低注码的理由是估计误差而不是曲线形状。
数据口径:书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;除注明的文献数据外,书中数据都是合成的。
对照数据表
下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 0.0013, 0.667, 10, 18
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,查看完整验算程序
# 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.")唯一数据源与引用
范雅福(Fan, Y.). (2026). 《四人不完全信息随机博弈、贝叶斯读牌与反事实遗憾最小化》第 6 章「博弈的解与钱」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24020464
DOI: 10.5281/zenodo.24020464 · 阅读本章所在专著 · 5DL-B-055 · v1.0.0 · CC-BY-NC-ND-4.0
BibTeX
@book{fan2026055,
author = {Fan, Yafu},
title = {Imperfect-Information Stochastic Games, Bayesian Hand-Reading and Counterfactual Regret Minimisation in Four-Player Tile Dynamics},
year = {2026},
publisher = {5D Library},
edition = {1.0.0},
doi = {10.5281/zenodo.24020464},
url = {https://doi.org/10.5281/zenodo.24020464}
}