Day 27 / DL x RL / 令世界惊艳的 AlphaGo

如果你经历过 2016 年，且对围棋或 AI 稍有研究，那你肯定听过 AlphaGo 的伟大事蹟 —— 在和世界顶尖围棋高手李世石的五盘较量中，AlphaGo 以 4:1 击败李世石。

围棋被称为世界上最复杂的游戏。围棋标准 19 x 19 盘面的所有走法庞大到难以穷举，所需的计算能力堪称所有游戏之最。能打败顶尖棋手的西洋棋 AI Deep Blue 早在 1996 年就被开发出来，但 2016 年之前应该鲜少有人相信有电脑 AI 可以击败职业围棋手。

那麽 RL 到底怎麽被用来训练 AlphaGo，让他能够超越人类？

AlphaGo

(Silver et al., 2016) Mastering the game of Go with deep neural networks and tree search

围棋游戏在 RL 框架里，大概是这样定义：

• Agent：AlphaGo AI。
• Environment：围棋游戏。
• State：盘面上的棋子摆放、轮到谁下等等。
• Action：下一手的落点。
• Reward：最终获胜与否。

AlphaGo model 主要包含三个元件：

1. Policy network：根据盘面预测下一个落点的机率。
2. Value network：根据盘面预测最终获胜的机率，类似预测盘面对两方的优劣。
3. Monte Carlo tree search (MCTS)：类似在脑中计算後面几步棋，根据几步之後的结果估计现在各个落点的优劣。

—— AlphaGo 中的元件。

AlphaGo 能下棋之前，会先用现成 data 和 RL 训练好 policy network 和 value network。接着下棋时，在每一步会需要模拟计算各种落点下面几步棋的进行，寻找胜率最高的落点。因为行棋可能性太多，会利用 MCTS 结合训练好的 policy network 和 value network 来优化搜寻过程。

接着来分别介绍一下这些元件。

Policy Network

Policy network 给定 input state，会 output 每个 action 的机率。

AlphaGo 中包含三种 policy network：

1. Supervised learning (SL) policy network
2. Reinforcement learning (RL) policy network
3. Rollout policy network

在 RL 之前，我们会先用 supervised learning 训练出一个还不错的 SL policy network。方法很简单，只要有棋谱，每一步都是一个 state-action pair，我们就从这些 data 来训练。AlphaGo 的 SL policy network 训练在 3 千万笔这样的 data 上，训练出来的 model 有 57% 预测准确率。

但是 supervised learning 还不够。用这样的方法训练，结果再好也不过跟人类能打罢了，因为终究是在模仿人类。因此我们在 SL policy network 之上用 RL 训练，让他自己不断尝试不同走法，这样才有机会真正走出人类没想过的好棋并打败人类。

因此 Alphago 中的 RL policy network 和 SL policy network 架构相同，不过藉由 RL 继续训练下去。方法是让这个 policy network 和另一个不同的 policy network 对下，赢的话 reward 是 +1，输的话是 -1，最後将 reward 返回到 network 里做 gradient descent。最後训练出的 RL policy network 对上 SL policy network 的胜率有 80%，大有进步。

最後是 rollout policy network，也是用 SL 训练，差别是 network 较小，evaluation 比较快，但精准度较低。这个 policy network 目的是让 MCTS 里的 simulation 更快，後面会提到。

Value Network

除了 policy network，我们还需要一个预测胜率的 value network。Input 是 state，output 是胜率值。

这个 network 也可以用 supervised learning 训练，data 是历史对局中的 state-outcome pair，loss 是 mean squared error (MSE)。

Monte Carlo Tree Search (MCTS)

有了 policy 和 value network，最後我们用 Monte Carlo tree search (MCTS) 结合这些 network 做 planning，决定游戏进行时的下一步。

所谓 tree search 就是将计算过程用树状结构表示，由 root 往下展开後，根据 leaf node 的游戏结果，回馈给中途每个 node 来计算胜率。

以围棋来说，用穷举法来计算会让整个 tree 太大，因此不可行。於是我们利用 Monte Carlo tree search 来减小 search space，过程大致包含四步骤：

—— MCTS 四步骤示意图。

