5D Library › 四人不完全信息随机博弈、贝叶斯读牌与反事实遗憾最小化 · English

第五章 弃胡:最优停时,与一个被说反的结论

写成最优停时

一家已经明显听牌。此后每一巡,玩家要么推(打可能放铳的牌,保住自己的机会),要么弃(此后只打安全牌,放弃自己的手牌但也不再放铳)。

这是一个有限期的马尔可夫决策过程 (Puterman 1994),可以用反向归纳精确求解 (Bellman 1957);最优停时的一般理论见 Chow、Robbins 与 Siegmund (Chow, Robbins, and Siegmund 1971),第 42 本讨论过这一类问题。

关键的建模选择:弃是吸收的。一旦弃牌就一直弃到这手结束,所以弃的价值就是对手在剩余巡数内自摸的风险。

推导

# Chapter 5. Folding as optimal stopping, and the limit of that framing. With
# one opponent visibly ready, each remaining turn a player either PUSHES
# (discards a tile that may deal in, keeping their own chance alive) or FOLDS
# (discards only safe tiles for the rest of the hand, abandoning their own
# hand but no longer able to deal in). Folding is absorbing: once a player
# folds they stay folded, so the value of folding at turn t is just the
# opponent's self-draw risk over the remaining turns. Pushing is solved by
# backward induction against that. Illustrative points; standard library only.
import math

def fold_value(t, turns, p_tsumo, v_tsumo):
    """Fold now and stay folded: lose v_tsumo if the opponent self-draws at
    any
    remaining turn."""
    remaining = turns - t
    return -(1.0 - (1.0 - p_tsumo) ** remaining) * v_tsumo

def solve(turns, p_win, v_win, p_deal, v_deal, p_tsumo, v_tsumo):
    V = [0.0] * (turns + 1)
    policy = [None] * turns
    for t in range(turns - 1, -1, -1):
        # push this turn: own win, deal-in, opponent self-draw, or continue
        p_cont = 1.0 - p_win - p_deal - p_tsumo
        push = (p_win * v_win - p_deal * v_deal - p_tsumo * v_tsumo
                + p_cont * V[t + 1])
        fold = fold_value(t, turns, p_tsumo, v_tsumo)
        if push >= fold:
            V[t], policy[t] = push, "push"
        else:
            V[t], policy[t] = fold, "fold"
    return V, policy

def first_push_turn(policy):
    """Turns are indexed 0..turns-1 from now; report the first turn at which
    pushing is optimal, or None."""
    for i, a in enumerate(policy):
        if a == "push":
            return i + 1
    return None

