5D Library › 四人不完全信息随机博弈、贝叶斯读牌与反事实遗憾最小化 · English
第四章 向聴、进张与赛跑:忽略三家会高估胜率
向聴数与进张
「还差几张才听牌」这个量叫向聴数,而它可以精确计算。标准型的和牌是四个面子加一对,所以向聴数由手牌能分解出的面子数与搭子数决定。计算方法是对每一门的牌张计数向量作递归分解,取面子数最多、其次搭子数最多的分解 (Bellman 1957)。
推导
# Chapter 4. Shanten (distance from a ready hand) and acceptance, by dynamic
# programming over tile counts. Shanten is defined as 2*(4 - melds) - partials
# - has_pair, floored appropriately; the standard recursive decomposition over
# a suit's count vector gives
# the maximum number of melds and partial sets, and the three suits plus
# honours combine additively subject to the four-meld-plus-one-pair target.
# This program implements that decomposition exactly for the standard shape
# (it does not handle seven pairs or thirteen orphans), then computes
# ACCEPTANCE: the set of tile types that lower shanten, and the number of live
# copies of each. Standard library only.
from functools import lru_cache
SUIT_LEN = 9
def parse(s):
"""'123406789' style string of counts per value, or a hand like '123m' ->
counts."""
return tuple(int(c) for c in s)
@lru_cache(maxsize=None)
def suit_best(counts, want_pair):
"""(melds, partials, pair_used) maximising melds then partials for one
suit."""
counts = list(counts)
i = 0
while i < SUIT_LEN and counts[i] == 0:
i += 1
if i == SUIT_LEN:
return (0, 0, 0)
best = (-1, -1, 0)
def rec(idx, c, melds, partials, pair):
nonlocal best
while idx < SUIT_LEN and c[idx] == 0:
idx += 1
if idx == SUIT_LEN:
key = (melds, partials, pair)
if (melds, partials, pair) > best:
best = key
return
# triplet
if c[idx] >= 3:
c[idx] -= 3
rec(idx, c, melds + 1, partials, pair)
c[idx] += 3
# run
if idx + 2 < SUIT_LEN and c[idx] and c[idx + 1] and c[idx + 2]:
c[idx] -= 1; c[idx + 1] -= 1; c[idx + 2] -= 1
rec(idx, c, melds + 1, partials, pair)
c[idx] += 1; c[idx + 1] += 1; c[idx + 2] += 1
# pair (as the hand's pair, at most once overall - handled by caller)
if c[idx] >= 2:
c[idx] -= 2
rec(idx, c, melds, partials + 1, pair)
c[idx] += 2
# partial run: idx, idx+1 and idx, idx+2
for step in (1, 2):
if idx + step < SUIT_LEN and c[idx] and c[idx + step]:
c[idx] -= 1; c[idx + step] -= 1
rec(idx, c, melds, partials + 1, pair)
c[idx] += 1; c[idx + step] += 1
# drop this tile
c[idx] -= 1
rec(idx, c, melds, partials, pair)
c[idx] += 1
rec(i, counts, 0, 0, 0)
return best
def shanten(hand):
"""hand: dict of (suit, value) -> count, suits 0,1,2 numbered and 3
honours."""
suits = []
for s in range(3):
suits.append(
tuple(hand.get((s, v), 0) for v in range(1, SUIT_LEN + 1))
)
hon = tuple(hand.get((3, v), 0) for v in range(1, 8))
best = 99
# try every tile type as the designated pair, plus the no-pair case
for pair in [None] + [k for k, v in hand.items() if v >= 2]:
h = dict(hand)
if pair is not None:
h[pair] -= 2
melds = partials = 0
for s in range(3):
c = tuple(h.get((s, v), 0) for v in range(1, SUIT_LEN + 1))
m, p, _ = suit_best(c, False)
melds += m
partials += p
for v in range(1, 8):
c = h.get((3, v), 0)
if c >= 3:
melds += 1
elif c >= 2:
partials += 1
melds = min(melds, 4)
partials = min(partials, 4 - melds)
st = 8 - 2 * melds - partials - (1 if pair is not None else 0)
best = min(best, st)
return best
def hand_from_text(spec):
"""'123m456p789s11z' -> dict. m,p,s numbered suits; z honours."""
out = {}
suit_map = {"m": 0, "p": 1, "s": 2, "z": 3}
digits = ""
for ch in spec:
if ch.isdigit():
digits += ch
else:
s = suit_map[ch]
for d in digits:
out[(s, int(d))] = out.get((s, int(d)), 0) + 1
digits = ""
return out
def acceptance(hand, visible=None):
"""Tile types that reduce shanten when drawn, with live copies
remaining."""
visible = visible or {}
base = shanten(hand)
out = []
for s in range(4):
for v in range(1, (SUIT_LEN if s < 3 else 7) + 1):
k = (s, v)
if hand.get(k, 0) >= 4:
continue
h = dict(hand)
h[k] = h.get(k, 0) + 1
# a 14-tile hand: discard the worst tile to re-evaluate at 13
best = 99
for d, c in list(h.items()):
if c == 0:
continue
h2 = dict(h)
h2[d] -= 1
if h2[d] == 0:
del h2[d]
best = min(best, shanten(h2))
if best < base:
live = 4 - hand.get(k, 0) - visible.get(k, 0)
out.append((k, live, best))
return base, out
NAMES = {0: "m", 1: "p", 2: "s", 3: "z"}
if __name__ == "__main__":
tests = [
("three runs + two pairs", "123456789m11p22s"),
("three runs + pair + two far singles", "123456789m11p25s"),
("two runs + pair + scattered", "12345678m11p258s"),
("all singles, maximal gaps", "147m258p369s12z"),
("six pairs + a single", "1199m1199p119s1z"),
]
print(
"Shanten counted for the STANDARD shape (four sets plus a pair): 0"
" means"
)
print("ready, one tile from a win. The maximum for this shape is 8.\n")
print(
" hand description tiles shanten"
)
for label, spec in tests:
h = hand_from_text(spec)
print(" {:36s} {:18s} {:6d}".format(label, spec, shanten(h)))
print(
"\n Note the last row: six pairs plus a single is 3 away from the"
" standard"
)
print(
" shape but only 1 away from a seven-pairs hand, which this program"
" does"
)
print(
" NOT implement. A shanten calculator that omits the alternative"
" shapes"
)
print(
" systematically overstates the distance of pair-heavy hands, and"
" that is"
)
print(" a real limitation of what follows, not a rounding detail.")
print(
"\nAcceptance is defined for hands at shanten 1 or more (this program"
" does"
)
print(
"not score a completed 14-tile hand as -1, so a ready hand shows"
" none)."
)
for spec in ("123456789m11p25s", "12345678m11p258s"):
h = hand_from_text(spec)
base, acc = acceptance(h)
total = sum(max(0, l) for _, l, _ in acc)
print("\n {} (shanten {})".format(spec, base))
print(" acceptance: {} distinct types, {} live copies"
.format(len(acc), total))
for (s, v), live, newst in sorted(acc):
print(" draw {}{} -> shanten {} ({} copies live)"
.format(v, NAMES[s], newst, live))
print(
"\nWhy this matters for the next section. Shanten plus acceptance is"
" exactly"
)
print(
"the state a Markov model of the race needs: shanten says how many"
" steps"
)
print(
"remain and acceptance says the per-draw probability of a step. The"
" next"
)
print(
"programme uses these two numbers and nothing else, which is both its"
)
print(
"strength (it is computable) and its weakness (it ignores hand value,"
" which"
)
print("the next section adds back as a separate term).")
# Shanten counted for the STANDARD shape (four sets plus a pair): 0 means
# ready, one tile from a win. The maximum for this shape is 8.
#
# hand description tiles shanten
# three runs + two pairs 123456789m11p22s 0
# three runs + pair + two far singles 123456789m11p25s 1
# two runs + pair + scattered 12345678m11p258s 2
# all singles, maximal gaps 147m258p369s12z 8
# six pairs + a single 1199m1199p119s1z 3
#
# Note the last row: six pairs plus a single is 3 away from the standard
# shape but only 1 away from a seven-pairs hand, which this program does
# NOT implement. A shanten calculator that omits the alternative shapes
# systematically overstates the distance of pair-heavy hands, and that is
# a real limitation of what follows, not a rounding detail.
#
# Acceptance is defined for hands at shanten 1 or more (this program does
# not score a completed 14-tile hand as -1, so a ready hand shows none).
#
# 123456789m11p25s (shanten 1)
# acceptance: 8 distinct types, 28 live copies
# draw 1p -> shanten 0 (2 copies live)
# draw 1s -> shanten 0 (4 copies live)
# draw 2s -> shanten 0 (3 copies live)
# draw 3s -> shanten 0 (4 copies live)
# draw 4s -> shanten 0 (4 copies live)
# draw 5s -> shanten 0 (3 copies live)
# draw 6s -> shanten 0 (4 copies live)
# draw 7s -> shanten 0 (4 copies live)
#
# 12345678m11p258s (shanten 2)
# acceptance: 13 distinct types, 45 live copies
# draw 3m -> shanten 1 (3 copies live)
# draw 6m -> shanten 1 (3 copies live)
# draw 9m -> shanten 1 (4 copies live)
# draw 1p -> shanten 1 (2 copies live)
# draw 1s -> shanten 1 (4 copies live)
# draw 2s -> shanten 1 (3 copies live)
# draw 3s -> shanten 1 (4 copies live)
# draw 4s -> shanten 1 (4 copies live)
# draw 5s -> shanten 1 (3 copies live)
# draw 6s -> shanten 1 (4 copies live)
# draw 7s -> shanten 1 (4 copies live)
# draw 8s -> shanten 1 (3 copies live)
# draw 9s -> shanten 1 (4 copies live)
#
# Why this matters for the next section. Shanten plus acceptance is exactly
# the state a Markov model of the race needs: shanten says how many steps
# remain and acceptance says the per-draw probability of a step. The next
# programme uses these two numbers and nothing else, which is both its
# strength (it is computable) and its weakness (it ignores hand value, which
# the next section adds back as a separate term).注
一处真实的缺陷。 本书的程序只实现标准型(四面子加一对),不实现七对子与国士无双。后果在表的最后一行可见:六对子加一张单牌在标准型下是 3 向聴,而在七对子型下只有 1 向聴。所以一个不实现替代型的向聴计算器会系统性高估对子型手牌的距离。这不是舍入细节,而是一个会改变取舍结论的缺陷,本书在用到向聴数的每一处都受这一限制约束。
进张(acceptance)是使向聴数下降的牌型及其活张数。程序给出两个例子:1 向聴的手牌有 8 种进张、28 张活牌;2 向聴的手牌有 13 种进张、45 张活牌。
向聴数与进张合起来正是下一节的赛跑模型需要的状态:向聴说还有几步,进张说每一步每次摸牌的概率。这是这个模型的长处(可以计算)也是它的短处(它不含手牌价值,价值要另外加回来)。
一手牌是一场赛跑
把一手牌写成吸收马尔可夫链:状态是剩余的向聴距离,每次摸牌以进张给出的概率前进一步,到 0 之后以活和牌张给出的概率完成。
推导
# Chapter 4. The hand as a race, and why a one-player race model is badly
# wrong. State = shanten distance; each own draw advances with probability set
# by the acceptance count (p04) over the unseen pool (p02). Once ready, the
# player wins by drawing or claiming a winning tile. The program first
# computes this WITHOUT competing risk, then adds the hazard that one of the
# three opponents ends the hand first, and compares. The gap between the two
# is the point of the chapter: ignoring the other three players inflates the
# win probability several-fold, which is the commonest error in informal
# analysis of this game. Illustrative parameters; standard library only.
import math
TURNS = 18
POOL = 70
def p_adv(acc):
return min(1.0, acc / float(POOL))
def p_hit(win_tiles):
"""Per-turn chance of completing: own draw plus roughly one claimable
discard."""
return min(1.0, 1.9 * win_tiles / float(POOL))
def simulate(shanten, acc, win_tiles, opp_hazard, turns=TURNS):
"""Exact forward recursion. Returns (P(win), P(someone else ends it),
P(exhaustive draw)). opp_hazard = per-turn probability the hand ends
through
an opponent (their win, by draw or by someone dealing in)."""
# state: (distance remaining); distance 0 means ready
state = {shanten: 1.0}
p_win = p_opp = 0.0
for t in range(turns):
nxt = {}
for d, w in state.items():
# the opponents may end the hand first, before this player's
# action
p_opp += w * opp_hazard
w2 = w * (1.0 - opp_hazard)
if d == 0:
h = p_hit(win_tiles)
p_win += w2 * h
nxt[0] = nxt.get(0, 0.0) + w2 * (1 - h)
else:
a = p_adv(acc)
nxt[d - 1] = nxt.get(d - 1, 0.0) + w2 * a
nxt[d] = nxt.get(d, 0.0) + w2 * (1 - a)
state = nxt
return p_win, p_opp, math.fsum(state.values())
if __name__ == "__main__":
print(
"One player's race, {} own draws, unseen pool {} tiles.\n".format(
TURNS, POOL
)
)
ACC = 28
print(
"A. WITHOUT competing risk (the naive model: no other players exist):"
)
print(" start shanten P(win) P(wall exhausts)")
naive = {}
for s in (1, 2, 3, 4):
pw, po, pe = simulate(s, ACC, 8, 0.0)
naive[s] = pw
print(" {:13d} {:8.3f} {:17.3f}".format(s, pw, pe))
print(
"\nB. WITH competing risk. Three opponents, each ending the hand with"
)
print(
"probability about 0.016 per turn, so a combined hazard near 0.047:"
)
print(" start P(win) P(an opponent P(wall naive / real")
print(" shanten ends it) exhausts)")
for s in (1, 2, 3, 4):
pw, po, pe = simulate(s, ACC, 8, 0.047)
print(" {:7d} {:10.3f} {:12.3f} {:13.3f} {:13.2f}"
.format(s, pw, po, pe, naive[s] / pw if pw else float("nan")))
f1 = naive[1] / simulate(1, ACC, 8, 0.047)[0]
f4 = naive[4] / simulate(4, ACC, 8, 0.047)[0]
print(
"\n The naive model overstates the win probability by a factor of"
" {:.2f} at".format(f1)
)
print(
" 1-shanten rising to {:.2f} at 4-shanten: the error GROWS with"
" distance,".format(f4)
)
print(
" because a hand far from ready spends more turns exposed to the"
" hazard."
)
print(
" That direction is the structural lesson, and it means any"
" comparison of"
)
print(
" a fast cheap hand against a slow valuable one is biased toward"
" the slow"
)
print(" hand if competing risk is left out.")
print(
"\n A calibration warning, because the absolute numbers above are"
" too high."
)
print(
" In recorded play a player wins roughly a fifth of hands, and"
" roughly"
)
print(
" half of the hands in which they declare a ready hand with a good"
" wait."
)
print(
" This model gives {:.2f} at 1-shanten even with the hazard, for"
" three".format(simulate(1, ACC, 8, 0.047)[0])
)
print(
" reasons: it starts every hand already at 1-shanten, whereas most"
" hands"
)
print(
" never get that close; it lets the player draw freely for all {}"
" turns;".format(TURNS)
)
print(
" and its completion rate per turn is generous. So the model is"
" COMPARATIVE"
)
print(" only - it ranks options against each other - and its absolute")
print(
" probabilities should not be quoted. Section C shows how sensitive"
" even"
)
print(
" the comparison is to the one parameter that is hardest to pin"
" down."
)
print("\nC. Sensitivity to the opponents' hazard, 1-shanten start:")
print(" combined hazard per turn P(win) P(opponent ends it)")
for hz in (0.00, 0.02, 0.047, 0.07, 0.10):
pw, po, pe = simulate(1, ACC, 8, hz)
print(" {:24.3f} {:8.3f} {:20.3f}".format(hz, pw, po))
print(
"\nD. The decision that actually arises: at 1-shanten, keep a wide"
" cheap"
)
print(
"shape or switch to a narrow valuable one? Hazard 0.047 throughout."
)
print(" option acceptance win tiles P(win) value"
" E[points]")
rows = []
for label, acc1, wint, value in (("wide and cheap", 28, 8, 2000),
("wide and medium", 24, 8, 3900),
("narrow and valuable", 12, 4, 8000),
("narrow and huge", 8, 2, 12000)):
pw, po, pe = simulate(1, acc1, wint, 0.047)
rows.append((label, pw, value, pw * value))
print(" {:21s} {:10d} {:10d} {:7.3f} {:6d} {:10.0f}"
.format(label, acc1, wint, pw, value, pw * value))
best = max(rows, key=lambda r: r[3])
widest = rows[0]
print("\n The highest expected points is '{}' at {:.0f},"
.format(best[0], best[3]))
print(" while the highest win probability is '{}' at {:.3f}."
.format(widest[0], widest[1]))
print(" The two rankings disagree, which is")
print(
" why a probability model is not yet a strategy: the quantity to"
" maximise"
)
print(" is points.")
print(
"\nE. And the term still missing: the cost of dealing in while"
" pushing."
)
print(
" E[points] = P(win) x value - q x 5200, for the deal-in"
" probability q:"
)
print(" option q = 0 q = 0.08 q = 0.15")
for label, pw, value, ev in rows:
print(" {:28s} {:9.0f} {:11.0f} {:10.0f}"
.format(label, ev, ev - 0.08 * 5200, ev - 0.15 * 5200))
neg = [r[0] for r in rows if r[3] - 0.15 * 5200 < 0]
print("\n At q = 0.15, {} of the four options are negative: {}."
.format(len(neg), ", ".join(neg) if neg else "none"))
print(
" Chapter 5 treats when to stop pushing as an optimal stopping"
" problem,"
)
print(
" and these numbers are why it cannot be settled by win probability"
" alone."
)
# One player's race, 18 own draws, unseen pool 70 tiles.
#
# A. WITHOUT competing risk (the naive model: no other players exist):
# start shanten P(win) P(wall exhausts)
# 1 0.973 0.027
# 2 0.943 0.057
# 3 0.886 0.114
# 4 0.790 0.210
#
# B. WITH competing risk. Three opponents, each ending the hand with
# probability about 0.016 per turn, so a combined hazard near 0.047:
# start P(win) P(an opponent P(wall naive / real
# shanten ends it) exhausts)
# 1 0.716 0.272 0.011 1.36
# 2 0.627 0.350 0.024 1.51
# 3 0.536 0.416 0.048 1.65
# 4 0.441 0.470 0.088 1.79
#
# The naive model overstates the win probability by a factor of 1.36 at
# 1-shanten rising to 1.79 at 4-shanten: the error GROWS with distance,
# because a hand far from ready spends more turns exposed to the hazard.
# That direction is the structural lesson, and it means any comparison of
# a fast cheap hand against a slow valuable one is biased toward the slow
# hand if competing risk is left out.
#
# A calibration warning, because the absolute numbers above are too high.
# In recorded play a player wins roughly a fifth of hands, and roughly
# half of the hands in which they declare a ready hand with a good wait.
# This model gives 0.72 at 1-shanten even with the hazard, for three
# reasons: it starts every hand already at 1-shanten, whereas most hands
# never get that close; it lets the player draw freely for all 18 turns;
# and its completion rate per turn is generous. So the model is COMPARATIVE
# only - it ranks options against each other - and its absolute
# probabilities should not be quoted. Section C shows how sensitive even
# the comparison is to the one parameter that is hardest to pin down.
#
# C. Sensitivity to the opponents' hazard, 1-shanten start:
# combined hazard per turn P(win) P(opponent ends it)
# 0.000 0.973 0.000
# 0.020 0.853 0.129
# 0.047 0.716 0.272
# 0.070 0.620 0.373
# 0.100 0.515 0.481
#
# D. The decision that actually arises: at 1-shanten, keep a wide cheap
# shape or switch to a narrow valuable one? Hazard 0.047 throughout.
# option acceptance win tiles P(win) value E[points]
# wide and cheap 28 8 0.716 2000 1433
# wide and medium 24 8 0.701 3900 2735
# narrow and valuable 12 4 0.454 8000 3628
# narrow and huge 8 2 0.242 12000 2907
#
# The highest expected points is 'narrow and valuable' at 3628,
# while the highest win probability is 'wide and cheap' at 0.716.
# The two rankings disagree, which is
# why a probability model is not yet a strategy: the quantity to maximise
# is points.
#
# E. And the term still missing: the cost of dealing in while pushing.
# E[points] = P(win) x value - q x 5200, for the deal-in probability q:
# option q = 0 q = 0.08 q = 0.15
# wide and cheap 1433 1017 653
# wide and medium 2735 2319 1955
# narrow and valuable 3628 3212 2848
# narrow and huge 2907 2491 2127
#
# At q = 0.15, 0 of the four options are negative: none.
# Chapter 5 treats when to stop pushing as an optimal stopping problem,
# and these numbers are why it cannot be settled by win probability alone.A 段是朴素模型:假装另外三家不存在。B 段加上竞争风险——三家中任何一家先结束这手牌的风险。
这是本书最重要的修正。对比两段:
- 1 向聴起手:朴素 0.973,加竞争风险后 0.716,高估 1.36 倍;
- 4 向聴起手:朴素 0.790,加竞争风险后 0.441,高估 1.79 倍。
误差随距离增大,因为离听牌远的手牌要在风险中多待几巡。这个方向是结构性的,而它的后果是:
忽略竞争风险的模型系统性偏向慢而贵的手牌。
任何「这手牌值得做大」的论证,如果用的是不含竞争风险的胜率,就已经偏了,而偏的方向正是支持该论证的方向。
注
校准警告,这一条必须读。 上面的绝对数字偏高。在记录数据中,一名玩家大约赢五分之一的手牌。本书的模型在加入竞争风险后仍给出 1 向聴起手 0.716,原因有三:它让每手牌都从 1 向聴开始,而真实牌局大多到不了那么近;它让玩家在全部 18 巡自由摸牌;它每巡的完成概率偏高。所以这个模型只作比较之用——它用来给选项排序——其绝对概率不可引用。C 段同时显示这个比较对那个最难定的参数(对手的风险率)有多敏感。
概率不是策略
D 段给出真正会遇到的决策:1 向聴时保留宽而便宜的形状,还是换成窄而贵的形状?
结果是:期望点数最高的是「窄而贵」(3628),而胜率最高的是「宽而便宜」(0.716)。两个排序不一致。这就是概率模型还不是策略的原因——要最大化的量是点数。
E 段再加一项:推牌到底的放铳代价。在放铳概率 0.15 时,四个选项中有几个变成负值。第五章把「什么时候停止推牌」写成最优停时问题,而这几个数就是它不能由胜率单独回答的理由。
假说 · 尚未验证
作者的假说(尚未确立): 在固定对手池的重复对局设计中,用含竞争风险的胜率估计作取舍的策略,优于用不含竞争风险的估计作取舍的策略,且差值主要来自后者在远离听牌时过度追求高价值手牌。什么样的结果能证明它是错的: 若该比较的点数差的 95% 置信区间包含零,则本假说错;若差值存在但按起手向聴数分层后在远距离层中不更大,则本假说的机制部分错。
本章小结
向聴数可由牌张计数向量的递归分解精确计算,而本书的程序只实现标准型,因此系统性高估对子型手牌的距离——这是一处会改变结论的真实缺陷。向聴与进张合起来给出赛跑模型的状态。本章的主要修正是:忽略另外三家的朴素赛跑模型把胜率高估 1.36 倍(1 向聴)到 1.79 倍(4 向聴),误差随距离增大,所以它系统性偏向慢而贵的手牌。模型的绝对概率偏高且不可引用,只能用于给选项排序。最后,期望点数最高的选项与胜率最高的选项不一致(窄而贵对宽而便宜),这说明概率模型还不是策略;再加上放铳代价后,部分选项变为负值,而这是第五章把弃牌写成最优停时的理由。
参考文献
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).