1. Selection：从 root 开始，藉由 policy network 预测下一步落点的机率，来选择要继续往下面哪一步计算。选择中还要考量每个 state-action pair 出现过的次数，尽量避免重复走同一条路，以平衡 exploration 和 exploitation。重复这个步骤直到树的深度达到 max depth L。
2. Expansion：到达 max depth 後的 leaf node ，我们想要估计这个 node 的胜算。首先从 往下 expand 一层。
3. Evaluation：每个 的 child node 会开始 rollout，也就是跟着 rollout policy network 预测的 action 开始往下走一阵子，取得 outcome z。最後 child node 的胜算会是 value network 对这个 node 预测的胜率和 z 的结合。
4. Backup： 会根据每个 child node 的胜率更新自己的胜率，并往回 backup，让从 root 到 的每个 node 都更新胜率。

最後 search 完有了每个 node 的胜率，AlphaGo 会选择往胜率最高的地方走。

整个过程其实就是人类在下围棋时，会考量各个选点往下走的变化图，并根据变化结果决定每个选点的胜率，最後走在胜率最大的地方。

看到这里应该会意识到，policy network 和 value network 好像都可以用来预测下一手，但他们并没有认真考虑後面变化之後带来的影响。MCTS 才是寻找最大胜率落点的过程，而 policy network 和 value network 的预测值是用来协助减小 search space 和估计胜率。

Results

AlphaGo 和一些其他围棋 AI 对战的胜率是 99.8%，和人类职业棋手 Fan Hui 对战结果是 5:0。这也是第一次围棋 AI 打败人类职业棋手。

除了拿来对战，AlphaGo model 还可以用来分析对战过程中的胜率和变化图，提供人类棋手参考学习。

—— AlphaGo 可以用来分析棋局。

AlphaGoZero

(Silver et al., 2017) Mastering the game of Go without human knowledge

其实 RL 在 AlphaGo 中不算功劳巨大。AlphaGo 的训练过程仰赖许多人类棋局的 data，包括 SL policy network 和 value network 的训练。

直到 AlphaGoZero 的出现，RL 的真实力才真的让人震惊。他做出了以下改变：

• 训练过程中没有使用 human data，纯粹依靠 RL。
• Input feature 只包含棋盘上的黑白子。
• 没有 policy network 和 value network 之分，只用了一个 network。
• 使用了更简单的 tree search 方法，不需要 rollout。

这个 single network 接收 input state 预测两个值：下一手的机率，和下一手的价值，其实就是 policy network 和 value network 的结合。训练过程一开始随机 initialize network，接着让自己和自己对战，并完全用胜负 reward 来进行 RL 训练。

虽然一开始预测胜负的准确度不及 supervised learning，但随着训练越来越久，准确度最终超越了 supervised learning，胜率也超越了先前的 AlphaGo。

—— AlphaGoZero 倒吃甘蔗，最终训练成果能超越人类更多。

AlphaGoZero 的训练过程有点像经历了几千年人类下围棋的历史，训练中途可以看到他已经自己学会了一些定石（局部双方的固定走法），甚至自己发明新的定石。现在的 AlphaGoZero 应该是没有 AI 存在的话，很多年以後人类围棋的发展结果吧。

结语

身为时常关注围棋界的棋迷，AI 带来的改变还是满深刻的。有些定石被 AI 的新定石淘汰，也有些被淘汰的定石被 AI 肯定而回归。下完棋後的覆盘讲解，大部分的老师都会用 AI 分析胜率和最佳选点，彷佛 AI 成了正确解答。透过和 AI 下棋，一些原本被环境资源限制的职业棋手，也能藉由和更强的对手练习而更接近世界级的水平。

虽然 AI 很强，也不可否认他为围棋的学习提供了方便的管道，但我觉得这般如同解答本的 AI 出现，也不尽然全是好处。学生不会写可能选择直接看答案，甚至为了让考试更高分选择背答案。热络的讨论会被 AI 选点取代，有趣的想法会被胜率驳回。那麽下围棋会不会有一天只剩胜负了呢？

无论如何，以围棋的复杂度来说，AlphaGo 和 AlphaGoZero 的出现证明了 RL 的巨大学习潜能。但这种学习能力是不是能被应用在游戏与机器人界以外的应用领域，仍然是 RL 发展的巨大挑战。

Checkpoint

• AlphaGo 中，policy network 和 value network 分别在 MCTS 中的什麽步骤中使用？为什麽他们能帮助 MCTS 减小 search space？
• MCTS 中，为什麽 rollout 时要使用不太准确但计算更快的 rollout policy network？

参考资料

1. A Simple Alpha(Go) Zero Tutorial
2. AlphaGo Zero Explained In One Diagram
3. AlphaGo: How it works technically?
4. (Video) Monte Carlo Tree Search (MCTS) Tutorial