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

第一章 规模:为什么不能把信息集列出来

博弈的形式

先把对象写清楚。一张四人牌桌是一个扩展式博弈:参与者轮流行动,行动之间插入随机节点(摸牌),而每个参与者在行动时只知道自己观察到的历史。von Neumann 与 Morgenstern 建立了这一形式 (Neumann and Morgenstern 1944),Nash 给出了非合作博弈的均衡概念 (Nash 1951),Osborne 与 Rubinstein 的教科书给出了标准处理 (Osborne and Rubinstein 1994)。

关键概念是信息集:所有在该参与者看来无法区分的历史的集合。玩家在信息集上行动,而不是在历史上行动——这是不完全信息博弈与象棋一类完全信息博弈的全部差别所在。

注

本书的规则假设。 本书使用标准的 34 种牌、每种 4 张共 136 张的牌组(三门数牌各 9 种,加 7 种字牌),13 张手牌,14 张王牌区不摸。番种与计分只在需要时以示意值出现,而本书的结论都不依赖具体的计分规则。凡涉及具体规则的地方,书中标明该结论对规则的依赖。

数一数

推导

# Chapter 1. How big is the game? Exact counts for the standard 34-type,
# 136-tile set (four copies of each of 34 types: 9 each in three numbered
# suits, plus 7 honours). The numbers matter because they decide which
# solution methods are even available: a game whose information sets number
# 10^x for large x cannot be solved by tabulating them, which is why Chapter
# 6's discussion of regret minimisation is about ABSTRACTIONS rather than
# about the game itself. Exact integer arithmetic, standard library only.
import math
from functools import lru_cache

TYPES, COPIES = 34, 4

@lru_cache(maxsize=None)
def multisets(n_types, n_tiles, copies=COPIES):
    """Number of multisets of size n_tiles from n_types types with at most
    `copies` each."""
    if n_tiles == 0:
        return 1
    if n_types == 0:
        return 0
    return sum(multisets(n_types - 1, n_tiles - k, copies)
               for k in range(0, min(copies, n_tiles) + 1))

def hands_with_counts(n_tiles):
    """Distinct hands of n_tiles as multisets, respecting the four-copy
    limit."""
    return multisets(TYPES, n_tiles)

def deals(n_tiles):
    """Number of distinguishable deals weighted by how many ways they can be
    drawn:
    this equals C(136, n) only if tiles of a type were distinguishable."""
    return math.comb(TYPES * COPIES, n_tiles)

if __name__ == "__main__":
    print("Standard set: {} types x {} copies = {} tiles.\n"
          .format(TYPES, COPIES, TYPES * COPIES))

    print(
        "A. Distinct hands as multisets (tiles of one type"
        " indistinguishable):"
    )
    print("   hand size   distinct hands")
    for n in (13, 14):
        print("   {:9d} {:17,d}".format(n, hands_with_counts(n)))

    print(
        "\nB. If tiles were all distinguishable, the number of 13-tile"
        " subsets:"
    )
    print("   C(136, 13) = {:,d}".format(deals(13)))
    print("   ratio to the multiset count: {:,.0f}"
          .format(deals(13) / hands_with_counts(13)))
    print(
        "   (so treating tiles as distinguishable overcounts by this factor;"
        " every"
    )
    print("    model below works with multisets)")

    print(
        "\nC. One player's own information at the first discard, as an"
        " order of"
    )
    print(
        "magnitude. The player knows: their 13 tiles, the seat winds, and"
        " nothing"
    )
    print(
        "about the other 3 x 13 = 39 concealed tiles or the 83 tiles in the"
        " wall."
    )
    # minus own hand and the dead wall
    unseen = TYPES * COPIES - 13 - 14
    print("   tiles not seen by this player: {}".format(unseen))
    print(
        "   ways the other three hands could be composed, as an ordered"
        " partition"
    )
    print(
        "   of 39 of those tiles into three hands of 13 -- an upper bound"
        " using"
    )
    print("   distinguishable tiles:")
    ub = (
        math.comb(unseen, 13)
        * math.comb(unseen - 13, 13)
        * math.comb(unseen - 26, 13)
    )
    print("   {:.3e}".format(ub))

    print(
        "\nD. Why this rules out tabulation. Suppose one byte per information"
        " set:"
    )
    for label, n in (("distinct 13-tile hands", hands_with_counts(13)),
                     ("hands x three-opponent configurations (upper bound)",
                      hands_with_counts(13) * ub)):
        print("   {:52s} {:.3e} bytes".format(label, float(n)))
    h13 = hands_with_counts(13)
    print("   rounded: {:.2f} x 10^10 hands, {:.1f} x 10^46 configurations,"
          .format(h13 / 1e10, ub / 1e46))
    print("   product {:.1f} x 10^57 bytes".format(h13 * ub / 1e57))
    print(
        "   The observable universe holds about 10^80 atoms, so the second"
        " line is"
    )
    print(
        "   not a storage problem but a category error: the game cannot be"
        " solved by"
    )
    print(
        "   enumerating its information sets, and every method in Chapter 6"
        " operates"
    )
    print("   on an abstraction with a vastly smaller state space.")

    print(
        "\nE. A useful smaller number: the count of distinct 14-tile winning"
        " shapes"
    )
    print(
        "is what a shanten calculator must recognise. Counting standard"
        " shapes"
    )
    print("(four sets plus a pair, ignoring sevenpairs and thirteenorphans):")
    # count melds by type: runs only within a numbered suit, triplets anywhere
    runs = 3 * 7              # three suits x starting values 1..7
    triplets = TYPES
    print(
        "   distinct run types: {}; distinct triplet types: {}".format(
            runs, triplets
        )
    )
    print("   distinct meld types: {}".format(runs + triplets))
    print("   multisets of 4 melds from {} types: {:,d}"
          .format(runs + triplets, math.comb(runs + triplets + 3, 4)))
    print("   times {} choices of pair = {:,d} nominal shapes before removing"
          .format(TYPES, math.comb(runs + triplets + 3, 4) * TYPES))
    print(
        "   those needing a fifth copy of some tile. The exact legal count is"
    )
    print(
        "   smaller; the point is that it is in the millions, not the"
        " billions,"
    )
    print("   which is why Chapter 4's dynamic programme over tile counts is")
    print("   feasible while enumerating information sets is not.")
