gamedesign

10.1 状态的可达性

状态空间不是「所有可能的状态」，而是「从开局真的能走到的状态」。本节用广度优先展开动作序列的前缀树、以 digest 去重，把《灰烬牌库》12 步内的可达集真的枚举出来：7637 个状态，只占粗粒度上界的十亿分之 250；再拿 8 类「永远不该出现」的状态去扫，命中数全为 0。

Leeting Yan 6 分钟阅读 2932 字

SLG 模块拆分 画的是系统的功能地图——有哪些模块、谁调谁；本节画的是状态空间语义——从开局出发到底能走到哪些状态、哪些状态永远走不到。前者是散文式的结构说明，后者是可以枚举、可以计数的集合。引擎内核 管渲染帧循环，逻辑内核管状态转移；本章回到逻辑侧，问一个比第 4 章更细的问题：状态机是纯函数、digest 是状态的充分表示——那么把动作序列展开成前缀树，到底能走出多少个不同状态。

10.1 状态的可达性

可达集（reachable set）的定义只有一句话：从开局状态 s₀ 出发，存在某条命令序列 x 使得 runSpec(spec, x) = s 的那些 s。它和「状态空间」是两回事——状态空间是「字段取值域之积」这个盒子，可达集是盒子被规则切出来的那一小片。4.1 已经证过状态机是纯函数，4.3 已经证过 digest 是状态的充分表示，于是可达集可以真的枚举：广度优先展开命令序列的前缀树，每个节点的状态由前缀重放得到，去重键用 digest。

枚举的规模由三重上限按住，与 core/src/ashdeck/solvability.ts 同口径：maxSteps 限深度、maxNodes 限去重后状态数、maxBranch 限单步分支。本节把深度放到 12 步，跑一遍可达集：

#!/usr/bin/env python3
# file: sim/gd_mech_10_reachability.py
# tier: S
# verify: /opt/homebrew/bin/python3 sim/gd_mech_10_reachability.py
"""10.1 状态的可达性（S 层）。

第 4 章已证 runSpec 是纯函数、digest 是状态的充分表示；本节据此把「从开局能走到
哪些状态」真的枚举一遍：广度优先展开动作序列的前缀树，用 digest 去重。产出三样：
  ① 逐深度的新增 / 累计可达状态数（CSV + SVG）；
  ② 可达集规模 vs 各独立字段取值域之积的**粗粒度上界**（忽略相关性）；
  ③ 8 类「永远不该出现」的状态扫可达集，命中数必须为 0。

上限三重与 core/src/ashdeck/solvability.ts 同口径。全整数，无浮点，无 random。
"""
from __future__ import annotations

import json
import os
import sys

import ashlib

ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
MAX_STEPS, MAX_NODES, MAX_BRANCH = 12, 200000, 6


def cost(spec, cid):
    return next((c["cost"] for c in spec["cards"] if c["id"] == cid), 999999)


def acts_of(spec, s):
    """可负担的出牌 p<i>，外加恒合法的 e——与 solvability.ts 的 legalActions 同口径。"""
    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):
    seen = {ashlib.digest(ashlib.run_spec(spec, []))}
    frontier, nodes, rows, trunc = [[]], 1, [], False
    for d in range(1, MAX_STEPS + 1):
        nxt, new = [], 0
        for seq in frontier:
            a = acts_of(spec, ashlib.run_spec(spec, seq))
            if len(a) > MAX_BRANCH:
                trunc, a = True, a[:MAX_BRANCH]
            for x in a:
                g = ashlib.digest(ashlib.run_spec(spec, seq + [x]))
                if g in seen:
                    continue
                if nodes >= MAX_NODES:
                    trunc = True
                    break
                seen.add(g)
                nodes += 1
                new += 1
                nxt.append(seq + [x])
            if trunc:
                break
        rows.append((d, new, nodes))
        if not nxt:
            break
        frontier = nxt
    if frontier and rows[-1][0] == MAX_STEPS:
        trunc = True  # 深度撞上 maxSteps 而前沿未空 → 完备性受损，如实标注
    return seen, nodes, rows, trunc


def hand_multisets(cards):
    """手牌多重集个数：4 种卡、各带上限、总数 0..handSize。整数组合计数。"""
    caps = [c["count"] for c in cards]
    total = 0

    def rec(i, left):
        nonlocal total
        if i == len(caps):
            total += 1
            return
        for k in range(min(caps[i], left) + 1):
            rec(i + 1, left - k)

    for size in range(6):
        rec(0, size)
    return total


