主题：关于MoGo -- 杜其衍

[FLASH]http://www.xueqi.cn/swf/WeiqiP.swf?ID=89cdb445-fd57-42a3-a0ff-0b8faa2d60af&type=qipu[/FLASH]

http://sjeng.org/leela.html

不过这个Leela是要钱的，支持19路棋谱对弈的要50欧元。好在还有个Leela Lite，可以下9路和13路。

晚上观战，无意中顺着高手指点，欣赏了主席和政委、教头的精彩对局，大为赞叹。不禁向主席推荐了这款Leela，顺便看了一下介绍，发现点击工具栏第二个按钮，还可以下升降对局。我说怎么默认一开始它就要让我5子呢。好吧，我就跟它较量较量，从25级升起。。。

本届西西河史克郎杯大赛前几轮下来，选手们纷纷表示，这样下棋，赛后还复盘，大家水平普遍提高。一旁观众呼应曰：就是看棋的也有提高啊。确实，前天晚上俺在观看史教头与lixwh对弈时，就幽幽地问了一句，221下在224位如何？经对弈双方及围观众位高手审核，暂定为好手。我不禁感叹，西西河大赛确实有助于提高水平啊，连我这25级的都提高了。想当初，我自负下棋多年，理所当然达到了9级水平，谁知某次在新浪上一气下了好几盘，降到25级去了。从此俺就告别了棋坛。。。

多亏了西西河大赛，让俺又恢复了信心。在和Leela Lite的交锋中，俺充分利用让子优势，取得节节胜利。让4子了、3子了、2子了。软件显示，我已经升至9级啦。俺决定一鼓作气，向8级进军，不料这次冲锋却异常坎坷。请看大屏幕：

没想到转贴也能得花，那就再帖一个。这是小说《墨绿》的作者“万精油”写的一篇，其中谈及：“深蓝的主要创造者许峰雄放出话来：十年之内可以看到战胜人类最高手的围棋程序。”

http://www.zhipingyou.com/qqsh/index.php?PHPSESSID=32d9701124e9636f89d06020a79f009c&topic=1004.0

人机对话

于: 三月 29, 2008, 10:37:28 am

--------------------------------------------------------------------------------

人机对话

“人战胜了机器”，这是本周美国围棋协会电子杂志的一个小标题。说是一个职业五段

在九乘九的棋盘上以二比一战胜围棋程序ＭＯＧＯ。读到这里，稍微有一点围棋程序常

识的人或许会问，有没有搞错？这说的是围棋程序吗？最好的围棋程序不是都要被让十

几子的吗？不会是国际象棋或五子棋吧？或者又是墨绿那样的虚幻东西。千真万确，这

是实实在在的围棋程序，不是只存在于虚幻世界里的墨绿。

说到墨绿，就必需要提到深蓝甚或它的前辈，浅蓝或者淡黄。我们还是从头说起。

让计算机下棋一直都是人工智能的一个重要课题之一。先是从简单的跳棋，五子棋之类

的搞起，后来搞国际象棋，围棋。虽说这些程序属于人工智能范畴，但实际上它们并没

有多少“智”的部分，主要部分都是在可行范围内搜索。各种研究也大都是怎样使搜索

更快更有效。它们缺乏“智”的部分的根本原因是我们自已就不是太清楚人类以怎样的

形式思考。比如你写一个名字问一个计算机系主任，这人是不是他系里的教授。系主任

马上就可以回答是或不是。如果你问计算机，计算机也可以马上正确地回答是或不是。

但计算机的方式是把这个名字与系统里所有名字比较以后得出的答案。计算机搜索很快，

全走一遍几乎可以瞬间完成。但我们知道系主任是不可能在短时间内把系里所有教授的

名单过一遍的。类似的问题还可以更进一步，如果有人拿一张照片问你这辈子有没有见

过这个人。一般情况下，你会很快告诉他有或没有。可是我们不能想象你在短时间内把

你这辈子（包括孩提时代）见过的人都检查一遍。那么你是怎样得出结论的呢？我们对

此还不是完全清楚。

懂计算机算法的人会说，计算机也不用把全部名单走一遍。它可以搞一种映射，拿到名

