关于「博弈的解与钱」,《四人不完全信息博弈》给出的定量结论是什么?

结论:第六章在两人零和博弈上验证反事实遗憾最小化(可利用度从 0.667 降到 0.0013,博弈值 −0.055554,理论值 −1/18),并在三人博弈上诚实地报告两个否定结果:可利用度照样降到 4 × 10⁻⁶,四种简单偏离也没能把玩家压到均衡值以下。凯利增长率曲线在最优点附近近乎对称(半凯利保 75.3%、1.5 倍凯利保 75.7%),所以降低注码的理由是估计误差而不是曲线形状。

数据口径:书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;除注明的文献数据外,书中数据都是合成的。

English version

对照数据表

下表数字由本章 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}
}

本书其他章节结论