12.3 组合爆炸的控制
《小游戏开发实战》卷一 4.1 包体预算 那篇把「资源上限」当成硬约束来管；本节把「组合枚举的计算上限」也当成一条硬约束来管——只是这里的预算是格数，不是字节。两者共享同一个姿态：先算上界，再决定要不要全跑。
闭式：全空间有多大
把 k 个旋钮各取 m 档，全空间就是笛卡尔积，格数有闭式：
N(k, m) = m^k （k 个旋钮各 m 档）
k: 1 2 3 4 5 6 7 8
m=3: 3 9 27 81 243 729 2187 6561
指数是真正的敌人：多一个旋钮，格数乘 3。逐格代价 = 种子数 × 单次仿真，于是总代价 = m^k × seeds × 单次。本节把预算钉在 budget = 256 格：低于它全枚举，高于它降级采样。
三条控制手段
| 手段 | 做法 | 本节实测效果 |
|---|---|---|
| 剪枝 | 用 12.1 的全零行把死旋钮塌缩成 1 档 | 旋钮 8 → 5，3^8 = 6561 → 3^5 = 243（27 倍） |
| 预算 | 定一个 budget，N ≤ budget 才全枚举 | 243 ≤ 256 → 剪枝后可全枚举 |
| 降级采样 | N > budget 时只跑 budget 格 | 6561 > 256 → 采样 256 格（覆盖率 39‰） |
采样必须用可播种 PRNG（这里复用 ashlib.rng_next 洗下标），绝不能用语言自带的随机数——否则结论不可复现，也跨不了语言。
组合枚举与降级采样（S 层）
脚本把「全空间」与「剪枝后空间」各跑一遍，同一套判据自动决定枚举还是采样，并如实报告两者耗时。
#!/usr/bin/env python3
# file: sim/gd_mech_12_combine.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/gd_mech_12_combine.py
"""卷一 12.3 组合爆炸的控制（S 层）：枚举上界、剪枝、预算与降级采样。
闭式：k 个旋钮各 m 档 → 全空间 N(k, m) = m^k。判据（整数）：
N ≤ budget → **全枚举**，结论完备；N > budget → **降级采样** budget 格，结论是估计量。
剪枝来自 12.1 的耦合矩阵：全零行（turnLimit / rewardGold / punishHp）是死旋钮，
塌缩成 1 档，指数从 8 降到 5，N 从 3^8 = 6561 降到 3^5 = 243（27 倍）。
采样用自实现 PRNG（ashlib.rng_next）洗下标，**不用 Python random**。
产出 out/mech12_combine.csv（枚举空间逐格）+ out/mech12_combine.svg（胜率谱）+ .json。
"""
import copy
import itertools
import json
import os
import sys
import time
import xml.etree.ElementTree as ET
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_mech_12_budget.json")
sys.path.insert(0, HERE)
import ashlib # noqa: E402
def cell(spec, seeds, strategy, over):
wins = php = 0
for sd in seeds:
s = copy.deepcopy(spec)
s["seed"] = sd
s["params"].update(over)
snap = ashlib.run_spec(s, strategy)
wins += 1 if snap["won"] else 0
php += snap["playerHp"]
n = len(seeds)
return {"winPermille": 1000 * wins // n, "avgPlayerHp": php // n}
def sample_index(total, want, seed):
"""自实现 PRNG 洗出 want 个互不相同的下标（升序），禁 random 模块。"""
idx = list(range(total))
state = seed % ashlib.RNG_MOD or 1
for i in range(total - 1, 0, -1):
state = ashlib.rng_next(state)
j = state % (i + 1)
idx[i], idx[j] = idx[j], idx[i]
return sorted(idx[:want])
def run_space(spec, seeds, strategy, knobs, keys, budget, sample_seed):
"""一个旋钮子空间：N ≤ budget 全枚举，否则降级采样 budget 格。"""
space = list(itertools.product(*[knobs[k] for k in keys]))
n = len(space)
mode = "enumerate" if n <= budget else "sample"
picked = list(range(n)) if mode == "enumerate" else sample_index(n, budget, sample_seed)
t = time.perf_counter_ns()
rows = [{"index": i, **dict(zip(keys, space[i])), **cell(spec, seeds, strategy, dict(zip(keys, space[i])))}
for i in picked]
wins = [r["winPermille"] for r in rows]
return {"keys": keys, "n": n, "mode": mode, "cells": len(rows), "runs": len(rows) * len(seeds),
"winMin": min(wins), "winMax": max(wins), "winMeanPermille": sum(wins) // len(wins),
"solveMs": (time.perf_counter_ns() - t) // 1000000, "rows": rows}
def draw(rows, path, meta):
"""枚举空间的胜率谱：一格一根竖条，高度 = 胜率千分比。"""
W, H, x0, y0, y1 = 760, 300, 60, 40, 230
bw = max(1, (W - x0 - 20) // max(1, len(rows)))
root = ashlib.svg_begin(W, H)
ashlib.svg_text(root, x0, 24, f"组合空间胜率谱：{meta}", 14)
ET.SubElement(root, "line", {"x1": str(x0), "y1": str(y1), "x2": str(W - 20), "y2": str(y1),
"stroke": "#64748b"})
for i, r in enumerate(rows):
h = r["winPermille"] * (y1 - y0) // 1000
fill = "#22c55e" if r["winPermille"] >= 800 else ("#f59e0b" if r["winPermille"] >= 400 else "#ef4444")
ET.SubElement(root, "rect", {"x": str(x0 + i * bw), "y": str(y1 - h),
"width": str(max(bw - 1, 1)), "height": str(max(h, 1)),
"fill": fill, "data-win": str(r["winPermille"])})
ashlib.svg_text(root, x0, y1 + 22, "绿 ≥800‰ / 琥珀 400–799‰ / 红 <400‰", 12, "#94a3b8")
return ashlib.svg_save(root, path)
def main():
t0 = time.perf_counter_ns()
spec = ashlib.load_spec()
with open(CONFIG, encoding="utf-8") as f:
cfg = json.load(f)
knobs, live = cfg["knobs"], cfg["liveKnobs"]
seeds, budget = cfg["seeds"], cfg["budget"]
strategy = cfg["probePattern"] * cfg["probeTurns"]
closed = [3 ** k for k in range(1, len(knobs) + 1)]
full = run_space(spec, seeds, strategy, knobs, list(knobs), budget, cfg["sampleSeed"])
pruned = run_space(spec, seeds, strategy, knobs, live, budget, cfg["sampleSeed"])
keys = pruned["keys"]
ashlib.write_csv(os.path.join(OUT, "mech12_combine.csv"),
["index"] + keys + ["winPermille", "avgPlayerHp"],
[[r["index"]] + [r[k] for k in keys] + [r["winPermille"], r["avgPlayerHp"]]
for r in pruned["rows"]])
size = draw(pruned["rows"], os.path.join(OUT, "mech12_combine.svg"),
f"N_all={full['n']} N_live={pruned['n']} budget={budget} mode={pruned['mode']}")
report = {"id": "gd_mech_12_combine", "levels": 3, "knobs": len(knobs), "liveKnobs": len(live),
"budget": budget, "closedForm": closed, "full": {k: v for k, v in full.items() if k != "rows"},
"pruned": {k: v for k, v in pruned.items() if k != "rows"},
"elapsedMs": (time.perf_counter_ns() - t0) // 1000000}
with open(os.path.join(OUT, "mech12_combine.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
print("closed form m^k (m=3): " + " ".join(f"k={k+1}:{n}" for k, n in enumerate(closed)))
for tag, r in (("full ", full), ("pruned", pruned)):
print(f"{tag} keys={len(r['keys'])} N={r['n']:>5} mode={r['mode']:<9} cells={r['cells']:>4} "
f"runs={r['runs']:>5} win[{r['winMin']},{r['winMax']}]‰ mean={r['winMeanPermille']}‰ "
f"solve={r['solveMs']} ms")
print(f"budget={budget} pruneFactor={full['n'] // pruned['n']}x svg={size} bytes")
print("wrote out/mech12_combine.csv out/mech12_combine.svg out/mech12_combine.json")
ET.parse(os.path.join(OUT, "mech12_combine.svg"))
return 0
if __name__ == "__main__":
raise SystemExit(main())
本机实跑 /opt/homebrew/bin/python3 sim/gd_mech_12_combine.py：
closed form m^k (m=3): k=1:3 k=2:9 k=3:27 k=4:81 k=5:243 k=6:729 k=7:2187 k=8:6561
full keys=8 N= 6561 mode=sample cells= 256 runs= 2048 win[0,1000]‰ mean=628‰ solve=72 ms
pruned keys=5 N= 243 mode=enumerate cells= 243 runs= 1944 win[0,1000]‰ mean=666‰ solve=43 ms
budget=256 pruneFactor=27x svg=19711 bytes
wrote out/mech12_combine.csv out/mech12_combine.svg out/mech12_combine.json
pruneFactor=27x 是剪枝的账面收益；full 行与 pruned 行的 mode 不同，正是同一条判据在两种空间上的两种结论。
组合预算的软告警（B 层）
降级采样不是免费的：它把「证明」换成了「估计」。下面这段是 B 层脚本，读 S 层产物，按四条整数判据发软告警，永远 exit 0，不使任何构建失败。
#!/usr/bin/env python3
# file: sim/gd_mech_12_budget.py
# tier: B
# verify: /opt/homebrew/bin/python3 sim/gd_mech_12_budget.py
"""卷一 12.3 组合预算的软告警（B 层）：**永远 exit 0**，只提示风险不使构建失败。
读 out/mech12_combine.json（12.3 的 S 层产物）与 config/gd_mech_12_budget.json，
按四条整数判据发软告警：预算越界降级、覆盖率、死旋钮剪枝比、采样偏差。
采样偏差判据：|采样均值 − 枚举均值| ≥ biasPermille(25‰) 即告警——
它是「降级采样把结论带偏了多少」的**直接证据**，不是噪声。
产出 out/mech12_budget.json（每条含 severity=soft 与 hardFail=false）。
"""
import json
import os
import sys
HERE = os.path.dirname(os.path.abspath(__file__))
ROOT = os.path.dirname(HERE)
OUT = os.path.join(ROOT, "out")
sys.path.insert(0, HERE)
import ashlib # noqa: E402
def main():
with open(os.path.join(OUT, "mech12_combine.json"), encoding="utf-8") as f:
comb = json.load(f)
with open(os.path.join(ROOT, "config/gd_mech_12_budget.json"), encoding="utf-8") as f:
cfg = json.load(f)
full, pruned, budget = comb["full"], comb["pruned"], comb["budget"]
bias = abs(full["winMeanPermille"] - pruned["winMeanPermille"])
coverage = 1000 * full["cells"] // full["n"]
warn = []
if full["mode"] == "sample":
warn.append({"code": "BUDGET_EXCEEDED", "severity": "soft", "n": full["n"], "budget": budget,
"message": f"全空间 N={full['n']} > budget={budget}，已降级为采样："
f"结论由「证明」降为「估计」，不得再写「穷尽」"})
warn.append({"code": "LOW_COVERAGE", "severity": "soft", "coveragePermille": coverage,
"message": f"采样只覆盖 {coverage}‰ 的组合（{full['cells']}/{full['n']}），"
f"未覆盖区域的性质只能外推"})
warn.append({"code": "DEAD_KNOB_PRUNE", "severity": "soft", "deadKnobs": cfg["deadKnobs"],
"factor": full["n"] // pruned["n"],
"message": f"{len(cfg['deadKnobs'])} 个死旋钮塌缩后 N 降 {full['n'] // pruned['n']} 倍"
f"（{full['n']} → {pruned['n']}），剪枝来自 12.1 的全零行"})
if bias >= 25:
warn.append({"code": "SAMPLING_BIAS", "severity": "soft", "biasPermille": bias,
"message": f"采样均值 {full['winMeanPermille']}‰ 与枚举均值 "
f"{pruned['winMeanPermille']}‰ 差 {bias}‰，降级采样把整体难度估计带偏了"})
report = {"id": "gd_mech_12_budget", "tier": "B", "hardFail": False,
"note": "B 档软告警：只提示组合预算风险，不使任何构建失败",
"N_all": full["n"], "N_live": pruned["n"], "budget": budget, "biasPermille": bias,
"warnings": warn}
os.makedirs(OUT, exist_ok=True)
with open(os.path.join(OUT, "mech12_budget.json"), "w", encoding="utf-8") as f:
json.dump(report, f, ensure_ascii=False, indent=2, sort_keys=True)
f.write("\n")
for w in warn:
print(f"SOFT WARN {w['code']}: {w['message']}")
print(f"N_all={full['n']} N_live={pruned['n']} budget={budget} bias={bias}‰ warnings={len(warn)}")
print("hardFail=false → exit 0")
print("wrote out/mech12_budget.json")
return 0
if __name__ == "__main__":
raise SystemExit(main())
本机实跑 /opt/homebrew/bin/python3 sim/gd_mech_12_budget.py：
SOFT WARN BUDGET_EXCEEDED: 全空间 N=6561 > budget=256，已降级为采样：结论由「证明」降为「估计」，不得再写「穷尽」
SOFT WARN LOW_COVERAGE: 采样只覆盖 39‰ 的组合（256/6561），未覆盖区域的性质只能外推
SOFT WARN DEAD_KNOB_PRUNE: 3 个死旋钮塌缩后 N 降 27 倍（6561 → 243），剪枝来自 12.1 的全零行
SOFT WARN SAMPLING_BIAS: 采样均值 628‰ 与枚举均值 666‰ 差 38‰，降级采样把整体难度估计带偏了
N_all=6561 N_live=243 budget=256 bias=38‰ warnings=4
hardFail=false → exit 0
wrote out/mech12_budget.json
四条告警里最硬的是 SAMPLING_BIAS：采样均值 628‰ 与枚举均值 666‰ 差 38‰，这就是降级采样把整体难度估计带偏的实测幅度。它不是噪声，是一个可以直接读出来的系统性偏差。所以「何时改用采样」的判据不该只看格数，还要看偏差是否还在容忍带内。
判据表
| 问题 | 判据 | 本节取值 |
|---|---|---|
| 要不要剪枝 | 存在全零行即可塌缩 | 3 个死旋钮，27 倍 |
| 能不能全枚举 | N ≤ budget | 剪枝后 243 ≤ 256，能 |
| 要不要降级采样 | N > budget | 全空间 6561 > 256，要 |
| 采样可不可信 | 采样均值与枚举均值之差 < 25‰ | 实测 38‰，越界 |
自检表
| 检查项 | 合格标准 |
|---|---|
| 上界有闭式 | 写成 m^k，并列出前几项 |
| 剪枝有依据 | 剪枝来自可复核的零行，不是「我觉得」 |
| 降级有判据 | 枚举 / 采样的切换条件是整数不等式 |
| 降级有代价 | 量化采样偏差，并承认结论从「证明」降为「估计」 |
一阶耦合、二阶交互、组合预算——三节合起来回答了「多个机制放在一起会怎样」。但机制不是一成不变的：下一章处理增量、赛季与退场，也就是规格演化时这套判据怎么跟着改。
阅读导航：上一节：12.2 协同与反协同 · 下一节：13.1 机制增量与兼容 。
继续阅读
探索更多技术文章
浏览归档，发现更多关于系统设计、工具链和工程实践的内容。