字后直接到映射位置找这个人（所谓Hash Table）。或者把东西分类按类别排除，几下

就找到相应的位置（比如K-D Tree）。或者在各种目标间加上大大小小的联接，然后按

联接排序（比如Google的PageRank），诸如此类的聪明方法都是人类在不懂得自已怎样

思维的情况下设计出来的，试图达到人类的思维效果。这些方法有用也很有效，在很多

方面都有应用。但当要搜索的空间实在太大（做表已经行不通）时，这些方法就不灵了，

速度不够，内存也跟不上。

人的大脑当然也不能存下这些大空间的东西。但人的大脑有一个很大的优点，那就是

“模式识别”（Pattern Recognition），不需要用到大搜索空间。前面的例子说明一个

人看见一张照片，几乎马上就可以知道他以前有没有见过这个人，不需要把他从前见过

的人都过一遍。再举一个真实的例子。在去年我参加的一个中国人的新年晚会上，有人

用黑管吹出［大海航行靠舵手］的曲子。虽然几十年没有听过这个曲子了，但下面的几

乎所有人都马上跟着哼起来。大家不需要在大脑里把以前听过的所有曲子过一遍来检索

到这个曲子。你或许要说这些东西大脑里都存着，只不过它有很快的方法搜到那里。这

“很快的方法”就是我们想要知道的。但我说的“模式识别”还不只是这些。再举一个

没有事先储存的例子。比如你去一个你常去的网站，打开网站后出现一整页的标题或文

章（以前从来没见过）。如果里面有任何地方提到你的名字（或ＩＤ），你几乎马上就

会注意到，并不需要你去一个字一个字地读整页内容。这种“模式识别”能力计算机

（或者说现在的人工智能）是没有的。所以，遇到大空间搜索问题计算机就显得很弱。

再回到下棋的问题。下棋的时候棋盘上可走的地方很多，但下棋的人并不是每种走法都

去考虑。比如一般情况下就不会有人去考虑在死角位置上走一子会有什么结果。那么哪

些位置需要考虑，哪些位置不需要考虑，这就是“模式识别”问题。计算机没有这种功

能，只好所有的位置都考虑，于是就产生了无穷大的搜索空间问题。几十年以前的国际

象棋程序就处于这种情况。因为大面积搜索不可行，就只能用一些自已设计的判别模式

进行选择性地搜索（模仿人的思维）。选择不见得对，搜索又不彻底，结果当然不会好

到哪里去。所幸的是，计算机领域里有一个莫尔规律（Moore's Law），说是计算机的速

度（以及别的相关能力）每一年半就会翻倍。几十倍上百倍地翻下去，以前速度和空间

不可行的搜索后来就变得可及或可行了。到了一九九七年，ＩＢＭ的深蓝就硬是用“硬

搜索”（Brute Force）打败了人类国际象棋最高手Kasparov。当然深蓝还请了一些国际

象棋专家指点判别程序，但主要靠的还是硬搜索。

讲围棋怎么扯到国际象棋去了？我们现在就回头来讲围棋。

深蓝的方法可不可以平移到围棋上来？一般的共识是不可以。这里面有两个问题。

第一个是搜索空间。围棋的变化空间比国际象棋大很多数量级。有人估计围棋的变化空

间是１０的１７０次方，相应的国际象棋变化空间是１０的１２０次方，差别是１０的

５０次方。古人在形容很大的数的时候常用的一个词是“恒河沙数”，因为沙是他们知

道的最小的东西，而恒河是它们知道的最大的河。按《孙子算经》大数单位算，恒河沙

数等于１０的５２次方。这是受佛经影响的抽象单位，实际恒河沙数没有那么大。按物

理学家卡尔·萨根估计，地球上所有沙滩上的沙粒数目可能是10的20次方。就算恒河占

其中十分之一，也就是10的19次方。大至算一下，如果恒河中的每一颗沙都是一条恒河，

把这10的19次方条恒河组合成一条大恒河。这大恒河的沙数是10的38次方。围棋复杂

度与国际象棋复杂度的比例就是这大恒河与其中一颗沙的比例再乘上一万亿倍。１０的

１７０次方可以与什么来比呢？现代人知道原子当然比沙要小很多，最大的东西也不能

