War Chest 的不完全信息 MCTS：从 Observation 到 Determinization

<!-- vault refs: alphazero-mcts-search game tree war-chest-hex-grid-primitives -->

在 alphazero-mcts-search 里，MCTS 的 root 是一个确定的局面。程序知道双方棋子在哪里、接下来能走什么，神经网络只需要回答：在这个完整局面下，哪些动作更值得搜索，这个局面对当前行动方有多好。

War Chest 不完全是这样的游戏。

棋盘、控制点、双方兵种名单和已经部署的单位是公开的，但对手的手牌、袋中棋子和未来抽取顺序不是。玩家做决策时面对的不是唯一一个完整 state，而是一组与当前所见事实一致的 state。

这改变的不只是 neural network 的输入，也改变了 game tree 本身。

Full state、observation 与 information set

先区分三个对象：

full state       一局游戏在规则引擎里的完整真相
observation      某个玩家当前有权看见的信息
information set  能产生同一个 observation 的所有可能 full states

先用一个故意缩小的场景把区别画出来。现在轮到红方行动；棋盘局面完全公开，红方也知道自己手里有一枚弓箭手 coin。蓝方手里有一枚 coin，但红方只知道它来自“长矛兵、狂战士、骑兵”这三个候选之一。为了聚焦概念，下面暂时忽略 bag 内部顺序等其他隐藏变量。

{:title "同一眼前局面，背后可能有三个完整真相"
 :observer "红方"
 :shared-facts ["红方行动" "红方弓箭手在 A" "蓝方侦察兵在 B"]
 :own-hand ["弓箭手"]
 :opponent-hand-size 1
 :worlds [{:id "A"
           :opponent-hand ["长矛兵"]
           :opponent-bag ["狂战士" "骑兵"]}
          {:id "B"
           :opponent-hand ["狂战士"]
           :opponent-bag ["长矛兵" "骑兵"]}
          {:id "C"
           :opponent-hand ["骑兵"]
           :opponent-bag ["长矛兵" "狂战士"]}]}

图中的 full state A、B、C 分别是一份可以让规则引擎继续运行的完整真相：蓝方手里究竟是哪枚 coin，在每个 state 里都有确定答案。

但从红方视角调用观察函数 O(state, 红方) 时，蓝方 coin 的正面会被遮掉。三个 state 因而得到完全相同的 observation：同一公开棋盘、同一行动方、同一红方手牌，以及“蓝方有 1 枚未知手牌”。Observation 是红方此刻实际拿到的一份数据，不是一组猜测。

红方无法排除 A、B、C 中的任何一个，所以这三个 full states 合起来才是当前的 information set。换句话说，information set 不是另一个更大的 observation；它是 observation 在 full-state 空间里的所有可能原像：

I(o) = \{s \mid O(s, \text{红方}) = o\}

War Chest 的 canonical full state 必须保存真实手牌、bag、supply 和 rules RNG，否则规则无法继续执行。但这些字段不能直接交给公平 AI。

第一版 observation-v1 采用明确的 allow-list：

- 公开棋盘、控制点、先手权、轮次、回合和当前行动方；

- 棋盘单位的阵营、位置和叠放层数，但不保存每枚 coin 的内部编号；

- 双方公开的兵种名单；

- 当前玩家自己的手牌、袋子、供应区、弃置区和移除区中，各兵种 coin 的数量；

- 去除私有信息后的公开行动历史。

它明确排除：

- 对手私有 hand、bag、supply、discard 和 removed 的具体内容；

- 双方 bag 的顺序；

- 规则引擎的随机状态；

- 每枚 coin 的内部编号。

因此，两个 full states 即使有不同的对手手牌、bag 顺序和 RNG，只要玩家能观察到的事实相同，就必须投影成相同 observation。

只 mask neural network 仍然会作弊

一个看似简单的方案是：MCTS 继续在真实 full state 上搜索，只在调用 neural network 时把隐藏字段 mask 掉。

这仍然不是公平搜索。

