-
-
手机阅读
前言：在今日Google的Alpha Go和李世石的比赛中，耗时4小时击败了这位当今最强人类棋手。
这两天大家都纷纷在讨论这个人工智能的新星，大家都很好奇这个人工智能系统到底是如何工作的呢？要回答这个问题，我们先来从最基础的人工智能下棋算法说起。
传统的下棋人工智能算法
平时，我们形容一个人下象棋下的好，我们可能会说“他脑子很会算，能算到5步以后呢”。这个意思就是说，这个人在选择下一步走法的时候，他评估每一步走法，会往后继续多想几步——“如果我这么走，对方会怎么下呢？那对方这么下之后，那个时候我可能选择的最佳走法又是什么呢？”以此类推。对人类来说，他在大脑中会进行多次推演，来选择最好的走法路径。所以能够想到5步之后，已经是很厉害的人类了！但这种思维方式，恰恰是计算机特别擅长的。MinMax算法就是一个这样的算法，成功应用在很多棋类AI中，基本思想和之后要讲的AlphaGo的MCTS算法也有相通之处。
图：MinMax算法示例，来自于wikipedia
圆形的节点表示“你”面对的局面，而方块的节点表示对手面对的局面。这里是4层两个回合的搜索树。
- 我们从最下层第4层开始，这一层是叶子节点，不再展开，我们使用“估值函数”（Evaluation Function）评估局面的“好坏”，为每一种局面打分，如图上节点上的数字所示。在中国象棋中，比如“估值函数”可以考虑的因素比如中国象棋中车的个数、卒是否过河、是否有空头跑架在对方的帅上方等等。分数越高，对你越有利。一个正无穷的分数，代表游戏结束并且你获得胜利，反之亦然。
- 接着第3层对手从这些局面中选择他最好的局面（也就是你最坏的局面），也就是得分最少的局面（因为计算得分是从你的角度计算的）。
- 接着你在第2层选择得分最多的局面。
- 接着对手在第1层选择得分最少的局面。
- 最后你在第0层选择得分最多的局面，也就是得分为-7的节点。
这样的树形结构成为搜索树，也称为搜索空间，其中的每一个节点代表了棋局中的一个可能性。可以看到，这样的搜索空间的规模是跟这颗树的层数（也称深度），以及每个节点可以衍生出来的子节点的个数（称之为Branching Factor）。比如上图就是一个深度为4，Branching Factor为2的搜索树，其搜索空间的总数为2 + 4 + 6 + 9 = 21。
对于国际象棋来说，Branching Factor为35，即对于一个局面平均有35种不同的合法走法。对于围棋来说，Branching Factor是250。（https://en.wikipedia.org/wiki/Branching_factor）因此在真实的棋类比赛中，搜索空间是巨大的。从根节点枚举出所有的子节点，再逐一进行考虑是绝对不现实的，再快的计算机也无法完成这一浩大的计算。在MinMax中会采用一种叫做Alpha-beta的剪枝算法，通过简单的逻辑让系统在某些分支上停止展开，尽早避免把搜索时间花在肯定不会有好结果的分支上。
所以一个好的搜索策略，会应用更智能的剪枝算法，优先选择更有希望导致胜利的分支进行搜索。同时，一个准确的估值函数，能够正确的评估某个分支代表的局面的好坏，这样不用算到最后的决胜局，就可在较浅的深度通过估值函数来预估胜算。
为什么围棋这么难？
总结上文，一个好的棋类AI，需要结合高效的搜索策略和准确的估值函数。我们从这个角度来分析以下，为什么20年前AI就已经打败国际象棋的人类世界冠军，直到现在围棋AI才刚刚崭露头角呢？
其一，围棋棋盘是19x19，因此每一步可以选的合法走法远远大于象棋（刚刚也提到围棋的Branching Factor是250，象棋只有35）。因此围棋搜索空间相对于国际象棋来说大得多
其二，围棋的估值函数很难设计。象棋里面你尚能用简单的统计棋子个数来推断，围棋棋局千变万化，可能看似风平浪静其实暗藏杀机。
这两个主要原因导致了围棋AI上面一直很难有大的进展。
AlphaGo怎么这次怎么做到的？
那这次出战的AlphaGo，又是有什么独门绝技呢？类似之前提到的MinMax搜索框架，AlphaGo（以及现在很多其他的围棋AI），在决定下一步棋怎么走的时候，采用了MCTS（Monte Carlo Tree Search）的搜索框架。
大致思想可类比MinMax算法：MCTS算法，对于给定的当根前节点，通过计算机模拟推演以当前根节点出发的各种可能的走法，配合高效的“剪枝”算法来控制搜索空间大小，并用演算到最后一步的结果来反过来影响当前跟节点下一步棋的选择。之前也提到过围棋相对于传统棋类AI的设计难点：1）可能的走法太多（即Branching Factor较大）导致搜索空间非常大 2）没有一个好的估值函数对进行中的围棋棋局计算一个静态得分。于是MCTS针对这两个问题提出解决方案：搜索空间更大我们就采取比Alpha-beta剪枝更激进的剪枝策略，只把有限的计算资源留给最最有希望的走法（后面会提到的Selection、Expansion）；对于中间棋局好坏很难估计，那我们就一路模拟到最后分出胜负为止（后面会提到的Simulation）！
MCTS算法是一个多轮迭代算法，每一轮迭代都会以此经历四个阶段：Selection，Expansion，Simulation和Back Propagation。下图展示了MCTS的某一时刻搜索空间的情形，当前有有限个子节点（而不是所有的可能性组成的全搜索空间）正在算法的搜索范围之内。
图注：MCTS搜索策略每一轮迭代的四个步骤
这四个步骤分别为：
1) Selection：根据现有的搜索空间，选择一个“最最需要展开”的子节点，比如图中Selection步骤当中，沿着粗线一路走到底的最下方的叶子节点。这个节点被选中，意味着当前状态下，系统认为沿着这个节点的这条路径，最有可能导致胜利
2) Expansion：对于上面被选中的节点，从它的子节点中挑选出一个最有希望的子节点，展开之（即加入到当前搜索空间中）
3) Simulation：从刚刚展开的这个节点，继续往下模拟(也称Rollout)，直到分出胜负。当然这个往下模拟采用了另一套搜索策略，由于在这个阶段搜索深度需要达到最终分出胜负为止，所以会采用更加简单的搜索策略，以保证在有限时间内能够搜索到决胜节点。
4) Back Propagation：Simulation阶段已经搜索到最终的决胜节点。那么根据这个Simulation的最终胜负，我们会反过来更新刚刚的选择和展开的节点所在的路径。比如Simulation最后结果是我方胜，那么说明刚刚导致这个结果的所有每一步（图中粗线所经过的所有节点），都是需要表扬和肯定的。那么具体来说，会更新这些节点所对应的得分，保证在下一轮迭代的时候这些节点会有更大的几率被选中。反之，如果Simulation的最终结果是我方输，那么相应的节点都会受到惩罚，在下一轮迭代中会更小的几率被选中。
那么经历过足够多轮的迭代之后（或者限定时间耗尽），迭代结束。这时候，会从当前根节点的所有探索过的子节点中，选择一个得分最高的子节点，作为最终的下一步走法。
类比之前对于MinMax的分析，MCTS策略的好坏，也是建立在对子空间的选择之上的。因为不可能枚举所有的子空间，所以在Selection和Exapansion阶段，就必须有效的挑选出最有希望的走法进行Simulation。如果选择不好，则会导致浪费大量的时间在其实没有希望的子节点上，甚至是错过最终可能导致胜利的子节点。
AlphaGo用两个深度神经网络来帮助这个选择：Policy Network和Value Network。
其中Policy Network用来在Selection和Expansion阶段，衡量为每一个子节点打分，找出最有希望、最最需要预先展开的那个子节点。Policy Network网络的训练，是通过观察其他人类之间对弈的棋局来学习的，主要学习的目标是：“给定一个棋局，我接下来的一步应该怎么走”？（这是一个静态的过程，不用继续深入搜索更深层的子节点）为此，AlphaGo先读取KGS（一个网络围棋对战平台）上面近16万局共3000多万步的人类走法，通过Supervised Learning的方法，学习出来一个简单的SL Policy Network（同时还顺便训练出来Simulation阶段用来一路算到决胜局使用的Rollout Policy）。然后基于这个在人类棋局上学习出来的SL Policy Network, 使用强化学习（Reinforcement Learning）的方法通过自己跟自己对弈，来进一步优化Policy Network。这么做的原因，一个可能的原因是通过人类棋局学出来的SL Policy Network，受到了人类自身能力的局限性的影响（KGS棋局中包含了很多非专业棋手，实力层次不齐），学不出特别好的策略来。那不如在此基础上，自己跟自己打，在此过程中不断学习不断优化自己的策略。这就体现了计算机的优势，只要不断电，计算机可以不分昼夜不断自己跟自己下棋来磨练棋艺。RL Policy Network初始参数就是SL Policy Network的参数，但青出于蓝而胜于蓝，实验指出RL跟SL策略对弈，RL胜率超过80%。RL Policy Network也是最终应用在实际对战过程中MCTS Selection阶段的策略。
Value Network是AlphaGo第一次提出来的，它的作用是为给定的局面打分，类似于之前MinMax算法中的估值函数(这也是我们提到的围棋AI中的一个难点，之前的研究都回避的这方面的工作)。Value Network可以给某个特定的局面打分，这样，在MCTS做Selection的时候，可以更准确的评估一个子节点的优劣，避免不必要的Expansion和Rollout Simulation。
技术分析|AlphaGo赢了围棋 人工智能就此崛起？
（图注：AlphaGo使用了Policy Network和Value Network在实战中的MCTS搜索中高效选择搜索子空间。训练过程：通过KGS上的人类棋局（Human expert positions)来学习SL Policy Network和Rollout Network，然后基于SL Policy Network进行机器自我对弈（Self-play Positioning)学习出更优秀的RL Policy Network, 最后通过RL Policy Network学习出Value Network）
可以看到，AlphaGo通过当前很火的深度学习，更有效的模拟了人类的下棋策略。并且通过不间断的自我学习，不断优化这个策略。通过Policy Network和Value Network共同筛选出MCTS搜索中下一步最应该优先探索节点，AlphaGo才能在有限的计算资源下，更快速准确地找到最佳下一步。
人工智能就此崛起了么？
在跟李世石的首局比赛中获胜，是人工智能发展史上有一个里程碑。也有人猜测，首局比赛中李世石为了避免下出AlphaGo曾经学过的棋路，特意采取了一种比较冒险的下法，导致最终的失利。并且，作为一个人类棋手，李世石的决策还受到了心理因素的影响，而不像冷酷无情的AlphaGo，自始至终的每一轮的计算都是那么的理性和缜密。我们拭目以待接下来李世石会以什么样的策略继续迎战AlphaGo，就算AlphaGo最终还是输了，以它现在每天不吃不喝左右互搏的学习能力，假以时日赢过人类也也是非常有可能啊。
那么，如果被人工智能攻克下被称为人类最后的智力优势的围棋，是否预示着人工智能就此崛起了呢？我觉得完全不用那么悲观。
首先，在现有的计算机体系下，程序都是确定的（deterministic），即人类让程序怎么做，程序就只能这么做，绝对不会超过人类预先划定的范围（包括计算机产生的随机数，从某种程度上讲，也是确定的哦）。人工智能作为程序的一种类型，也遵循这么一个铁的定律。即使本文中讲到的RL Policy Network训练中的自我“学习”，也是在人类规定下进行的：迭代多少轮、每一轮怎么通过强化学习更新模型参数，都是由人一一事先确定的好的。这并不是人类意义上可以举一反三的自我学习。除非一种全新的体系诞生，让程序可以自行推理、自我复制、自我学习，在超出人类界定框架之外自我进化，并且恰巧进化出来要消灭人类这么一个念头，那才是我们真正需要担心的事情。
其次，虽然现在计算机在象棋、围棋、智力问答方面已经超过了人类，能够在微秒之内完成百万之间的乘法运算，能够存储下世界上所有图书馆里面的知识 —— 但是在某些方面，连3岁的人类小孩都不如。比如人类小孩能够轻易的认出妈妈和爸爸，能够通过观察大人关灯的动作就自己学习出来墙上的开关和屋顶的电灯存在着某种联系，这些看似事对于当今最强的人工智能算法，也无法做到。所以有一些任务，如果不能被很好的抽象成一个具体的步骤序列，那么计算机根本无能为力。
所以，距离真正的人工智能，还有很长的一段距离。距离战胜人类象棋冠军过去了20年，人类才刚刚造出来一个可以击败人类围棋冠军的AI，何足畏惧。
不过，这次Google的AlphaGo的意义仍是非比寻常的。1997年IBM的深蓝计算机在国际象棋上击败了当时的国际象棋世界冠军，2011年IBM的Watson系统在知识问答类竞赛Jeopardy!上击败了竞赛有史以来最聪明、知识最渊博的几位人类选手。今天，终于，轮到了Google的AlphaGo，在围棋上击败了人类世界冠军李世石。虽然这只是5轮比赛的首轮，最终鹿死谁手尚未可知，但无疑今天AlphaGo的首战告捷已经成为了人工智能历史上又一个值得被载入史册的里程碑！
更重要的是，借助AlphaGo研究这个契机，一些深度学习方面的算法得以进一步被深入研究，并且可以平行借鉴到其他领域中去。如同IBM闭门5年造出来Watson Deep QA系统，在Jepardy!大赛上击败人类选手之后，除了为IBM带来了巨大声誉，也让IBM将相关技术应用到金融、医疗等领域。又如同前段时间发现引力波的LIGO的研发，其顺带的研究副产品，比如减震系统技术，也惠及了人类其他科技领域的发展。所以，AlphaGo对于人类的意义，绝不仅仅是它击败了人类围棋冠军而已。
我们是这个时代的幸运者，能够见证一个新的里程碑的诞生。不管最终谁输谁赢，都是我们人类的胜利。
-
引用 xuwenbin 2016/3/12 17:11:13 发表于2楼的内容
-
引用 fung 2016/3/13 10:32:17 发表于3楼的内容
-
-
-
-
hypermill9 | 当前状态：在线
总积分：7709 2024年可用积分：0
注册时间： 2007-02-07
最后登录时间： 2023-08-18
-
-
hypermill9 发表于 2016/3/14 15:32:04
4楼 回复本楼真不知道说什么好咯
引用 hypermill9 2016/3/14 15:32:04 发表于4楼的内容
-