大于可观测到的宇宙。有人算过，可观测到的宇宙中的原子个数大约是１０的８０次方。

假设每个原子就是一个宇宙，把这些所有宇宙中的原子个数加起来仍然不够１０的１７０

方。有了这些背景，从现实意义来说，我们完全可以把围棋的变化空间１０的１７０次

方当成无穷大，可望而不可及。当然，围棋程序并不需要搜索到底，只需要搜索到人类

下棋时搜索的深度就可以了。

如果要让一个围棋程序达到与深蓝同样深度的搜索，对计算机速度的要求是一百万倍以

上。这不是一两个莫尔规律可以解决的问题。

第二个问题，也是更严重的问题，就是判别好坏的问题。国际象棋的好坏可以有比较明

显的判别方法，比如吃掉对方的皇后基本上应该算是好棋。事实上深蓝的判别更简单，

搜索到几十步以后数子。如果某种走法剩的子数多，这种走法就算好（子数当然是加权

过的，比如皇后算九个兵之类的）。可是围棋没有很好的优劣判别方法。一个子的好坏

或许要到几十步以后才显示出来，或者与盘上十几格以外的子有关（比如征子的情况）。

而且吃子也不见得就一定是好事。

搜索空间大和判别优劣难这两个问题加起来，几乎就完全否定了深蓝的方法在围棋上的

应用。

由于意识到“硬搜索”在围棋上行不通，几乎所有围棋程序设计者都选择走“人工智能”

的路。也就是模仿人类的思维，搞模型识别，算死活，背定式等等。由于没能真正搞清

楚人类的思维方法，这些模仿都不是很成功。这些方法产生的最佳程序仍然处于很初等

的阶段，以至于我这样的一般围棋爱好者左手让它九子也没有问题。很多人甚至认为有

生之年看不到战胜人类最高手的围棋程序了。比如台湾的应昌期先生就没能在他的有生

之年看到哪怕是战胜业余初段的围棋程序，他放出的一百万美元大奖至今也没人能领。

在大家对围棋程序的前途悲观失望的时候，深蓝的主要创造者许峰雄放出话来：十年之

内可以看到战胜人类最高手的围棋程序。他的观点半年前发表在ＩＥＥＥ的杂志上。如

果是别人放出这种话，我一定把它当成痴人说梦，不去理会。但许峰雄不是一般人，他

腰下插着深蓝的金牌，说话还是有份量的。他的文章至少值得一读。

许峰雄说大家现在对“硬搜索”在围棋程序上不抱希望，就象几十年前大家对国际象棋

程序一样。纯“人工智能”的路现在看来效果不是很好，而“硬搜索”却有很大潜力。

我们都清楚，只要搜的足够深，“硬搜索”产生出来的程序是可以很强大的，不信可以

去问一问Kasparov。深蓝的搜索深度是，普遍搜索１２层，特殊搜索４０层以上。据他

估计，一个围棋程序要达到深蓝的搜索深度必需搜索１０的１９次方个节点。这看起来

是一个可望而不可及的数，但他认为是可以有办法把它拿下的。他的这个结论主要有四

个支撑点。

第一点，用Alaph-Beta搜索。Alpha-Beta不是什么新东西，计算机科学家很早就发明出

来。其主要思想是，在搜索某个节点时发现如果继续搜下去最好结果也不会好于到现在

为止在别的节点上搜到的最好结果，那就没有必要继续搜下去。比如这一步棋让对方一

大块死棋变活，大概就没有搜下去的必要。这个Alpha-Beta搜索可以把搜索空间缩小到

平方根，也就是从１０的１９次方到１０的９。５次方。

第二点，加入零空间搜索。所谓零空间搜索相当于停走一步。我们看围棋比赛，偶尔会

听见观战者说这个时候即使白棋停走一步，黑棋也没得下，意思是白棋赢多了。零空间

搜索就是这个意思。由于国际象棋的特殊规则（有时停走一步反到有优势），深蓝不能

采用零空间搜索。但围棋完全可以采用零空间搜索。如果停走一步还有很大优势，则这

一路搜索就有很大价值（或者很没有价值，如果停走的是对方的话）。据他说加入零空

