注：本文其实只介绍mogo程序所采用的MC+UCT算法。记得以前还曾为深蓝击败顶尖人类棋手而暗喜，庆幸自己选择了围棋这一体现人类智慧优越感的游戏。因为人机博弈的设计不外乎两个方面：估值和搜索，而这两者在国际象棋上表现非常好，深蓝仅仅靠的暴力搜索下出的妙手让大师也手足无措，你要不信，去问问卡斯帕罗夫和深蓝对局时什么感受。然后估值和搜索用在围棋上似乎失灵了，一来无值可估，计算机如何看待局部的好手成了全局的恶手，它又如何学会弃子呢？二来搜索空间太大，计算机算不了多少步，它的基本思路是考虑我方可能下的每手棋，对方的所有可能应对，而对每一个应对，又考虑我方接下来的所有应对……这是一个指数增长的算法，用不了几步就成了一个天文数字。但是围棋中的征子动辄二三十步，摩尔定律十八个月翻一番充其量也就是个平方，追的上指数吗？深蓝拿下国象，黑石拿下五子棋，唯有围棋几十年来固若金汤，可说是仅存的一片乐土了。我也曾经坚信，除非基础理论出现重大变革，否则计算机在围棋上战胜人类是痴人说梦。然后这个信念随着2007年mogo的出现，动摇了。确切的说，我的信念是在前几天和mogo下过几盘棋后动摇的。直到昨天我才好好研究了一下mogo所用的算法，心中狂喜，我为这样天才的想法而叫好，我不再为信念动摇而悲伤了，反正我业余玩玩，总也玩不过职业的。等到计算机真的攻下围棋，我就叛变，何况我的主业本就是计算机。话说我闻道欣喜之余，总想找个人去传道，我可怜的妻子，没有半点程序基础的人，就成了第一个受害者，在她理解了我的倾述欲望后，问我：“要多久？”我想了想，坚定的回答：“十分钟。”一个真正天才的想法只是常人没想到而已，它本身不会很复杂的，因此我觉得十分钟足矣。MC方法我先介绍蒙特卡罗（即MC）方法，这是一个赌城的名字，Monte Carlo，位于摩纳哥。这个方法与赌博有关，如果你愿意，你也可以把它叫做拉斯维加斯方法，或者麻糕方法，没听过麻糕？那么插播一个笑话：a:听到一特好听的歌，歌词只记得是“一个芝麻糕，不如一针细”，求歌名啊！b:你可知Macau，不是我真姓……－_－!为了启发她使用MC方法，我从她熟悉的事物说起：你前段时间经常玩新浪空间的我爱老虎机游戏，你知道你玩的老虎机胜率是多少吗？什么胜率？就是类似你炒股一样，有个投资回报率，或者换个说法叫收益率。平均100个币能变成200吧这么说，收益率就是100%了？嗯，对。大家看，我妻子已经用MC方法计算出了老虎机的收益率，她没有看过老虎机的源代码，不知道它何时吐币多少的内部规律，可是她能知道收益率。如果给我源代码，我也能算出来期望值是多少，但是以前我反编译过那个老虎机的flash，发现其吐币逻辑在服务器端，所以我很难得到源代码。UCB算法在启发她知道什么是MC方法后，我决定给她一个难题，考察她灵活运用MC方法的能力。我说，你看，现在老虎机游戏每天只能在一个好友那里投10次币，每个好友只有一台老虎机，假设游戏改一下规则，每个好友那里有10台老虎机，每个人的每台老虎机收益率都不同，并且每天一变，那现在你怎么玩这个游戏呢？我妻子想了想，说，我每台老虎机投10个币，看看哪台赚的多，然后就玩哪台。我说，不错，你已经掌握了MC方法的精髓了，但是每天在一个好友那里最多只能投100个币，你10台都试完了就不能再投币了，你已经知道哪台收益率最高，可是第二天收益率就变了，这时候你该怎么办？我妻子说，不知道了。我说，没关系，因为接下来我要给你介绍的方法是人工智能领域里最前沿的算法，这个方法叫UCB，你不用管它的名字，它其实就是用来玩老虎机的。我在纸上画了10个老虎机，指着其中一个说，假设你一开始玩这个，得到了一些收益，然后你如何决定接下来玩哪个呢？有个科学家提出了UCB算法，他对每个老虎机计算一个UCB值，这个值由两部分相加而组成：第一部分是这台老虎机以前的收益情况，第二部分与这台老虎机被玩的次数及你总共玩的次数有关。第一部分好理解，因为以前的收益情况，提供你选择的标准，通常都会选以前收益最大的，第二个部分就是说，如果一台老虎机你都没玩过，你怎么知道它的收益好不好呢？所以你要给它一个机会，也给你自己机会。就是说被玩次数少的，UCB值的第二部分会给出一个较大的增益，让它有被选择的机会……我妻子顿悟：我知道了，就好像我喜欢吃烤鸡腿堡，但也不能老吃，偶尔也要吃吃大白菜。我说，恭喜你，你已经站在了人工智能领域的最高峰了，我怎么就没想到这样浅显的比喻呢！以后UCB算法也可以叫鸡腿堡算法了。这样，我妻子很快就明白了UCB方法的含义了，尽管她还不知道UCB公式的细节：UCB=X+sqrt(2ln(N)/T)，X表示以前的收益，N表示所有机器玩过的总次数，T表示这台机器玩过的次数。MC之于围棋现在我们要切入正题，我要讲的是围棋AI的设计。假设我下了一步想走在这里，那么我怎么知道这步棋好不好呢？有个科学家就提出了，假设你这步棋已经下到这了，找两个傻子，让他们随便下，把棋下完，看看是黑棋胜还是白棋胜。只有两个傻子，这结局太有偶然性了，那么我们找10000对傻子来下一万盘棋（妻子突然打断我，弱弱的问，这一万盘棋都是由电脑来模拟吧），然后统计一下是黑棋赢的多还是白棋赢的多，这样我就得到了这一手棋的获胜概率，然后我把所有可能下法的获胜概率都这样算出来，选择获胜概率最大的下法。这个方法是不是有点眼熟？哈哈，和前面10台老虎机问题时，我妻子给出的方法如出一辙。（由于我妻子不懂树(Tree)，接下来我都在纸上画给她看，因此她的作用在本文中到此为止了。）到这里为止，本文给出的mogo的算法细节还没超出关于mogo的新闻报道，而下面的内容会难一点，如果读者就此打住，那么凭此文也就能遐想一下围棋AI的前景，你无法得到mogo算法的奥义。UCT登场MC直接用在围棋上的缺点十分突出，首先是浪费了模拟次数，因为在有限的时间内只能模拟出一定的棋局数。其次，它没有考虑对方的下一手，如果我们把MC当做估值函数，那么对比传统的人机博弈程序，简单的MC相当于只搜索了一步。如果估值无比精准的话，那么一步足矣。实际上围棋还不存在这么精确的估值，以MC的估值速度，往深算几步，耗费的时间无法接受。博弈搜索可以理解成一个树形结构上搜索，在树形搜索上结合UCB，就是UCT算法了（UCB for Tree）。假设我们已经有了一棵树，每一个叶子节点上有一台老虎机，我们怎么用UCB算法来玩这些老虎机呢？方法一是把所有的叶子节点都列出来，然后按公式计算每一个叶子节点的UCB值，从中取最大值的那个叶子节点来玩。这个方法有点笨，既然这样，何必要用树呢？方法二，由每一个非叶节点汇总它下面的节点的收益和玩过的次数，如果下面节点也不是叶节点，那么也向下汇总。这样计算UCB值时，只需要计算直接子节点中的最大值，然后进入这个子节点，再去选择它的下一级节点的最大值，以此类推，最终选到的那个叶节点就是我们要玩的那台老虎机。方法二与方法一选出来的最大值不是同一个，因为，方法二多出一个假定，我要选的最大值是在我的最大分支里面。而实际上一个最有钱的城市里不一定住着最有钱的人，因此，这个假定不一定合理，不过无所谓了，就算找出来的不是最有钱的，也不会太平庸，何况我面对的是一个概率，而不是确切的多少钱，如果你这个分支整体上都表现很差的话，我凭什么相信你呢？方法二与方法一的分歧我们先放一放，以后实现时可以两种方法都试一下。总之，我们所说的UCT就是方法二。为了确定读者是否明白了UCT方法，我再把算法步骤写下来。UCT算法描述：对于已经建立的一棵树从根节点开始利用UCB公式计算每个子节点的UCB值，选择最大值的子节点若此节点不是叶节点，则从此节点开始，重复2直到遇到叶节点，play叶节点，得到收益，将这个收益更新到该节点及它的每一级祖先节点上去回到1，除非时间结束或者达到预设循环次数从根节点的子节点中挑选平均收益最高的，作为最佳点如果有疑问，可以先跳过下下一节，那里会有一个比这更复杂的等着你。UCT之于围棋如果把UCT用于围棋，我们会面临两个问题：一，UCT的树是已经建立好的，而对于围棋，初始情况下是没有树的，树如何建立？二，围棋是黑白双飞轮流下子，这个又当如何考虑呢？下面解决这两个疑问。首先，如果我们假设（注意仅仅是假设），事先建立起了一棵庞大无比的博弈树，它的节点已经包含了全部的n层对局，就是任意下n手，得到的局面都已经出现在了这棵树的节点上。这个时候，我们不就可以利用UCT进行搜索了吗？不错，但是这个时侯最多也只能搜索n层，你做的还不够。而且，大部分节点你根本来不及去使用，为何要预先把它们造出来呢？因此，我们一开始建立根节点，再为根节点建立它的第一层子节点，除此之外我们不再预先建立子节点，而仅在需要的时候再建造。这个时候我们开始寻找这棵树的最大UCB值的叶节点了，就用上一节中的UCT算法，遇到叶节点后，我们开始玩它，得出了一个胜负结果，然后更新它的祖先节点，直到此时，算法的进行与UCT一模一样，现在又开始下一轮寻找最大UCB了，假设找到的还是上一轮的那个节点，我们发现，它竟然是已经被玩过的，与上一节的UCT差别就在这，玩过的我们不要，我们为它生成它的下一层子节点，然后继续用UCT的方法寻找最大的UCB值，然后继续玩。这里的玩，就是指来一次模拟对局，现在我们发现按这种方法，其实每一个节点所代表的局面，最多只进行一次模拟对局，因为下次再选中它时，就会继续深入到它的子节点了。这再一次印证了UCT的思想，不要最强的节点，只要最强的分支。因此单个节点由于运气表现不好时，只要整个分支表现好，还是有机会的。我们能够建立这棵树了，那么双方轮流下子的问题怎么解决呢？很简单，每一层子节点所属的是黑子还是白子这是可以知道的，所以我们在更新胜负结果数时，只更新对应颜色的胜局数。举个例子，你代表的是黑色的节点，你下面的节点向你报告，黑方胜利，那么你把自己的玩过的局数加1，胜利局数加1，然后往上报；而如果下面报告说白方胜利，那对不起，你把玩过的局数加1，胜利数没你的份了。按照这样的方式汇总胜负数，在寻找UCB最大值时，就刚好是符合双方都走最强应对的原则。因为每方只记录自己这方的胜利数，选择的时候，都是选使得自己这方胜率最大的节点。按照这样的算法，我们有理由相信，mogo能走对任意步数的征子，而实际上它的确能走对。这样看来，UCT算法用在围棋AI上，恰好实现了一种高明的剪枝，而且它用的是循环而不是递归，它的棋力跟循环次数有关，而不像传统程序一样由递归深度来控制。我仍然给一个算法说明，来检验一下读者是否看明白了：UCT应用于围棋的算法描述：由当前局面建立根节点，生成根节点的子节点从根节点开始利用UCB公式计算每个子节点的UCB值，选择最大值的子节点若此节点不是叶节点，则从此节点开始，重复2直到遇到叶节点，如果叶节点曾经被模拟对局过，为这个叶节点生成子节点，从此节点开始，重复2否则对这个叶节点进行模拟对局，得到胜负结果，将这个收益按对应颜色更新到该节点及它的每一级祖先节点上去回到1，除非时间结束或者达到预设循环次数从根节点的子节点中挑选平均收益最高的，作为最佳点实际运用中，不必每次从头建立根节点，只要把上一手棋选择的节点作为根节点，其他分支简单抛弃掉，因为它们在实际对局中不会再用到了（这好像浪费掉了因不同手顺而产生的同一局面的统计结果，不过我还不知道如何解决同局不同顺的问题，先不管它了）。看完这个介绍，有没有想要自己实现一个类似于mogo的程序呢？貌似现在mogo的源代码还没有公开，公开源代码的有名的程序叫gnugo，基于模式匹配的，那个复杂呀，棋力还不行，远不及mogo的优雅简单。等我真的做出一个实现时，我会补上下一篇的，现在先向读者说再见了。
本文已收录于以下专栏：
相关文章推荐
日，Google Deepmind在Nature上发文宣布其人工智能围棋系统AlphaGo历史性的战胜人类的职业围棋选手！这条重磅新闻无疑引起了围棋界和人工智能界的广泛关注！3月份A...
日，Google Deepmind在Nature上发文宣布其人工智能围棋系统AlphaGo历史性的战胜人类的职业围棋选手！这条重磅新闻无疑引起了围棋界和人工智能界的广泛关注！3月份A...
围棋程序=围棋数据结构+围棋算法e.g.各种典型的棋局或对弈程序=棋盘的数据结构+各种典型的下棋步骤
以下经验只针对北京的滑雪场，阅读对象仅限从没滑过雪的人。我不说滑雪的感受，那些你们自己滑的时候去体验。我只探讨如何花尽量少的钱享受尽量多的乐趣。 选周一到周五去，不要在周末。因为一，周末票价贵一点，二...
代码先公布：http://download.csdn.net/source/891878到现在为止，我只实现了一个棋盘，确切的说是在棋盘上随机走棋的速度测试程序，我借鉴了lib-ego，在上面做了一些...
上次一个网友建议我用遗传算法，不过当时我没有找到合适的遗传因子，其实根本原因是我那时候正在手工测试程序的棋力，我自己和程序下，发现问题，然后看看怎么改进。这个过程中其实带有太强的主观色彩了，直到一周前...
他的最新文章
讲师：王哲涵
讲师：王渊命
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)围棋AI为什么这么强 强在哪里？（下）_棋牌_新浪竞技风暴_新浪网
围棋AI为什么这么强 强在哪里？（下）
大桥拓文六段
文章来源：微信公众号&找借口安静
原址：http://diamond.jp/articles/-/134617
原题：AI囲碁はどこがどう強いのか、大橋六段がその‘思考法’を解説
作者：大桥拓文 六段
点击查看上篇&
颠覆围棋百年常识的AlphaGo
通过AlphaGo的下法，来探索一下AI的“思考法”
在AlphaGo左右互搏的对局中，经常会看到如图1所示的点三三。
点三三的手段在人类的常识中只会出现在终盘阶段，在布局阶段就早早点三三被认为是“恶手”，是绝对不能选择的一手棋。
为什么呢？
我们再下8手棋在进行说明。
在人类的定式里，点三三之后的定型如图下所示，▲基本上可以说是黑棋的地盘。黑棋得到的实地不到10目的样子。而白棋则获得了相当的厚势，这个厚势有10目以上的价值所以得出“白棋有利”的结论，这是人类在100年以上的研究中得出的围棋常识。
但是AlphaGo依旧淡定地选择点三三，让白棋形成厚势。在人类的固定思维里，黑棋得到的目数也只不过10目不到，而相较于白棋的厚势，虽然没有利用好厚势的话很有可能没有价值，但是一旦用好了可能会有50目以上的价值。
在布局阶段，判断厚势的价值是非常困难的事情。对此，人们很少在布局阶段就早早地选择点三三。但是在AlphaGo的对局里，经常会看到它早早地点入三三。是不是觉得白棋的厚势必定要比黑棋10目不到的价值要小呢？
AlphaGo对未来和风险的判断是否准确
我们可以得出，AlphaGo在判断厚势，以及对未来的风险性上，比我们人类的判断要深刻并且准确。在庞大的对局数中得到的经验，就已经远远的超过了人类。
2017年的最新版AlphaGo的最大特点就是点三三，这手棋对人类来说是一个非常有风险的棋，并且经常看到我们很难理解的手段。现在职业棋手都纷纷开始模仿点三三，并且成为了一个流行的下法。而点三三的成功率，目前看来还是喜忧参半。
棋手们每天在研究AlphaGo的棋谱，不仅对AlphaGo的强大感到震惊，但是我们却很难模仿AlphaGo的棋。虽然AlphaGo比人类强大已经成为了事实，但是人类模仿AlphaGo的棋反而有可能适得其反。
我们现在是否已经追不上AlphaGo了，AlphaGo左右互搏的棋到底是不是好棋，这些都还是个未知数。另外，AlphaGo在一年前喜欢的手段，在现在基本上不再选择了。
现在除了AlphaGo之外，利用深度学习而开发的围棋AI也越来越多，花的精力最多的应该是日本的“DeepZenGo”和中国大型企业，腾讯公司的“绝艺”。而这两款AI下出的棋和AlphaGo稍有不用，围棋AI也像人类一样有个性。这个原因和数据库的不同，以及他们自己左右互搏的结果形成的。
就这样，可以体现出AI的围棋和人类的差别了。虽然很多围棋AI还比不上AlphaGo，但是已经达到了人类顶尖棋手的水平，他们也借此机会来尝试AlphaGo的下法。
所以在不远的将来，社会上的各种疑难杂症也会用同样的方法进行解决。我还是想比社会更早一步的观察AI，观察活跃在围棋界的围棋AI的进展，寻找人与AI和睦相处的道路。（完）
相关阅读：
加载中，请稍候...
加载中，请稍候...绝艺中邪般地连出破绽，失误堪称百年难遇
& &特约记者古柯报道&4月25日，由腾讯开发的人工智能“绝艺”对人类高手的“人机对抗赛”在腾讯围棋（野狐围棋）网上进行了第25、第26局比赛，绝艺在优势下意外不敌王垚六段，6连胜被终结。
& &王垚执黑先行，双方在右上角爆发激战，绝艺抢先出头，赢是将右上黑棋摁住，迫其苦活。而后抢得先手后又对中腹黑棋发起攻势，招法是令人熟悉的“绝艺流”，大局明晰，选点大气，缠斗中，王垚无奈放弃右边盘黑大龙，转而强杀左上白棋，但这实则是勉强之极的选择。
& & 但就在黑棋用强围猎左上白角的时候，绝艺突然出现了匪夷所思的失误，它本可在三路上尖一手做劫的，这样左上角白棋弹性很大，不易被杀，实战绝艺竟然选择二路粘，黑棋简单渡过连成一片后，左上角白棋无疾而终！这实在是绝艺棋局中难得一见的失误。
& & 即便如此，绝艺的形势仍然占优，只要正常进行下去的话，王垚依然无法逆转局面，但这天的绝艺就像中邪一般地接着出现失误，它只需正常收官即可获胜，而且，这也是围棋AI的强项，因为一旦它判断形势占优，其后的着法都极其稳健，甚至不惜让步。可绝艺在这盘棋表现十分反常，不知为何，它突然冲动起来，之后的着法都是典型的围棋AI发现局面已非后开启的疯狂模式，各种无理强杀、大方送吃都令人目瞪口呆，最后王垚大胜。
& & 局后，王垚表示：“不小心爆了个冷门，第一次和AI下棋感触良多，自认为是强项的布局和中盘在绝艺强大的力量面前惨遭碾压，本是完败之局没想到AI突然短路……后来我唯一要做的就是不点错鼠标就好！过程很糟糕结果却很美妙，期待下一次和AI的交手。”
& & 之后对韩国李志贤四段之局，绝艺正常发挥，稳扎稳打，平常以对，最后以1目半之优胜出。
& & 4月26日，绝艺将分别对阵范胤六段（单身情歌）和谢尔豪四段（终结者5），欢迎棋友们观战！当前位置： &
聂卫平：绝艺下出名局感觉 人类现在已很难赢AI
17:01:07 & &腾讯体育 &
精彩高清图推荐：