if __name__ == "__main__":
    TURNS = 12
    VW, VD, VT = 3900, 5200, 2600
    PT = 0.03
    print("One opponent visibly ready; {} turns remain.".format(TURNS))
    print("Own win +3900, dealing in -5200,")
    print(
        "opponent self-draw -2600 at {:.0%} per turn. Folding is absorbing.\n"
        .format(PT)
    )

    print(
        "A. Own hand ready, two-sided wait (p_win 0.10 per turn), deal-in"
        " risk 0.05:"
    )
    V, pol = solve(TURNS, 0.10, VW, 0.05, VD, PT, VT)
    print("   turn from now   policy   value from here   fold value here")
    for t in range(TURNS):
        print("   {:13d}   {:6s} {:16.1f} {:17.1f}"
              .format(t + 1, pol[t], V[t], fold_value(t, TURNS, PT, VT)))

    print(
        "\nB. Policy against own win probability, deal-in risk fixed at 0.05:"
    )
    print("   p_win   turns pushed (of {})   value now".format(TURNS))
    for pw in (0.02, 0.04, 0.06, 0.08, 0.12, 0.16):
        V, pol = solve(TURNS, pw, VW, 0.05, VD, PT, VT)
        print("   {:5.2f} {:22d} {:12.1f}"
              .format(pw, sum(1 for a in pol if a == "push"), V[0]))

    print(
        "\nC. Policy against deal-in risk, own win probability fixed at 0.08:"
    )
    print("   p_deal   turns pushed (of {})   value now".format(TURNS))
    for pd in (0.01, 0.03, 0.05, 0.08, 0.12):
        V, pol = solve(TURNS, 0.08, VW, pd, VD, PT, VT)
        print("   {:6.2f} {:22d} {:12.1f}"
              .format(pd, sum(1 for a in pol if a == "push"), V[0]))

    print(
        "\nD. The one-turn indifference condition. Ignoring continuation,"
        " pushing"
    )
    print("beats folding when p_win x {} >= p_deal x {},".format(VW, VD))
    print("i.e. p_win >= p_deal x {:.3f}.".format(VD / VW))
    print(
        "   (the opponent's self-draw term cancels: folding does not"
        " prevent it)"
    )
    print("   p_deal   break-even p_win")
    for pd in (0.01, 0.03, 0.05, 0.08, 0.12):
        print("   {:6.2f} {:18.3f}".format(pd, pd * VD / VW))
    print(
        "\n   The self-draw term cancelling is the structural point, and it"
        " is often"
    )
    print(
        "   stated backwards. Folding buys protection ONLY against dealing"
        " in; it"
    )
    print(
        "   buys nothing against the opponent drawing the tile themselves."
        " So the"
    )
    print(
        "   case for folding rests entirely on p_deal, and a nearly safe tile"
        " should"
    )
    print("   be pushed even with a weak hand.")

    print(
        "\nE. What this framing gets WRONG. Three things, in order of"
        " seriousness."
    )
    print(
        "   1. It is not a decision problem at all. p_deal depends on"
        " what the"
    )
    print(
        "      opponent waits on, and a thinking opponent chooses that"
        " partly in"
    )
    print(
        "      anticipation of being read (p03). Treating p_deal as a"
        " constant"
    )
    print(
        "      assumes a non-adaptive opponent, and Chapter 6 shows what"
        " changes"
    )
    print("      when that assumption is dropped.")
    print(
        "   2. There are three opponents, not one, and their hands are"
        " dependent"
    )
    print(
        "      through the tiles nobody has drawn. A tile safe against one"
        " can be"
    )
    print(
        "      the winning tile for another, so 'fold' is not a single"
        " action."
    )
    print(
        "   3. Points are not utility. In the last hand of a match, with a"
        " deficit"
    )
    print(
        "      to make up, the correct policy can be to take a"
        " negative-expectation"
    )
    print(
        "      push, which this objective cannot express. Chapter 6"
        " treats the"
    )
    print(
        "      bankroll version of that problem and Chapter 8 the match"
        " version."
    )
# One opponent visibly ready; 12 turns remain.
# Own win +3900, dealing in -5200,
# opponent self-draw -2600 at 3% per turn. Folding is absorbing.
#
# A. Own hand ready, two-sided wait (p_win 0.10 per turn), deal-in risk 0.05:
#    turn from now   policy   value from here   fold value here
#                1   push              262.2            -796.0
#                2   push              256.3            -740.2
#                3   push              249.2            -682.7
#                4   push              240.5            -623.4
#                5   push              229.8            -562.3
#                6   push              216.9            -499.2
#                7   push              201.1            -434.3
#                8   push              181.8            -367.3
#                9   push              158.3            -298.2
#               10   push              129.6            -227.1
#               11   push               94.6            -153.7
#               12   push               52.0             -78.0
#
# B. Policy against own win probability, deal-in risk fixed at 0.05:
#    p_win   turns pushed (of 12)   value now
#     0.02                      0       -796.0
#     0.04                      0       -796.0
#     0.06                      8       -609.8
#     0.08                     12       -142.4
#     0.12                     12        605.3
#     0.16                     12       1147.4
#
# C. Policy against deal-in risk, own win probability fixed at 0.08:
#    p_deal   turns pushed (of 12)   value now
#      0.01                     12       1189.6
#      0.03                     12        466.0
#      0.05                     12       -142.4
#      0.08                      2       -777.3
#      0.12                      0       -796.0
#
# D. The one-turn indifference condition. Ignoring continuation, pushing
# beats folding when p_win x 3900 >= p_deal x 5200,
# i.e. p_win >= p_deal x 1.333.
#    (the opponent's self-draw term cancels: folding does not prevent it)
#    p_deal   break-even p_win
#      0.01              0.013
#      0.03              0.040
#      0.05              0.067
#      0.08              0.107
#      0.12              0.160
#
#    The self-draw term cancelling is the structural point, and it is often
#    stated backwards. Folding buys protection ONLY against dealing in; it
#    buys nothing against the opponent drawing the tile themselves. So the
#    case for folding rests entirely on p_deal, and a nearly safe tile should
#    be pushed even with a weak hand.
#
# E. What this framing gets WRONG. Three things, in order of seriousness.
#    1. It is not a decision problem at all. p_deal depends on what the
#       opponent waits on, and a thinking opponent chooses that partly in
#       anticipation of being read (p03). Treating p_deal as a constant
#       assumes a non-adaptive opponent, and Chapter 6 shows what changes
#       when that assumption is dropped.
#    2. There are three opponents, not one, and their hands are dependent
#       through the tiles nobody has drawn. A tile safe against one can be
#       the winning tile for another, so 'fold' is not a single action.
#    3. Points are not utility. In the last hand of a match, with a deficit
#       to make up, the correct policy can be to take a negative-expectation
#       push, which this objective cannot express. Chapter 6 treats the
#       bankroll version of that problem and Chapter 8 the match version.

