牛顿棋RL 1：强化学习靠左脚踩右脚，真的可以上天？

本篇为了讲清楚我所理解的 RL 进步原理，写完发现篇幅较长…全文约 5,467 字，预计阅读 12 分钟…吗？那是不可能的，要思考的话应该不止 12 分钟（）

如果对于牛顿棋规则和背景不清楚，可以看系列文章上一篇， 牛顿棋RL 前言：我想训练出牛顿棋的第一个“AI棋圣”

要真正开始 RL 了，看零基础的情况下，能不能在 AI 大人帮助下搓一个能跑的牛顿棋 AI。

基建

首先，当然是把游戏从单纯给人玩，改造出一套给程序（和AI）使用的方便的接口。总不能指望 AI 跟我们一样靠视觉识别（没必要，效率低下）。这也是我没有直接用原版游戏的缘由，自己 vibe 一个总是更称心如意。（当然，如果官方真的看见了想要做个 api 接口出来给 AI 调用，那就再好不过了）。

什么，你问我具体怎么做的？我也不知道。大概就是把上面的这段话发给 AI，它就把程序接口写好了。以后 AI 下棋，就可以 用函数调用等方式来做，而不是傻乎乎地网页截图了。

然后我还让 AI 设计了一下棋局导入导出的方式，AI 直接给设计了一种编码，形如： nf1.9.9.2.p.001102111211211105221312062107130814152223241516241725333433323141322635.1gstytb 具体是啥意思其实也不用太深究，能用就行（） nf1 是 newton force 1，标记协议版本；9.9.2 则是 9x9 棋盘、双人模式的设定。 p 是棋局状态正在进行的意思，00 11 02 这种，则代表 第一步下了 （0，0），第二步（1，1），第三步（0，2），以此类推，结尾则有个完整性校验码。还有一些细节也就不深究了。导入导出的方式定义好，后续要收集对局、分享对局、replay 都方便。

为了未来更灵活探索，多人模式、自由定义的棋盘形状等也顺手做了。尽管最初的目标是做双人模式、9x9 棋盘，可能以后还能训三人模式或是更大棋盘的 AI，对吧？

调研

有道是，站在巨人肩膀上才能看得更远…

所以，一开始我就随便语音输入了一段话先让 AI 调研给我出一个方案（同时看看硬件的可行性）。尤其是我提及了大名鼎鼎的 AlphaZero：它不需要人类棋谱，完全通过自我对弈训练，实力超越了早期的 AlphaGo，而且一套算法同时搞定围棋、国际象棋、将棋。

好消息是，对于我目前想要做个小 Demo 而言，M4Pro+48G 的 mac mini 还是绰绰有余的。然后方案我放一下 AI 的原话：

嗯…AI 分析得头头是道，但是呢，什么是 MCTS？什么是 Gumbel？直接继续追问 AI 即可得到答案，我下面会在合适的时候用自己的话讲讲我的理解，仅供参考。至于 DQN 和 MuZero，既然已经 AI 排除了，就先放一边不管了。

后续的记录中，若非必要，这种 AI 聊天的记录我也就不直接放了。这里直接放的用意也是让大家看到其实我也跟大家一样，就是不懂直接向 AI 提问，没有什么特别的。

而后面讲解我的计划是用自己的话把我的理解以及思维链讲出来，以达到整理思路和印证所学的效果。但限于水平，很可能会有纰漏，所以大家辩证地看，同时也欢迎自行向 AI 求助，并通过评论等互动不吝赐教。

AI 在预测什么？

AI 选的方案看起来很酷。但是呢，我想知道：AlphaZero 做到自我对弈并提升的秘密是什么？

原来，AI 设计的神经网络会预测两个东西：1. “policy”，策略网络负责预测棋盘每个格子落子的倾向，分数高的格子意味着 AI 网络更想下在那儿；2. “value”，价值网络负责预测当前局面对当前下棋方的有利程度（可以理解为，“我”有多可能会赢）。

