关于「规模:为什么不能把信息集列出来」,《四人不完全信息博弈》给出的定量结论是什么?
结论:第一章给出规模:13 张手牌的不同多重集约有 9.85 × 10¹⁰ 个,另外三家的配置约 5.0 × 10⁴⁶ 种,所以枚举信息集是范畴错误。
数据口径:书中以标注框区分已发表的证据、可运行的 Python 计算(16 段程序)、原典与作者的模型和假说;除注明的文献数据外,书中数据都是合成的。
对照数据表
下表数字由本章 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}
}