问题在于 neural network 只是 MCTS 中负责评估 leaf 的一个组件。一次 simulation 从 root 走到 leaf，还需要反复调用规则引擎提供的 legal-actions 和 next-state。如果它们接收的仍是真实 full state，那么搜索树在调用 neural network 以前就已经读过隐藏信息。

继续使用上一节的简化场景。红方看到的 observation 在 A、B、C 三个世界中完全相同；假设真实世界恰好是 A，也就是蓝方手里有长矛兵。Full-state MCTS 会据此只生成蓝方当前真正能执行的长矛兵动作，而不会生成狂战士或骑兵动作。simulation 走到未来抽牌时，也会直接沿着真实 bag 顺序前进。

于是三个玩家无法区分的世界，会产生三棵不同的搜索树：

                     ┌─ A：蓝方手里是长矛兵 ─▶ 长矛兵合法动作、真实后续抽牌 ─┐
同一个 observation ─┼─ B：蓝方手里是狂战士 ─▶ 狂战士合法动作、真实后续抽牌 ─┼─▶ 不同的 Q、N
                     └─ C：蓝方手里是骑兵   ─▶ 骑兵合法动作、真实后续抽牌   ─┘

对红方玩家来说，A、B、C 无法区分；但服务器知道实际是哪一个。假设这局的真实情况是 A，蓝方手里确实有长矛兵，那么 full-state MCTS 的每一次 simulation 都只在 A 这棵树里进行。它不会同时考虑“也许是狂战士”或者“也许是骑兵”。

这就是问题所在：玩家面对三个可能世界，搜索却假装自己面对一个已经确定的世界。 mask neural network input 只能遮住一张输入表，不能把一棵已经选定的搜索树重新变回三个可能世界。

用一组虚构但更直观的教学数字来看。假设红方 root 只有“推进”和“防守”两个动作；Q 在 -1 到 1 之间，越大表示 simulation 认为对红方越有利；N 表示这个动作被访问了多少次。下面不是实际引擎跑出的数值，只用于展示三个隐藏世界为什么会给出不同搜索结论：

如果红方不知道蓝方是哪一枚 coin，一个最简单的公平近似是给 A、B、C 各分 100 次 simulation，再聚合三个世界的 root visits：

推进 N = 20 + 55 + 70 = 145
防守 N = 80 + 45 + 30 = 155

结果接近五五开。这表达的是红方真正拥有的信息：长矛兵世界偏向防守，但狂战士和骑兵世界又提供了推进的理由，当前 observation 无法支持一个非常确定的判断。

如果程序偷用了服务器中的真实情况 A，并把全部 300 次 simulation 都放进长矛兵这一棵树，结果可能变成：

推进 Q ≈ -0.45，N ≈ 60
防守 Q ≈ +0.30，N ≈ 240

neural network 虽然始终只收到“蓝方有 1 枚未知手牌”，最终动作分布却从接近 145 : 155 变成了明显偏向防守的 60 : 240。这个差异只能来自玩家看不到的“蓝方实际是长矛兵”。因此 Q 和 N 可以理解为搜索对大量 simulation 的压缩摘要：它们没有直接写出隐藏手牌的名字，却保留了使用这项隐藏信息后产生的决策倾向。

所以这里的泄漏不是“把长矛兵三个字偷偷塞回 neural network”，而是“先用长矛兵这个真相搜索，再把搜索结果交给决策过程”。只看最终的 Q、N，已经足以让 AI 表现得像知道对手手牌。

这会在两个阶段造成问题：

1. 实际行动时作弊。 MCTS 通常根据 root visit counts 选动作。即使 network 每次只看 observation，外层搜索仍会针对对手的真实手牌和真实未来抽牌做出选择。

2. 训练时继续泄漏。 如果把这些 root visits 归一化后作为 policy target，训练数据里的“教师答案”也已经依赖当时玩家看不到的真相。network 会被要求拟合一个由作弊搜索产生的策略。

一个更直接的公平性检查是：给定相同 observation、相同 model 和相同 search seeds，决策结果不应该因为服务器内存中的真实世界是 A、B 还是 C 而改变。真实 full-state search 无法满足这个条件。