value 预测出来的东西就是个实数，取值 [-1,1]，负数代表不利我方，正数代表利于我方。（这里的我方，就是当前下子的一方）。policy 则给每个格子预测一个数（直观可以理解为概率，实际上需要用 softmax 归一化成概率），数越大代表 AI 越想要下这里。

但是初始化的时候，无论是 policy 网络还是 value 网络，都是随机出来的，宛若新生婴儿，啥也不会。那怎么才能进步呢？网络学习的目标是谁，想要向谁看齐（拟合）呢？

value 的学习“榜样”

首先看 value 如何学习：AI自己下棋，就算乱下，也可以得到一盘盘数据。然后根据规则判定赢了还是输了，以及赢多少输多少，就可以得到真实的 value 值（一开始为了方便，我们定义，如果“我方”赢了就记真实 value 为 1，输了就是-1，平局就是 0）。而 价值网络 学习的目标就是这些真实产生的对应数据的 value 值了。

让 AI 自己重复对局，每一次对局我们都会看作一系列的动作串成一条链子（如果说每一步我们考虑几种可能性的话，甚至可以串成一个树），当每局结算的时候，就可以回过来把这条链的每一步标上正一和负一。

其实我一开始就感觉，如果不只给输和赢的信息，而加上输多少赢多少的信息，可能会更好。但是当时急着睡觉，所以让 AI 自己干去了，它选了只给输和赢。

policy 的学习“榜样”

policy 的学习就比较有趣了，在 AlphaZero 论文里，它的学习目标是：改版的MCTS（蒙特卡洛树搜索，但是用 PUCT 指导…PUCT: Predictor + Upper‑Confidence‑bounds applied to Trees）形成的访问频率。

AlphaZero style 的 MCTS

头大了？别急，我努力理解了一下想法，感觉其实思想是简单的。首先人类下棋一般会做「计算」，也就是预测往后的几手棋的多种可能性，以及评估他们的优劣。AIphaZero 也是这样的思想，AI 做这种计算的时候用 树 这种数据结构来表示，从当前局面开始作为树的根（root），预测几个可能的下一步走法放在第一层，然后继续预测下一步的下一步对手如何应对… 如此这般搜索下去，理论上我们就可以穷尽棋局所有的可能性然后找出最优解了（doge）

但是显然计算量过大，这种做法是不现实的。在 9x9 的牛顿棋中，可能计算量在 $10^{80}$ ～ $10^{120}$ 量级 哪怕是拿超算算到宇宙尽头都算不完。所以只能有选择性地去计算。这就是 MCTS（Monte‑Carlo Tree Search，蒙特卡洛树搜索）的思想。每一步往下走（的时候，我们并不会去搜所有的情况，而是按照公式去探公式给出评分较好的情况。具体而言，每次计算（或者叫simulation，后面称为 sims）包含四步：

1. 选择探索的边（select）：从根节点往下走（每一次走动相当于沿着树走一条边，从一个节点走到另一个节点），在每个已展开的节点上，选 公式给出评分 最大的动作（这个例子中，就是后文会讲的 PUCT）。直到找到一个还未展开计算的节点。
2. 展开（expand）：从当前未展开的节点，按照 AI 的策略网络预测，选一个它最想走的步骤，走到一个新的节点。
3. 对新节点评估价值（evaluate）：每当我们模拟一步，会同时去评估一下它的价值 value（还记得吗，可以理解为当前我方有多大概率赢）。
4. 价值回传，更新祖先节点（backup）：而每当一个盘面节点往下模拟了新的走法，产生了新节点及其对应 value，自然的会把它的祖先盘面节点的 value 相应地进行更新（因为，我们对某一个局面进行了更多的模拟预测，产生了更多孩子节点，有了更加精确的 value 判断，所以就相应地更新这个作为祖先的 value）。

