《小游戏开发实战》卷一 6.1 核心循环拆解
用 S 层数的是核心循环的时长占比——一局的秒数怎么被切开，是时间轴上的量；本节数的是策略空间——把动作序列当对象，先量它的规模，再量它的形状，是状态空间上的量。两者的底座是同一份 config/play_spec.json，但一个数秒、一个数条，口径不重叠。上一节说明了策略有两种写法，本节把其中的动作序列这一侧做成可数的对象。
1.2 策略空间枚举与 Shannon 熵
**策略空间（strategy space）**就是全部合法动作序列的集合。它的规模由两个数决定：字母表大小 |A| 和序列长度 L。如果不加任何约束，长度恰为 L 的序列一共有 |A|^L 条。对《灰烬牌库》来说 |A| = 6、baseline 长度 L = 25，于是：
|A|^L = 6^25 = 28430288029929701376 ≈ 2.8 × 10^19
这个数字大得没有意义——它把「打一张不存在的牌」「能量不够还硬打」「游戏结束后继续按键」这些根本不可能发生的序列也算进去了。所以「策略空间有多大」这个问题，必须先把「合法」两个字补上。
先剪枝：只有合法的序列才算数
一条指令在某个状态下合不合法，由规格决定：p<i> 要求 0 ≤ i < len(hand) 且 card.cost ≤ energy，e 恒合法，游戏结束后扇出为 0。把非法指令在生成时就丢弃，剩下的就是合法序列。这个过滤有多强，可以在一个能完整枚举的深度上量出来：深度 8 的粗上界是 6^8 = 1679616，合法序列只有 181166 条——剪枝率 107‰，也就是砍掉了将近九成。
| 深度 d | 该层合法序列 | 累计合法 | 粗上界 6^d |
|---|---|---|---|
| 1 | 6 | 6 | 6 |
| 2 | 31 | 37 | 36 |
| 3 | 123 | 160 | 216 |
| 4 | 464 | 624 | 1296 |
| 5 | 1975 | 2599 | 7776 |
| 6 | 8285 | 10884 | 46656 |
| 7 | 33746 | 44630 | 279936 |
| 8 | 136535 | 181165 | 1679616 |
注意深度 2 那一行：合法序列 31 条，而粗上界只有 36 条——几乎全部合法。到了深度 8，合法只剩粗上界的 107‰。剪枝的力量随深度增加，因为序列越长，越容易撞上「能量不够」或「游戏已结束」的边界。
四个 Shannon 熵
规模只是一个数，形状要用熵来刻画。本节在枚举出来的合法空间上算四个熵，全部取 ‰（千分比），全部用整数定点计算（避免浮点）：
| 记号 | 定义 | 它在问什么 |
|---|---|---|
H0 先验熵 | `log2( | A |
Hact 动作熵 | 6 个符号在枚举树上的出现分布之熵 | 空间在动作维度上摊得有多开 |
Hbr 分支熵 | 每个节点的合法动作个数（扇出）分布之熵 | 分支有多不均匀 |
Hout 结果熵 | 深度 D 前沿上 won / lost / ongoing 三类分布之熵 | 到这个深度分出胜负了吗 |
熵的定义是 H = −Σ pᵢ·log2(pᵢ)。为了不引入浮点，脚本用整数平方逐位逼近 log2：L(n) = floor(2^20·log2(n))，于是 H ≈ [N·L(N) − Σ nᵢ·L(nᵢ)] / (N·2^20)，再乘 1000 取整。
S 层：枚举与四个熵
sim/gd_play_01_entropy.py 读规格与 config/gd_play_01_space.json，广度优先展开合法前缀树（按序列计数，不是按状态），同时统计扇出直方图、符号直方图与终局直方图，最后算出四个熵。全整数，无浮点，无随机。
{
"id": "gd_play_01_space",
"note": "卷二 1.2/1.3 策略空间：枚举深度、枚举上限、种子与采样数（全整数，禁浮点）",
"seeds": [201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216],
"enumDepth": 8,
"maxNodes": 200000,
"maxBranch": 6,
"sampleCount": 4096,
"sampleDepth": 12
}
#!/usr/bin/env python3
# file: sim/gd_play_01_entropy.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/gd_play_01_entropy.py
"""卷二 1.2 策略空间枚举与 Shannon 熵（S 层）。
策略空间 = 全部**合法动作序列**的集合。本节先给出规模（|A|^D 的粗上界），再用广度
优先把深度 D 以内的合法前缀树真的枚举出来（非法指令在生成时就被剪掉，游戏结束后
扇出为 0），最后在这个枚举出来的空间上算四个熵：
H0 先验熵 = log2(|A|) 均匀随机按键时的最大熵（上界，与机制无关）
H_act 动作熵 = 枚举树上 6 个符号的出现分布之熵（策略空间有多「摊得开」）
H_br 分支熵 = 每个节点的扇出数（合法动作个数）分布之熵（分支有多不均匀）
H_out 结果熵 = 深度 D 前沿上 won / lost / ongoing 三类终局分布之熵
熵全部用**整数定点**算（BITS 位小数），输出取 ‰，避免浮点：
H = log2(N) − (1/N)·Σ nᵢ·log2(nᵢ) ≈ [N·L(N) − Σ nᵢ·L(nᵢ)] / (N·2^BITS)
其中 L(n) = floor(2^BITS·log2(n)) 由整数平方逼近得到。
**这些熵都是代理指标（proxy）**：它们度量策略空间的形状，不等于「好玩」，只用于
相对比较，禁止写成「熵越高越好」这类绝对结论。产出 out/play01_entropy.{json,csv,svg}。
"""
from __future__ import annotations
import json
import os
import sys
import xml.etree.ElementTree as ET
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_01_space.json")
BITS = 20
def alphabet(spec: dict) -> list[str]:
return ["p" + str(i) for i in range(spec["params"]["handSize"])] + ["e"]
def log2_scaled(n: int, bits: int = BITS) -> int:
"""floor(2^bits · log2(n))，纯整数（整数平方逐位逼近小数部分），n ≥ 1。"""
if n < 1:
raise ValueError("log2 只接受 n>=1")
k = n.bit_length() - 1
res = k << bits
y = (n << bits) >> k # y = n/2^k · 2^bits ∈ [2^bits, 2^(bits+1))
for i in range(bits):
y = (y * y) >> bits
if y >= (1 << (bits + 1)):
res |= 1 << (bits - 1 - i)
y >>= 1
return res
def entropy_permille(counts: list[int]) -> int:
"""Shannon 熵 ×1000 取整（整数定点）。counts 全 0 时返回 0。"""
total = sum(counts)
if total <= 0:
return 0
acc = total * log2_scaled(total)
for c in counts:
if c:
acc -= c * log2_scaled(c)
return (1000 * acc) // (total << BITS)
def cost(spec: dict, cid: str) -> int:
return next((c["cost"] for c in spec["cards"] if c["id"] == cid), 999999)
def legal(spec: dict, s: dict) -> list[str]:
"""可负担的出牌 p<i> + 恒合法的 e；游戏结束则为空（与 solvability 同口径）。"""
if s["over"]:
return []
a = ["p" + str(i) for i, cid in enumerate(s["hand"]) if cost(spec, cid) <= s["energy"]]
a.append("e")
return a
def bfs(spec: dict, depth: int, cap: int) -> tuple:
"""按**序列**枚举合法前缀树：返回 (边数, 逐深度行, 扇出直方图, 符号直方图,
终局直方图, 是否截断)。"""
frontier: list[list[str]] = [[]]
edges, fanout, symbols = 0, {}, {}
rows, trunc = [], False
last_snaps: list[dict] = []
for d in range(1, depth + 1):
nxt, snaps = [], []
for seq in frontier:
s = ashlib.run_spec(spec, seq)
acts = legal(spec, s)
fanout[len(acts)] = fanout.get(len(acts), 0) + 1
for a in acts:
if edges >= cap:
trunc = True
break
edges += 1
symbols[a] = symbols.get(a, 0) + 1
nxt.append(seq + [a])
snaps.append(None) # 占位，终局在下一轮算
if trunc:
break
rows.append((d, len(nxt), edges))
if trunc or not nxt:
last_snaps = [ashlib.run_spec(spec, seq) for seq in frontier] if not nxt else []
break
frontier = nxt
last_snaps = [ashlib.run_spec(spec, seq) for seq in frontier]
return edges, rows, fanout, symbols, last_snaps, trunc
def outcome_hist(snaps: list[dict]) -> dict:
h = {"won": 0, "lost": 0, "ongoing": 0}
for s in snaps:
h["won" if s["won"] else ("lost" if s["over"] else "ongoing")] += 1
return h
def entropy_svg(path: str, bars: list[tuple]) -> int:
root = ashlib.svg_begin(620, 240)
ashlib.svg_text(root, 20, 30, "1.2 策略空间的四个熵（‰，上限 = log2|A| = 2585‰）", 14)
for i, (label, val, den) in enumerate(bars):
y = 52 + i * 42
ashlib.svg_text(root, 20, y + 16, label, 12)
ashlib.svg_bar(root, 170, y, 380, 22, val, den, "#38bdf8", f"{val}‰")
ashlib.svg_text(root, 20, 228, "熵是代理指标：只做相对比较，不判定「好玩」", 11, "#94a3b8")
return ashlib.svg_save(root, path)
def main() -> int:
spec = ashlib.load_spec()
with open(CONFIG, encoding="utf-8") as f:
cfg = json.load(f)
alpha = alphabet(spec)
D, cap = cfg["enumDepth"], cfg["maxNodes"]
edges, rows, fanout, symbols, last_snaps, trunc = bfs(spec, D, cap)
raw = len(alpha) ** D
h0 = entropy_permille([1] * len(alpha)) # 先验：均匀
h_act = entropy_permille([symbols.get(a, 0) for a in alpha])
h_br = entropy_permille([fanout.get(b, 0) for b in range(0, len(alpha) + 1)])
hist = outcome_hist(last_snaps)
h_out = entropy_permille([hist[k] for k in ("won", "lost", "ongoing")])
prune = (edges + 1) * 1000 // raw
n = ashlib.write_csv(os.path.join(OUT, "play01_entropy.csv"),
["depth", "atDepth", "cumulative"], [list(r) for r in rows])
bars = [("H0 先验熵", h0, h0), ("H_act 动作熵", h_act, h0),
("H_br 分支熵", h_br, h0), ("H_out 结果熵", h_out, h0)]
b = entropy_svg(os.path.join(OUT, "play01_entropy.svg"), bars)
report = {"id": "gd_play_01_entropy", "alphabet": alpha, "alphabetSize": len(alpha),
"enumDepth": D, "maxNodes": cap, "rawSpace": raw, "legalSpace": edges + 1,
"truncated": trunc, "prunePermille": prune,
"entropyPermille": {"H0": h0, "Hact": h_act, "Hbr": h_br, "Hout": h_out},
"fanout": fanout, "symbols": symbols, "outcome": hist, "rows": rows}
with open(os.path.join(OUT, "play01_entropy.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
print(f"alphabet |A|={len(alpha)} : {','.join(alpha)}")
print(f"enumDepth={D} maxNodes={cap}")
print(f"rawSpace |A|^D={raw} legalSpace={edges + 1} truncated={trunc}")
print("depth atDepth cumulative")
for r in rows:
print(" ".join(str(x) for x in r))
print(f"prunePermille={prune}‰（合法空间 / 粗上界）")
print(f"fanout histogram (合法动作个数: 节点数) = "
f"{dict(sorted(fanout.items()))}")
print(f"symbol histogram (符号: 出现次数) = {dict(sorted(symbols.items()))}")
print(f"outcome histogram = {hist}")
print(f"H0={h0}‰ Hact={h_act}‰ Hbr={h_br}‰ Hout={h_out}‰")
print(f"wrote out/play01_entropy.csv rows={n}")
print(f"wrote out/play01_entropy.svg bytes={b}")
ET.parse(os.path.join(OUT, "play01_entropy.svg"))
return 0
if __name__ == "__main__":
sys.exit(main())
本机实跑 /opt/homebrew/bin/python3 sim/gd_play_01_entropy.py：
alphabet |A|=6 : p0,p1,p2,p3,p4,e
enumDepth=8 maxNodes=200000
rawSpace |A|^D=1679616 legalSpace=181166 truncated=False
depth atDepth cumulative
1 6 6
2 31 37
3 123 160
4 464 624
5 1975 2599
6 8285 10884
7 33746 44630
8 136535 181165
prunePermille=107‰（合法空间 / 粗上界）
fanout histogram (合法动作个数: 节点数) = {1: 6856, 2: 3204, 3: 4344, 4: 7152, 5: 12189, 6: 10886}
symbol histogram (符号: 出现次数) = {'e': 44631, 'p0': 34031, 'p1': 34679, 'p2': 33455, 'p3': 23483, 'p4': 10886}
outcome histogram = {'won': 8, 'lost': 0, 'ongoing': 136527}
H0=2584‰ Hact=2483‰ Hbr=2446‰ Hout=0‰
wrote out/play01_entropy.csv rows=8
wrote out/play01_entropy.svg bytes=2168
判读：三个熵都接近上界，唯独结果熵塌了
H0 = 2584‰ 是理论上限（log2(6) = 2.585）。它是「玩家闭着眼均匀按键」时的熵，跟机制无关，放在这里只是为了给另外三个熵一把尺子。
Hact = 2483‰ 接近上界。枚举出来的合法空间里，6 个符号的出现次数是 e: 44631、p0: 34031、p1: 34679、p2: 33455、p3: 23483、p4: 10886——分布相当均匀（p4 偏少是因为它是手牌第 5 张，只有手牌满时才存在）。这说明合法空间在动作维度上摊得很开，没有哪条指令被边缘化。
Hbr = 2446‰ 也接近上界。扇出直方图是 {1: 6856, 2: 3204, 3: 4344, 4: 7152, 5: 12189, 6: 10886}——大部分节点的扇出是 5 或 6，只有少数是 1。分支分布同样均匀，说明这个机制在深度 8 内几乎处处都留了选择。
Hout = 0‰ 则是本节最该停下来读的一行。深度 8 的前沿上，136535 个状态里只有 8 个已经分出胜负，其余 136527 个全是 ongoing——结果分布几乎是一个点，熵自然塌成 0。这不是「空间没结果」，而是深度不够：一局《灰烬牌库》要打 4 个回合、约 25 步才能赢，深度 8 连一半都到不了。要把结果熵算准，需要枚举到 20 步以上，而 6^20 ≈ 3.6 × 10^15 条序列根本枚举不完。
这条落差正是下一节的入口：枚举能算的深度和结果需要的深度之间隔着一道墙。
熵是代理指标
四个熵都只是代理指标（proxy），不是「好玩」的度量。它们描述的是策略空间的形状——摊得多开、分支多均匀、结果多分散——只用于相对比较：换一组参数，Hact 从 2483‰ 掉到 1500‰，可以说「这个改动让策略空间在动作维度上变窄了」；但不能说「熵越高越好玩」，因为「好玩」从来没有被定义过一个单位。这一点在全卷通用，后面每一节的机制量指标都要照此声明。
| 检查项 | 合格标准 |
|---|---|
| 规模有上界 | 给出 ` |
| 合法有定义 | 非法指令的判据写清（下标、费用、结束态） |
| 枚举可复现 | 同一深度同一上限，两次枚举的计数逐位相同 |
| 熵是整数 | 用定点 log2，输出 ‰，禁浮点 |
| 代理显式 | 正文声明熵是代理指标，只做相对比较、禁绝对化 |
| 诚实标注 | 结果熵为 0 时说明是深度不足，不假装它「没结果」 |
下一节把这道墙拆成可操作的工程问题：当枚举撞上上限时，怎么用剪枝、去重与采样把空间压回可算，并给出「何时改用采样」的整数判据。
阅读导航：上一节：1.1 策略的表示：动作序列与决策树 · 下一节：1.3 策略空间的规模控制 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。