所以，遮住最后一个 evaluator 并不能消除前面整棵树的信息泄漏。搜索从哪个 state 开始、规则函数可以读取哪些字段，也必须一起进入信息边界。

Belief sampler：从所见事实构造可能世界

公平搜索需要从 information set 中取得一个可能的完整世界。这里的组件叫 belief sampler：

(sample-consistent-state observation belief-seed)
;; => 一个可供规则引擎继续模拟的完整可能世界

它只能接收 observation、公开行动历史和指定的随机种子，函数根本不接收真实 state。这样可以从结构上避免“先偷看真相，再假装采样”。

按这个公开信息边界，:structural-uniform-v1 应该：

1. 直接保留双方公开的兵种名单，不对对手兵种做猜测；

2. 根据公开棋盘、公开行动历史和各兵种 coin 的总数，构造对手 coin 在手牌、袋子、供应区、弃置区和移除区之间的一种可能分布；

3. 为玩家看不到的袋中顺序构造一种可能排列；

4. 验证这个可能世界符合游戏规则，并且从玩家视角观察时与原 observation 完全相同。

最后这个“重新观察后仍然相同”的约束很重要：

(= observation
   (player-observation sampled-state observer public-history))

同一个 observation 和随机种子必须得到同一个可能世界；不同的随机种子可以得到不同的隐藏世界，但都不能改变玩家已经看到的事实。

这里的采样器没有高手对局经验，也不会推理对手的策略。它只做一件事：在所有符合当前 observation 和游戏规则的隐藏状态中，按照随机种子选出一个，作为一次 simulation 使用的完整 state。实际搜索可以用不同种子重复这个过程，得到多个可能世界。

例如，公开信息允许“对手手里是长矛兵、狂战士或骑兵”三种情况时，这个采样器不会因为对手上一回合选择防守，就判断“骑兵在手里的概率更高”。只要三种情况都符合公开信息和 coin 数量约束，它就把它们都当作可以采样的候选。

因此它不是一个从高手棋谱中学出来的概率模型，也不保证每种隐藏状态被采到的频率符合真实玩家的行为。这里的目标只是先做到两点：不读取服务器中的真实隐藏状态，并且每个采样结果都与玩家看到的 observation 一致。固定相同的随机种子会得到相同结果，只是为了让测试和实验可以重复，并不表示采样过程没有随机性。

从多个可能世界分别搜索

这一做法通常叫 Determinization。它的意思是：程序从玩家无法区分的所有情况中，暂时选定一种完整的隐藏状态，把它当作一个可能世界，然后在这个世界里运行普通 MCTS。

为什么要先“暂时选定”一个世界？因为普通 MCTS 无法直接对“对手可能拿着三种不同手牌”进行状态转移。它每走一步，都需要规则引擎明确回答当前有哪些合法动作，以及动作之后会变成什么局面。采样出的完整 state 为这些问题提供了一套临时答案，但它只是一种假设，不是服务器中的真实答案。

当前做法不是只相信一个假设，而是在红方开始思考时，从同一个 observation 构造 K 个可能世界：

                         ┌─▶ 可能世界 1 ─▶ 普通 MCTS ─┐
observation + 随机种子 ──┼─▶ 可能世界 2 ─▶ 普通 MCTS ─┼─▶ 汇总各动作的访问次数
                         └─▶ 可能世界 K ─▶ 普通 MCTS ─┘

假设一次决策允许做 300 次 simulation，并采样了 3 个可能世界，那么可以给每个世界分配 100 次。三个世界使用同一套游戏规则和同一个 neural network，分别得到各个动作的 Q 和 N。

当前实现的汇总方式很直接：先确认不同世界里的动作对玩家来说是同一个动作，再把它们的访问次数 N 相加。上一节的例子中，“推进”在三个世界里分别被访问 20、55、70 次，因此汇总结果就是 20 + 55 + 70 = 145；“防守”同理是 80 + 45 + 30 = 155。这里不会直接把三个 Q 相加；最终选择主要使用汇总后的 N。