AlphaZero 这边用所谓的 PUCT（Predictor + Upper‑Confidence‑bounds applied to Trees）：

$$\mathrm{PUCT}(s,a) = c_{\mathrm{puct}} \cdot P(s,a) \cdot \frac{\sqrt{N(s)}}{1 + N(s,a)}+ Q(s,a)$$

看到公式就容易头大…但其实直观理解，这个公式是在平衡“探索没见过的新步骤”、“AI 的价值网络的落子偏好”和“实际搜索得到的价值评估”。且听我道来：s 代表当前棋盘的状态（也就是各个子摆在哪里了），a 则代表我们关心的那个格子，P(s,a) 说的是，策略网络（policy network）在输入当前棋盘状态 s 之后，对于格子 a 给出的落子概率。这一项乘上了 $\frac{\sqrt{N(s)}}{1 + N(s,a)}$ 这个系数，其中的 N(s)代表当前搜索树中，该 state 模拟过了多少次（每个棋盘的状态恰好对应树的一个节点），N(s，a)则代表当前搜索树中，从该 state 下了 a 这个步骤对应的这个边走过的次数（对一个 state 进行一次落子 a，相当于从一个节点走到下一个节点，也就可以用两个节点之间的边来表示）。

那么这个系数可以理解为，如果分子N(s)比较大，说明当前 state 被访问较多，大概是因为 select 的时候，PUCT 认为这个边更值得探索。那么对于一个比较值得探索的棋盘局面，我们应该给它分配更高的 PUCT 分数，更多地探索它。但同时，分母的 N(s,a)又说，如果这一步（从 s 落子 a 的某一步）探索得已经比较多了，那么我们就让一些机会给新的步骤（比如从 s 落子 a’）。所以 N(s,a)越大，PUCT 中的这个系数就越小。

P(s,a)这一项还乘了个系数 $c_{\mathrm{puct}}$，这个则完全是我们定义的一个调节参数。如果这个系数给的大，那么我们就在 PUCT 选择的时候让 P(s,a)的权重更多，也就是让 AI 的价值网络更多地去指导搜索。反之，就会减小 P(s,a)的权重，相当于增大了 Q(s,a)的权重。

那么 Q(s,a)是啥呢？它是从局面 s 走出动作 a 这一步，到目前为止搜索得到的平均价值。什么叫做“到目前为止”？这里就涉及到 backup 这个步骤的细节了。

假如某一步是第一次在搜索中走出，那么不存在什么“到目前为止搜索得到的平均价值”，也就是 Q(s,a)=0，此时 PUCT 退化为只含网络策略 policy P(s,a)的那一项。所以 expand 这一步的时候我们也可以用 PUCT 来指导选择：因为此时 N(s)=1，N(s,a)=0，代入 PUCT 公式，可不就是 $\mathrm{PUCT}(s,a) = c_{\mathrm{puct}} \cdot P(s,a)$，“按照 AI 的策略网络预测，选一个它最想走的步骤，走到一个新的节点。”

以及还有一些实现上的小细节，比如训练期间，搜索时在 root 节点的 PUCT 上加一点噪声扰动。因为根上走的那一步很容易一开始退化为只包含网络 policy——但是你的目标是训练这个 policy，Policy 本来就蠢的话，那就很容易固化这个网络的固有的倾向。所以加一点噪声，尝试把它踢出去 policy 的效应，逼他多探索探索。

但是一旦某一步(s, a)探索之后，我们就会用 backup 来回传它带来的价值 value。 这一步大致是， $N(s,a)\mathrel{+}=1$ , 某一步的总价值 $W(s,a)\mathrel{+}=v,\quad Q(s,a)=\frac{W(s,a)}{N(s,a)}$ ——可见，Q(s,a)的定义就是总价值除以探索次数，也就是平均价值了。