间搜索又可以把搜索空间开方。而且这个优势是深蓝没有的。

第三点，重复利用已有知识。比如一块棋活了，就不用老去算它的死活，除非附近有新

情况发生。这个“除非”在国际象棋上出现太多，因为棋盘太小，所以不好用。判断

“除非”所用的时间以及上下传递已知信息所花的时间使它的利用得不偿失。但围棋棋

盘大，很多时候一块棋的死活与别处无关，如果再用特殊硬件加速已知信息的交流，这

个优势在围棋程序上就可以很大。

最后一点又是莫尔规律。他说深蓝过去十年了。现在的新技术几乎可以把与深蓝有同等

能力的计算机放到一个ＰＣ上（深蓝用的是４８０个加有平行结构的超级处理器），再

过十年，速度又可以提高１００倍。假如再加上几百个平行结构的联接，则又可以提高

几百倍。

把以上几点加在一起，可以消掉在深蓝搜索范围内围棋与国际象棋的一百万倍的差别。

十年以后我们将会有一个与深蓝有同等能力的围棋程序。如果假设围棋职业棋手与国际

象棋职业棋手搜索的深度一样的话，那么这个程序就可以打败人类最高手。

许峰雄是高手，他的话应该有一定的可信度。他说他的研究生已经开始着手这方面的工

作了。但是他的文章里始终没谈判别好坏问题，而我认为这是一个关键问题。因为没有

搜索到底，始终都存在判断好坏的问题。搜索到１２步或者４０步以后怎样决定结果的

好坏。四五十步棋的时候中盘或许刚开始，怎样判断什么是好什么是坏。这个问题大概

得输入一些专家知识。相当于当初深蓝让国际象棋大师作顾问。许峰雄现在在中国，找

专家当然不是什么难事。

对这个没搜索到底的问题有疑虑的人还不少。象我这样的人只是问一问，另外有些人就

要想法设计四十步以后的判断算法。还有些人更进一步，干脆搜索到底。且慢，你刚才

不是说搜到底是无穷大吗？怎么有人可以搜索到底。这又要扯到人工智能的另一个方法：

模拟。

围棋是完全信息游戏。不象桥牌或Poker，总有未知因素。桥牌要考虑牌形分布，大牌的

位置等等。Poker的未知因素就更明显，虽说手上的２，７是最烂的牌，但如果Flop出来

７，７，２，你的牌马上就变成强牌。围棋没有这个问题，对弈双方可以使用的一切招

术以及结果都没有未知成分。可是，虽说没有未知成分，但因为没有人能够算到底，这

些公开的信息并不是清楚地摆在双方的面前。想得深的就多一些信息，想得浅的就少一

些信息。下棋时对方给你设圈套就是只望你算不到那么深。好象一口井，只有竹杆够长

的人才能打到里面的水。有些问题，比如围棋程序问题，深一点或许不够，希望能深入

到底。可是太多的路径选择又不允许每条路径都走到底。这时候我们就采用一种叫做随

机模拟的方法。其基本思想是，虽然不能每条路都走到底，但选择一些路走到底是可以

的。在每个分岔点我们都随机的选一些岔道走下去。走到底以后看结果。如果某个结点

后随机选的岔道都显示这是一条好路，从概率上来说这是一条好路的可能信就很大。这

种随机模拟的算法在很多方面都有应用，尤其是在物理和工程上。第二次世界大战时美

国的一批造原子弹的物理学家（费米，冯。诺曼等）给这种随机模拟方法取了一个响亮

的名字叫Monte-Carlo。这是欧洲以赌场闻名的一个城市名字。这种算法和赌场都靠大量

的随机结果为其工作原理。

本文最开始说的围棋程序ＭＯＧＯ就是基于这种原里。ＭＯ就是Monte-Carlo的前两个字

母，ＧＯ就是英文围棋的名字。这个程序不需要背任何定识，做任何模式识别。只是随

机地在棋盘上选许多点，走一步以后再随机的选许多点，一直这样把一盘棋下完，然后

数子。因为一直走到底，胜负已经很清楚，不需要任何判断。如果某个点以后随机选择

的路径以最大胜率结束，这个点就被认为是最有利的点，程序就选这一步。顺便说一句，