因为总 simulation 次数会尽量平均分给各个可能世界，直接相加等价于让每个世界拥有近似相同的权重。例如 301 次分给 3 个世界时，实际会分成 101、100、100 次。如果以后有一个学出来的概率模型，认为某些可能世界更常见，那么这里才需要按概率分配更多 simulation 或对结果进行加权；当前版本没有这种高手判断。

汇总时需要按玩家眼中的动作来归类，而不能被规则引擎的内部实现干扰。同一兵种的 coin 对玩家来说没有区别，所以不同可能世界中的“支付弓箭手 coin 并推进”都应当算作同一个动作。但使用不同兵种、发动不同战术或者选择不同目标，仍然属于不同动作，不能合并。

程序最终只会在玩家当前可以执行的动作中做选择，不会把某个可能世界里的内部结果直接拿回游戏执行。可能世界提供的是搜索证据；汇总后的访问次数才用于决定真正要走的一步。

当前方法解决了什么，还没有解决什么

前面的方案是在红方开始思考时采样多个可能世界，分别搜索，再汇总 root 的访问次数。这类方法通常叫 PIMC（Perfect Information Monte Carlo）。名字可以暂时不记，它的关键特征只有一句话：只在搜索开始时采样，之后每棵树都把自己采到的世界当成确定事实。

它比直接使用服务器中的真实状态公平，因为采样器没有偷看真相；它也很容易实现，因为每个可能世界都可以直接复用普通 MCTS。但它仍有两个重要限制。

限制一：搜索可能假设玩家以后能分辨实际上无法分辨的世界

假设 A 和 B 两个世界在红方下一次行动时仍然产生相同的 observation。现实中的红方到那一刻仍不知道自己处于 A 还是 B，所以必须在两种情况下做出同一个选择。

但两棵独立搜索树互不相识：

世界 A 的树 ─▶ 红方选择防守 ┐
                             ├─▶ 两边都被当作好结果计入当前动作
世界 B 的树 ─▶ 红方选择推进 ┘

汇总结果可能同时享受到“A 中知道要防守”和“B 中知道要推进”的好处，仿佛未来的红方能够识别自己在哪个世界。现实中它没有这项信息，无法执行这种“看情况再选”的策略。这个问题通常叫 strategy fusion，可以直译为“把多个世界中互不兼容的策略融合到了一起”。

更严格的 information-set search 会把“当前玩家看起来完全相同”的局面视为同一个搜索节点。A 和 B 如果产生相同 observation，就共享同一组访问次数，也必须学习同一个选择，而不是在两棵树里各自选择最有利的动作。

限制二：一个可能世界的隐藏未来从 root 开始就固定了

当前方法构造世界 A 时，不只确定了蓝方当前手牌，也确定了袋中 coin 的一种未来顺序。整棵树会一直沿用这个顺序。构造世界 B 时则会固定另一种顺序。

这能让规则引擎顺利进行 simulation，却可能让一棵树过度适应某一种未来抽牌。现实中的玩家只知道可能出现哪些抽牌，并不知道从 root 开始就已经写好的答案。这个限制通常叫 fixed sampled future，也就是“固定了一条采样出的未来”。

RIS-MCTS：轮到谁，就重新站到谁的视角

还有一个更严格的方法叫 RIS-MCTS（Re-determinizing Information Set MCTS）。它不会让一份在 root 采样出的隐藏世界从头用到尾。simulation 每走到一名玩家行动时，都会根据那名玩家当时能看到的信息，重新构造一个与其 observation 一致的可能世界。

例如，红方开始搜索时，可以为自己看不到的蓝方手牌采样；simulation 走到蓝方行动时，则重新站到蓝方视角，确保模拟中的蓝方不会利用蓝方当时看不到的红方私有信息。它希望做到：无论 simulation 走到谁行动，那名玩家的选择都只能依赖其当时有权看到的信息。

当前 PIMC：root 采样一次 ─▶ 同一个隐藏世界一直用到 simulation 结束

RIS-MCTS： 红方行动 ─▶ 按红方所见构造世界
                    └─▶ 蓝方行动 ─▶ 按蓝方所见重新构造世界
                                      └─▶ 红方行动 ─▶ 再按红方所见重新构造