所以再回首 PUCT 公式，也就没那么可怕了，它就是在“探索没见过的新步骤”（$\frac{1}{1 + N(s,a)}$）、“AI 的价值网络的落子偏好”($P(s,a)$)和“实际搜索得到的价值评估”($Q(s,a)$)三者间找平衡。

第三步 evaluate 值得一提的一个细节：由于搜索次数限制，在棋局最初可能很难搜到终局去，那么 value 是由 AI 的价值网络给出的预测。假如搜索到了终局结算的 state，则由确定性的游戏规则来给出实际的 value。

MCTS 搜完之后，AI 怎么落子？

刚刚说了那么多，其实都是 AI 棋手在每一步落子之前考虑的事情。比如，我设置了 96 sims 的搜索预算，那么 AI 在考虑下一步的时候，就会按照 MCTS 的四个步骤，重复 96 次 sims，形成当前步骤的一颗搜索树（大约有 97 个节点？根节点，加上 96 sims 搜出来的 96 节点）。

那么“颅内”进行了一番计算，我们选择下哪一手呢？回到 root 根节点局面（目前我们面对的局面），然后看一看它的直接子节点（从根出发，只下一手），摆在面前仔细思考的话，其实有这么几个可能的选项：

1. 看 N(s,a)，谁被 PUCT 搜索走过得多，说明它是 PUCT 这个评价体系下综合价值比较好的一步。
2. 看 Q(s,a)，网络经过搜索之后，平均给这一步的价值评估
3. …？

而 AI 最终选择了 1，理由是：

Q 确实是「搜出来的平均价值」，但样本少时很飘。

典型事故：某步只被点过 1～2 次，叶子运气好 Value 很高，Q 暂时第一；另一手被认真挖了几百次，Q 略低但稳。若按 Q 走，会去选那个几乎没被检验过的「幸运一击」。

N 高表示：在整段预算里，PUCT反复愿意把模拟砸回来。那通常要同时满足：

• Q 已经不错（利用项留得住它）
• 又经得起和别的高 policy 网络 偏好、探索较少的招法竞争

回到最初的问题：policy 学习的榜样是谁呢？就是经过搜索之后得到的“下一手的分布”，按照 N 的多少，我们把它当做是搜索网络得出的下一步各个格子的落子概率，让 policy 去拟合它。

“左脚踩右脚上天”的进步方式

终于绕过了啰嗦的原理部分，我们知道了 AI 到底在预测什么，以及预测的 value 和 policy 应该向什么数据去拟合，那么接下来就是如何收集这些数据？

AlphaZero 说的是不需要人类的对局数据，所以这些数据自然靠网络自己对弈生成。一开始我们的 value 和 policy network 的参数都是随机的，然后 AI 自己下棋，按照刚才 MCTS 那一套下若干盘之后，会得到一批对弈数据，他们包含了真实的 value（value network 的拟合目标），以及在这个搜索过程中，MCTS得到的下一手的 N 的分布（policy network 的拟合目标）。收集够一批对弈数据之后，我们就可以用传统的机器学习反向传播那一套算法去更新参数。

更新参数之后，再下若干盘，再收集一批数据，然后呢再反向传播更新参数…如此往复，就是这么简单…?

但是看到这里，各位小伙伴想必跟我一样，都有一些疑惑：如果一开始 policy 预测也不准，value 预测也不准，一开始让它自己下棋，那不就是瞎下？为啥能进步呢？

可能的一种答案是，神经网络和 MCTS 搜索互相之间达成了一种“左脚踩右脚上天”的关系。

刚刚讲 MCTS 的时候，我们已经发现了一个很关键的事情：AI 真正落子之前，并不是把棋盘丢给神经网络，然后直接按照 policy 最大的格子就下了。神经网络更像是在给它提供一种直觉——policy 告诉它“哪些地方看起来比较值得下”，value 告诉它“这个局面看起来怎么样”。

然后 MCTS 会拿着这些直觉，再额外想一会儿。