ＭＯＧＯ的前辈（第一个在这方面有成就的程序）叫做疯棋（Crazy Go），我觉得这个

名字恰如其分。这个看似疯狂而且简单的原理居然弄出惊人的结果。首先是在计算机围

棋比赛中战胜了所有其它对手。在此之前，计算机围棋程序的冠军几乎一直都是陈志行

教授写的［手谈］。陈志行教授自己是围棋高手，又是计算机专家，把自己的许多想法

都注入了［手谈］，所以，它能打败同类的其它程序。［手谈］可以说是一个典型的

“人工智能”程序。没想到这个“人工智能”高手遇到这么一个没有任何“智能”成分

的傻瓜程序却无能为力。这一方面说明［手谈］的所谓“人工智能”还有很多缺陷，另

一方面也说明ＭＯＧＯ的算法有一定道理。

不光是对计算机程序，这种完全随机的模拟方法对人类也有优良表现。正规的１９路棋

盘现在对它们来说还太大，于是从小棋盘开始。中国旅欧职业五段棋手郭娟与ＭＯＧＯ

的前身疯棋在小棋盘上下了很多盘。在７Ｘ７的棋盘上，疯棋执白从来不输，执黑也偶

尔能赢。在９Ｘ９的棋盘上与郭娟下了１４盘，９胜５负。成绩还是很拿得出手的。

ＭＯＧＯ比疯棋又进化了一步，在最近的一次计算机围棋程序比赛上，ＭＯＧＯ与疯棋

的新版疯子（Crazy Stone）进行冠亚军决赛，ＭＯＧＯ大胜。看来ＭＯＧＯ要比疯棋强

很多。所以当另一职业五段２胜一负战胜ＭＯＧＯ时就成了大新闻。

出于好奇，我把ＭＯＧＯ与疯子的决赛棋谱调出来看了一下，同时发现一些可喜和可忧

的部分。可喜的是ＭＯＧＯ似乎能产生有很强的大局观的棋。对方在角上压过来时它居

然会脱先去占大场，而且这个大场不是三路或四路，而是在五路上。只看布局，很有武

宫正树宇宙流的风格。在对杀时还能走出单立这样的好棋。可忧的是它毕竟没有什么智

能，走到后来简直惨不忍睹，或者说愚不可及，比一个刚学棋一天的人都不如。毕竟它

们是一点智力都没有。从这一点上看，这条路还有得一阵走。另外，从小棋盘到大棋盘

进发的问题，还是由莫尔规律来掌握其进度吧。

写到这里，正好看到记者采访聂卫平谈到围棋程序，聂卫平说围棋程序不是还处在随便

一个人都可以让二十多子的水平吗？看来聂卫平需要有人给他更新一下有关围棋程序水

平的认识了。

ＭＯＧＯ与许峰雄的“硬搜索”都是朝非传统人工智能的方向走。如果有朝一日走出一

个没有任何智能却能打败人类最高手的程序，真的是一种悲哀。所以有人在围棋网络上

呼吁程序员们不要继续这种程序，要给人类留一块圣地。我想，挡是挡不住的，呼吁也

没有用。人们在前进的道路上总是要在不同的路径上进行探索。［手谈］是一条路，疯

棋又是一条路，还有别的许多路，我个人认为墨绿是更好的路。不同的路都走一走，才

知道哪条路好。从某种意义上来说，人类的进步不也正是一种Monte-Carlo过程吗？

ＧＯ，ＭＯＧＯ！ ＧＯ，ＭＯＲＥ ＧＯ。

－－万精油－－

二零零八年三月二十八日于波士顿西郊

注：有兴趣的读者可以到以下网址读到相关文章：

１。许峰雄：Cracking Go

http://spectrum.ieee.org/oct07/5552

２。ＭＯＧＯ与疯子对局

http://www.grappa.univ-lille3.fr/icga/round.php?tournament=167&round=7&id=2

３。墨绿

http://www.zhipingyou.com/qqsh/index.php?topic=280.0

最后编辑时间: 三月 31, 2009, 10:19:39 am 作者 万精油

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有自己的局限，如果没有新的算法上的突破，恐怕很难跳出业余的段位。