# Standard set: 34 types x 4 copies = 136 tiles.
#
# A. Distinct hands as multisets (tiles of one type indistinguishable):
#    hand size   distinct hands
#           13    98,521,596,000
#           14   326,520,504,500
#
# B. If tiles were all distinguishable, the number of 13-tile subsets:
#    C(136, 13) = 483,774,556,165,488,000
#    ratio to the multiset count: 4,910,340
#    (so treating tiles as distinguishable overcounts by this factor; every
#     model below works with multisets)
#
# C. One player's own information at the first discard, as an order of
# magnitude. The player knows: their 13 tiles, the seat winds, and nothing
# about the other 3 x 13 = 39 concealed tiles or the 83 tiles in the wall.
#    tiles not seen by this player: 109
#    ways the other three hands could be composed, as an ordered partition
#    of 39 of those tiles into three hands of 13 -- an upper bound using
#    distinguishable tiles:
#    4.992e+46
#
# D. Why this rules out tabulation. Suppose one byte per information set:
#    distinct 13-tile hands                               9.852e+10 bytes
#    hands x three-opponent configurations (upper bound)  4.918e+57 bytes
#    rounded: 9.85 x 10^10 hands, 5.0 x 10^46 configurations,
#    product 4.9 x 10^57 bytes
#    The observable universe holds about 10^80 atoms, so the second line is
#    not a storage problem but a category error: the game cannot be solved by
#    enumerating its information sets, and every method in Chapter 6 operates
#    on an abstraction with a vastly smaller state space.
#
# E. A useful smaller number: the count of distinct 14-tile winning shapes
# is what a shanten calculator must recognise. Counting standard shapes
# (four sets plus a pair, ignoring sevenpairs and thirteenorphans):
#    distinct run types: 21; distinct triplet types: 34
#    distinct meld types: 55
#    multisets of 4 melds from 55 types: 424,270
#    times 34 choices of pair = 14,425,180 nominal shapes before removing
#    those needing a fifth copy of some tile. The exact legal count is
#    smaller; the point is that it is in the millions, not the billions,
#    which is why Chapter 4's dynamic programme over tile counts is
#    feasible while enumerating information sets is not.

把这些数读一遍。

13 张手牌的不同多重集有 985 亿个(9.85×10109.85\times10^{10})。这个数本身是可以处理的:按一字节一个,不到 100 GB。

但信息集不是手牌。一名玩家在首次打牌时所处的信息集,要把另外三家的可能配置也算进去——因为那些配置在该玩家看来无法区分,而博弈的解要对每个信息集指定行动。用可区分牌张的上界算,另外三家配置数约 5.0×10465.0\times10^{46};与手牌数相乘约 4.9×10574.9\times10^{57} 字节。可观测宇宙约有 108010^{80} 个原子。

所以

枚举信息集不是一个「需要很大硬盘」的问题,而是方法上的范畴错误。

