|
【阅读时间】21min - 24min 10999字 在之前的详解：深入浅出看懂AlphaGo中，详细定义的DeepMind团队定义围棋问题的结构，并且深入解读了AlphaGo1.0每下一步都发生了什么事，就在最近，AlphaGo Zero横空出世。个人观点是，如果你看了之前的文章，你就会觉得这是一个水到渠成的事情 另，如果你只对这个事件感兴趣的，而不想了解论文和技术细节，链接奉上，欢迎跳过到最后评论和总结部分（但这部分网上的大牛太多了，知乎答案内最高票对结合围棋的分析很漂亮！建议阅读） 上限置信区间算法（UCT），一种博弈树搜索算法，是AlphaGo中一个重要组成部分：MCTS搜索算法中的核心 法国南巴黎大学的数学家西尔万·热利(SylvainGelly)与巴黎技术学校的王毅早(YizaoWang，音译)将UCT集成到一个他们称之为MoGo的程序中。该程序的胜率竟然比先前最先进的蒙特卡罗扩展算法几乎高出了一倍。 2007年春季，MoGo在大棋盘比赛中也击败了实力稍弱的业余棋手，充分展示了能力。科奇什（UCT算法发明者）预言，10年以后，计算机就能攻克最后的壁垒，终结人类职业棋手对围棋的统治。今年是2017年，AlphaGo系列横空出世。10年，总有着天才的人具有先知般的远见。详见UTC算法 【小发现】看完论文发现，这篇文章的接受时间是2017年4月7号，审核完成时间是2017年9月13号，而在乌镇对阵柯洁（2017年5月23号）用的可能是AlphaGo Master（这里没法证据来证明到底是AlphaGo Zero还是AlphaGo Master）。这个团队也是无情啊，人类再一次感觉被耍了，根据Elo得分，Deepmind团队可能在赛前就透露过吧，即使是Master也有4858分啊，对于一个棋手来说，我感受到的是风萧萧兮易水寒决绝的背影。为柯洁的勇气打Call，当真围棋第一人，天下无双 论文正文内容详细解析先上干货论文：Mastering the Game of Go without Human Knowledge ，之后会主要以翻译论文为主，在语言上尽量易懂，避免翻译腔 AlphaGo Zero，从本质上来说完全不同于打败樊麾和李世石的版本
AlphaGo Zero 的强化学习问题描述在开始之前，必须再过一遍如何符号化的定义一个围棋问题 围棋问题，棋盘 有以上定义，我们就把围棋问题转化为。
简而言之
网络结构新的网络中，使用了一个参数为 θ （需要通过训练来不断调整） 的深度神经网络fθ
改进的强化学习算法自对弈强化学习算法（什么是强化学习，非常建议先看看强化学习的一些基本思想和步骤，有利于理解下面策略、价值的概念，推荐系列笔记） 在每一个状态 ⃗s ，利用深度神经网络 fθ 预测作为参照执行MCTS搜索（蒙特卡洛搜索树算法），MCTS搜索的输出是每一个状态下在不同位置对应的概率 π （注意这里是一个向量，里面的值是MCTS搜索得出的概率值），一种策略，从人类的眼光来看，就是看到现在局面，选择下在每个不同的落子的点的概率。如下面公式的例子，下在(1,3)位置的概率是 MCTS搜索得出的落子概率比 fθ 输出的仅使用神经网络输出的落子概率 p 更强，因此，MCTS可以被视为一个强力的策略改善（policy improvement）过程 使用基于MCTS提升后的策略（policy）来进行落子，然后用自对弈最终对局的胜者 z 作为价值（Value），作为一个强力的策略评估（policy evaluation）过程 并用上述的规则，完成一个通用策略迭代算法去更新神经网络的参数 θ ，使得神经网络输出的落子概率和评估值，即 fθ(⃗s)=(p,v) 更加贴近能把这盘棋局赢下的落子方式（使用不断提升的MCST搜索落子策略π 和自对弈的胜者 z 作为调整依据）。并且，在下轮迭代中使用新的参数来进行自对弈 在这里补充强化学习的通用策略迭代（Generalized Policy Iteration）方法
我们知道，最初的蒙特卡洛树搜索算法是使用随机来进行模拟，在AlphaGo1.0中使用局面函数辅助策略函数作为落子的参考进行模拟。在最新的模型中，蒙特卡洛搜索树使用神经网络 fθ 的输出来作为落子的参考（详见下图Figure 2） 每一条边 (⃗s,⃗a) （每个状态下的落子选择）保存的是三个值：先验概率 P(⃗s,⃗a)，访问次数 N(⃗s,⃗a)，行动价值 Q(⃗s,⃗a)。 每次模拟（模拟一盘棋，直到分出胜负）从根状态开始，每次落子最大化上限置信区间 Q(⃗s,⃗a) U(⃗s,⃗a) 其中 U(⃗s,⃗a)∝P(⃗s,⃗a)1 N(⃗s,⃗a) 直到遇到叶子节点 s′ 叶子节点（终局）只会被产生一次用于产生先验概率和评估值，符号表示即 fθ(s′)=(P(s′,⋅),V(s′)) 模拟过程中遍历每条边 (⃗s,⃗a) 时更新记录的统计数据。访问次数加一 N(⃗s,⃗a) =1；更新行动价值为整个模拟过程的平均值，即 Q(⃗s,⃗a)=1N(⃗s,⃗a)Σ⃗s′|⃗s,⃗a⇒⃗s′V(⃗s′) ，⃗s′|⃗s,⃗a⇒⃗s′ 表示在模拟过程中从 ⃗s 走到 ⃗s′的所有落子行动 ⃗a 
MCTS搜索可以看成一个自对弈过程中决定每一步如何下的依据，根据神经网络的参数 θ 和根的状态 ⃗s 去计算每个状态下落子位置的先验概率，记为 π=αθ(⃗s) ，幂指数正比于访问次数 π⃗a∝N(⃗s,⃗a)1/τ，τ 是温度常数 训练步骤总结使用MCTS下每一步棋，进行自对弈，强化学习算法（必须了解通用策略迭代的基本方法）的迭代过程中训练神经网络
AlphaGo Zero训练过程中的经验最开始，使用完全的随机落子训练持续了大概3天。训练过程中，产生490万场自对弈，每次MCTS大约1600次模拟，每一步使用的时间0.4秒。使用了2048个位置的70万个Mini-Batches来进行训练。 训练结果如下，图3 
在24小时的学习后，无人工因素的强化学习方案就打败了通过模仿人类棋谱的监督学习方法 为了分别评估结构和算法对结构的影响，得到了，下图4 
AlphaGo Zero学到的知识在训练过程中，AlphaGo Zero可以一步步的学习到一些特殊的围棋技巧（定式），如图5 
AlphaGo Zero的最终实力之后，最终的AlphaGo Zero 使用40个残差模块，训练接近40天。在训练过程中，产生了2900万盘的自对弈棋谱，使用了310万个Mini-Batches来训练神经网络，每一个Mini-Batch包含了2048个不同的状态。（覆盖的状态数是63亿（1010），但和围棋的解空间 2361≈10108 相比真的很小，也从侧面反映出，围棋中大部分选择都是冗余的。在一个棋盘局面下，根据先验概率，估计只有15-20种下法是值得考虑的） 被评测不同版本使用计算力的情况，AlphaGo Zero和AlphaGo Master被部署到有4个TPUs的单机上运行（主要用于做模型的输出预测Inference和MCTS搜索），AlphaGo Fan（打败樊麾版本）和AlphaGo Lee（打败李世乭版本） 分布式部署到机器群里，总计有176GPUs和48GPUs（Goolge真有钱）。还加入了raw network，它是每一步的仅仅使用训练好的深度学习神经网的输出 pa 为依据选择最大概率点来落子，不使用MCTS搜索（Raw Network裸用深度神经网络的输出已经十分强大，甚至已经接近了AlphaGo Fan） 下图6展示不同种AlphaGo版本的棋力情况 
最终，AlphaGo Zero 与 AlphaGo Master的对战比分为89：11，对局中限制一场比赛在2小时之内（新闻中的零封是对下赢李世乭的AlphaGo Lee） 论文附录内容我们知道，Nature上的文章一般都是很强的可读性和严谨性，每一篇文章的正文可能只有4-5页，但是附录一般会远长于正文。基本所有你的技术细节疑惑都可以在其中找到结果，这里值列举一些我自己比较感兴趣的点，如果你是专业人士，甚至想复现AlphaGo Zero，读原文更好更精确 围棋领域先验知识AlphaGo Zero最主要的贡献是证明了没有人类的先验知识机器也可以在性能上超越人类。为了阐释清楚这种贡献来自于何处，我们列举一些AlphaGo Zero使用到的知识，无论是训练过工程中的还是MCTS搜索中的。如果你想把AlphaGo Zero的思路应用的到解决其他游戏问题上，这些内容可能需要被替换 围棋基本规则无论实在MCTS搜索中的模拟还是自对弈的过程，都依赖游戏最终的胜负规则，并且在落子过程中，根据规则还可以排除一部分不可以落子的点（比如已经落子的点，无法确认在AlphaGo Zero还有气为零的点不能下这个规则，因为不记录气的信息了。但可以写一个函数来判断当前局面 ⃗s 下下一步所有可能的落子点，不一定非得计算这个信息，这个过程可以完全多线程） Tromp-Taylor规则在AlphaGo Zero中使用的是PSK（Positional Superko）禁全同规则（中国，韩国及日本使用），只要这一手（不包括跳过）会导致再现之前的局面，就禁止。 旋转与镜面对于围棋来说，几个状态 ⃗s 在经过旋转或反射后是完全相同的，这种规律可以用来优化训练数据和MCTS搜索中的子树替换策略。并且因为贴目（黑棋先下优势贴目7目半）规则存在，不同状态 ⃗s 换颜色也是相同的。这个规则可以用来使用当前下子的棋手的角度来表示棋盘 除了以上的三个规则，AlphaGo Zero 没有使用其他任何先验知识，它仅仅使用深度神经网络对叶子节点进行评估并选择落子位置。它没有使用任何Rollout Policy(这里指的应该是AlphaGo之前版本的快速走子策略)或者树形规则，MCTS搜索也没有使用其他的标准启发式规则或者先验常识规则去进行增强 整个算法从随机初始化神经网络参数开始。网络结构和超参数选择 见下一节。MCTS搜索的超参数 cpuct 由高斯过程优化决定，为了优化自对弈的性能，使用了一个神经网络进行预训练。对于一个大规模网络的训练过程（40个残差模块，40天），使用一个小规模网络（20个残差模块，3天）来反复优化MCTS搜索的超参数 cpuct。整个训练过程没有任何人工干预 自对弈训练工作流AlphaGo Zero的工作流由三个模块构成，可以异步多线程进行：
优化参数每一个神经网络 fθi 在64个GPU工作节点和19个CPU参数服务器上进行优化。 每个工作节点的批次（Batch）大小是32，每一个mini-batch大小为2048。每一个 mini-batch 的数据从最近50万盘的自对弈棋谱的状态中联合随机采样。 神经网络权重更新使用带有动量（momentum）和学习率退火（learning rate annealing）的随机梯度下降法（SGD），损失函数见公式1 学习率退火比率见下表
动量参数设置为0.9 方差项和交叉项的权重相同，原因是奖励值被归一化到 r∈[−1, 1] L2正则化系数设置为 c=10−4 优化过程每1000个训练步数执行一次，并使用这个新模型来生成下一个Batch的自对弈棋谱 评估器为了保证生成数据的质量（不至于棋力反而下降），在使用新的神经网络去生成自对弈棋谱前，用现有的最好网络 fθ∗ 来对它进行评估 【评估神经网络 fθi 的方法】使用 fθi 进行MCTS搜索得出的 αθi 的性能（得到 αθi 的MCTS搜索过程中使用 fθi 去估计叶子节点的位置和先验概率，详见MCTS搜索这一节） 每一个评估由400盘对局组成，MCTS搜索使用1600次模拟，将温度参数设为无穷小 τ⇒0（目的是为了使用最多访问次数的落子下法去下，追求最强的棋力），如果新的选手 αθi 在这400盘中胜率大于55%，将这个选手更新为最佳选手 αθ∗ ，用来产生下一轮的自对弈棋谱，并且设为下一轮的比较对象 自对弈通过评估器，现在已经有一个当前的最好棋手 αθ∗，使用它来产生数据。每次迭代中， αθ∗ 自对弈25000盘，其中每一步MCTS搜索模拟1600次（模拟的每次落子大约0.4秒，这里的一次表示的就是MCTS搜索中走到叶子节点，得出胜负结果） 前30步，温度 τ=1，与MCTS搜索中的访问次数成正比，目的是保证前30步下法的多样性。在之后的棋局中，温度设为无穷小。并在先验概率中加入狄利克雷噪声 P(⃗s,⃗a)=(1−ϵ)p⃗a ϵη⃗a ，其中 η∼Dir(0.03) 且 ϵ=0.25。这个噪声保证所有的落子可能都会被尝试，但也可能下出臭棋 投降阈值 vrerign 自动设为错误正类率（如果AlphaGo没有投降可以赢的比例）小于5%，为了测量错误正类(false positives)，在10%的自对弈中关闭投降机制，必须下完 监督学习为了进行对比，我们还使用监督学习训练了一个参数为 θSL 神经网络。神经网络的结构和AlphaGo Zero相同。数据集 (⃗s,π,z) 随机采样自KGS数据集，人类的落子策略位置即设置 πa=1 。使用同样的超参数和损失函数，但是平方误差的系数为0.01，学习率图参照上表的第二列。其他超参数和上一节相同 比AlphaGo1.0z中使用两种网络，使用这种结构的网络，可以有效的防止过拟合。并且实验也证明这个网络结构的的效果要好于之前的网络 MCTS搜索算法这一部分详解的AlphaGo Zero的算法核心示意图Figure2 AlphaGo Zero使用的是比AlphaGo1.0中更简单的异步策略价值MCTS搜索算法（APV-MCTS）的变种 搜索树中的节点 ⃗s 包含一条边 (⃗s,⃗a) 对应所有可能的落子 ⃗a∈A(⃗s) ，每一条边中存储一个数据，包含下列公式的四个值
多线程（并行）执行多次模拟，每一次迭代过程先重复执行1600次Figure 2中的前3个步骤，计算出一个 π ，根据这个向量下现在的这一步棋 Selcet - Figure2aMCTS中的选择步骤和之前的版本相似，详见AlphaGo之前的详解文章，这篇博文详细通俗的解读了这个过程。概括来说，假设 其中计算 U(⃗st,⃗a) 使用PUCT算法的变体 U(⃗s,⃗a)=cpuctP(⃗s,⃗a)√Σ⃗bN(⃗s,⃗b)1 N(⃗s,⃗a)其中 cpuct 是一个常数。这种搜索策略落子选择最开始更趋向于高先验概率和低访问次数的，但逐渐的会更加趋向于选择有着更高行动价值的落子 cpuct 使用贝叶斯高斯过程优化来确定 Expand and evaluate - Figure 2b将叶子节点 ⃗sL 加到队列中等待输入至神经网络进行评估， fθ(di(⃗sL))=(di(p),v) ，其中 di 表示一个1至8的随机数来表示双方向镜面和旋转（从8个不同的方向进行评估，如下图所示，围棋棋型在很多情况如果从视觉角度来提取特征来说是同一个节点，极大的缩小了搜索空间）  队列中8个不同位置组成一个大小为8的mini-batch输入到神经网络中进行评估。整个MCTS搜索线程被锁死直到评估过程完成（这个锁死是保证并行运算间同步）。叶子节点被展开(Expand)，每一条边 (⃗sL,⃗a)被初始化为 N(⃗sL,⃗a)=0;W(⃗sL,⃗a)=0;Q(⃗sL,⃗a)=0P(⃗sL,⃗a)=pa这里的 pa 由将 ⃗s 输入神经网络得出 p （包括所有落子可能的概率值 pa），然后将神经网络的输出值 v 传回（backed up） Backup - Figure 2c沿着扩展到叶子节点的路线回溯将边的统计数据更新（如下列公式所示） N(⃗st,⃗at)=N(⃗st,⃗at) 1W(⃗st,⃗at)=W(⃗st,⃗at) vQ(⃗st,⃗at)=W(⃗st,⃗at)N(⃗st,⃗at)
使用虚拟损失（virtual loss）确保每一个线程评估不同的节点。实现方法概括为把其他节点减去一个很大的值，避免其他搜索进程走相同的路，详见 Play - Figure 2d完成MCTS搜索（并行重复1-3步1600次，花费0.4s）后，AlphaGo Zero才从 ⃗s0 状态下走出第一步 ⃗a0，与访问次数成幂指数比例 π(⃗a|⃗s0)=N(⃗s0,a)1/τΣ⃗bN(⃗s0,⃗b)1/τ其中 τ 是一个温度常数用来控制探索等级（level of exploration）。它是热力学玻尔兹曼分布的一种变形。温度较高的时候，分布更加均匀（走子多样性强）；温度降低的时候，分布更加尖锐（多样性弱，追求最强棋力） 搜索树会在接下来的自对弈走子中复用，如果孩子节点和落子的位置吻合，它就成为新的根节点，保留子树的所有统计数据，同时丢弃其他的树。如果根的评价值和它最好孩子的评价值都低于 vresign AlphaGo Zero就认输 MCTS搜索总结与之前的版本的MCTS相比，AlphaGo Zero最大的不同是没有使用走子网络（Rollout），而是使用一个整合的深度神经网络；叶子节点总会被扩展，而不是动态扩展；每一次MCTS搜索线程需要等待神经网络的评估，之前的版本性能评估（evaluate）和返回（backup）是异步的；没有树形策略 至于很重要的一个关键点：每一次模拟的中的叶子节点 【个人分析】是由时间来决定，根据论文提到的数据，0.4秒执行1600次模拟，多线程模拟，在时限内能走到的深度有多深就是这个叶子节点。可以类比为AlphaGo 1.0中的局面函数（用来判断某个局面下的胜率的），也就是说不用模拟到终盘，在叶子节点的状态下，使用深度神经网的输出 v 来判断现在落子的棋手的胜率 网络结构网络输入数据输入数据的维度 从状态 ⃗s 开始，记录了倒退回去的15步，双方棋手交替。最后一个  【个人理解】为了更加直观的解释，如果是上面的局部棋盘状态 ⃗s，接下里一步是黑棋落子，走了4步，那么输入数据是什么样的呢？ X2=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝⋮⋮⋯01⋯⋯10⋯⋮⋮⎞⎟ ⎟ ⎟ ⎟ ⎟⎠Y2=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝⋮⋮⋯10⋯⋯01⋯⋮⋮⎞⎟ ⎟ ⎟ ⎟ ⎟⎠X1=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝⋮⋮⋯00⋯⋯10⋯⋮⋮⎞⎟ ⎟ ⎟ ⎟ ⎟⎠Y1=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝⋮⋮⋯00⋯⋯01⋯⋮⋮⎞⎟ ⎟ ⎟ ⎟ ⎟⎠C=⎛⎜ ⎜ ⎜ ⎜ ⎜⎝⋮⋮⋯10⋯⋯01⋯⋮⋮⎞⎟ ⎟ ⎟ ⎟ ⎟⎠同理，如果有8步的话，也就是16个对应的 X 和 Y 加一个 C 来表示现在的棋盘状态（注意，这里面包含的历史状态）。这里的数据类型是Boolean，非常高效，并且表达的信息也足够 至于使用八步的原因。个人理解，一方面是为了避免循环劫，另一方面，选择八步也可能是性能和效果权衡的结果（从感知上来说当然信息记录的越多神经网络越强，奥卡姆剃刀定理告诉我们，简单即有效，一味的追求复杂，并不是解决问题的最佳途径） 深度神经网结构整个残差塔使用单独的卷机模块组成，其中包含了19或39个残差模块，详细结构参数如下图所示  过了深度卷积神经网络后接策略输出与评估值输出，详细结构参数如下图所示  数据集图5更多细节
Figure 5a中每种定式出现的频率图
Figure 5b中每种定式出现的频率图
总结与随想AlphaGo Zero = 启发式搜索 强化学习 深度神经网络，你中有我，我中有你，互相对抗，不断自我进化。使用深度神经网络的训练作为策略改善，蒙特卡洛搜索树作为策略评价的强化学习算法 之后提出一些我在看论文时带着的问题，最后给出我仔细看完每一行论文后得出的回答，如有错误，请批评指正！ 问题与个人答案训练好的Alpha Zero在真实对弈时，在面对一个局面时如何决定下在哪个位置？评估器的落子过程即最终对弈时的落子过程（自对弈中的落子就是真实最终对局时的落子方式）：使用神经网络的输出 p 作为先验概率进行MCTS搜索，每步1600次（最后应用的版本可能和每一步的给的时间有关）模拟，前30步采样落子，剩下棋局使用最多访问次数来落子，得到 π ，然后选择落子策略中最大的一个位置落子 AlphaGo Zero的MCTS搜索算法和和上个版本的有些什么区别？最原始MCTS解析，AlphaGo Lee加上策略函数和局面函数改进后的MCTS解析 对于AlphaGo Zero来说
AlphaGo Zero 中的策略迭代法是如何工作的？策略迭代法（Policy Iteration）是强化学习中的一种算法，简单来说：以某种策略（ π0 ）开始，计算当前策略下的价值函数（ vπ0 ）；然后利用这个价值函数，找到更好的策略（Evaluate和Improve）；接下来再用这个更好的策略继续前行，更新价值函数……这样经过若干轮的计算，如果一切顺利，我们的策略会收敛到最优的策略（ π∗ ），问题也就得到了解答。 π0E→vπ0I→π1E→vπ1I→π2E→⋯I→π∗E→v∗对于AlphaGo Zero来说，详细可见论文，简单总结如下
总的来说，有点像一个嵌套过程，MCST算法可以用来解决围棋问题，这个深度神经网络也可以用来解决围棋问题，而AlphaGo Zero将两者融合，你中有我，我中有你，不断对抗，不对自我进化 AlphaGo Zero 最精彩的部分哪部分？l=(z−v)2−πTlog(p) c∥θ∥2毫无悬念的，我会选择这个漂亮的公式，看懂公式每一项的来历，即产生的过程，就读懂了AlphaGo Zero。这个公式你中有我，我中有你，这是一个完美的对抗，完美的自我进化 第二我觉得很精彩的点子是将深度神经网络作为一个模块嵌入到了强化学习的策略迭代法中。最关键的是，收敛速度快，效果好，解决各种复杂的局面（比如一个关于围棋棋盘的观看角度可以从八个方向来看的细节处理的很好，又如神经网络的输入状态选择了使用历史八步） 随想和评论
随着AlphaGo Zero的归隐，DeepMind已经正式转移精力到其他的任务上了。期待这个天才的团队还能搞出什么大新闻！ 对于围棋这项运动的影响可能是：以后的学围棋手段会发生变化，毕竟世界上能复现AlphaGo Zero的绝对很多，那么AlphaGo Zero的实力那就是棋神的感觉，向AlphaGo Zero直接学习不是更加高效嘛？另，围棋受到的关注也应该涨了一波，是利好 感觉强化学习会越来越热，对于和环境交互这个领域，强化学习更加贴近于人类做决策的学习方式。个人预测，强化学习会在未来会有更多进展！AlphaGo Zero 可能仅仅是一个开头 以上！鞠躬！ |
|
|
