MCTS — Wu Chenfeng

四颗石子放在桌上，两人轮流拿走一颗或两颗，拿走最后一颗的人获胜。根玩家现在行动：拿一颗会留下三颗，对手无论怎样拿，根玩家都能拿完；拿两颗却允许对手立即获胜。这个小游戏可以穷举，也能让我们看清蒙特卡洛树搜索（MCTS）怎样用反复试局逐渐偏向第一个动作。

MCTS把已尝试的状态留在树中，每轮从根出发，选择已有分支、扩展一个新动作、模拟到终局，再把收益写回路径。下面始终把收益存成根玩家获胜为+1、失败为−1。例子是确定性、完全信息、双人零和游戏。

状态与动作

节点保存剩余石子数、下一位行动者、父边动作、访问次数N和累计收益W。根节点为(4,+1)。执行拿一颗得到(3,−1)，下一次执行拿两颗得到(1,+1)。剩余为零时停止，胜者是刚刚行动的人，所以终局收益为下一行动者符号的负值。

树保存统计，不直接修改真实游戏。这里状态是两个整数，子节点直接生成新值；棋盘游戏则需要复制状态或执行动作后撤销。若模拟漏掉撤销一步，后续搜索会从被污染的局面出发，统计量再准确也属于错误状态。合法动作由剩余数量决定：还有一颗时只能拿一颗。

扩展与模拟

节点有合法但尚未建子节点的动作时，先建立一个子节点。本例按动作1、2排序，每轮最多扩展一次，然后从新节点随机选择合法动作直到终局。随机模拟提供的是当前模拟策略下的一次样本，它并不代表双方最优对弈。

第一次搜索扩展根动作1，留下三颗。模拟中对手拿两颗、根玩家拿一颗，根获胜，收益+1。根与动作1子节点都更新为N=1,W=1。第二次扩展根动作2，对手拿完两颗，收益−1；根变为N=2,W=0，动作2子节点为N=1,W=−1。两条路径都只获得一次样本，搜索尚不能因此停止。

UCT选择

根动作都扩展以后，继续探索需要在已有收益与尚未充分尝试之间取舍。UCT对子节点i计算：

$S_i=s\frac{W_i}{N_i}+C\sqrt{\frac{\ln N_p}{N_i}}$

Np是父节点访问数，s在父节点轮到根玩家时为+1，轮到对手时为−1。两方都最大化S；对手通过负号倾向选择根收益低的分支。探索项始终为正，本例取C=√2，与±1的收益尺度配套。未访问动作由扩展优先处理，公式只用于访问数大于零的子节点。

前两轮后，根的两个利用项分别为1和−1，探索项都为√(2 ln2)≈1.177，所以第三轮走动作1。到了剩三颗、对手行动的节点，再扩展动作1。模拟中根拿一颗、对手拿完最后一颗，收益−1。动作1根子节点现在累计两次访问、收益0。搜索没有推翻“拿一颗可获胜”的博弈结论；它暴露的是随机模拟会漏掉根玩家之后的正确应对。继续扩展后，树会逐渐在这些后续状态里也进行决策。

若把对手处的s写成+1，对手会主动追求根玩家获胜，得到合作式搜索。若在回传中逐层翻转W，又保留这里的s，则收益被翻转两次。根视角存储和选择符号必须作为一套契约使用。

完整迭代与回传

完整Python参考实现把合法动作、状态转移、模拟、UCT和路径回传全部展开。下面是其迭代的执行关系，具体游戏转移在前两节已有定义：

text

从根开始，将根加入路径
只要当前节点非终局：
    若有未展开合法动作：生成新状态和子节点，加入路径，结束选择
    否则：计算每个子节点UCT，进入最高分节点，加入路径
从路径末端状态随机执行合法动作，直到石子数为零
value = 终局中下一行动者符号的负值
对路径中的每个节点：N += 1，W += value

回传更新根在内的每个经过节点，未经过的兄弟保持不变。从全新空根开始时，根访问数等于实际完成迭代数；根非终局且每轮均进入一个根子节点时，根的子节点访问数之和也等于迭代数。若输入本身已是终局，只有根获得回传，子节点总访问数为零，行动接口应返回无合法动作。终局节点直接回传胜负，不再生成空动作；若工程使用深度上限，则叶估值也必须使用根视角和相同收益尺度。

固定种子7、120轮的参考运行中，动作1获得116次访问、累计收益110，动作2获得4次访问、累计收益−2。这个结果说明该局面和模拟器下搜索集中到了可胜分支，不能据此保证任意局面的有限预算质量。

