站内《数值平衡与商业化运营》 把「代价」算在数值与付费上——培养一个赛季要多少资源、一个礼包定价多少；本节算的是另一笔账：为了知道最优是什么，要搜索多少状态；而最优一旦被找到，又会让玩法付出什么。前者是计算代价，后者是设计代价，都属于博弈最优口径，与赛季膨胀和定价无关。
3.1 minimax 与极小极大 算出纯策略无鞍点，3.2 混合策略与纳什直觉 用支撑枚举解出了均衡（值 −4）。那两节都默认「我们能算出最优」。本节追问：算得出吗、算出来又值不值。
3.3 最优解的代价
「最优」不是一个免费的概念，它标着两笔价：
| 代价 | 花在哪 | 度量 | 本节读数 |
|---|---|---|---|
| 计算代价 | 找到最优要搜索多少节点 | 搜索树叶数 b^d 与预算之比 | 满深度 6^20 ≈ 3.66×10^15，远超预算 |
| 设计代价 | 最优落地后策略空间被压掉多少 | 均衡支撑大小与熵相对均匀分布的比例 | 支撑 2/4，熵保留 459‰ |
两笔价是一对张力：搜索越深越贵（计算代价涨），但越能锁定一个更优的解（设计代价更早兑现）；而一个越「锐利」的最优解（支撑越小、熵越低），对玩法多样性的压缩越狠。最优越确定，玩法越单调——这不是修辞，是可以算出来的整数。
(A) 计算代价：搜索树有多大
《灰烬牌库》里玩家每一步的动作符号是 handSize + 1 = 6 个（打第 0–4 张，或结束回合），这就是 minimax 搜索树的分支因子 b。搜索深度受回合上限约束，d 层深的穷举树有 b^d 个叶。分支固定、深度一涨，叶数指数爆炸。
给一个节点预算 nodeBudget（配置里的 10^7），就能算出「穷举还跑得动」的最大深度；再考虑 alpha-beta 剪枝（对手会优先堵住你的强招，实际搜索量在最理想情况下约 b^(d/2)），得到第二组可行深度。矩阵博弈这一侧用支撑枚举：Σ_{k≥1} C(R,k)·C(C,k) = C(R+C,R) − 1 个子博弈，对 4×5 就是 C(9,4) − 1 = 125 个。
(B) 设计代价：最优压窄了可玩空间
3.2 的均衡只用了 4 招里的 2 招（重击、格挡），支撑 2/4，活性 500‰。用 3.2 的整数熵度量，均衡熵 919 相对均匀分布的 2000 只保留 459‰——最优解落地，策略空间的可玩度被压掉一半多。若矩阵存在纯策略鞍点（3.1 的简单情形），最优是支撑 1、熵 0：只留一招，可玩度归零，游戏被「解开」（solved）。
S 层：把两笔代价都算成整数
脚本把搜索树逐深度列出来，标出穷举与 alpha-beta 各自的可行深度，再把 3.2 的均衡支撑与熵相对均匀分布换算成千分比保留率。熵用整数定点 log2，无浮点。
#!/usr/bin/env python3
# file: sim/gd_play_03_cost.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/gd_play_03_cost.py
"""卷二 3.3 最优解的代价（S 层）：找到最优要付多少搜索代价，最优本身又让设计付什么代价。
两种代价，都是整数：
(A) 计算代价 —— 求最优要搜索多少节点。分支因子 b = handSize+1 = 6 个动作符号，
穷举深度 d 的 minimax 树有 b^d 个叶；与节点预算 nodeBudget 比，给出可行深度 d*。
alpha-beta 最好情况把指数减半（b^(d/2)），据此给出第二组可行深度。
矩阵博弈侧用支撑枚举：Σ_{k≥1} C(R,k)·C(C,k) = C(R+C,R) − 1 个子博弈。
(B) 设计代价 —— 最优解是一个（或一小组）策略，找到它就压缩了策略空间。
用 3.2 的混合均衡支撑与熵度量：支撑越小、熵越低，可玩空间的「活性」越低。
纯策略最优（支撑 1）的熵恒为 0；混合最优保留均匀熵的一个比例（千分比）。
全整数、无浮点（log2 用整数定点）。产出 out/play03_cost.csv + .json + .svg。
"""
from __future__ import annotations
import json
import os
import sys
import time
import xml.etree.ElementTree as ET
from math import comb
import ashlib
HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
CONFIG = os.path.join(ROOT, "config/gd_play_03_matrix.json")
def log2_milli(n: int) -> int:
"""floor(1000·log2(n))，n>=1，纯整数定点（20 位二进制小数）。"""
k = n.bit_length() - 1
p = 20
x = (n << p) >> k
frac = 0
for i in range(20):
x = (x * x) >> p
if x >= (1 << (p + 1)):
x >>= 1
frac |= 1 << (19 - i)
return k * 1000 + (frac * 1000 >> 20)
def entropy_milli(counts: list[int]) -> int:
"""千分比整数分布（Σ=1000）的 Shannon 熵，单位 milli-bit。"""
pos = [c for c in counts if c > 0]
return log2_milli(1000) - sum(c * log2_milli(c) for c in pos) // 1000
def search_cost(b: int, budget: int, dmax: int):
"""(A) 穷举 minimax 与 alpha-beta 最好情况的逐深度节点数。"""
rows = []
for d in range(1, dmax + 1):
leaves = b ** d
ab = b ** ((d + 1) // 2) # alpha-beta 最好情况 ~ b^(d/2)
rows.append({"depth": d, "leaves": leaves, "feasible": leaves <= budget,
"abLeaves": ab, "abFeasible": ab <= budget})
plain = max(r["depth"] for r in rows if r["feasible"])
ab = max(r["depth"] for r in rows if r["abFeasible"])
return rows, plain, ab
def main() -> int:
t0 = time.perf_counter_ns()
spec = ashlib.load_spec()
with open(CONFIG, encoding="utf-8") as f:
cfg = json.load(f)
stances, actions = cfg["enemyStances"], cfg["playerActions"]
budget = cfg["nodeBudget"]
b = spec["params"]["handSize"] + 1 # 动作符号数：p0..p4 + e
dmax = spec["params"]["turnLimit"] # 回合上限 = 穷举深度上界
# ---- (A) 搜索代价
rows, plain_d, ab_d = search_cost(b, budget, dmax)
full_leaves = b ** dmax
print("== (A) 计算代价：minimax 搜索树 ==")
print(f"分支因子 b = handSize+1 = {b} 深度上界 dmax = turnLimit = {dmax} 预算 = {budget}")
print(f"{'d':>3}{'b^d':>22}{'穷举可行':>10}{'b^(d/2)':>22}{'ab 可行':>10}")
for r in rows:
if r["depth"] <= 10 or r["depth"] == dmax:
print(f"{r['depth']:>3}{r['leaves']:>22}{str(r['feasible']):>10}"
f"{r['abLeaves']:>22}{str(r['abFeasible']):>10}")
print(f"穷举可行最大深度 d* = {plain_d}；alpha-beta 最好情况 d* = {ab_d}")
print(f"满深度 {dmax} 的穷举叶数 = {full_leaves}（远超预算，须改用采样）")
R, C = len(actions), len(stances)
subgames_all = comb(R + C, R) - 1
subgames_2x2 = comb(R, 2) * comb(C, 2)
print(f"矩阵博弈支撑枚举：全部子博弈 = C({R}+{C},{R})−1 = {subgames_all}"
f"（其中 2×2 = {subgames_2x2}）")
# ---- (B) 设计代价：均衡的支撑与熵
pmix = [334, 0, 0, 666]
qmix = [250, 750, 0, 0, 0]
h_p, h_q = entropy_milli(pmix), entropy_milli(qmix)
uni_p = entropy_milli([1000 // R] * R)
uni_q = entropy_milli([1000 // C] * C)
support = sum(1 for x in pmix if x > 0)
live = support * 1000 // R
retention = h_p * 1000 // uni_p
print("\n== (B) 设计代价：最优解压缩了策略空间 ==")
print(f"玩家均衡支撑 {support}/{R}（活性 {live}‰） 混合熵 {h_p} / 均匀 {uni_p}"
f" = 保留 {retention}‰")
print(f"敌人均衡支撑 2/{C} 混合熵 {h_q} / 均匀 {uni_q}")
print(f"纯策略最优（若存在鞍点）支撑 1，熵 0 —— 活性归零")
assert h_p == 0 or retention < 1000, "最优解不应比均匀分布更分散"
# ---- CSV
csv_rows = [[r["depth"], r["leaves"], int(r["feasible"]), r["abLeaves"],
int(r["abFeasible"])] for r in rows]
n = ashlib.write_csv(os.path.join(OUT, "play03_cost.csv"),
["depth", "leaves", "feasible", "abLeaves", "abFeasible"], csv_rows)
# ---- SVG：搜索树增长 + 预算线
W, H = 700, 300
root = ashlib.svg_begin(W, H)
ashlib.svg_text(root, 16, 28, f"minimax 搜索树的叶数增长（b={b}）与预算线", 15)
ashlib.svg_text(root, 16, 48, f"预算={budget} 穷举可行深度 d*={plain_d}"
f" alpha-beta 最好情况 d*={ab_d}", 11, "#94a3b8")
x0, y0, bw = 70, 250, 52
top = b ** 10
for i, r in enumerate(rows[:10]):
h = 200 * r["leaves"] // top
fill = "#22c55e" if r["feasible"] else "#ef4444"
ET.SubElement(root, "rect", {"x": str(x0 + i * bw), "y": str(y0 - h),
"width": str(bw - 12), "height": str(max(2, h)),
"fill": fill, "data-depth": str(r["depth"])})
ashlib.svg_text(root, x0 + i * bw + (bw - 12) // 2, y0 + 16, str(r["depth"]), 11, "#cbd5e1", "middle")
by = y0 - 200 * budget // top
ET.SubElement(root, "line", {"x1": str(x0), "y1": str(by), "x2": str(x0 + 10 * bw),
"y2": str(by), "stroke": "#facc15", "stroke-width": "2"})
ashlib.svg_text(root, x0 + 10 * bw + 6, by + 4, "预算", 11, "#facc15")
size = ashlib.svg_save(root, os.path.join(OUT, "play03_cost.svg"))
report = {"id": "gd_play_03_cost", "branching": b, "turnLimit": dmax, "budget": budget,
"fullLeaves": full_leaves, "plainMaxDepth": plain_d, "abMaxDepth": ab_d,
"subgamesAll": subgames_all, "subgames2x2": subgames_2x2,
"playerSupport": support, "livePermille": live, "playerEntropy": h_p,
"uniformPlayer": uni_p, "retentionPermille": retention,
"enemyEntropy": h_q, "uniformEnemy": uni_q,
"elapsedMs": (time.perf_counter_ns() - t0) // 1000000}
os.makedirs(OUT, exist_ok=True)
with open(os.path.join(OUT, "play03_cost.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
print(f"csv={n} rows svg={size} bytes elapsed={report['elapsedMs']} ms")
print("wrote out/play03_cost.csv out/play03_cost.json out/play03_cost.svg")
ET.parse(os.path.join(OUT, "play03_cost.svg"))
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/gd_play_03_cost.py：
== (A) 计算代价：minimax 搜索树 ==
分支因子 b = handSize+1 = 6 深度上界 dmax = turnLimit = 20 预算 = 10000000
d b^d 穷举可行 b^(d/2) ab 可行
1 6 True 6 True
2 36 True 6 True
3 216 True 36 True
4 1296 True 36 True
5 7776 True 216 True
6 46656 True 216 True
7 279936 True 1296 True
8 1679616 True 1296 True
9 10077696 False 7776 True
10 60466176 False 7776 True
20 3656158440062976 False 60466176 False
穷举可行最大深度 d* = 8；alpha-beta 最好情况 d* = 16
满深度 20 的穷举叶数 = 3656158440062976（远超预算，须改用采样）
矩阵博弈支撑枚举：全部子博弈 = C(4+5,4)−1 = 125（其中 2×2 = 60）
== (B) 设计代价：最优解压缩了策略空间 ==
玩家均衡支撑 2/4（活性 500‰） 混合熵 919 / 均匀 2000 = 保留 459‰
敌人均衡支撑 2/5 混合熵 812 / 均匀 2322
纯策略最优（若存在鞍点）支撑 1，熵 0 —— 活性归零
csv=20 rows svg=2748 bytes elapsed=6 ms
wrote out/play03_cost.csv out/play03_cost.json out/play03_cost.svg
判读：指数墙与 459‰
(A) 计算代价撞的是一堵指数墙。 分支因子 b = 6 看起来小，但深度每加 1，叶数就乘 6：
| 深度 d | 穷举叶数 6^d | 穷举可行 | alpha-beta 6^(d/2) | ab 可行 |
|---|---|---|---|---|
| 4 | 1296 | 是 | 36 | 是 |
| 8 | 1679616 | 是 | 1296 | 是 |
| 9 | 10077696 | 否 | 7776 | 是 |
| 16 | 6^16 ≈ 2.8×10^12 | 否 | 1679616 | 是 |
| 20 | 6^20 ≈ 3.66×10^15 | 否 | 60466176 | 否 |
预算 10^7 下，穷举只够到 d* = 8；alpha-beta 剪枝把指数减半，把可行深度推到 16——这就是「何时改用采样」的判据：深度一旦超过 d*，穷举不再可行，必须换蒙特卡洛采样。3.1 的 4×5 矩阵之所以能精确解，是因为它把状态压成了 20 个格（支撑枚举 125 个子博弈）；一旦要跑真实的多回合战斗树，就只能采样——这是策略空间规模控制的直接后果。
(B) 设计代价压在 459‰。 均衡把玩家的活性压到 2/4 = 500‰，熵保留 459‰。两个数字都不到一半，但都没归零：
| 情形 | 支撑 | 熵（milli-bit） | 活性 | 判读 |
|---|---|---|---|---|
| 均匀分布（无最优） | 4/4 | 2000 | 1000‰ | 没有最优，玩家随便打 |
| 混合均衡（本例） | 2/4 | 919 | 500‰ | 有最优，但保留两招随机 |
| 纯策略鞍点（3.1 简单情形） | 1/4 | 0 | 250‰ | 最优唯一，游戏被解开 |
这张表就是本章的主结论：最优解的「锐利度」和玩法的多样性是一对反比量。混合均衡保留了 2 招、919 milli-bit 的熵，是一个可玩的最优；纯策略鞍点把熵压到 0，是一个退化的最优——它把游戏变成了一道有标准答案的题。设计者要的往往是「有最优、但最优不唯一」的那个中间地带，而它恰好落在 459‰ 这样的非零熵上。
熵与活性在这里是代理指标（proxy）：它们度量的是策略分布的分散度，不是「好玩」，只能用来相对比较不同均衡（混合 vs 纯、本例 vs 均匀），不能绝对化成「可玩性 = 459」。
自检表
| 检查项 | 合格标准 |
|---|---|
| 代价分两类 | 计算代价（搜索树）与设计代价（策略空间）分开算 |
| 复杂度上界 | 给出 b^d 的指数形式与可行深度 d*，不藏「跑不动」 |
| 采样判据 | 明确「深度超过 d* 改用采样」，不是笼统说「太大」 |
| 熵为代理 | 熵与活性标注为代理指标，只做相对比较、禁绝对化 |
| 全整数 | 叶数与熵都是整数，无浮点（log2 用整数定点） |
均衡算完了、代价算清了，第 3 章到此收束。但「最优」只描述了双方都停手的那个点——机制跑起来还会自发长出一堆设计时没写进规格的模式，那是下一章的主题。
阅读导航：上一节：3.2 混合策略与纳什直觉 · 下一节：4.1 涌现：从规则到模式 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。