比如说网络单独看棋盘的时候，只进行了一次前向计算；但是 MCTS 可以额外做 96 次 sims，去尝试不同的后续走法。它会按照 PUCT 不断挑选值得探索的分支，看看这些棋到底往后会发生什么，再把搜到的信息一点一点积累回来。

所以我们可以粗暴地把它理解成：神经网络负责直觉，MCTS 负责计算。

虽然一开始这个“直觉”非常烂，甚至跟随机差不多，但 MCTS 并不是完全照抄网络的答案。它会进行探索，也会不断利用后续搜索得到的 Q 值来修正自己的判断；如果真的搜索到了终局，那么终局到底谁赢谁输，更是直接由游戏规则说了算，不需要相信神经网络。

也就是说，哪怕网络一开始啥也不会，整个系统里面仍然存在一个非常重要的“不会骗人的老师”：游戏规则。

你可以乱下，但是乱下一盘之后，谁赢了就是谁赢了，谁输了就是谁输了。这个结果不会因为神经网络比较蠢就跟着变蠢。

于是，在一次 MCTS 搜索里，网络先给出一个很粗糙的判断，MCTS 再在这个判断的基础上多想一点。多想出来的结果未必每一次都一定比原来的网络聪明，但总体而言，通过额外的搜索计算，它把原本网络“一眼看过去”的判断进一步加工，更有概率得到更靠谱的结果。

于是就出现了一个很有趣的过程：

$$\text{当前网络} \rightarrow \text{MCTS 深度思考} \rightarrow \text{得到更好的搜索结果} \rightarrow \text{网络去学习这个结果}$$

其中，MCTS 搜出来的访问次数分布 (N(s,a))，就拿来教 policy network；自我对弈最终真实的胜负结果，则拿来教 value network。

换句话说，网络在学习 MCTS 思考之后得到的答案。

等训练完一轮之后，新的网络就会比以前更有“棋感”：它看到一个棋盘之后，policy 给出的落子倾向更靠谱了，value 对局面的判断也更靠谱了。

那么下一次 MCTS 再开始搜索的时候，它拿到的起点自然也更好了。

原来可能是：

“呃……我觉得这几个地方差不多吧，随便搜搜？”

现在可能变成：

“网络直觉上觉得这三步比较有希望，优先往这里算算。”

于是同样是那么多次 sims，建立在更强网络上的 MCTS，也往往能够把有限的计算预算花在更加靠谱的地方，得到更好的搜索结果。

然后这些更好的搜索结果，又重新变成下一轮网络训练的数据。

于是整个过程就变成了：

$$\text{更强的网络} \rightarrow \text{更强的 MCTS 搜索} \rightarrow \text{更好的训练数据} \rightarrow \text{更强的网络} \rightarrow \cdots$$

嗯？这不就是神经网络和 MCTS 左脚踩右脚上天吗？所以 AlphaZero 最有意思的地方之一，大概就在这里：它把昂贵的“思考”结果，重新训练进了快速的“直觉”里面；而越来越强的直觉，又让下一次思考变得更加有效。

其实人类学棋何尝不是这样呢，尤其是面对一个新的棋类，从完全没有经验，多下几把，多思考一下，把深度思考的结果慢慢培养成方法论，培养成直觉，最终达成棋力的成长。

训了一晚上，结果…

AI 自己写了个贪心算法作为参照的对手，每个 iteration 会先自对弈 240 局，然后收集到的数据用于训练网络参数，然后下个 iter 再用新网络自对弈 240 局…如此这般。最初每次 MCTS sims 数是 48.（都是 AI 一键生成的啦，包括本期按下不表的网络结构之类的…其实是因为我也还没问 AI 大人网络结构是怎么设计的）。

看上去有点进步，我就让它自己继续增加 iter 数还有做一些优化，比如增加 sims 的思考深度。直到第二天，我上手跟它打，却发现了一些问题…甚至，ox alpha 在实现过程也留了个粗心的坑…（未完待续）