5D Library › Imperfect-Information Stochastic Games, Bayesian Hand-Reading and Counterfactual Regret Minimisation in Four-Player Tile Dynamics · 中文
Chapter 1. Scale: Why the Information Sets Cannot Be Listed
The form of the game
First the object, stated clearly. A four-person table is an extensive-form game: players act in turn, chance nodes are interleaved (drawing), and each player acting knows only the history they have observed. von Neumann and Morgenstern established this form (Neumann and Morgenstern 1944), Nash gave the equilibrium concept for non-cooperative games (Nash 1951), and Osborne and Rubinstein’s textbook gives the standard treatment (Osborne and Rubinstein 1994).
The key concept is the information set: the set of all histories that are indistinguishable to the player about to act. Players act on information sets, not on histories — and that is the whole difference between an imperfect-information game and a perfect-information game such as chess.
Note
This book’s rule assumptions. The book uses the standard set of 34 tile types with four copies each, 136 tiles in all (nine in each of three numbered suits plus seven honours), 13-tile hands, and a 14-tile dead wall that is not drawn. Scoring appears only as illustrative values where needed, and none of the book’s conclusions depends on a particular scoring rule. Where a conclusion does depend on a rule, the dependence is stated.
Counting
Calculation
# 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.Read these numbers once through.
There are distinct 13-tile multisets. That number is by itself tractable: at one byte each, under 100 GB.
But an information set is not a hand. The information set a player occupies at their first discard has to include the possible configurations of the other three hands, because those configurations are indistinguishable to that player, and a solution of the game must prescribe an action at every information set. Using an upper bound with distinguishable tiles, the other three hands admit about configurations; multiplied by the hand count that is about bytes. The observable universe holds about atoms.
So
enumerating information sets is not a problem of needing a big disk. It is a methodological category error.
That determines the whole content of Chapter 6. The two-player poker solvers — Bowling and colleagues’ solution of heads-up limit hold’em (Bowling et al. 2015), DeepStack (Moravčík et al. 2017), Brown and Sandholm’s Libratus (Brown and Sandholm 2018) — do not work on the original game but on an abstraction: similar information sets are bucketed, the abstract game is solved, and the solution is mapped back. Microsoft’s Suphx handles four-player mahjong with deep reinforcement learning and introduces global reward prediction, oracle guiding and run-time policy adaptation (Li et al. 2020); Mizukami and Tsuruoka earlier built a mahjong program from Monte Carlo simulation and opponent models (Mizukami and Tsuruoka 2015). All of these are abstractions or approximations; none enumerates the original information sets.
Evidence
What can be stated. The scale and feasibility conclusions above are arithmetic and depend on no empirical assumption. The facts about the solvers are also checkable: Bowling and colleagues reported in 2015 that heads-up limit hold’em is “essentially solved” (Bowling et al. 2015), Brown and Sandholm reported superhuman performance at six-player no-limit hold’em in 2019 (Brown and Sandholm 2019), and Li and colleagues reported that Suphx is rated above 99.99 % of ranked human players on the Tenhou platform (Li et al. 2020). What cannot be stated is whether those results transfer to the rules and tables this book discusses, since the rules, the scoring and the opponent pool all differ.
The number that is tractable
The program’s last section computes a much smaller quantity: the distinct shapes of four sets plus a pair are in the millions, not the billions. That is why the shanten dynamic programme of Chapter 4 is feasible — it works on tile count vectors, not on information sets.
This yields the book’s methodological principle:
Quantities that depend only on one’s own tiles (shanten, acceptance, hand value) can be computed exactly; quantities that depend on opponents’ tiles (deal-in probability, what an opponent waits on) can only be estimated under a model and a prior.
Chapters 2 and 4 handle the first kind, Chapters 3 and 5 the second, and the two differ greatly in how much they can be trusted. The book marks which kind is in play at every point.
Hypothesis · not established
The author’s hypothesis (not established): under the rules discussed here, a policy using only quantities of the first kind (one’s own shanten, acceptance and hand value) plus a single fixed table of deal-in probabilities differs from a policy that additionally performs hand-by-hand Bayesian reading by less than 0.01 buy-ins per scored decision against a fixed opponent pool. What would show it to be wrong: in the duplicate design of Chapter 8, a lower bound above 0.01 on the 95 % confidence interval for the reading policy’s advantage would refute it. Note that this hypothesis is directly testable with the Chapter 8 protocol, and its content is that the marginal value of hand reading may be smaller than usually assumed.
Summary
A four-person table is an imperfect-information extensive-form game whose solution prescribes actions at information sets rather than at histories. There are distinct 13-tile multisets, which is tractable; but a player’s information set at their first discard must also contain the other three hands’ configurations, bounded above by about , and the product is about bytes — far beyond the atom count of the observable universe, so enumerating information sets is a category error rather than a storage problem. Every existing solver and mahjong program works on an abstraction or an approximation, which Chapter 6 takes up. On the other hand the shapes of four sets plus a pair number only in the millions, so dynamic programming over tile count vectors is feasible. Hence the book’s methodological principle: quantities depending only on one’s own tiles can be computed exactly, quantities depending on opponents’ tiles can only be estimated under a model and a prior, and the two differ greatly in reliability.
References
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).