def box_bound(spec):
    p = spec["params"]
    block_max = sum(c["block"] * c["count"] for c in spec["cards"])
    parts = [p["turnLimit"] + 1, p["energyMax"] + 1, p["playerHp"] + 1, p["enemyHp"] + 1,
             block_max + 1, ashlib.deck_size(spec) + 1, 2, 2, hand_multisets(spec["cards"])]
    prod = 1
    for v in parts:
        prod *= v
    return parts, prod


UNREACHABLE = {
    "energy<0": lambda p, s, d: s["energy"] < 0,
    "energy>energyMax": lambda p, s, d: s["energy"] > p["energyMax"],
    "block<0": lambda p, s, d: s["block"] < 0,
    "cardCount!=deckSize": lambda p, s, d: s["cardCount"] != d,
    "enemyHp>enemyHp0": lambda p, s, d: s["enemyHp"] > p["enemyHp"],
    "playerHp>playerHp0": lambda p, s, d: s["playerHp"] > p["playerHp"],
    "dealt>enemyHp0": lambda p, s, d: s["dealt"] > p["enemyHp"],
    "won&&enemyHp>0": lambda p, s, d: s["won"] and s["enemyHp"] > 0,
}


def scan(spec, states):
    p, d = spec["params"], ashlib.deck_size(spec)
    return {name: sum(1 for g in states if pred(p, json.loads(g), d))
            for name, pred in UNREACHABLE.items()}


def main():
    spec = ashlib.load_spec()
    states, nodes, rows, trunc = bfs(spec)
    parts, bound = box_bound(spec)
    ppb = nodes * 1000000000 // bound
    n = ashlib.write_csv(os.path.join(ROOT, "out", "mech10_reachability.csv"),
                         ["depth", "newStates", "cumStates"], [list(r) for r in rows])

    root = ashlib.svg_begin(720, 300)
    ashlib.svg_text(root, 20, 30, "10.1 可达状态数随搜索深度累积（maxSteps=%d）" % MAX_STEPS, 15)
    top = rows[-1][2]
    for i, (d, _new, cum) in enumerate(rows):
        y = 52 + i * 18
        ashlib.svg_text(root, 20, y + 15, "d=%d" % d, 12)
        ashlib.svg_bar(root, 60, y, 520, 22, cum, top, "#38bdf8", "累计 %d" % cum)
    ashlib.svg_text(root, 20, 282, "可达 %d · 上界 %d · 占比 %d ppb" % (nodes, bound, ppb), 13)
    b = ashlib.svg_save(root, os.path.join(ROOT, "out", "mech10_reachability.svg"))

    print("deckSize=%d handSize=%d maxSteps=%d maxBranch=%d" %
          (ashlib.deck_size(spec), spec["params"]["handSize"], MAX_STEPS, MAX_BRANCH))
    print("depth newStates cumStates")
    for r in rows:
        print(" ".join(str(x) for x in r))
    print("boxBoundParts " + " ".join(str(v) for v in parts))
    print("boxBound=%d reachable=%d ratioPPB=%d truncated=%s" % (bound, nodes, ppb, trunc))
    hits = scan(spec, states)
    print("unreachableHits " + " ".join("%s=%d" % (k, v) for k, v in hits.items()))
    print("wrote out/mech10_reachability.csv rows=%d" % n)
    print("wrote out/mech10_reachability.svg bytes=%d" % b)
    return 0 if sum(hits.values()) == 0 and nodes > 1 else 1


if __name__ == "__main__":
    sys.exit(main())

实跑 /opt/homebrew/bin/python3 sim/gd_mech_10_reachability.py：

deckSize=12 handSize=5 maxSteps=12 maxBranch=6
depth newStates cumStates
1 5 6
2 16 22
3 45 67
4 110 177
5 208 385
6 326 711
7 477 1188
8 689 1877
9 950 2827
10 1254 4081
11 1622 5703
12 1934 7637
boxBoundParts 21 4 61 51 11 13 2 2 204
boxBound=30493374912 reachable=7637 ratioPPB=250 truncated=True
unreachableHits energy<0=0 energy>energyMax=0 block<0=0 cardCount!=deckSize=0 enemyHp>enemyHp0=0 playerHp>playerHp0=0 dealt>enemyHp0=0 won&&enemyHp>0=0
wrote out/mech10_reachability.csv rows=12
wrote out/mech10_reachability.svg bytes=5265

