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 亿个()。这个数本身是可以处理的:按一字节一个,不到 100 GB。
但信息集不是手牌。一名玩家在首次打牌时所处的信息集,要把另外三家的可能配置也算进去——因为那些配置在该玩家看来无法区分,而博弈的解要对每个信息集指定行动。用可区分牌张的上界算,另外三家配置数约 ;与手牌数相乘约 字节。可观测宇宙约有 个原子。
所以
枚举信息集不是一个「需要很大硬盘」的问题,而是方法上的范畴错误。
这一点决定了第六章的全部内容。两人扑克的求解器——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 亿个,这个数可以处理;但一名玩家首次打牌时的信息集还要包含另外三家的配置,其上界约 ,与手牌数相乘约 字节——远超可观测宇宙的原子数,所以枚举信息集是范畴错误而非存储问题。已有的求解器与麻将程序全部在抽象或近似上工作,这一点在第六章展开。另一方面,四面子加一对的牌型只有百万量级,所以在牌张计数向量上做动态规划是可行的。由此得到本书的方法论原则:只依赖自己手牌的量可以精确计算,依赖对手手牌的量只能在模型与先验下估计,而两者的可信度相差很远。
参考文献
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).