最终决策与预算

UCT用于分配下一次试局，所以很少访问的动作可能获得较大探索奖励。实际落子时已经没有后续探索收益，本例选根节点访问次数最多的动作。若某动作访问100次、均值0.8，另一动作访问1次、均值1，单取均值会选中证据最少的那个。工程也可采用明确的温度采样策略，但应将最终行动规则与树内探索分开记录。

每轮需要状态转移和模拟，长回合游戏的耗时会随模拟深度增加。实时预算先测每轮成本，再限制时间；离线复现固定迭代数、动作顺序、随机种子和随机消费顺序。仅固定种子而按墙钟停止，机器速度仍会改变树的规模。

本例没有机会节点。存在随机事件时按事件概率采样，不能把事件当作试图击败根玩家的对手。隐藏信息游戏还必须从决策者可知状态采样：若搜索直接读取对方暗牌，得到的是不可执行策略。将每种暗牌分别当完全信息游戏搜索也可能产生策略融合，需采用与信息集相符的搜索模型。这些变化改变状态与采样语义，不能只替换UCT系数。

搜索结果与真实状态

最终动作只有在真实局面仍与搜索根状态一致时才能提交。搜索开始记录局面版本，输出根动作与该版本；异步搜索结束时版本已变化就丢弃结果，不能把旧树的合法动作套到新局面。版本比较、合法动作复查和实际落子必须在游戏状态的同一提交入口完成；先比较再异步排队落子，会让两次合法决策都消费同一局面版本。搜索树由该搜索任务独占，超时或取消先等待任务在检查点退出，再复用其子树或释放节点；仅忽略迟到动作不能阻止后台继续修改已复用的W和N。

动作成功应用后，以匹配的根子节点作为新根并断开旧父引用，保留其统计。如果新根行动者成为新的“根玩家”，则将保留子树全部W取反、所有行动者±1标记也取反，使收益与选择符号继续采用新根视角；直接改根指针而沿用旧视角W，会让下一位行动者追求上一位的胜利。若搜索仍服务原玩家并跨过对手的实际行动后复用，就保留原玩家视角，只沿实际动作继续取子树。若实际状态与该子节点不同，例如出现未建模随机事件，则从实际状态重建根。

复用的访问数已经包含旧搜索贡献，新增迭代数应以本轮根N减去搜索开始时保存的N计算。原子树节点第一次被扩展时，可能从它直接做过一次模拟、没有访问它的任何子节点；因此复用为根后，根N与现有子节点N之和允许相差这份历史叶样本。例如旧节点N=5、子节点合计4，复用后完成3轮并都经过根子节点，得到根N=8、子节点合计7，而本轮确实只完成3轮。不能为了套用空根的守恒式强行改N，删掉这些访问却保留W会使均值与探索项同时失真。

时间预算在迭代边界检查，当前正在进行的模拟也设定深度或取消检查点。中止一轮时不回传半条路径；只完成选择而尚未得到终局收益，不能把默认零当作一次平局写入N。

本页的实时接入将本轮新扩展的节点和父边暂存在搜索任务内，直到得到完整收益才把该边挂入树、从未展开动作集合移除该动作，并完成整条路径的N/W回传。取消发生在此之前就丢弃临时节点，原树不变；提交阶段作为不处理中途取消的短临界步骤完成后，再响应下一检查点。

若提前把新节点挂树，却在取消时只跳过回传，会留下N=0的已展开子节点，后续UCT便可能除零。这也要求复用子树必须等待当前任务完成取消清理。

没有完成任何迭代时返回按稳定编号最小的合法备用动作，不能从空子节点列表取最大值。UCT与最终访问数平局时按稳定动作编号选择，以免相同状态和随机种子因容器遍历顺序改变决策。

实现与证据

运行 python 知识库/examples/retained_review/mcts/test_reference.py 检查120轮访问守恒、已知可胜动作、终局回报与固定种子重放。实现使用Python标准库，输入是初始石子数、迭代数和种子，输出根树和逐轮路径。它是完整微型游戏搜索，不包含大型棋盘、隐藏信息或实时预算质量测量。原有UCT选择检查继续覆盖根最大化、对手最小化和未访问优先。

参考资料

Browne等：MCTS综述：树搜索、随机模拟与变体的文献入口；本页石子例和代码为独立教学实现。
Kocsis与Szepesvári：Bandit Based Monte-Carlo Planning：UCT原论文入口。