三组数字要分开读。7637 个可达状态是 12 步内真实走到的不同状态（含开局），去重键是 digest。30493374912 是粗粒度上界——把各独立字段的取值域直接相乘：turn(21) × energy(4) × playerHp(61) × enemyHp(51) × block(11) × played(13) × over(2) × won(2) × 手牌多重集(204)。这个上界是故意算松的：它把字段当成互相独立的，完全忽略「dealt 由 enemyHp 决定」「played 与手牌互补」这类相关性。即便如此，可达集也只占它的 十亿分之 250——约合 0.25 ppm。可达集是盒子里薄得几乎看不见的一层。

第三组是逐深度增长：5、16、45、110、208、326、477、689、950、1254、1622、1934，单调上升且没有饱和的迹象。这说明 12 步内状态空间还在扩张，前沿没被穷尽——所以 truncated=True，本节的可达集严格说是「12 步以内的可达集」，不是全图的。把这条如实标出来，比假装「搜完了」重要得多；它同时就是 4.3 那条判据「去重率过低 / 撞上限仍无解就换采样」在可达性上的对应物。

可达集的规模就是设计的自由度预算。可达状态太少，每一局的走向都雷同，玩家第三次就摸透了；太多，则穷举、平衡与 QA 都做不动。7637 这个量级对本规则是合适的：小到能在 12 步内枚举完第一层结构，又大到足以容纳不同种子下的开局差异（第 9 章的方差分析正是建立在这批状态上）。真正要警惕的是可达集萎缩——某次改规则之后可达状态数突然塌缩，通常意味着新规则把大半动作序列变成了空转步，而不是「玩法更聚焦了」。

深度 d新增状态累计状态读法
156开局 5 张手牌，分支恰好 5（energy=3，只有费用 0/1/2 的牌可出）
4110177第一个回合内，伤害与手牌组合开始分叉
868918774.3 的最短取胜序列就在这一层结束
1219347637撞上 maxSteps，前沿未空 → truncated=True

真正让「可达性」有意义的是它的反面：不可达状态。把 8 类「永远不该出现」的状态拿去扫可达集，命中数必须全为 0——命中任何一类，就说明规则漏了：

不可达类为什么不可达由哪条规则保证
energy < 0欠费动作被 continue 跳过，能量只减可负担的费用combat.ts 的 c.cost > energy 前置
energy > energyMax能量只在 e 里重置为 energyMax，从不上溢energy = p.energyMax
block < 0敌人攻击先扣格挡再扣血，扣的是 min(block, attack)Math.min(block, p.enemyAttack)
cardCount != deckSize三区搬运不增不减，洗牌只重排4.2 的牌数守恒
enemyHp > enemyHp₀伤害只减不增，且封顶在剩余血量Math.min(c.damage, enemyHp)
playerHp > playerHp₀玩家血量只在 e 里减少（本项目无治疗牌）规格选择，非规则漏洞
dealt > enemyHp₀dealt 是伤害封顶后的累计，等于敌方总掉血d = min(...) 与 dealt += d
won && enemyHp > 0won 只在 enemyHp <= 0 时置位if (enemyHp <= 0) won = true

实跑输出里 unreachableHits 八项全为 0，这一列就是「可达集里一个都没有」的机械证据。要注意这八条不是搜索碰运气得出的：每一条都能指回一行规则（右列），扫描只是交叉验证。这和 4.2 的负例断言是同一套方法论——没有反面的可达性主张等于没主张。

检查项合格标准
可达集有定义明确「从 s₀ 出发、某条命令序列可达」，不是「字段取值域之积」
去重有依据用 digest 当去重键，依据是 4.1 的状态充分性
上界给得出给出粗粒度上界公式与各部分取值域，并声明它故意算松
完备性如实撞上限即标 truncated，把「12 步以内」写进结论
不可达可指认每类不可达状态都能指回一行规则，扫描命中数为 0

可达集给了「能走到哪」，但它没回答「哪些状态不允许存在」。那正是下一节要汇总的东西：把散落在第 1、3、4 章的不变量收成一张可执行清单。

阅读导航：上一节：9.3 可播种随机与确定性回放 · 下一节：10.2 不变量清单 。

继续阅读

探索更多技术文章

浏览归档，发现更多关于系统设计、工具链和工程实践的内容。

全部文章 返回首页

「gamedesign」更多文章

  1. 附录 A 品类参数表、机制距离矩阵与数据集索引
  2. 9.3 自走棋的涌现
  3. 9.2 自走棋的经济与平衡