https://metool.online/_assets/js/go-mcts-algorithm.zh.D9h5TBAQ.js

1/* © 2024-2026 MeTool.online. All rights reserved. Unauthorized copying or redistribution is prohibited. */
2const t=`<blockquote>
3<p>围棋之所以难，不只是「规则复杂」，而是<strong>空枰上就有上百个几乎等价的合法点</strong>。穷举到终局不可能，评估函数又极易写偏；MCTS 用「大量随机对局 + 把算力投到更有希望的分支」在两者之间走出一条可落地的路。</p>
4</blockquote>
5<p><img src="/blog/go-mcts-algorithm/cover.webp" alt="围棋空盘上分支爆炸，MCTS 用随机对局把算力集中到少数有希望的落点"></p>
6<h2>为什么围棋特别适合、也特别依赖 MCTS？</h2>
7<p>围棋的搜索空间大到无法靠「算到底」解决：19 路空盘约有 361 个空点，合法着法随局面变化，对局长度常超百手。若每步平均还有几十个合理候选，树的宽度与深度都会爆炸；而手写启发式（吃子优先、占角、连气）在空旷开局又容易退化成贴边乱爬。</p>
8<p>MCTS（Monte Carlo Tree Search，蒙特卡洛树搜索）不试图穷举，也不依赖一张「全局评分表」。它反复做短局随机对局，用胜负结果回传，把更多模拟预算投给看起来更好的分支。分支因子越大、局面评估越难写准时，这种「用采样代替穷举」的思路越有价值——这也是它在围棋、以及后来许多不完全信息游戏里被广泛采用的原因。</p>
9<h2>MCTS 的一轮迭代在做什么？</h2>
10<p>一轮完整的 MCTS 迭代通常拆成四步，循环直到时间或模拟次数用尽：</p>
11<ol>
12<li><strong>选择（Selection）</strong>：从根出发，按 UCB1 一类公式在已展开的子节点里往下走，平衡「已知胜率高」和「还没试够」；</li>
13<li><strong>扩展（Expansion）</strong>：走到还有未试过的合法着法时，随机或按某种先验挑一手，长出一个新子节点；</li>
14<li><strong>模拟（Simulation / Rollout）</strong>：从新局面起双方随机（或弱启发式）下到终局，按规则数子判胜负；</li>
15<li><strong>回传（Backpropagation）</strong>：把这一局的胜负沿路径写回每个节点的 visits / wins。</li>
16</ol>
17<p>最终落子一般取<strong>根节点下访问次数最多的子节点</strong>（argmax visits），而不是瞬时胜率最高的那个——访问次数本身已经融合了「试过很多次仍站得住」的信息，比早期噪声很大的胜率更稳。</p>
18<table>
19<thead>
20<tr>
21<th>步骤</th>
22<th>输入</th>
23<th>输出</th>
24<th>常见坑</th>
25</tr>
26</thead>
27<tbody>
28<tr>
29<td>选择</td>
30<td>已展开的树 + UCB1</td>
31<td>一条通向叶/待扩展节点的路径</td>
32<td>探索常数过大 → 访问摊平</td>
33</tr>
34<tr>
35<td>扩展</td>
36<td>未试过的合法着法</td>
37<td>一个新子节点</td>
38<td>根上塞进自杀/填眼点会污染终局</td>
39</tr>
40<tr>
41<td>模拟</td>
42<td>当前局面</td>
43<td>一局胜负</td>
44<td>模拟阶段若乱填自己的眼，估值失真</td>
45</tr>
46<tr>
47<td>回传</td>
48<td>胜负</td>
49<td>路径上 visits/wins 更新</td>
50<td>视角要统一（始终相对同一方）</td>
51</tr>
52</tbody>
53</table>
54<h2>UCB1 是怎么在「利用」和「探索」之间折中的？</h2>
55<p>UCB1 给每个子节点打一个分数，大致是：</p>
56<p>[
57\\frac{w_i}{n_i} + C \\sqrt{\\frac{\\ln N}{n_i}}
58]</p>
59<p>前一项是经验胜率（利用），后一项随该节点访问变少而变大（探索）。(C) 越大，越愿意去试生疏分支。</p>
60<p>教科书常取 (C=\\sqrt{2}\\approx 1.41)，那是收益落在 ([0,1])、且子节点不太多时的理论推导。围棋根上往往有几十上百个合法点，而浏览器里一次思考往往只有几千到几万次模拟：此时探索项很容易压过胜率差，结果是<strong>访问几乎均匀，首选手占比可掉到约 2%</strong>——既选不出好棋，根上的「倾向度」也失去可读性。工程上常把 (C) 下调（例如 0.4），让有限预算更快集中。</p>
61<p>一个可观测的收敛信号是根节点首选手的访问占比：同样 9 路局面，约 1200 次模拟时 top1 常只有个位数百分比，两万次可到约 17%，四万次可到约 40% 量级。占比低时，优先怀疑「还没搜够」，而不是「盘上真的到处一样好」。</p>
62<h2>「倾向度」和最终落子是什么关系？</h2>
63<p>根上各子节点的 <code>visits / Σvisits</code> 可以读成相对倾向度：搜索把算力投到了哪里。UI 若展示 top-N 候选，通常就是按 visits 排序后截断；最终一手仍取 visits 最大者。</p>
64<p>几条读数时容易忽略的边界：</p>
65<ul>
66<li><strong>总和一般小于 1</strong>：长尾候选被过滤掉后，展示集合的概率和会小于 1，这是刻意的——top1 占比本身在说「有多确定」；</li>
67<li><strong>模拟量不足时分布很平</strong>：19 路把几千次模拟摊到上百空点，每点只有几十次，倾向度接近噪声；</li>
68<li><strong>不要用温度采样去「故意下弱」</strong>：在尚未收敛的分布上按 visits 采样，会把本就平坦的分布变得更接近均匀，棋力会塌成乱下。弱化更干净的做法是<strong>减少模拟预算</strong>，仍用 argmax 选点。</li>
69</ul>
70<h2>开局为什么不能靠「少想一会儿」提速？</h2>
71<p>空枰合法点最多，单点分到的模拟最少，恰恰是全局最缺算力的阶段。一种直觉是：「首手 top1 只有个位数百分比，说明各点差不多，少搜一点也没事。」自对弈会打脸：同强度引擎，开局砍预算的一方可到约 2:8 的惨败。正确读法是——<strong>占比低 = 还没收敛</strong>，不是「已经等价」。</p>
72<p>更稳妥的提速是<strong>开局知识收窄根候选</strong>：把根上的未试着法限制在少数公认成立的要点（例如仍空着的角星），分支从上百降到个位数，每个候选反而能分到数百次模拟。等角被占满、或要点周边开始接触、或盘上出现只剩一气的紧急棋块，就整体退回全盘搜索。这种做法在大棋盘上通常既省时间又提高单点信噪比；在 9 路这类分支本就不算夸张的盘上，强行收窄反而可能是净损失，需要按盘面规模开关。</p>
73<h2>收官阶段为什么要显式避开「自己的眼」？</h2>
74<p>围棋里往自己的真眼里落子通常合法却极差——等于自杀气。随机模拟若不禁止填眼，估值会被大量自毁棋污染；根节点若不排除自己的眼，收官时「已无棋可下」的一方还可能去填眼把活棋走死，而不是停手。</p>
75<p>因此成熟一点的纯 MCTS 围棋实现会在两处同时处理：模拟阶段不走填眼；根候选里也滤掉己方眼位。只剩眼可填时，正确动作是<strong>停一手</strong>，让双方进入数子流程。</p>
76<h2>纯 MCTS 的能力边界在哪里？</h2>
77<p>理解边界比背公式更重要：</p>
78<table>
79<thead>
80<tr>
81<th>维度</th>
82<th>纯 MCTS（随机 rollout）</th>
83<th>带策略/价值网络的 MCTS</th>
84</tr>
85</thead>
86<tbody>
87<tr>
88<td>先验</td>
89<td>几乎没有，靠访问慢慢集中</td>
90<td>网络给出着法先验与局面价值</td>
91</tr>
92<tr>
93<td>同等时间棋力</td>
94<td>

94受模拟量硬约束，大棋盘噪声大</td>
95<td>通常显著更强</td>
96</tr>
97<tr>
98<td>可解释的「倾向度」</td>
99<td>直接来自 visits 分布</td>
100<td>还混有网络先验，需分开读</td>
101</tr>
102<tr>
103<td>实现与算力</td>
104<td>可在浏览器 Web Worker 里跑</td>
105<td>通常需要模型权重与更大算力</td>
106</tr>
107<tr>
108<td>弱化难度</td>
109<td>减 <code>maxSims</code> / 时间即可</td>
110<td>还要调温度、噪声等</td>
111</tr>
112</tbody>
113</table>
114<p>此外还有几条工程边界：没有神经网络时，19 路短时搜索的倾向度只宜作参考；中国数子与日本点目的终局定义不同，模拟终点的计分规则必须与产品规则一致；劫争、自杀合法性要在「合法着法生成」里处理正确，否则树会学到非法捷径。</p>
115<h2>小结</h2>
116<p>MCTS 用「选择 → 扩展 → 模拟 → 回传」把有限算力投向更有希望的分支，最终常按访问次数最多的一手落子。围棋根上分支极多，UCB1 的探索常数、开局是否收窄候选、模拟是否禁填眼，都会在真实预算下决定棋力与可读性。读 visits 占比时，先问「这盘棋搜了多少次」——收敛之前，平坦的分布说明的是算力不够，而不是棋盘上到处都是好点。</p>
117`;export{t as default};