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;博弈值收敛到 −0.055554-0.055554,而该博弈对先手的已知值是 −1/18=−0.055556-1/18 = -0.055556;平均策略用最差牌下注的比例与用最好牌下注的比例之比为 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.

本书的第一个否定结果是:在这个三人玩具博弈上,同一算法照样把可利用度压到 4×10−64\times10^{-6}。 也就是说,它找到了非常接近均衡的东西。

可利用度随迭代次数的下降,两人零和博弈(实线,程序 p07)与三人博弈(虚线,程序 p08),双对数坐标。两条曲线上的数值即两段程序打印的数值。三人博弈没有收敛定理,而它在这里降得比两人的更低。

这必须照实报告:「没有收敛定理」不等于「算法会失败」。Abou Risk 与 Szafron 把 CFR 用于三人扑克,得到有竞争力的代理,而同样没有保证 (Abou Risk and Szafron 2010);Brown 与 Sandholm 的六人扑克结果也是在没有多人保证的情况下取得的 (Brown and Sandholm 2019)。缺的是保证,不一定是结果。

第二个否定结果:本书没有工作例

多人博弈还有另一个问题,而它不随算法收敛而消失。在两人零和博弈中,均衡策略保证至少拿到博弈值,无论对手怎么打。多人博弈中没有这条保证。

本书想给这件事一个工作例,于是构造了四种简单的对手偏离。结果是:没有一种把玩家压到均衡值以下——每一种都让玩家更好,因为在那个博弈里乱下注是亏的,偏离者自己付钱。

所以

本书没有一个展示多人「无价值保证」现象的工作例,并且不假装有。

能确定的只有两件事,而要分开说:一件是哪些定理存在——两人零和的价值保证没有多人对应物,这与任何具体博弈无关;另一件是在某个具体博弈里这个缺口是否咬人——这是经验问题,而在本书的玩具博弈里它没有咬人。对手联盟的完整最小化(约 1.7×1071.7\times10^{7} 个策略组合)未算,所以更强的偏离可能存在而本书没有找到。

注

为什么把两个否定结果都写出来。 按第 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.

这是一个 2×22\times2 零和博弈,有唯一的混合均衡:以 0.1667 的概率打有价值的那张牌。A 段的要点是:两个确定性策略都比混合差——总是打价值牌值 −2.00-2.00,总是打安全牌值 −0.50-0.50,而均衡混合值 +0.0833+0.0833。混合优于任何一个纯选择,这在单人决策问题里不可能,在博弈里是常态。

B 段给出损失曲线:在均衡处有一个折点,两侧线性上升。所以「总是出奇」与「从不出奇」同样错,而正确的比例不是品味问题——它由支付矩阵唯一决定。第七章与《孙子》并读的正是这一点。

C 段给出这个论证的上界,而它比通常的说法窄。矩阵假设对手能观察到足够多的手数来估计玩家的混合比例。而第八章的程序 p11 说明,估计一个小差别需要数千手。所以对一个只看了几百手的对手,确定性策略事实上不可被利用——没有足够的数据去读它。混合的论证因此是有条件的,而在休闲牌桌上那个条件通常不成立。

第二部分 钱

凯利,与一处流行说法的修正

证据

凯利准则。 Kelly 证明按最大化财富对数的比例下注,使长期增长率几乎必然最大 (Kelly 1956);Breiman 给出了更一般的结果 (Breiman 1961);MacLean、Thorp 与 Ziemba 的文集收集了理论与实践 (MacLean, Thorp, and Ziemba 2011)。Peters 把这一类问题放进非遍历性的框架 (Peters 2019)。第 19 本整本书讨论这一主题,这里只取这个博弈特有的两处。

这个博弈有两个特点改变答案。一是它在点数上零和而在金钱上负和(抽水)。二是结果不是两路赌注,而是一个分布,所以凯利比例要解 E[X/(1+fX)]=0E[X/(1+fX)] = 0,不能用教科书的 f=p−qf = p – q。

推导

# 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%。注码对抽水比对优势本身敏感得多。

两路公式有错误的符号。 把这个分布当作「两成的时候赢」代入 f=p−qf = p – q 得 0.27−0.73=−0.470.27 – 0.73 = -0.47,而正确值是 +0.0696+0.0696。赢的时候赢得多,所以胜率低于一半与有优势完全相容;用两路公式会得出「不该下注」的结论。

增长率曲线在最优点附近近乎对称。 这是对流行说法的修正。半凯利保 75.3% 的增长率,1.5 倍凯利保 75.7%——下得太少与下得太多的代价相差不到半个百分点;只有到 2 倍凯利才塌到 3.7%。所以

「增长率曲线在上方陡降」不是降低注码的好理由,因为在任何人会选择的范围内它两边差不多。

凯利增长率随注码变化。最优点标出,灰带为最优点的 0.5 到 1.5 倍。曲线在该范围内近乎对称,只有在更大的注码上才塌陷。

真正的理由:优势要估计

推导

# 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.001680-0.001680,全凯利为 −0.003106-0.003106,而只有 0.25 倍凯利的增长率为正(+0.000121+0.000121)。这一优势随样本增大而收窄,在所计算的范围内并不反转——到 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、博弈值收敛到 −0.055554-0.055554(理论 −1/18-1/18)、最差牌与最好牌的下注比为 3.01(理论 3.00);并记下一处不会报错的实现陷阱——最优反应必须按信息集算。随后是两个否定结果:在三人玩具博弈上同一算法照样把可利用度压到 4×10−64\times10^{-6},所以「没有定理」不等于「会失败」;而本书构造的四种对手偏离没有一种把玩家压到均衡值以下,所以本书没有展示多人无价值保证现象的工作例,也不假装有。混合优于任何纯策略是定理,但它要求对手有足够观察量,而那需要数千手,所以这个论证是有条件的。钱的部分修正三处:抽水决定有没有赢家(优势在 0.0128 处消失,抽水 0.010 使注码降 79%);两路凯利公式在这里符号相反;增长率曲线在最优点附近近乎对称,所以降低注码的理由是优势要估计而非曲线形状——在 100 手样本上 0.75 倍凯利确实更好。最后,破产的三个杠杆中资金与注码以指数进入,优势只以线性进入。

参考文献

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

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