这一点决定了第六章的全部内容。两人扑克的求解器——Bowling 等人解出单挑限注德州扑克 (Bowling et al. 2015)、DeepStack (Moravčík et al. 2017)、Brown 与 Sandholm 的 Libratus (Brown and Sandholm 2018)——都不是在原博弈上工作,而是在抽象上工作:把相似的信息集归并成桶,在抽象博弈上求解,再把解映射回原博弈。微软的 Suphx 用深度强化学习处理四人麻将,并引入全局奖励预测、先知引导与运行时策略适应三项技术 (Li et al. 2020);Mizukami 与 Tsuruoka 较早用蒙特卡洛模拟与对手模型构建麻将程序 (Mizukami and Tsuruoka 2015)。这些都是抽象或近似,没有一个在原信息集上穷举。

证据

可以确定的是什么。 上述程序的规模与可行性结论是算术,不依赖任何经验假设。关于求解器的事实也是可核实的:Bowling 等人 2015 年报告单挑限注德州扑克「本质上已被解决」(Bowling et al. 2015),Brown 与 Sandholm 2019 年报告六人无限注德州扑克的超人表现 (Brown and Sandholm 2019),Li 等人报告 Suphx 在天凤平台上的评分高于 99.99% 的有段位人类玩家 (Li et al. 2020)。不能确定的是这些结果能否推广到本书讨论的规则与牌桌,因为规则、计分与对手池都不同。

可以处理的那个数

程序的最后一段算出一个小得多的数:四面子加一对的不同牌型在百万量级,而不是十亿量级。这就是为什么第四章的向聴动态规划是可行的——它在牌张计数向量上工作,不在信息集上工作。

这给出本书的方法论原则:

凡是只依赖自己手牌的量(向聴、进张、手牌价值),都可以精确计算;凡是依赖对手手牌的量(放铳概率、对手的听牌),都只能在模型与先验下估计。

第二章到第四章处理第一类,第三章与第五章处理第二类,而两类的可信度相差很远。本书在每一处都标明属于哪一类。

假说 · 尚未验证

作者的假说(尚未确立): 在本书讨论的规则下,一个只使用第一类量(自己手牌的向聴、进张与价值)加上一条固定的放铳概率表的策略,与一个额外使用逐手牌贝叶斯读牌的策略相比,在固定对手池上的点数差小于每个计分决策 0.01 个买入。什么样的结果能证明它是错的: 在第八章的重复对局设计中,若读牌策略相对固定表策略的点数差的 95% 置信区间下限大于 0.01,则本假说错。注意这个假说是可以用第八章的方案直接检验的,而它的内容是:读牌的边际价值可能比通常假设的小。

本章小结

四人牌桌是一个不完全信息的扩展式博弈,解要对信息集而不是对历史指定行动。13 张手牌的不同多重集有 985 亿个,这个数可以处理;但一名玩家首次打牌时的信息集还要包含另外三家的配置,其上界约 5.0×10465.0\times10^{46},与手牌数相乘约 4.9×10574.9\times10^{57} 字节——远超可观测宇宙的原子数,所以枚举信息集是范畴错误而非存储问题。已有的求解器与麻将程序全部在抽象或近似上工作,这一点在第六章展开。另一方面,四面子加一对的牌型只有百万量级,所以在牌张计数向量上做动态规划是可行的。由此得到本书的方法论原则:只依赖自己手牌的量可以精确计算,依赖对手手牌的量只能在模型与先验下估计,而两者的可信度相差很远。

参考文献

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.
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.
Li, Junjie, Sotetsu Koyamada, Qiwei Ye, Guoqing Liu, Chao Wang, Ruihan Yang, Li Zhao, Tao Qin, Tie-Yan Liu, and Hsiao-Wuen Hon. 2020. “Suphx: Mastering Mahjong with Deep Reinforcement Learning.” arXiv:2003.13590 [cs.AI]. https://doi.org/10.48550/arXiv.2003.13590.
Mizukami, Naoki, and Yoshimasa Tsuruoka. 2015. “Building a Computer Mahjong Player Based on Monte Carlo Simulation and Opponent Models.” In 2015 IEEE Conference on Computational Intelligence and Games (CIG), 275–83. https://doi.org/10.1109/CIG.2015.7317929.
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.
Nash, John. 1951. “Non-Cooperative Games.” Annals of Mathematics 54 (2): 286–95. https://doi.org/10.2307/1969529.
Neumann, John von, and Oskar Morgenstern. 1944. Theory of Games and Economic Behavior. Princeton: Princeton University Press.
Osborne, Martin J., and Ariel Rubinstein. 1994. A Course in Game Theory. Cambridge, Massachusetts: MIT Press.

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