飞扬围棋

标题: [转帖]人机对话 [万精油] [打印本页]

作者: Fish 时间: 2008-4-1 09:12
标题: [转帖]人机对话 [万精油]
<h2>人机对话 [万精油]</h2><div class="t_msgfont" id="postmessage_287568">“人战胜了机器”，这是本周美国围棋协会电子杂志的一个小标题。说是一个职业五段 在九乘九的棋盘上以二比一战胜围棋程序ＭＯＧＯ。读到这里，稍微有一点围棋程序常 识的人或许会问，有没有搞错？这说的是围棋程序吗？最好的围棋程序不是都要被让十 几子的吗？不会是国际象棋或五子棋吧？或者又是墨绿那样的虚幻东西。千真万确，这 是实实在在的围棋程序，不是只存在于虚幻世界里的墨绿。 说到墨绿，就必需要提到深蓝甚或它的前辈，浅蓝或者淡黄。我们还是从头说起。 让计算机下棋一直都是人工智能的一个重要课题之一。先是从简单的跳棋，五子棋之类 的搞起，后来搞国际象棋，围棋。虽说这些程序属于人工智能范畴，但实际上它们并没 有多少“智”的部分，主要部分都是在可行范围内搜索。各种研究也大都是怎样使搜索 更快更有效。它们缺乏“智”的部分的根本原因是我们自已就不是太清楚人类以怎样的 形式思考。比如你写一个名字问一个计算机系主任，这人是不是他系里的教授。系主任 马上就可以回答是或不是。如果你问计算机，计算机也可以马上正确地回答是或不是。 但计算机的方式是把这个名字与系统里所有名字比较以后得出的答案。计算机搜索很快， 全走一遍几乎可以瞬间完成。但我们知道系主任是不可能在短时间内把系里所有教授的 名单过一遍的。类似的问题还可以更进一步，如果有人拿一张照片问你这辈子有没有见 过这个人。一般情况下，你会很快告诉他有或没有。可是我们不能想象你在短时间内把 你这辈子（包括孩提时代）见过的人都检查一遍。那么你是怎样得出结论的呢？我们对 此还不是完全清楚。 懂计算机算法的人会说，计算机也不用把全部名单走一遍。它可以搞一种映射，拿到名 字后直接到映射位置找这个人（所谓Hash Table）。或者把东西分类按类别排除，几下 就找到相应的位置（比如K-D Tree）。或者在各种目标间加上大大小小的联接，然后按 联接排序（比如Google的PageRank），诸如此类的聪明方法都是人类在不懂得自已怎样 思维的情况下设计出来的，试图达到人类的思维效果。这些方法有用也很有效，在很多 方面都有应用。但当要搜索的空间实在太大（做表已经行不通）时，这些方法就不灵了， 速度不够，内存也跟不上。 人的大脑当然也不能存下这些大空间的东西。但人的大脑有一个很大的优点，那就是 “模式识别”（Pattern Recognition），不需要用到大搜索空间。前面的例子说明一个 人看见一张照片，几乎马上就可以知道他以前有没有见过这个人，不需要把他从前见过 的人都过一遍。再举一个真实的例子。在去年我参加的一个中国人的新年晚会上，有人 用黑管吹出［大海航行靠舵手］的曲子。虽然几十年没有听过这个曲子了，但下面的几 乎所有人都马上跟着哼起来。大家不需要在大脑里把以前听过的所有曲子过一遍来检索 到这个曲子。你或许要说这些东西大脑里都存着，只不过它有很快的方法搜到那里。这 “很快的方法”就是我们想要知道的。但我说的“模式识别”还不只是这些。再举一个 没有事先储存的例子。比如你去一个你常去的网站，打开网站后出现一整页的标题或文 章（以前从来没见过）。如果里面有任何地方提到你的名字（或ＩＤ），你几乎马上就 会注意到，并不需要你去一个字一个字地读整页内容。这种“模式识别”能力计算机 （或者说现在的人工智能）是没有的。所以，遇到大空间搜索问题计算机就显得很弱。 再回到下棋的问题。下棋的时候棋盘上可走的地方很多，但下棋的人并不是每种走法都 去考虑。比如一般情况下就不会有人去考虑在死角位置上走一子会有什么结果。那么哪 些位置需要考虑，哪些位置不需要考虑，这就是“模式识别”问题。计算机没有这种功 能，只好所有的位置都考虑，于是就产生了无穷大的搜索空间问题。几十年以前的国际 象棋程序就处于这种情况。因为大面积搜索不可行，就只能用一些自已设计的判别模式 进行选择性地搜索（模仿人的思维）。选择不见得对，搜索又不彻底，结果当然不会好 到哪里去。所幸的是，计算机领域里有一个莫尔规律（Moore's Law），说是计算机的速 度（以及别的相关能力）每一年半就会翻倍。几十倍上百倍地翻下去，以前速度和空间 不可行的搜索后来就变得可及或可行了。到了一九九七年，ＩＢＭ的深蓝就硬是用“硬 搜索”（Brute Force）打败了人类国际象棋最高手Kasparov。当然深蓝还请了一些国际 象棋专家指点判别程序，但主要靠的还是硬搜索。 讲围棋怎么扯到国际象棋去了？我们现在就回头来讲围棋。 深蓝的方法可不可以平移到围棋上来？一般的共识是不可以。这里面有两个问题。 第一个是搜索空间。围棋的变化空间比国际象棋大很多数量级。有人估计围棋的变化空 间是１０的１７０次方，相应的国际象棋变化空间是１０的１２０次方，差别是１０的 ５０次方。古人在形容很大的数的时候常用的一个词是“恒河沙数”，因为沙是他们知 道的最小的东西，而恒河是它们知道的最大的河。有好事者粗略地估计了一下，恒河沙 数大概是１０的５２次方。大至说起来，如果围棋是恒河，国际象棋只不过是１００颗 沙。１００颗沙还不到一勺，而且是挖耳朵用的勺。１０的１７０次方可以与什么来比 呢？现代人知道原子当然比沙要小很多，最大的东西也不能大于可观测到的宇宙。有人 算过，可观测到的宇宙中的原子个数大约是１０的８０次方。假设每个原子就是一个宇 宙，把这些所有宇宙中的原子个数加起来仍然不够１０的１７０方。有了这些背景，从 现实意义来说，我们完全可以把围棋的变化空间１０的１７０次方当成无穷大，可望而 不可及。当然，围棋程序并不需要搜索到底，只需要搜索到人类下棋时搜索的深度就可 以了。 如果要让一个围棋程序达到与深蓝同样深度的搜索，对计算机速度的要求是一百万倍以 上。这不是一两个莫尔规律可以解决的问题。 第二个问题，也是更严重的问题，就是判别好坏的问题。国际象棋的好坏可以有比较明 显的判别方法，比如吃掉对方的皇后基本上应该算是好棋。事实上深蓝的判别更简单， 搜索到几十步以后数子。如果某种走法剩的子数多，这种走法就算好（子数当然是加权 过的，比如皇后算九个兵之类的）。可是围棋没有很好的优劣判别方法。一个子的好坏 或许要到几十步以后才显示出来，或者与盘上十几格以外的子有关（比如征子的情况）。 而且吃子也不见得就一定是好事。 搜索空间大和判别优劣难这两个问题加起来，几乎就完全否定了深蓝的方法在围棋上的 应用。 由于意识到“硬搜索”在围棋上行不通，几乎所有围棋程序设计者都选择走“人工智能” 的路。也就是模仿人类的思维，搞模型识别，算死活，背定式等等。由于没能真正搞清 楚人类的思维方法，这些模仿都不是很成功。这些方法产生的最佳程序仍然处于很初等 的阶段，以至于我这样的一般围棋爱好者左手让它九子也没有问题。很多人甚至认为有 生之年看不到战胜人类最高手的围棋程序了。比如台湾的应昌期先生就没能在他的有生 之年看到哪怕是战胜业余初段的围棋程序，他放出的一百万美元大奖至今也没人能领。 在大家对围棋程序的前途悲观失望的时候，深蓝的主要创造者许峰雄放出话来：十年之 内可以看到战胜人类最高手的围棋程序。他的观点半年前发表在ＩＥＥＥ的杂志上。如 果是别人放出这种话，我一定把它当成痴人说梦，不去理会。但许峰雄不是一般人，他 腰下插着深蓝的金牌，说话还是有份量的。他的文章至少值得一读。 许峰雄说大家现在对“硬搜索”在围棋程序上不抱希望，就象几十年前大家对国际象棋 程序一样。纯“人工智能”的路现在看来效果不是很好，而“硬搜索”却有很大潜力。 我们都清楚，只要搜的足够深，“硬搜索”产生出来的程序是可以很强大的，不信可以 去问一问Kasparov。深蓝的搜索深度是，普遍搜索１２层，特殊搜索４０层以上。据他 估计，一个围棋程序要达到深蓝的搜索深度必需搜索１０的１９次方个节点。这看起来 是一个可望而不可及的数，但他认为是可以有办法把它拿下的。他的这个结论主要有四 个支撑点。 第一点，用Alaph-Beta搜索。Alpha-Beta不是什么新东西，计算机科学家很早就发明出 来。其主要思想是，在搜索某个节点时发现如果继续搜下去最好结果也不会好于到现在 为止在别的节点上搜到的最好结果，那就没有必要继续搜下去。比如这一步棋让对方一 大块死棋变活，大概就没有搜下去的必要。这个Alpha-Beta搜索可以把搜索空间缩小到 平方根，也就是从１０的１９次方到１０的９。５次方。 第二点，加入零空间搜索。所谓零空间搜索相当于停走一步。我们看围棋比赛，偶尔会 听见观战者说这个时候即使白棋停走一步，黑棋也没得下，意思是白棋赢多了。零空间 搜索就是这个意思。由于国际象棋的特殊规则（有时停走一步反到有优势），深蓝不能 采用零空间搜索。但围棋完全可以采用零空间搜索。如果停走一步还有很大优势，则这 一路搜索就有很大价值（或者很没有价值，如果停走的是对方的话）。据他说加入零空 间搜索又可以把搜索空间开方。而且这个优势是深蓝没有的。 第三点，重复利用已有知识。比如一块棋活了，就不用老去算它的死活，除非附近有新 情况发生。这个“除非”在国际象棋上出现太多，因为棋盘太小，所以不好用。判断 “除非”所用的时间以及上下传递已知信息所花的时间使它的利用得不偿失。但围棋棋 盘大，很多时候一块棋的死活与别处无关，如果再用特殊硬件加速已知信息的交流，这 个优势在围棋程序上就可以很大。 最后一点又是莫尔规律。他说深蓝过去十年了。现在的新技术几乎可以把与深蓝有同等 能力的计算机放到一个ＰＣ上（深蓝用的是４８０个加有平行结构的超级处理器），再 过十年，速度又可以提高１００倍。假如再加上几百个平行结构的联接，则又可以提高 几百倍。 把以上几点加在一起，可以消掉在深蓝搜索范围内围棋与国际象棋的一百万倍的差别。 十年以后我们将会有一个与深蓝有同等能力的围棋程序。如果假设围棋职业棋手与国际 象棋职业棋手搜索的深度一样的话，那么这个程序就可以打败人类最高手。 许峰雄是高手，他的话应该有一定的可信度。他说他的研究生已经开始着手这方面的工 作了。但是他的文章里始终没谈判别好坏问题，而我认为这是一个关键问题。因为没有 搜索到底，始终都存在判断好坏的问题。搜索到１２步或者４０步以后怎样决定结果的 好坏。四五十步棋的时候中盘或许刚开始，怎样判断什么是好什么是坏。这个问题大概 得输入一些专家知识。相当于当初深蓝让国际象棋大师作顾问。许峰雄现在在中国，找 专家当然不是什么难事。 对这个没搜索到底的问题有疑虑的人还不少。象我这样的人只是问一问，另外有些人就 要想法设计四十步以后的判断算法。还有些人更进一步，干脆搜索到底。且慢，你刚才 不是说搜到底是无穷大吗？怎么有人可以搜索到底。这又要扯到人工智能的另一个方法： 模拟。 围棋是完全信息游戏。不象桥牌或Poker，总有未知因素。桥牌要考虑牌形分布，大牌的 位置等等。Poker的未知因素就更明显，虽说手上的２，７是最烂的牌，但如果Flop出来 ７，７，２，你的牌马上就变成强牌。围棋没有这个问题，对弈双方可以使用的一切招 术以及结果都没有未知成分。可是，虽说没有未知成分，但因为没有人能够算到底，这 些公开的信息并不是清楚地摆在双方的面前。想得深的就多一些信息，想得浅的就少一 些信息。下棋时对方给你设圈套就是只望你算不到那么深。好象一口井，只有竹杆够长 的人才能打到里面的水。有些问题，比如围棋程序问题，深一点或许不够，希望能深入 到底。可是太多的路径选择又不允许每条路径都走到底。这时候我们就采用一种叫做随 机模拟的方法。其基本思想是，虽然不能每条路都走到底，但选择一些路走到底是可以 的。在每个分岔点我们都随机的选一些岔道走下去。走到底以后看结果。如果某个结点 后随机选的岔道都显示这是一条好路，从概率上来说这是一条好路的可能信就很大。这 种随机模拟的算法在很多方面都有应用，尤其是在物理和工程上。第二次世界大战时美 国的一批造原子弹的物理学家（费米，冯。诺曼等）给这种随机模拟方法取了一个响亮 的名字叫Monte-Carlo。这是欧洲以赌场闻名的一个城市名字。这种算法和赌场都靠大量 的随机结果为其工作原理。 本文最开始说的围棋程序ＭＯＧＯ就是基于这种原里。ＭＯ就是Monte-Carlo的前两个字 母，ＧＯ就是英文围棋的名字。这个程序不需要背任何定识，做任何模式识别。只是随 机地在棋盘上选许多点，走一步以后再随机的选许多点，一直这样把一盘棋下完，然后 数子。因为一直走到底，胜负已经很清楚，不需要任何判断。如果某个点以后随机选择 的路径以最大胜率结束，这个点就被认为是最有利的点，程序就选这一步。顺便说一句， ＭＯＧＯ的前辈（第一个在这方面有成就的程序）叫做疯棋（Crazy Go），我觉得这个 名字恰如其分。这个看似疯狂而且简单的原理居然弄出惊人的结果。首先是在计算机围 棋比赛中战胜了所有其它对手。在此之前，计算机围棋程序的冠军几乎一直都是陈志行 教授写的［手谈］。陈志行教授自己是围棋高手，又是计算机专家，把自己的许多想法 都注入了［手谈］，所以，它能打败同类的其它程序。［手谈］可以说是一个典型的 “人工智能”程序。没想到这个“人工智能”高手遇到这么一个没有任何“智能”成分 的傻瓜程序却无能为力。这一方面说明［手谈］的所谓“人工智能”还有很多缺陷，另 一方面也说明ＭＯＧＯ的算法有一定道理。 不光是对计算机程序，这种完全随机的模拟方法对人类也有优良表现。正规的１９路棋 盘现在对它们来说还太大，于是从小棋盘开始。中国旅欧职业五段棋手郭娟与ＭＯＧＯ 的前身疯棋在小棋盘上下了很多盘。在７Ｘ７的棋盘上，疯棋执白从来不输，执黑也偶 尔能赢。在９Ｘ９的棋盘上与郭娟下了１４盘，９胜５负。成绩还是很拿得出手的。 ＭＯＧＯ比疯棋又进化了一步，在最近的一次计算机围棋程序比赛上，ＭＯＧＯ与疯棋 的新版疯子（Crazy Stone）进行冠亚军决赛，ＭＯＧＯ大胜。看来ＭＯＧＯ要比疯棋强 很多。所以当另一职业五段２胜一负战胜ＭＯＧＯ时就成了大新闻。 出于好奇，我把ＭＯＧＯ与疯子的决赛棋谱调出来看了一下，同时发现一些可喜和可忧 的部分。可喜的是ＭＯＧＯ似乎能产生有很强的大局观的棋。对方在角上压过来时它居 然会脱先去占大场，而且这个大场不是三路或四路，而是在五路上。只看布局，很有武 宫正树宇宙流的风格。在对杀时还能走出单立这样的好棋。可忧的是它毕竟没有什么智 能，走到后来简直惨不忍睹，或者说愚不可及，比一个刚学棋一天的人都不如。毕竟它 们是一点智力都没有。从这一点上看，这条路还有得一阵走。另外，从小棋盘到大棋盘 进发的问题，还是由莫尔规律来掌握其进度吧。 写到这里，正好看到记者采访聂卫平谈到围棋程序，聂卫平说围棋程序不是还处在随便 一个人都可以让二十多子的水平吗？看来聂卫平需要有人给他更新一下有关围棋程序水 平的认识了。 ＭＯＧＯ与许峰雄的“硬搜索”都是朝非传统人工智能的方向走。如果有朝一日走出一 个没有任何智能却能打败人类最高手的程序，真的是一种悲哀。所以有人在围棋网络上 呼吁程序员们不要继续这种程序，要给人类留一块圣地。我想，挡是挡不住的，呼吁也 没有用。人们在前进的道路上总是要在不同的路径上进行探索，不同的路都走一走，才 知道哪条路好。从某种意义上来说，人类的进步不也正是一种Monte-Carlo过程吗？ ＧＯ，ＭＯＧＯ！ＧＯ，ＭＯＲＥＧＯ。 －－万精油－－ 二零零八年三月二十八日于波士顿西郊 注：有兴趣的读者可以到以下网址读到相关文章： １。许峰雄：Cracking Go <a href="http://spectrum.ieee.org/oct07/5552" target="_blank">http://spectrum.ieee.org/oct07/5552</a> ２。ＭＯＧＯ与疯子对局 <a href="http://www.grappa.univ-lille3.fr/icga/round.php?tournament=167&round=7&id=2" target="_blank">http://www.grappa.univ-lille3.fr ... mp;round=7&id=2</a> ３。墨绿 <a href="http://www.zhipingyou.com/qqsh/index.php?topic=280.0" target="_blank">http://www.zhipingyou.com/qqsh/index.php?topic=280.0</a></div>

作者: wombat 时间: 2008-5-1 19:47
good

欢迎光临飞扬围棋 (http://flygo.net/bbS/)