AlphaGo是怎样下围棋的？ - 简书
AlphaGo是怎样下围棋的？
这周最出名的狗非阿尔法狗莫属了。
昨天下午，自己笔记本电脑开着直播放旁边戴上耳机听解说。。。是的听解说不是看，因为还在上班，也别问为什么周六还要上班T T
“诶怎么了，哦，投子，认输了，嗯另一位同行棋手走过来了，这时候李需要和同行一起”
都知道这一天迟早会来，却都没想到会这么快。
这里不谈任何人工智能发展对人类的影响，只谈技术，即AlphaGo是怎样下围棋的？（PS：我非常非常非常高兴地看到今天这个情况）
Google将论文发表在了上，全文对AlphaGo的技术实现做了一个大概的说明。接触过相关算法的同学，不求看完能写出一个AlphaGo，至少可以了解AlphaGo工作的细节，以下的内容全部来自于对此篇论文的理解，图片也都出自此篇，不再另外注明。
人类如何下围棋
在没有人工智能以前，人类最引以为豪的，就是“直觉”。我们人类下棋的时候，可以非常直觉地看出接下来这一步棋，大致有哪些理想的下法。而早期的下棋程序呢，并没有这种能力，机器能做的，只有暴力搜索，尝试所有可能的下法并递归下去到终局，找出能赢的下法。当然，仅凭直觉，成不了大师。
我下棋的时候，大致是这样的，相信大部分人也都是这样的：1，凭“直觉”看出几个可能的下法。2，对每一步可能的下法，猜测对手的应对方法，然后是接下来我的应对方法，能算几层，取决于当时脑子的灵活程度= =，大师级的棋手也都是在这里领先普通人。3，对计算到的每一个局面，估算局面的有利程度，取有利程度最大的那一个，既是应选的下法。
可以看出，上面的三个过程，全部都要依靠“直觉”，1自然不用说，3呢，有利程度怎么估算，中国象棋可以是棋力总和的比较，车算10分，马炮各5分，兵一分，还要加上棋子在不同位置上的考量，中炮的威力和边炮的威力当然不会一样。围棋呢，算围地的大小吗？当然不会这样简单，围棋一个棋子位置的差别，在收官的时候，会使结果天差地别。你现在目数领先了并不意味着你现在局面占优，所以3其实也是靠直觉。2呢，直接又包含了一次1，2，3。
机器下围棋的难点，正是在于怎样实现这些“直觉”。Google DeepMind实现的AlphaGo，下棋步骤基本符合上面的1，2，3。
SL policy network
为了实现1的“直觉”，DeepMind采用了KGS围棋游戏平台上面的30百万盘高手之间的对盘数据来训练AlphaGo，实现了SL policy network。训练方法叫做 supervised learning，是一类机器学习算法。
怎样理解这一类算法呢，其实就是变种的回归分析。在高中数学上，我们就知道能通过离散点的坐标数据，来计算出符合这些点的函数表达式，然后预测出下一个点的位置。而机器学习将此更近一步，计算的数据不仅限于坐标轴数据了，任何东西都可以，是的，任何东西。
人脸识别就是上述的产物。我们不用教机器人脸应该是怎样的，哪里有个鼻子哪里有个嘴巴，只需要拿出一堆照片，告诉机器，这些就是人脸，就像线性回归分析中我们直接输入已知的坐标数据一样。同样的，线性回归分析输出符合这些点数据的函数表达式。机器学习算法则输出符合人脸特征的函数表达式，你再输入一张图片，这台机器就查找这张图片有没这些特征，有就判定为人脸，没有就判定为不是人脸，就是这么暴力。
DeepMind输入了30百万盘的对盘数据，计算出了什么呢？是对于每一个局面，预测人类高手会选择的下法。这一部分，就是SL policy network。像不像人类的1步骤？
Rollout policy
相对于SL policy network，Rollout policy可以说是快棋版本。据论文上面的数据，计算出一步SL policy network，需要3ms的时间，而经过参数调整的Rollout policy，则只需要2 μs 。当然，节省了时间，也牺牲了准确率。前者预测人类高手下法的准确度为57.0%，后者仅为24.2%。后面你将会知道为什么要有Rollout policy。
RL policy network
DeepMind团队不满足于SL policy network，因为人类高手的下法一定就是正确的吗？为了提高policy network，DeepMind用第一代的SL policy network自己和自己玩，记录每一种下法的胜率，这样就增加了对盘数据。然后把这些对盘数据又通过supervised learning更新policy network，进化出下一代，又再一次的自己和自己玩，不断进化下去。据坊间传闻，自从AlphaGo打败欧洲冠军后，在三个月时间里，自己和自己又下了两千万盘。多么恐怖的数据。。。这样出来的policy network就叫做RL policy network。这样，AlphaGo就有了无限提高自己能力的方法。
Value networks
AlphaGo可以说由两个大脑组成，一个是上述组成的policy network，另一个就是Value networks。value networks就对应于人类的步骤3。
这东西怎么来的呢，回想下上面说过的人脸识别，既然可以通过一堆原始人脸数据，由机器提取特征，以后输入一张图片，机器就能通过匹配特征值来判断是不是人脸。那我输入一堆围棋对盘数据每一步的图片，告诉机器，这张图片结果是赢了，这张图片结果是输了。能不能通过同样的算法，机器提取出特征值，以后输入一张围棋的图片，机器就能匹配特征值来预测结果会是赢还是输呢？答案是肯定的，DeepMind团队就是这么干的，借用于自己和自己下的那几千万盘数据，训练出了Value networks。这个Value networks能对于每一个局面，预测输赢的概率。而且随着自我对盘局数的增加，这个概率将会越来越准确。想想都觉得恐怖是不是，机器根本不用知道什么是围棋，规则是什么，你只要给它足够多的图片数据，它以后就需瞄围棋棋盘一眼，就能预测输赢结果的概率，恐怖恐怖。（注：直接用图片会极大的降低准确度，所以实际用的是棋盘上棋子的坐标数据，但用图片不是不可以）
nature16961-f1.jpg
这张图说明了上述四者之间的关系。通过人类对盘数据训练出Rollout policy和SL policy network，通过SL policy network自我对局训练出了RL policy network。通过RL policy network的对盘数据，又训练出了Value network。
Monte Carlo tree search
有了1，3，还缺2呢。为了实现2，DeepMind采用了几乎所有围棋软件都会采用的方法：Monte Carlo tree,大名鼎鼎的蒙特卡洛树。
要理解蒙特卡洛树先要理解UCB算法。想象你到商场一楼，有一堆夹娃娃的机器，你手上有一100元，怎样夹到最多的娃娃呢？初来扎到，你当然不知道哪一台更容易夹到对不对，但你懂UCB啊，冷静的你开始喜感的夹娃娃了。1，为每一台机器贴一张纸条，写上num=0，value=0。并且手上也拿一张纸条，写上sum=0。1，随机挑一台机器，投入一元硬币，并将该台机器的num加1，然后开始夹，如果夹到了，value加1，否则不加。并且将sum加1。2，计算每台机器的UCB = value/num + (2ln(sum)/num)^1/2（想知道为什么是这个公式，可查看论文《Finite-time Analysis of the Multiarmed Bandit Problem》）。哪台机器的UCB值最大，则挑哪一台进行下一次夹娃娃。3，每次到机器夹娃娃，就将num加1，夹到value就加1，夹不到就不加。并且每次都要将sum加1，重复2和3。
这样，当你用完了100元，也即sum=100，理论上你将获得最多的娃娃而不会吃亏。其实公式已经很明白的表达了为什么要这么做。第一项value/num。是这台机器的平均收益，称为exploit项。通过你前面的记录，这台机器夹到的次数越高，投入的钱越少，exploit项的值越高，你就越应该多来这台夹。第二项(2ln(sum)/num)^1/2，是explore项，这个项给了那些一开始表现不好的机器一些机会。你前几次夹不到，不意味着你这台机器夹到的概率低，也可能是刚好那几次运气不好，所以有时候你也应该来这台试一试，当然，很多次都夹不到了，explore值会越来越低，你就应该减少来这台机器夹的次数。由于num都是分母，当num是0时，UCB是无限大，所以UCB算法会让你把所有机器都先尝试一次。这也是非常符合常理的。UCB的每一次选择，并不能保证你这次的选择有最大的数学期望值，但能保证你这次的期望值总比上次高。
现在可以来看一下蒙特卡洛树搜索(MCTS)了。
nature16961-f3.jpg
围棋下到每一步，我们要知道接下来下哪里赢的概率最高。如上图，将接下来所有合法的下法展开来计算是不现实的，因为围棋棋盘太大了。。。直接展开算算到宇宙毁灭都算不出来。但是呢，我们就可以利用上述的UCB算法，同样的道理对不对，对于每个节点，计算UCB值，挑最大的去展开计算，然后更新UCB值，以此重复，这样，你总能保证下次算出的走法比上次的走法好。而且最重要的是这个算法可以在任意时间内结束。就相当于你有50块钱或者100块钱都不影响你去使用UCB算法来玩夹娃娃。当然，围棋用的不是那个公式，而是在exploit前面再乘上一个参数，以调整UCB值，并称之为UCT。
上面的方法，用于早期的围棋程序，但是达不到职业选手的水准，因为你还是绕不开那个问题，棋盘辣么大，就算只展开一个节点，数字也是天文数字。
而DeepMind有了新的方法，嗯，就是前面的policy networks 和value networks。DeepMind将这两者和Monte Carlo tree search结合了起来。
对于展开哪一个节点去计算，AlphaGo不是去计算UCT，而是用了SL policy network和RL policy network。通过这两个，AlphaGo“直觉”出了接下来可能的好的走法，其中有SL“直觉”出来的，也有RL“直觉”出来的。
接下来，对前面“直觉”出来的走法（节点）进行展开，用Rollout policy下到终局，不是下一盘，而是下很多很多盘，然后计算出这个节点赢的概率，现在知道为什么要有Rollout policy了吧，因为它够快。同时，对于那个展开的节点，直接用value networks预测出赢的概率。两者取平均值，就能知道这样走赢的更准确的概率了。
选出赢的概率最大的那个，就是接下来要走的子，AlphaGo就靠着这样的算法，连赢了李三盘 : )
AlphaGo的思维
有了RL policy network，现在没有人知道AlphaGo计算过程具体的每一步是怎样选择的，包括DeepMind团队也不可能知道，因为它在不断的进化，进化。
而且，要给AlphaGo献上一个稳如狗的称号，因为，它的每一步，都是选赢的概率最大的那一个。80%的概率赢1目，70%的概率赢20目，AlphaGo会毫不犹豫的选择前者。所以，在三盘和李的对局中，能明显的看到，AlphaGo会尽量的去简化局面，选择稳赢的一步，而不可能主动去冒险。阿尔法狗，真心稳如狗。
原文自谢培阳的博客
http://xiepy.meAlphaGo之父详解背后的故事：“围棋上帝”是怎样炼成的|围棋|AlphaGo|人类_新浪新闻
历史悠久的围棋已经流传了近3000年，但人类一直低估了一点：以第五条线为代表的棋局中部区域。这是AlphaGo之父、DeepMind创始人Demis Hassabis向外界分享AlphaGo背后故事的时透露的重要信息。自从去年3月首尔那场载入史册的比赛以来，AlphaGo超越人类棋手固有思维和套路的招法，对围棋界的冲击史无前例。用Demis Hassabis 的话说，“就像人们利用哈勃望远镜发现新的宇宙空间一样。AlphaGo就是围棋界的‘哈勃天文望远镜’。”AlphaGo之父Demis Hassabis5月24日，DeepMind创始人Demis Hassabis以及AlphaGo团队负责人David Silver一起对外详解了AlphaGo背后的研发故事，以及AlphaGo究竟意味着什么?“AlphaGo已经展示出了创造力，在某一个领域它甚至已经可以模仿人类直觉了。” Demis Hassabis说，在未来能看到人机合作的巨大力量，人类智慧将通过人工智能进一步放大。“强人工智能是人类研究和探寻宇宙的终极工具。”围棋难在哪儿?历史上，电脑最早掌握的第一款经典游戏是井字游戏，这是1952年一位博士在读生的研究项目;随后是1994年电脑程序Chinook成功挑战西洋跳棋游戏;3年后，IBM深蓝超级计算机在国际象棋比赛中战胜世界冠军加里·卡斯帕罗夫。相比之下，围棋看似规则简单，复杂性却是难以想象的。它一共有10的170次方 种可能性，这个数字比整个宇宙中的原子数10的80次方都多，没有办法穷举出围棋所有可能的结果。可以对比的是，国际象棋有着巨大的数据库，如果棋盘上少于9个棋子的时候，通过数学算法就可以计算出谁胜谁败;如果棋盘上少于九个棋子的时候，下象棋时人类是没有办法获胜的。可以说，国际象棋的算法已经近乎极致。在Demis Hassabis看来，更困难的是围棋不像象棋等游戏靠计算，而是靠直觉。“围棋中没有等级概念，所有棋子都一样，围棋是筑防游戏，因此需要盘算未来。你在下棋的过程中，是棋盘在心中，必须要预测未来。小小一个棋子可撼动全局，牵一发动全身。围棋\'妙手\'如受天启。”哈萨比斯如此解释道。第一位与AlphaGo对阵的人类职业棋手樊麾对记者感慨，“曾经以为计算机打败职业棋手，一辈子都不会看到，没想到这么快就实现了。”对 AlphaGo 团队来说，是时候寻找一种更聪明的方法来解开围棋谜题了。如何训练AlphaGo?AlphaGo系统的关键是，将围棋巨大无比的搜索空间压缩到可控的范围之内。为了应对围棋的巨大复杂性，AlphaGo 采用了一种新颖的机器学习技术，结合了监督学习和强化学习的优势。具体而言，首先是通过训练形成一个策略网络(policy network)，将棋盘上的局势作为输入信息，并对所有可行的落子位置生成一个概率分布。然后，训练出一个价值网络(value network)对自我对弈进行预测，以 -1(对手的绝对胜利)到1(AlphaGo的绝对胜利)的标准，预测所有可行落子位置的结果。这两个网络自身都十分强大，而 AlphaGo将这两种网络整合进基于概率的蒙特卡罗树搜索(MCTS)中，实现了它真正的优势。最后，新版的AlphaGo 产生大量自我对弈棋局，为下一代版本提供了训练数据，此过程循环往复。AlphaGo 如何决定落子?在获取棋局信息后，AlphaGo 会根据策略网络探索哪个位置同时具备高潜在价值和高可能性，进而决定最佳落子位置。在分配的搜索时间结束时，模拟过程中被系统最频繁考察的位置将成为 AlphaGo 的最终选择。在经过先期的全盘探索和过程中对最佳落子的不断揣摩后，AlphaGo的搜索算法就能在其计算能力之上加入近似人类的直觉判断。Demis Hassabis表示，阿尔法狗不仅仅只是模仿其他人类选手的下法，而且在不断创新。例如，在与李世石第二局里对弈第37步，这一步是Demis 在整个比赛中感到最震惊的一步。Demis解释道：在围棋中有两条至关重要的分界线，从右数第三根线。如果在第三根线上移动棋子，意味着你将占领该线右边的领域。而如果是在第四根线上落子，意味着你计划向棋盘中部进军，潜在的，未来你会占棋盘上其他部分的领域，可能和你在第三根线上得到的领域相当。因此，在过去的3000多年里，人们普遍认为在第三根线上落子和第四根线上落子有着相同的重要性。但在第37步中，阿尔法狗却把字棋子落在了第五条线，进军棋局的中部区域。“这可能意味着，在过去几千年里，人们低估了棋局中部区域的重要性。”值得一提的是，和去年战胜李世石的AlphaGo相比，DeepMind 科学家David Silver称现在AlphaGo要更强三子，他介绍道：“与李世石对战的AlphaGo 在 云上有50个TPUs在运作，搜索50个棋步为10000个位置/秒，而昨天打败柯洁的AlphaGo Master则在单个TPU上进行游戏，AlphaGo成为自己的老师，它从自己的搜索里学习，有着更强大的策略和价值网络。”柯洁也在今日的微博中，对于AlphaGo团队给出的检测报告感叹：自己是在跟怎样可怕的对手下棋。“这个差距有多大呢?简单的解释一下就是一人一手轮流下的围棋，对手连续让你下三步...又像武林高手对决让你先捅三刀一样...”柯洁说。除了下围棋，AlphaGo还能做什么?围棋之外，Demis Hassabis告诉记者，AlphaGo 的高效算法是一种通用型的算法，也可以推广到其他算法，把人工智能运用到各种各样的领域，如将AI用到材料设计、新药研制上，还有现实生活中的应用，如医疗、智能手机、教育等。他曾举例，通过与人类专家的合作，可以找到各种各样的创新方式，包括从“其中一种变体应用于医疗行业，我们正在着力解决蛋白质折叠的问题，用来治疗各种疾病。”“人机合作可以达到1+1大于2的效果，人类的智慧将被人工智能放大。人工智能和AlphaGo都是工具，就像哈勃望远镜一样，可以推进人类文明的进步。”他说。不过他也对第一财经坦言，围绕AlphaGo，背后的技术包括图像处理、大数据分析等，这些技术目前在其它领域的使用还在早期探索阶段，只在AlphaGo研究的中间环节某些领域应用，但是在未来肯定会在多个领域推广相关的技术。Demis Hassabis还表示，目前信息过载和系统冗杂是人类面临的巨大挑战.希望利用AI找到元解决方案。“我们的目标是实现‘人工智能科学家’或‘人工智能辅助科学‘。”“人工智能和所有强大的新技术一样，在伦理和责任的约束中造福人类。” Demis Hassabis说。这意味着，人工智能应该是应用于科学、制药等领域，而不是应用于研发武器、战争上;此外，人工智能不能只为少数几家公司使用，而是为全人类所共享。
跟格局小的人打交道，就像被缩骨伞夹住脑袋一样不痛快。
号外号外，特朗普又出行政命令啦！行政命令有多强，买不了吃亏，买不了上当，是XX你就坚持60秒！
吴承恩的人生经历，决定了《西游记》背后必然影射着中国特色的官场文化。
没有石油的生活，可能比如今这种依赖石油的生活更加有趣和充实。机器学习与人工神经网络(三)：AlphaGo 怎么下棋？ | 数据之声
机器学习与人工神经网络(三)：AlphaGo 怎么下棋？
&>>&&>>&机器学习与人工神经网络(三)：AlphaGo 怎么下棋？
1 次，平均分
通常一场赛局(game)的发展可以用树形图表示，将当下的可能性全部列出，并且分别推演接下来的步骤(图一)。在围棋和西洋棋中也能画出树形图。不同的是，西洋棋树形图共有 10120 个不同的节点，比全宇宙的原子数目还要多(约 1080个)！更甚的事，在19*19的围棋棋盘上，一共有 10360以上个可能性，是一个极度复杂的赛局。
图一：圈圈叉叉的树形图示意图。我们能发现其中有几条是必胜的策略。(source: wikimedia)
●深蓝如何击败西洋棋冠军？
通常认为深蓝透过暴力法计算可能的步骤，这个说法只对了一半。从上述的复杂度来看，不可能存在暴力解法找到必胜策略，因此深蓝的算法改用另一个策略，分为两个部分：一个是上述的树形图暴力法搜寻，但仅计算未来6步之内的所有可能性；第二，透过一个估计函数，算出6步之后盘面的胜率，深蓝挑出其中胜率最高的路径走。如此，深蓝不必计算出所有的盘面，大大降低计算深度。但相对地，它只能挑选获胜「机率」大的路径，不能保证胜利。
简而言之，深蓝能否致胜取决于两个条件：
计算机的计算能力。若能推算到第7步、第8步以后，盘面会越接近盘末点，估计出的胜率会越真实，决策也会越正确。
胜率估计函数的准确度。
当初 IBM 聘请几位西洋棋高手为深蓝设计这个函数。尽管当时函数的表现效果很好，但就像是在手写识别的例子中提到的一样，人类设计算法要付出极大心思，并且有其限制。在围棋中，这将是深度学习能大展身手的地方。
●AlphaGo怎么下棋？
上述的方法在围棋上行不通。一场西洋棋对弈双方平均一共进行约80手，而围棋平均约有150手。若要有效评估每一步棋的胜率，必须向未来推算更多步骤。不仅如此，不同于西洋棋每个棋子移动的范围有限，围棋棋子可以任意摆放在19*19的棋盘上，每一步的树形图很广，推算未来所需要的计算量大上好几个数量级。这也是为什么在深蓝获胜后的20年间，围棋仍被认为是人工智能难以匹敌人类的棋艺。
图二：大幅减少计算的两个关键：策略神经网络和估值神经网络。策略神经网络接受1919的棋面(s)，输出一个1919的数值数组，每一个数值代表棋子下在该位置的机率(a)。估值神经网络接受19*19的棋面(s’)，输出该棋面的获胜机率(v(s’))。(参考数据[1])
深度学习是一种基于深度神经网络、让计算机自己学习的一种算法，使下围棋变得的可能。Google 的 AlphaGo 透两种深度神经网络，减少在树形图的广度和深度，大幅降低计算量。第一种神经网络为策略网络(policy network)。这个神经网络从棋谱中学习围棋高手如何应付各种棋势。经过三千万张棋谱的训练后，在遇到一个从来没有看过的棋面，它能预测高手会将棋子下在哪里，准确度接近60%。透过模仿高手下棋的位置，AlphaGo 删去了许多不合理的棋步，减少了树形图中不必要的广度探索。此外，科学家让 AlphaGo 和自己对弈、向自己学习下棋方式，更进一步地优化策略网络。
第二种神经网络为估值网络(value network)。和深蓝的估计函数的功能一样，它让 AlphaGo 仅需推算未来数步，剩下的交由估值网络来估计胜率，减少了树形图探索的深度。但和深蓝不同的是，这个估值网络不需要请围棋高手来设计，而从透过千万张棋谱训练神经网络中的链接。
综合来说，面对对手的一步棋，AlphaGo 会先用策略网络从所有可能性中，依照之前学习的经验挑选几步最可行的方案。针对这些可行的方案，估值网络算出它们的胜率，AlphaGo 从中挑选最佳的致胜方案。这种单从未来几步棋的棋面评断获胜率的方式，可被称为 AlphaGo 的「直觉」。有趣的是 Google 科学家另外融合了「快速推演」，即很快速但不准确地的推敲当前这步棋下到最后的结果。这像极了人类的思考方式，我们不仅透过直觉谨慎思考当下状况，也大致推敲未来的情形。Google 科学家发现融合直觉和快速推演的结果，比单单使用两者之一好上许多。
表一：世界围棋积分节录。AlphaGo其实是一位男性。(source: updated on 12/09/2016 )
●AlphaGo 的胜利代表什么？
回到文初的问题，AlphaGo 和深蓝有什么不一样，让世界这么疯狂呢？首先，在复杂度极高的围棋中，AlphaGo 在对弈中计算的次数竟比深蓝当时少了几千次。这象征着人工智能已大幅进步。再者，这个进步并不只来自于计算能力。若只靠硬件科技的进展，人们预估至少要10年以后人工智能才有机会在围棋上和人类较劲。AlphaGo 利用深度学习，透过的策略网络和估值网络分别大幅减少计算的广度和深度，是算法上的突破。最重要地，这些算法基于人工神经网络，从大数据中学习，不需要请专家设计，因此不需要领域内知识(Domain Knowledge)：深蓝的算法仅适用于西洋棋，但AlphaGo算法的应用不局限于围棋。这也是为什么 Google DeepMind 总裁 Demis Hassabis 评论道：「AlphaGo 的目的不是要击败人类，而是要证明这种算法的能力，并用它解决现实生活中的问题。」
参考数据：
David Silver et al., Mastering the game ofGo with deep neural networks and tree search, Nature 529, 484–489 (2016)
Christopher Burger, Google DeepMind'sAlphaGo: How it works (2016)
除特别注明外，本站所有文章均为原创，转载请注明出处来自
发现数据之美
关注我们微信公众号：大音如霜
咨询服务：
邮箱：每日文章搜索
2017年七月
101112131416
17181920212223
24252627282930
精品文章订阅
您也可以使用第三方帐号快捷登录
扫一扫二维码分享【原创】AlphaGo怎么下围棋的
最近DeepMind团队（google旗下）的AlphaGo（一个围棋的AI）以4:1战胜顶尖人类职业棋手李世石。她到底是怎么下棋的？
AlphaGo在面对当前棋局时，她会模拟(推演棋局)N次，选取“模拟”次数最多的走法，这就是AlphaGo认为的最优走法。
例如图中，所有没有落子的地方都是可能下子的，但在模拟中，右下那步走了79%次， 就选那一步了，就那么简单。后面你会发现，“模拟”次数“最多”的走法就是统计上“最优”的走法。
1. 啥是模拟？
模拟就是AlphaGo自己和自己下棋，相当于棋手在脑袋中的推演，就是棋手说的”计算“。
AlphaGo面对当前局面，会用某种（下面会讲）策略，自己和自己下。其中有两种策略：往后下几步（提前终止，因为AlphaGo有一定判断形势的能力）；或者一直下到终局（终局形势判断相对简单，对于棋手简单，对于机器还有一定难度，但是这个问题已经基本解决）。对于棋手来说就是推演棋局。
AlphaGo会模拟多次，“不止一次”。越来越多的模拟会使AlphaGo的推演“越来越深”（一开始就1步，后来可能是几十步），对当前局面的判断“越来越准”（因为她知道了后面局面变化的结果，她会追溯到前面的局面，更新对前面局面的判断），使后面的模拟“越来越强”（更接近于正解，她后面模拟出来的着法会越来越强）。怎么做到的？看她怎么模拟的。
注意，这里的模拟是下棋（线上）时的模拟，后面还会有个学习时的模拟，不要混淆了。
2.AlphaGo怎么模拟的？
每次模拟中，AlphaGo自己和自己下。每步中由一个函数决定该下哪一步。函数中包括了以下几个方面：这个局面大概该怎么下（选点：policy net），下这步会导致什么样的局面，我赢得概率是多少（形势判断：value net 和rollout小模拟），鼓励探索没模拟过的招法。这些英文名词后面会有解释。
模拟完一次后，AlphaGo会记住模拟到棋局，比如几步以后的棋局。并且计算这时policy，value。因为这时已经更接近终局了，这时的值会更加准确（相对于前面的模拟或局面）。AlphaGo还会用这些更准的值更新这个函数，函数值就越来越准了，所以模拟的每一步越来越接近正解（最优的下法），整个模拟越来越接近黑白双方的最优下法（主变化，principle variation），就像围棋书上的正解图一样。到此为止，你已经大概了解AlphaGo她怎么工作的了，下面只是一些细节和数学了。
3. 那个函数是啥， 好神奇？
这个函数，分为两个部分。
Q 是action value， u是bonus。Q其实就是模拟多次以后，AlphaGo计算走a这步赢的概率，其中会有对未来棋局的模拟（大模拟中的小模拟），和估计。u中包括两个部分。一方面根据局面（棋形）大概判断应该有那几步可以走，另一方面惩罚模拟过多的招法，鼓励探索其他招法，不要老模拟一步，忽略了其他更优的招法。
4.Q（action value）具体是什么？
Q看上去有点复杂，其实就是模拟N次以后，AlphaGo认为她模拟这步赢得平均概率。&
分母N是模拟这步棋的次数。
分子是每次模拟赢的概率（V)的加和。
其中V又包括两部分，value net对形势的判断。和一个快速模拟到终局，她赢的概率。
valuenet是说她看这个这个局面，就要判断赢的概率，“不准”往下几步想了。value net下面详细讲。
快速模拟是说她看这个这个局面，自己和自己下完，看看黑白谁赢的概率高。快速模拟是我们这个大模拟中的一个小模拟。
Q就是看当下（value net），也看未来（快速模拟），来决定怎么模拟（对人来说就是往哪里想，对于棋手就是思考哪些可能的着法），下棋方（模拟中下棋方黑白都是AlphaGo）下那一步赢的概率高，从而决定模拟下那一步。
5.u（bonus）具体是啥？
u中包括两个部分。
分子是AlphaGo根据当前局面判断（policy net），不模拟，比如棋手根据棋形大概知道应该有哪几步可以走。
分母是模拟到现在走当前步的累加，越大下次模拟越不会走这了。
一句话，（Q+u）就是决定模拟中，下棋方会走（模拟）哪里。
到此，我们大概了解了AlphaGo的两大神器：value net（形势判断：模拟中，我走这步，我赢的概率是多少）和policynet（选点：模拟中，这个局面我走那几步最强）。下面会揭开他们神秘的面纱。
6. 为什么选模拟次数最多的一步？
根据以上的函数可知，模拟次数最多一步，其实就是在多次模拟中，AlphaGo认为那一步最可能赢的次数的累加（或平均，除以总模拟次数）。
7. 为什么要分为policy net（选点）和value net（形势判断）呢，选点和形势判断不是一个东西吗？
确实，选点和形势判断是互相嵌套的。首先，围棋的形势判断是非常困难的。在围棋直播中我们经常看到，职业9段也不能准确判断当前局面，除非地域已经确定，没有什么可以继续战斗的地方，一般也就是接近终局（官子阶段）。即使职业棋手，选点和判断也是定性的成分偏多，定量的成分偏少。以前说中国顶级棋手古力能推演到50步，已经非常强了。
再说嵌套问题，准确的定量的选点和判断，就要计算（对于棋手是在脑子里推演，对于机器就是模拟）才行。在推演中，我选点走那步决定于，走这步后我赢的概率，而这个概率又决定于对手走那一步（我会假设对手弈出她最强的一步，对我最不利），对手走那一步决定于，她走那步后，她对形势的判断要对她最好，这又取决于我的下下步（第3步了）走哪里（对手她也会假设我会下出对她最不利的一步，自然对我最优），从而不断的嵌套，这个“死结”要到终局（或者接近）才能解开（终局形势判断比较简单）。所以不到终局，判断形势是非常困难的，即使职业的9段也不行。这就是围棋比象棋难的关键所在，它没有简单的形势判断的方法，而象棋有。
要回答这个问题7还要看下面了。
8.AlphaGo是怎么打开这个死结的？
AlphaGo没有进行直接的形势判断，就是没有直接学习valuenet，而是先做一个选点（policynet）程序。选点可以认为是一个时序（走棋）的一个局部问题，就是从当前局面大概判断，有哪几步可能走，暂时不需要推演（那是模拟的工作）。棋手的选点是会推演的，这里的基础policy net是不推演的，前已经看到AlphaGo线上模拟中选点（Q+u）是有推演的。
所以policynet是用在“每次模拟”中，搜索双方可能的着法，而最优步的判断是“N次模拟”的任务，policy net不管。此外policy net还用来训练value net，也就是说，value net是从policy net 来的，先有policy 才有value。
选点（policy net）能成立吗？如果不成立，也是没用。
9. 第一神器policy net怎么工作的？
先大概看下这个图。现在轮到黑棋下，图上的数字是AlphaGo认为黑棋应该下这步的概率。我们还发现，只有几步（2步在这个图中）的概率比较大，其他步可能性都很小。这就像职业棋手了。学围棋的人知道，初学者会觉得那里都可以走，就是policy（选点）不行，没有选择性。随着棋力增长，选择的范围在缩小。职业棋手就会锁定几个最有可能的走法，然后去推演以后的变化。AlphaGo通过学习，预测职业选手的着法有57%的准确率。提醒一下，这还是AlphaGo“一眼”看上去的效果，她没开始推演（模拟）呢。而且她没预测对的着法不一定比职业棋手差。
policynet怎么学习的，学啥？
首先，policy net是一个模型。它的输入时当前的棋局（19*19的棋盘，每个位置有3种状态，黑，白，空），输出是最可能（最优）的着法，每个空位都有一个概率（可能性）。幸运的是，着法不像形势判断那么无迹可寻。我们人已经下了千年的棋。policy net先向职业选手学习，她从KGS围棋服务器，学习了3000万个局面的下一步怎么走。也就是说，大概职业选手怎么走， AlphaGo她已经了然于胸。学习的目的是，她不是单纯的记住这个局面，而是相似的局面也会了。当学习的局面足够多时，几乎所有局面她都会了。这种学习我们叫做“监督学习”（supervised
learning）。以前的职业棋手的棋谱，就是她的老师（监督）。&
AlphaGo强的原因之一是policy net这个模型是通过深度学习（deep learning）完成的。深度学习是近几年兴起的模拟人脑的机器学习方法。它使AlphaGo学习到的policy更加准确。以前的AI都没有那么强的学习能力。
更加厉害的是，AlphaGo从职业棋手学完后，感觉没什么可以从职业棋手学的了。为了超越老师和自己，独孤求败的她只能自己左右互搏，通过自己下自己，找到更好的policy。比如说，她从监督学习学到了一个policy，P0。AlphaGo会例外做一个模型P1。P1一开始和P0一样（模型参数相同）。稍微改变P1的参数，然后让P1和P0下，比如，黑用P1，白用P0选点，直到下完（终局）。模拟多次后，如果P1比P0强（赢的多），则P1就用新参数，否则，重新再原来基础上改变参数。我们会得到比P0强一点点的P1。注意，选点是按照policy的概率的，所以每次模拟是不同的。多次学习后AlphaGo会不断超越自己，越来越强。这种学习我们叫做增强学习（reinforcement
learning）。它没有直接的监督信息，而是把模型发在环境中（下棋），通过和环境的互相作用，环境对模型完成任务的好坏给于反馈（赢棋还是输），从而模型改变自己（更新参数），更好的完成任务（赢棋）。增强学习后，AlphaGo在80%的棋局中战胜以前的自己。
最后，AlphaGo还有一个mini的policy net， 叫rollout。它是用来上面所说的模拟中，快速模拟的终局的。它的输入比正常policynet 小，它的模型也小，所以它的耗时是2微妙，而一个policy要3毫秒。它没有policy准，但是它快。
总结一下policy。它是用来预测下一步“大概”该走哪里。它使用了深度学习，监督学习，增强学习等方法。它主要用于每次模拟中的bonus的先验（我大概该怎么走），和value net的学习（后面的重点）。
如果单纯用policy预测的着法来作为最优着法，不通过value net的计算和上面说的模拟，对职业棋手那是不行的。但是，单纯用policy预测已经足够打败以前的围棋AI（大约有业余5段实力）了。这说明了上面3种学习方法的强大威力。AlphaGo就看了一眼，还没有推演，你们就败了。policynet为解开那个死结走出了第一步，下面我们就讲讲这第二个“神器”：value net。
10.第二神器value net怎么工作的
前面说了，形势判断是什么无迹可寻，就连职业9段也做不到。有了policy net，整个世界都不一样了。 AlphaGo她的灵魂核心就在下面这个公式里。
V*（s）=Vp*（s）约等于Vp（s）。
s是 棋盘的状态，就是前面说的19*19，每个交叉3种状态。
V是对这个状态的评估，就是说黑赢的概率是多少。
V*是这个评估的真值。
p*是正解（产生正解的policy）
p是AlphaGo前面所说学到的最强的policy net。
如果模拟以后每步都是正解p*，其结果就是V*，这解释了等号。
如果你知道V*这个函数，在当前局面，你要对走下一步（围棋平均有250种可能性）后的状态s进行评估，选最大的V*走就行。围棋就完美解决了。但是，前面说了，V*不存在。同样p*也不存在（理论上存在，实际因为搜索空间太大，计算量太大找不到。在5*5的棋盘中下棋可以做到）。
AlphaGo天才般的用最强poilicy，p来近似正解p*，从而可以用p的模拟Vp来近似V*。即使Vp只是一个近似，但已经比现在的职业9段好了。想想她的p是从职业选手的着法学来的，就是你能想到的棋她都想到了。而且她还在不断使的p更准。顶尖职业棋手就想以后的20-40步，还会出错（错觉）。AlphaGo是模拟到终局，还极少出错。天哪，这人还怎么下。
围棋问题实际是一个树搜索的问题，当前局面是树根，树根长出分支来（下步有多少可能性，棋盘上的空处都是可能的），这是树的广度，树不断生长（推演，模拟），直到叶子节点（终局，或者后面的局面）。树根到叶子，分了多少次枝（推演的步数）是树的深度。树的平均广度，深度越大，搜索越难，要的计算越多。围棋平均广度是250，深度150，象棋平均广度是35，深度80。如果要遍历围棋树，要搜索250的150次方，是不实际的。这也是围棋比象棋复杂的多的原因之一。但更重要的原因前面讲了：是象棋有比较简单的手工可以做出的value函数。比如，吃王（将）得正无穷分，吃车得100分，等等。1997年打败当时国际象棋世界冠军的DeepBlue就是人手工设计的value。而围棋的value比象棋难太多了。手工根本没法搞。又只能靠深度学习了。
在讲value的原理前，先看看定性看看value的结果。如图，这是AlphaGo用value net预测的走下一步，她赢的概率。空的地方都被蓝色标示了，越深说明AlphaGo赢的概率越高。这和我们学的棋理是相符的，在没有战斗时，1,2线（靠边的地方）和中间的概率都低，因为它们效率不高。而且大多数地方的概率都接近50%。所以说赢棋难，输棋也很难。这当然排除双方激烈战斗的情况。
这里讲讲怎么通过policy net 得到value net。有了policy，value就不是那么难以捉摸了，死结打开了。AlphaGo可以模拟（自己和自己下，黑白都用最强的policy），直到终局。注意，这里的模拟和最初说的模拟有点不同。最初的模拟是AlphaGo在下棋（线上）中用的，用来预测。这里的模拟是她还在学习（线下）呢。终局时V*（谁赢）就比较容易判断了。当然，对机器来说也不是那么容易的，但相对于中局来说是天渊之别。
valuenet也是一个监督的深度学习的模型。多次的模拟的结果（谁赢）为它提供监督信息。它的模型结构和policy net相似，但是学的目标不同。policy是下步走哪里，value是走这后赢的概率。
总结一下，value net预测下一走这后，赢的概率。本身无法得到。但是通过用最强policy来近似正解，该policy的模拟来近似主变化（就围棋书上那个，假设书上是对的），模拟的结果来近似准确的形势判断V*。value net用监督的深度学习去学模拟的得到的结果。value net 主要用于模拟（在线，下棋的时候）时，计算Q值，就是平均的形势判断。
再回顾一下模拟，模拟的每一步是兼顾： 模拟到现在平均的形势判断value net， 快速rollout模拟到终局的形势判断， 根据当前形势的选点policy，和惩罚过多的模拟同一个下法（鼓励探索）等方面。经过多次模拟，树会搜索的越来越广，越来越深。由于其回溯的机制，Q值越来越准，下面的搜索会越来越强。因为每次的Q值，都是当前模拟认为的最优（排除鼓励探索，多次后会抵消），模拟最多的下法（树分支）就是整个模拟中累积认为最优的下法。
到此为止，AlphaGo她神秘的面纱已经揭开。她的基本框架见下图。下棋时的线上过程是图中红箭头。线下的准备工作（学习过程）是蓝箭头。。再串一下。AlphaGo下棋（线上）靠模拟，每次模拟要选下那一步，不是简单的选点policy就完了，而是要参考以前模拟的形势判断，包括：value net和快速模拟（小模拟）到终局，鼓励探索，policy（先验），就是（Q+u），它比单纯的policy准。她选择模拟最多的下法（就是平均最优）。这是线上，下着棋了。之前（线下），她要训练好policy模型，
rollout模型和value 模型。其中，policy，rollout可以从棋谱，和自己下棋中学到。value可以从用学好的policy下棋的模拟结果监督学到。从而完美解决value学不到的问题和policy和value互相嵌套的死结。从棋谱直接学value net现在还不行。
11. AlphaGo用到哪些技术？
AlphaGo在树搜索的框架下使用了深度学习，监督学习和增强学习等方法。
以前最强的围棋AI使用蒙特卡洛树搜索的方法。蒙特卡洛算法通过某种“实验”的方法，等到一个随机变量的估计，从而得到一个问题的解。这种实验可以是计算机的模拟。让我们看看蒙特卡洛树搜索怎么模拟的。算法会找两个围棋傻子（计算机），他们只知道那里可以下棋（空白处，和非打劫刚提子处），他们最终下到终局。好了，这就可以判断谁赢了。算法就通过模拟M（M&&N）盘，看黑赢的概率。可以看到这明显的不合理。因为每步是乱下的。有些棋根本就不可能。即使如此，这个算法可以达到业余5段左右水平。
AlphaGo可不是乱下，她是学了职业棋手着法的。所以AlphaGo的搜索叫beam search(只搜索几条线，而不是扫一片)。前面也可以看到AlphaGo认为的可能着法就几种可能性，而不是随机的250种。这就是从250的150次方到几（&10)的n(n&&150，可以提前终止搜索，因为有value net）次方，的计算量降低。虽然AlphaGo每次模拟的时间更长（因为要深度模型的预测policy 和value，不是乱下），但是AlphaGo的模拟次数可以更少，是蒙特卡洛树搜索的1/15000。就是说AlphaGo的搜索更有目的性了，她大概知道该走哪里。解说说她下棋更像人了。我会说她下棋更像职业棋手，甚至超过职业棋手。线下的学习使得她的行为（模拟）有了极强的目的性，从而完成最终目标（赢棋）。
12.什么是打劫
打劫，是指黑白双方都把对方的棋子围住，这种局面下，如果轮白下，可以吃掉一个黑子；如果轮黑下，同样可以吃掉一个白子。因为如此往复就形成循环无解，所以围棋禁止“同形重复”。根据规则规定“提”一子后，对方在可以回提的情况下不能马上回提，要先在别处下一着，待对方应一手之后再回“提”。如图中的情况：
打劫因为反复走同一个点，会使搜索树的深度加大，而且因为其他位置劫才会影响劫的输赢，劫才之间又相互影响，有可能打劫中又产生新的劫。总之，打劫规则会使围棋的复杂度加大。
因为前两局棋没有下出打劫，有人会怀疑DeepMind和李世石有不打劫协议。在后面的棋局中，AlphaGo确实下出了主动打劫。而且从算法层面看，打劫也不会是她的模拟框架崩溃（可能会有一些小麻烦）。
13.&遇强则强，遇弱则弱？
AlphaGo的表现似乎是遇强则强，遇弱则弱。这可能是由于她的学习监督信息决定的。policy和value学习时，和rollout模拟时，最后的结果是谁赢(的概率)，而不是谁赢“多少”（赢几目）。所以在AlphaGo领先时（几乎已经是常态了），她不会下出过分的棋，她只要保证最后赢就行了，而不是像人一样要赢的多，赢的漂亮。即使有杀大龙（一大块棋）的机会，她也不一定杀，而是走温和的棋，让你无疾而终。估计只有在AlphaGo判断她大大落后的时候，她才会冒险走过分的棋（这好像不常见）。
14. AlphaGo下棋为什么花钱？
AlphaGo有单机版，多机（分布式）。分布式明显比单机强。去年的分布式有40个搜索线程，1202个CPU，176个GPU（显卡）。和李世石下棋时可能更多。这么多机器的运作和维护就是烧钱。
15.AlphaGo有哪些技术突破，使她能战胜人类顶尖棋手？
a. 继承了蒙特卡洛树搜索的框架进行模拟。
b. 在学习policy中使用了监督学习，有效的利用现有的棋手的棋谱，学到了他们的选点策略。
c. 在学习policy中使用了增强学习，从左右互搏中提高自己。
d. 利用policy net（选点模型）近似正解，用policy net的对弈的结果模拟正解对弈的结果，即正确的形势判断，从而打破形势判断和选点相互嵌套的死结。就是先学policy，再学value。
e. 在学习policy， value， rollout中使用深度学习模型。深度学习有非常强的学习能力。使得选点和形势判断前所未有的准（对比蒙特卡洛是随机选点，现在是职业棋手帮她选点了）。因为在每次模拟中用到了这两个“准”，使得在树搜索（就是推演）的过程更有目的性（树大量减枝，只模拟比较优良的下法）
f. 当然还有机器一贯的优势，不疲劳，不受心理情绪影响，不会错的记忆力等等。
到此AlphaGo终于介绍完了。
下面是去年底DeepMind团队的nature paper。
Mastering the game of Gowith deep neural networks and tree search。
1,&1,&1,&1,&1,&1,&1,&1,&1,&1,&1,1,&2,&1,&2,&1,&1,&1,&1,&1.
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：530次
排名：千里之外