主题：关于MoGo -- 杜其衍

http://www.computergo.net/forum/tag.php?name=mogo

这里有malaybear写的《MoGo的故事》。西西河不鼓励转贴，有感兴趣的看完之后，我会删除，只保留链接。

MOGO的故事1

有幸见证了今年风头正盛MOGO的成长，而且大家都对它的算法很感兴趣。我就将一些MOGO有趣的故事吧。 MOGO的诞生先从王一早说起吧。一早是北大数学00的学生，之后来Ecole Polytechnique学习应用数学硕士（Polytechnique是法国的清华）。看到他的名字，我总是不由自主地想起鲁迅刻在书桌上的那个‘早’字。事实上，一早很聪明也很勤奋，做事认真一丝不苟。事实上，mogo中他编写的代码可读性最强。2006年4月，他在lri（法国信息技术研究室）作了毕业实习，和Sylvain Gelly（当时还是在读博士）一起工作。因为一早他从小热爱围棋（我的围棋就是他教的，哈哈），就开始尝试计算机围棋的编写。在我看来，计算机围棋和象棋相比，主要难点在于没有一个好的评估函数（Evaluate function）。在国际象棋中，如果一方损失了大子，如后，或者子力没有及时展开，那么形势很可能就一边倒了。所以评估函数往往是各个子的加权平均，加上每个子可以攻击到位置，再加上一些修正项。有了评估函数，就大大简化了搜索。如果评估函数是100%精确的，只要进行一次max min的搜索找最大值就可以了。即使评估函数只是近似，也可以省去很多无用的搜索。但是在围棋中，据我所知，还没有一个令人满意的评估函数。在这种情况下，大家就提出用MC模拟来代替评估函数。但是问题又出现了，MC模拟的收敛速度是1/sqrt(N)，走不能只模拟不搜索其他可能的棋步啊。这就是一个典型的Exploration vs Exploitation的问题。在Bandit问题中，UCT算法是相当不错的。当N(模拟次数)趋于无穷时，最好的分支和其他分支的模拟次数分别是N和LnN量级。MC和UCT的结合产生了MOGO的雏形。 在06年6月份，MOGO的雏形就完成了。一早邀请我们和MOGO对弈，来寻找bug。当时MOGO棋力很差，在9x9的棋盘上，连我这个只学了2个月围棋的菜鸟都下不过。（想想现在，我都已经没有和mogo下棋的勇气了）

MOGO的故事2

MOGO的MC改进 在棋魂中，佐为，塔矢都在追求着神之一招。我不明白神之一招的确切含义，但是在电脑围棋这个领域里，大家确实是不断创新，不断改进，来挑战人对围棋的垄断。 Random MC部分前面已经说过了，用MC模拟来代替评估函数，但是问题是好比两个高手下棋，下了一半，让两个不会下棋的门外汉来胡走一气，直至终局，来判断之前高手下棋的形势。这总是说不过去的。一早在这里做了一个关键的改进。 即使在高手下棋中，除了开局和突然投入对方阵地的棋，大家一般都是使用飞，长，断，连，尖，冲，立等围绕着自己已有棋子和对方的棋子做文章的棋，所以一早让MC模拟部分只能做这些固定的形。就好比是高手下棋之后让两个庸手下至终局，这样评判的效果比两人胡下，要好太多了。这个改进立竿见影，MOGO的棋力立刻可以和已有的电脑围棋程序一较高下了。 之后，就是对MC部分的微调了，可以想象，当MC部分越智能，他给出的终局结果越有意义，但是相应的运算时间就长，模拟次数就少了。为了找到这两者之间的平衡，光是我看到MC代码，就有45种，一早和sylvain以及之后的开发者，不停试验，不断改进。 UCT部分事实上，在现在的MOGO程序中，已经不使用UCT算法了，而是代以很类似AMAF算法。之所以换算法，原因也很简单，使用AMAF算法的围棋程序对UCT的胜率超过50%。

MOGO的故事3

基于MC的围棋程序相对于基于围棋知识的程序，最大的好处就是，随着电脑运算能力的提高，MC围棋的棋力也是水涨船高。大家都熟知的摩尔定律--CPU的性能每18个月提高一倍，价钱下降一半。我记得几年前，大家还热热闹闹的讨论摩尔定律是否能持续下去--因为随着IC尺度的缩小，散热，量子效应都成为难以逾越的瓶颈。但是现在看来，这个定律通过另一种方法持续下去了--多核技术。（插一句题外话，Playstation 3以他强大华丽的9核，令人乍舌的价格，不到4000人民币，出人意料的找到了除了游戏迷外新的粉丝--并行运算的实验室） 判断一个围棋程序优劣的最佳方法就是相互下棋看赢棋率，但是这很耗时间。所以大家选用了另一个紧密相关但可以实时监测的参数--每秒MC的次数作为一个优化的目标。在单CPU的优化有所突破之后，下一步自然是并行运算。事实上，MC是天然适合并行运算的。 并行运算又分为两个层次--多核和计算机组。两者的区别在于多核的计算机共用相同的内存（shared memory multiprocessor），而计算机组的内存也是相互独立的（他们之间的信息传输需要通过mpi, message passing interface for distributed-memories ） 这两个层次在MOGO都使用了，但是都有各自的问题。 个人理解，MPI的关键在于算法，SMP的关键在于技术。 MPI我就举一个简单的例子。由于不同CPU有各自的内存，而MOGO的MC会不断的改变树（增加节点），所以各个CPU中的树是不一样的。他们不停的进行update，但是如何把两个不同的树合并，就成了难点。比如说，在CPU1中，某个节点搜索了x次，在CPU2中，这个节点搜索了y次，那么在两棵树合并之后，这个节点搜索了多少次呢？ 我们假设搜索了f(x,y)次，我们可以做一些基本的判断 1 对称性 f(x,y)=f(y,x) 2 一次齐次函数 f(kx,ky)=kf(x,y) 3 f(x,x)=x 如果两棵树是全同的，那么合并之后也应该是一样的 在这样的基本架设下，有哪些备选函数呢 max(x,y), (x+y)/2,... min(x,y)也是满足这些性质的，但是这个函数是不合理的。（为什么？作为大家的思考题吧） 还有一大类函数满足，p模平均 [(x^p+y^p)/2]^(1/p) 当p趋于无穷时，这个函数趋于max(x,y)，当p=1,就是算术平均 至少我们就有了一个参数，可以通过调节p，使效果最好。

