关于「规模:为什么不能把信息集列出来」,《四人不完全信息博弈》给出的定量结论是什么?

结论:第一章给出规模:13 张手牌的不同多重集约有 9.85 × 10¹⁰ 个,另外三家的配置约 5.0 × 10⁴⁶ 种,所以枚举信息集是范畴错误。

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

English version

对照数据表

下表数字由本章 Python 程序原样打印,可重新运行复现。 程序只用 Python 标准库与结论吻合的打印值: 10, 13, 5.0, 9.85

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
查看完整验算程序
# 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.")

唯一数据源与引用

范雅福(Fan, Y.). (2026). 《四人不完全信息随机博弈、贝叶斯读牌与反事实遗憾最小化》第 1 章「规模:为什么不能把信息集列出来」(版本 1.0.0). 5D Library. https://doi.org/10.5281/zenodo.24020464

DOI: 10.5281/zenodo.24020464 · 阅读本章所在专著 · 5DL-B-055 · v1.0.0 · CC-BY-NC-ND-4.0

BibTeX
@book{fan2026055,
  author    = {Fan, Yafu},
  title     = {Imperfect-Information Stochastic Games, Bayesian Hand-Reading and Counterfactual Regret Minimisation in Four-Player Tile Dynamics},
  year      = {2026},
  publisher = {5D Library},
  edition   = {1.0.0},
  doi       = {10.5281/zenodo.24020464},
  url       = {https://doi.org/10.5281/zenodo.24020464}
}

本书其他章节结论