相消的那一项

D 段是本章的主结果,而它常被说反。

一巡的无差异条件是:推优于弃当且仅当

pwin×3900≥pdeal×5200,p_{\text{win}}\times 3900 \ \ge\ p_{\text{deal}}\times 5200,

也就是 pwin≥1.333pdealp_{\text{win}} \ge 1.333\,p_{\text{deal}}。对手自摸的那一项不出现在条件里——因为弃牌不防自摸,所以它在推与弃两边相等,相消了。于是

弃牌只防放铳。因此弃牌的全部理由落在放铳概率上,而一张接近安全的牌即使手牌很弱也该推。

常见的说法是「拿不准就弃」,而按上面的条件,拿不准时要看的是这张牌有多危险,不是手牌有多弱。两者在手牌弱而牌很安全时给出相反的建议,而那种情形很常见。

推与弃的无差异边界。横轴为放铳概率,纵轴为自己的和牌概率;边界是斜率 1.333 的直线,与对手自摸概率无关。边界上方推,下方弃。

B 段与 C 段给出策略随两个参数的变化,而方向是单调的:自己的和牌概率越高推得越久,放铳概率越高推得越短。A 段给出一个具体的轨迹,并把每一巡的弃牌价值列在旁边,便于看出比较是怎么做出来的。

这个框架不成立的三处

E 段写明三处,按严重程度排列。

第一,它根本不是决策问题。 放铳概率依赖对手听什么,而一个会思考的对手部分是针对「自己会被读」来选择听牌与舍牌的(第三章)。把 pdealp_{\text{deal}} 当作常数就是假设了一个不适应的对手,而第六章说明对适应的对手没有固定规则是安全的。

第二,有三家而不是一家。 而且三家的手牌通过「谁都没摸到的牌」相依,所以一张对一家安全的牌可能正是另一家的和牌张。「弃牌」因此不是一个单一的行动——弃给一家可能喂另一家。本书的模型只处理一家,这是一处明确的简化。

第三,点数不是效用。 在一场比赛的最后一局,要追分时,正确的策略可以是接受负期望的推——因为目标是排名而不是点数。这个目标函数无法表达这件事。第六章处理资金层面的同一问题(凯利与破产),第八章把它作为终局条件处理。

假说 · 尚未验证

作者的假说(尚未确立): 在固定对手池上,一个按本章的无差异条件(只看放铳概率与自己的和牌概率,不看自己手牌的「弱」)决定推弃的策略,优于一个以手牌强弱为主要依据的策略。什么样的结果能证明它是错的: 在第八章的重复对局设计中,若该比较的点数差的 95% 置信区间包含零或方向相反,则本假说错。

注

与第 42 本的关系。 第 42 本讨论贝叶斯搜索与最优停止,那里的对象是单人决策问题,停止规则有干净的最优性结果。本章的差别正是第一处限制:这里的「环境」会回应,所以最优停时的标准结果只在把对手冻结之后才适用。把单人停止理论直接搬到博弈上,是这一类分析里最常见的越界。

本章小结

把弃牌写成有限期马尔可夫决策过程并反向归纳求解,得到阈值策略:自己的和牌概率越高推得越久,放铳概率越高推得越短。主要结果是一个常被说反的结构性结论:对手自摸的项在推与弃的比较中相消,因为弃牌只防放铳不防自摸,所以无差异条件只含放铳概率与自己的和牌概率(这里是 pwin≥1.333pdealp_{\text{win}} \ge 1.333\,p_{\text{deal}})。于是一张接近安全的牌即使手牌很弱也该推,这与「拿不准就弃」相反。该框架有三处不成立:放铳概率依赖会适应的对手,所以这不是决策问题;有三家且手牌相依,所以「弃」不是单一行动;点数不是效用,最后一局追分时正确的策略可以是负期望的推。

参考文献

Bellman, Richard. 1957. Dynamic Programming. Princeton: Princeton University Press.
Chow, Y. S., Herbert Robbins, and David Siegmund. 1971. Great Expectations: The Theory of Optimal Stopping. Boston: Houghton Mifflin.
Puterman, Martin L. 1994. Markov Decision Processes: Discrete Stochastic Dynamic Programming. New York: Wiley.

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).