MOGO的故事4

代码优化 在版上有人问怎么样能提高每秒MC的次数。就我个人的理解是，首先考虑算法优化，如果把一个复杂度n^2的算法变成n的算法，提高的效果是用其他方法难以达到。之后考虑并行运算（至少SMP），表现一般可以提高数倍。最后考虑代码优化，一般可以将运行时间缩短到原来的50%-80%。 我之前曾说过一早的代码可读性最高，这倒不是因为其他人的编程习惯不好(比如，Sylvain现在在google工作，他的代码是专业级的)。一个重要原因是之后大量使用了代码优化的技术（如mask，想象一下代码中十六进制数和位操作满天飞，可读性能好吗？）。对于国际象棋，位棋盘是很天然的，8x8的棋盘，两个长整就可以表达，之后所有的运算都是位运算（很少用循环）。围棋基本上还是用数组实现的，当然MOGO中也作了一些类似于位棋盘的优化，以节省时间。 在这种常规招数使用完之后，我们就需要特殊的工具来优化代码了。我强烈推荐Oprofile，尽管gprofile是自带工具，使用方便，但是不支持multithread。Oprofile可以得到每个函数运行的时间（或者每行代码），cache miss的频率，等等来判断程序的瓶颈。我举一个例子 如果我们发现在程序中，一个整型x，下面这行代码占了整体运行时间的20%（这行代码频繁运行） x=abs(x); 我们可以做怎么样的优化呢？在C++中，abs在标准函数库中大概是这样的 if (x<0) x=-x; return x; 这样的代码有什么不足呢？这要从CPU pipeline说起。由于一条指令往往不能再一个CPU时钟周期内解决，CPU在执行时，把一条指令的运行分为读入，解码，提取内存内容，运算，写入内存内容几步。在前一条指令完成读入环节进入解码，后一条指令也就开始读入了。这样可以大大提高指令的运行效率。但是前提条件是这些指令之间的相互顺序是可以调换的。而if就不是这样，在if语句运算完成之前，CPU无法预知下一条指令是在if之内还是之外。 当x是整型时，我们可以用位运算代替if，代码如下 static inline abs(int x){ int y=x>>15; x=(x-y)^(-y); return x } 这样这段代码效率会提高5倍左右。

MOGO的故事5

mogo还可以走多远？ 让我们先从深蓝聊起吧。去年国际象棋世锦赛时，我正好和朋友在看网络直播，同时一个朋友在笔记本上打开了国际象棋程序，让程序来计算最强走法，然后两位国际大师的招数，和电脑指出的一模一样，大家啧啧赞叹，不愧是国际大师，走得和电脑一样。这个给我的印象非常深刻，在国际象棋领域，人脑和电脑的对抗已经没有任何悬念了。 这中间，不能不说到卡斯帕罗夫对深蓝（以及更深的蓝）之间史诗般的交手。但是在这件事的背后，有着另一个故事。在我看来，这是一个天才的marketing策略。在当时，ibm被挤在超级计算机销售的前三名之外（第一名是大名鼎鼎的clay，紧随其后的是两家日本公司），在其他领域更是被microsoft抢走了IT王者的宝座。可以说88年到95年ibm是一个忧郁的巨人。而国际象棋在西方世界有着巨大的影响力，以电脑对抗人脑，必然带来极大的关注，证明它制造的超级计算机的性能。在结果来看，ibm顺利成为超级计算机的销量冠军，它的股票也一飞冲天，从95年的20美元涨到了120美元。 说了这么多废话，核心就在于，尽管围棋确实比国际象棋难很多，但是围棋和国际象棋在人工智能上的差距却更有可能是两者投入差距的体现。围棋本身的市场集中在东亚，受关注程度也远不如国际象棋，使得很少有企业愿意投入，光靠实验室的研究是很漫长的。（如果google愿意投入财力和人力，我相信一定会带来电脑围棋的飞跃） mogo刚在前几天受让7子战胜了周俊勋，让6子战胜了职业初段，又在9x9上战胜了一个职业二段。大家也很关注mogo以及它所代表的mc+uct算法可以走多远。 mogo的uct+MC的方法是到目前为止计算手筋和局部战斗最好的算法，从它在9x9棋盘上表现就可以看出。 mogo现在的棋力超过了它所有的开发者（一早大概是业初段，arpad rimmel大概是kgs 1k，Sylvain Gelly，Hoock Jean-Baptiste，olivier Teytaud都是围棋的门外汉） 但是mogo有自己的局限，如果没有新的算法上的突破，恐怕很难跳出业余的段位。