当前版本只实现了第一行，也就是在 root 采样多个世界并汇总答案。它是用于验证 observation、可能世界采样和 MCTS 能否连通的第一版，不是完整的 information-set search，也不是 RIS-MCTS。

搜索公平以后，神经网络看什么、学什么

前文解决的是 MCTS 从哪些可能世界进行 simulation。接下来还有一个独立问题：神经网络本身接收什么输入，又从什么答案学习？

这个网络仍然有两个任务：

- policy：判断当前各个动作大概有多值得搜索；

- value：判断当前局面对行动方大概有多有利。

它的输入只能是当前行动方的 observation。规则引擎为了推进 simulation，内部可以暂时持有一个完整的可能世界；但完整世界中的对手手牌、袋中顺序等内容不能进入 neural network。这里仍然遵守最开始的原则：同一个 observation 必须产生同一份 network input。

训练 policy 时，不能只检查输入有没有隐藏信息，还要检查作为“正确答案”的搜索结果从哪里来。如果教师 MCTS 偷看真实 full state，那么它给出的 root visits 已经泄漏真相；即使再把输入换成 observation，训练样本仍然是在教 network 模仿作弊答案。

因此，公平训练样本应该是：

玩家的 observation ─▶ 从多个可能世界搜索 ─▶ 汇总后的 root visits
        │                                      │
        └──────── network input                └─ policy 学习目标

value 的最终监督信号可以来自对局胜负，但表达时必须始终说明是对哪一方有利。这样 network、MCTS 和回传结果才不会在行动方切换时混淆正负方向。

完整局面仍然可以保存在实验记录中，用来重放对局和检查采样是否符合规则；关键是它只能用于审计，不能悄悄进入 network input 或公平 policy 的教师答案。

第一版实验只验证流程能够连通

第一版实验故意做得很小：只取 1 局中的 4 个局面，训练一个 CPU 上运行的两层小网络；模型自我对局时，每一步只做 4 次 simulation，并只构造 2 个可能世界。

产生一小局对局记录
        │
        ▼
从每一步生成 observation 与训练目标
        │
        ▼
训练一个很小的 neural network
        │
        ▼
让 network 参与可能世界搜索与自我对局
        │
        ▼
确认对局能够重放，搜索记录能够检查

这次实验没有遇到无效样本或运行失败，搜索产生的访问次数也能完整进入训练和对局流程。但对局规模和搜索次数都太小，测试对手后的结果也只是平局。

所以它只回答了一个工程问题：observation、可能世界采样、MCTS、训练和对局记录能否首尾连通，并且可以重复检查。它没有证明模型有棋力，也没有解决上一节提到的策略融合和固定未来问题。

另外，当前代码仍把对手兵种名单当成隐藏信息重新采样，而实际规则中双方兵种名单是公开的。这个信息边界需要先修正并重新运行实验；旧结果只能证明流程曾经跑通，不能作为正确规则边界已经验证的证据。

接下来沿着已知限制继续改

后续工作可以直接对应前文发现的问题，而不只是盲目扩大训练规模：

1. 先修正公开信息。 observation 应包含双方兵种名单；采样器只猜测真正隐藏的 coin 分布和袋中顺序。

2. 让可能世界的概率更真实。 当前采样器只保证结果符合规则。以后可以利用公开行动历史和对局数据，判断哪些隐藏状态更可能出现，而不是近似等权看待所有候选。

3. 避免融合现实中无法执行的策略。 当不同可能世界产生相同 observation 时，让它们共享搜索统计和选择，不能让每棵树假设玩家知道自己在哪个世界。

4. 轮到谁，就只允许谁使用自己的信息。 simulation 中行动方变化时，按新行动方的 observation 重新构造可能世界，逐步走向 RIS-MCTS。

5. 最后才扩大训练。 只有上述信息边界可以被测试和审计后，增加对局数量、simulation 次数和网络规模才有意义。

不完全信息 AI 最容易犯的错，不是模型太弱，而是它悄悄知道了玩家不该知道的东西。先证明每一步只使用玩家有权看到的信息，才有资格继续讨论搜索和模型能有多强。