【转载】科幻围棋小说《墨绿》(上) by 万精油
3/26/2009 01:10:00 上午 发帖者 流水弦歌
【流年转载按】
这是2005年在新语丝网站上发表的科幻围棋小说,曾获得新语丝文学奖二等奖。文中涉及了神经网络学习演化、模式识别,量子计算等等的计算机人工智能概念,但请不要被这些名词所吓倒,作者在小说中所讲述的内容,可是我们所平素见惯的对弈游戏——围棋哦。
即便您对围棋一点都不了解,看着这计算机程序如何长棋——从臭棋篓子杀到绝顶高手,直到孤独求败的过程,相信也一定会和我一样,感到心血澎湃吧。
这里是作者主页 ,如果有兴趣也可以前去拜访。
————————————————————————
墨 绿
--万精油--
墨绿的出现,同时震惊了中日韩三国棋院,一个共同的问题是:墨绿究竟是谁?
──人民日报体育版2005年9月10日
看著《人民日报》的这篇报道,我心里充满了喜悦,自豪和得意。这世界上除我之外再没有第二个人知道墨绿的真实身份了。
一.引子
话要从大约十年前说起。由IBM科研小组研制出来的“深蓝”国际象棋程序,战胜了当时的世界第一高手卡斯帕洛夫,西方舆论界为之哗然。被西方人作为第一智力游戏的国际象棋,人类被机器打成下手,惊呼当然是很自然的。但是,在一片叫好声中,纽约时报有一篇报道却在幽默中表现出冷静。它说:“我们这里的大呼小叫,最多让亚洲人(日本,中国和韩国)伸伸懒腰,不以为然。因为对他们所玩的游戏──围棋──来说,计算机还处在原始时代”。
计算机围棋程序处在原始时代,并不是因为没人重视。事实上,相当大的人力物力投入了围棋程序的开发。个人的,集体的;有计算机专业人员,也有职业棋手。最大的投入要数日本,他们的第五代机算机开发的一个重要课题就是围棋程序。台湾的亿万富翁应昌期先生生前还为此设了巨额奖金。说是在二十世纪末如有计算机程序战胜台湾职业棋手,则可得一百万美元的奖金。如此种种,目前的围棋程序却仍被冠以原始时代的雅号,追究起来其主要原因是围棋太难。国际象棋与它的难度相差不是一两个数量级的问题。
我对围棋程序的热衷由来已久。我写过很多别的游戏程序,但对自己最喜爱的围棋却一直没敢写,因为不知从何下手,想得到的思路别人早已试过了。这个愿望一直悬在那里,心里放不下,手上又搞不动。九八年上半年事情开始有了转机。由于工作需要,我接触到一些遗传编程(GENETIC PROGRAM-MING)的东西。有一天读一个样板程序,突然想到也许可以用同样的思路来写围棋程序。程序开始的好坏不要紧,关键是要有很好的鉴别函数使其能合理地进化。
二.原始版
照著样板程序,很快就写了一个原始程序。它没有任何高级技术,只懂得提子规则以及最后的点目。基本的想法是让它自己与自己下,利用它懂得的这两点基本功能来进化出高级技术。这样做成功的先例是有的。有人用这种想法写过一个BACKGAMMON的程序,没有任何高级技术,完全利用基本规则,在它自己与自己下完五万盘以后,进化出一个可以与人类最强手对抗的程序。不幸的是,同样的想法不能搬到围棋上来,因为围棋的变化实在是太多了。事实很快证明了这一点。我的原始程序进化来进化去,全是盲目的,看不出一点朝著好的方向前进的迹象。根本算不上进化,最多只能叫变化。看来完全靠原始程序是不行的,还得加一些高级一点的概念,比如角上的基本对应以及群体死活(而不是每颗子的死活)概念。从理论上来说,这些概念都可以从基本规则中推出来。但是,因为影响进化的因素几乎都是局部的,像群体死活这类的高级概念很难进化出来,但这些概念在基础阶段却尤其重要。
加进这些高级概念以后,情况开始有了一点起色。要死的棋居然知道逃。虽然明明逃不出去,但从局部来说,能延缓死亡时间就是进步。因为是程序同程序下,逃不出去的棋有时也居然就给它逃出去了,这又进一步强化了这种愚蠢的下法。但不管怎样,相对于先前的盲目变化,这种暂时性的进步也是很可喜的。许多别的高级概念也似乎有了一些模型。不过,从一些明显的愚蠢变化中,我也发现了许多原始程序的问题,并做了相应改动。就这样程序自己的进化加上我的随时改动,半年以后这程序居然有了一点会下棋的样子。再也没有自己撞紧气之类的明显错误,偶尔竟然会走出枷这样的概念。这种时候我感到特别的惊喜。估计照这样下去,它就会逐渐强大起来。
遗憾的是事情并不按照这种理想的路子走下去。初始时期的快速进步逐渐缓慢下来。因为总是程序跟程序自己下,没有外来的影响,基因库很快就达到局部稳定状态。不管再让它们自己下多少盘,结果总是在原地打转。而且,通过半年的进化,中间的一些程序我已经看不懂,也不可以像开始那样任意加上我的改动。当然我可以同它下,让它从我的下法中取得新变化的基因。但这种办法是几乎不可以想象的慢,因为进化的过程需要很多很多盘才可以实现,而我是不可能一天二十四小时都陪它下棋的。而且我也不会摹仿坏棋,我的棋下出去都是这程序不可以接受的跳跃。于是这程序就这样死在那里。
由于我的心思完全套死在这个程序上,一个明显的出路放在那里我竟然一直看不见。现在想起来很自然的事,当时却一直想不到。我在网络上下棋好多年了,但一直把它当成消遣娱乐的地方,从来没有想到过我的程序也可以从上面学棋。有一天我突然意识到,只要写一个界面程序,就可以把它一直挂在网上,一天二十四小时与人对弈。
三.网上学棋
网上下棋的人很多,各种水平的都有,而且风格各异,正适合我的程序用来学棋。我的程序挂在那里,只要有人邀请,不管什么水平,马上就跟他下。这样一天二十四小时下下来,比我跟它下不知好了多少倍。一方面时间多,另一方面网上可以找到很多初学者,学起来恰到好处。但真正的进化需要很多这样的机会,一天二十四小时我仍然嫌不够。于是我又给我的界面引进了多线功能,也就是说同时可以有好几个同样的程序在下棋。只要有人邀请,他就马上开一盘。这样一来每天都可以下很多盘,进化的机会也就多起来。每到周末我就对程序作一次全面整理。一个月以后,我的程序有了明显进步。而且居然有了带星号的27级。虽然很差,但比起最低级别,还算是赢面占多。这使我很兴奋,这至少说明它是在进步,而且这是在没有我介入的情况下获得的。又过了一个月,它又升到26级。高兴之余也发现了新问题。
这所谓自我学习,就是要不断产生新的子程序,新的模式。久而久之,程序就变得越来越大,运行起来就越来越慢。像生物学上的进化一样,新产生出来的东西并不是都有用的。事实上,我们人类的DNA链上绝大部分都是没有用的。开始阶段我还可以用人工的办法把那些没有用的东西去掉。到后来,新产生的东西越来越多,靠人工是完全不能胜任了。而且,最严重的是,我的判定并不可靠。我认为没有用的东西或许在意想不到的地方有用。这个问题困惑了我很久,我的程序也从网上取了下来,因为我不能再让它产生新的子程序。
正在我不知从哪里突破的时候,有一天在网上看见一篇讲进化论中的用进废退原理。我突然意识到我的程序中就缺少这么一个机制。于是,我就在我的程序里加了这样一个检验程序。如果一个模式或者一个子程序在一定时间里没有被调用过,主程序就自动把它去掉。这样一来,它虽然失去了一些可能产生好基因的途径,但主要障碍清除了,又创造出许多别的机会。很有意思的是,我发现有一个子程序被调用的特别多,就把它取出来看一看。一般来说它自已进化出来的子程序我是看不懂的。但我这次存了心一定要看它是干什么用的。花了好几个晚上一步步地看,终于发现它居然是用来判断征子是否有利的。这种子程序都能进化出来,我对它的前途产生了很大的信心。
重新上网以后,每天都有新程序产生,也有一些旧程序和模式被清除。程序逐渐快了起来(因为开始堆积的废物太多)。等级分又开始往上走,半年以后升到了15级。这时候它的棋已经下得有模有样,尤其是局部战斗,已经有一定的杀力。但围棋不是单靠局部拼杀定胜负的,必须要有整体观念,而这整体观念是不能从15级的对手中学来的。这程序又像上次那样停在那里,长久没有进步。好几个月都一直是15级。
四.向专家学棋
一般来说进化都是局部性的,在局部上有优势的走法就很自然地被保留下来,这样永远也不会有整体观念的突破。虽然加进了突变的概念,但也最多产生出枷、飞、伸大腿这样的局部技术,弃子取势这样的整体观念是不可能自动进化出来的。
有一天我在网上看富士通决赛,好几步棋都看不懂,仍然看得精精有味。突然想到要学棋并不一定只学完全懂的棋。专家的棋看多了,走起棋来自然而然就有了好形,而且也知道什么地方是大场。所谓“熟读唐诗三百首,不会作诗也会吟”就是这个道理。想到了这个思路,剩下的就好办了。专家的棋网上有的是,要多少有多少。几个晚上就从网上搞来了上千盘棋谱。我先给我的程序加了一些模式识别的功能,然后就让它没日没夜地打起谱来了。从打谱中学会了占大场,占完大场后接下来的变化它并不清楚。但这不是什么问题,因为这些变化大都是局部的,而我这程序的强项就是局部变化。几个星期下来,再把它放到网上的时候,棋力已经大长,在同级棋手中所向披靡,很快就升到7级,然后与7级的棋手盘旋了几个星期又慢慢地升到6级,5级,4级。
我这个程序的成长与我们大多数人学任何新东西一样,都是一个阶梯一个阶梯地上。许多人到了某个阶梯,因为没有明师指点,就长期停在那里。我自己就认识很多下棋十几二十年都不长棋,打牌十多年不长牌,打球十多年不长球的人,因为他们总是迈不过眼前这个阶梯。这是由游戏本身内在的复杂性所决定的,与学它的人无关。我这程序也一样,每过一段时间就要遇见一个阶梯而停步不前。IGS的4级似乎就是这样一个阶梯。它长到4级以后就再也不长了,长期停在那里。
说起来,IGS的4级已经比现在其它所有的围棋程序高出一大截,如果拿出去卖已经很可以大赚一笔了。但这不是我想要的,我的最终目的是要产生一个战胜专业棋手的程序。IGS的4级与专业棋手还有很大的差距。虽然如此,这个级别的棋已经有相当的水平,再往上进步已经不能单靠计算,还要讲究对棋有感觉。而感觉这个东西是现在的任何程序都不具备的。这次停下来,一停就是半年。虽然也随时在网上与别人下棋,但总是没有长进。出路在哪里呢?
五.模糊函数与量子波
计算机程序的一大优点是对任何棋形都可以有个好坏判断,在搜索范围内一切都不会错过。可是,从某种意义上来说这也是一种缺点。一切都靠算,能覆盖的面积自然就少了。而且,许多棋的好坏要到十几步甚至几十步以后才会表现出来,这是不可能算出来的,主要是靠感觉。另外,一个棋形的好坏并不是一成不变的,在某些情况下坏棋形也会有好价值。就连被认为是最坏棋形的空三角也经常在专业棋手的对局中出现。如果我们把一个棋形的好坏价值定死了,就没有产生这种变化的可能。我很早就想过要把模糊函数的概念弄到我的判断程序里面去。可是无论怎样模糊,在运算过程中,模糊量的大小还是得人为地规定。对一个固定棋形还是会算出同样的结果(虽然结果以模糊的形式出现)。
每一块棋除了死变化以外,都是有生命的。它的生命力以辐射方式向外散发,所以有“空提一子三十目”的说法。固定的程序是没有办法算出这种生命力来的。有一天读到一篇讲量子计算的文章,突然想到可以试一试在我的程序中加入量子波。这样一切运算都以概率的方式出现,没有固定结果,但通常会产生最自然和理想的结果。加进去以后,它果然变得丰富多采起来。居然可以走出很多从前绝对想不到的棋。不过,加进量子运算以后,效率变得比较低,搜索范围变小了,棋力居然比以前小有退步。但我并不为此失望,退一步进两步,只要大方向是朝前就行。关键是方法,效率问题总是有办法提高的。后来我花了一些时间把程序彻底整理了一下,又把我的计算机硬件升了级。如此一来,它的运算效率比以前增加了一倍,棋力也随之猛长起来,而且这次长起来就没有停。几个月下来就升到一段(1D★),而且根本没有停的意思。我的兴趣也跟著高起来,随时随地都在思考它的问题和解决办法。什么事情都想看看对我的程序是否有帮助,连开车等红灯都在想这最短路径问题是否可以用到这程序的搜索路径中去。这样一来,新的想法天天都有。
IGS是国际性的网站,任何时候世界上总有一半的地方是白天,也就是说任何时候都有人下棋。我的任何新想法都可以立即得到是否有用的验证。我每天下班回家就全力扑在它上面。不断地改进,不断地加上新的想法。我把这程序没日没夜地挂在网上,它的棋力每天都在长。两年下来它终于达到4D★。
这个程序的运作很依赖计算机的速度,这包括主机速度,硬盘阅读速度,以及内存容量。为了充分发挥它的潜力,我当然想给它配置最好的装备,这就需要钱。而且如果想买刚上市的新产品,就要花大钱。台湾每年一次的计算机围棋比赛,如果能拿第一名,就可以得到相当数量的奖金,至少买新机器不成问题。但我又不愿引起别人的注意。于是我把我的程序简装了以后去参加这个比赛。所谓简装就是拿掉一些子程序。但我的程序比别的程序高出太多,拿掉子程序后我又给它加了一些限制,基本上就是让它每盘能赢,但总在十目以内。最后一轮以前,我的程序全胜,即使输掉最后一盘也稳拿第一。于是,我在最后一场比赛前又拿掉了最主要的子程序,输了最后一盘。这样别人都认为它与别的程序属于一个档次。我又不像别的参赛人总想打名声好卖他们的程序,而是拿了第一名的奖金就赶快走人。因此,我的程序虽然拿了第一,却没有造成什么影响。第二年的比赛我没有去参加,这程序就渐渐地从大家的记忆中消失。有少数人记得,也只知道它大约是业余5级的水平。
六.墨绿问世
在达到4D★以前,我的程序有输有赢。虽然赢比输多多了(从30K升到4D★),但并没有引起人们的注意。我觉得该是给它起名字打名气的时候了。起什么名字好呢?因为我的最终目的是要打败人类最高手,所以一定要起一个与深蓝类似的名字。开始想叫它“深绿”,但又觉得与深蓝靠得太近。而且,深蓝的“深”有深层搜索的意思。我这个程序主要原理并不在深层搜索。叫它“浅绿”又觉得名字不够响亮。正在为起名字的事犯愁,恰好有多年不见的朋友来访,说是下一盘棋叙叙旧。于是从壁橱里拿出已经起灰的云子。这几年虽然也常下棋,但都是在网上下,手上摸的都是鼠标,这棋子已经有好几年没有摸过了。手里摸著这棋子,突然想到以前朋友曾告诉我鉴别真假云子的办法。说是把黑子拿起来对著光看,真云子会成墨绿色。这真是踏破铁鞋无觅处,得来全不费功夫。“墨绿”这个名字真是太合适不过了。既与深蓝相近,又有神秘深邃的意思。名字想好以后我就立即在IGS为它注册了一个4D的账号,英文名叫SLATEGREEN。
这时墨绿的棋力实际上已经比一般4D★强,但为了安全起见,开始只找弱4D下。主要目的是要连胜以造成轰动效应。IGS的概率指令可以用来判别强弱4D。因为它一天24小时全挂在上面,能找到对手就下,没有对手就跟自已下(我机器上还同时运行著另一个与它同时进化出来的程序)。几个星期下来,它连胜40盘,并且打成了5D★。一般人到了这种水平,一年半载也长不了什么棋。而墨绿不一样,它每下一盘棋都以最优方式重新整理内部联络,也就是说它一直都在长棋。打成5D★的时候,它的棋力其实已经高于5D★。所以,跟5D★下也一直赢。几个月以后又升到了6D★。6D★的级别,加上七八十盘的连胜很快引起了大家的注意。每次下棋的时候总有很多人观看,这种时候我特别得意。由于连胜,找它下棋的人越来越多,甚至还有7D★以上的。为保险起见,它只接受同级人的挑战。不到7D★就不接受7D★的挑战,而且也不跟新账号下。因为这些人或许是正在上升途中,实力可能很强。
因为墨绿成年累月都挂在网上,形形色色的人都会碰到。在4D★以前,时不时就会遇见耍赖的。开始的时候,耍赖对墨绿没有什么用处,因为他不在乎输赢,而且有的是时间。打到4D★以后这个问题就变得比较严重起来。因为要用连胜造影响,就一盘都不能输。如果遇见逃跑的还好,一个月以后IGS会自动判逃跑者负。可有时候墨绿明明大胜的棋,我这边突然断线。等我再连回去对方已经跑了,这样IGS算墨绿逃跑。好在4D★以上的人已经比较有棋品,这样干的不多。连胜二十盘的时候被我遇到过一次。于是我在它的程序里专门加了一句等候此人的指令。除非它一个月内不出现(届时IGS系统会算墨绿逃跑而判负),只要他一出现,墨绿就会抓住他。4D★的人棋瘾都已经很大了,要让这样的人一个月不上IGS是很不容易的。这些耍赖的人往往是出来探一下头,如果有他们欠棋的人在线上,他们就立即断线。由于墨绿有了这句等候他的指令,使得他连探头的时间都没有。他逃跑一星期后又联进了IGS,刚联进不到5秒钟就被墨绿发现,他还没来得及打退出的指令,墨绿已经恢复了他所欠的棋,这时候再要退出就算他逃跑,所以他只好把这盘棋下完,输棋走人。
另外经常碰到的是打听消息的。一般来说,墨绿对别人的问题一律不理。但有时如果我在看棋,我就会帮它回答一些问题。“你是不是职业棋手?”“是。”“你现在在哪里?”“计算机里。”“你24小时都泡在这里,不干别的事吗?”“是。”我总是用这种怎样解释都可以的答案来回答。
七.墨绿成长
墨绿的实力现在已远远高出我的实力,我跟它下棋几乎总是输。但因为我是看著它长大的,知道它的一些别人不知道的弱点,所以偶尔我也可以赢它一盘。但它如果在同一个弱点上连续两次吃亏,就会弥补掉这个弱点。因为我已经不可能去改它的程序了,只能通过这种办法来克服它的弱点,好象也很有效。我有时为了特意让它暴露出它的弱点,就跳过它的程序帮它走棋。为此还产生过一个小闹剧。
墨绿到了4D★以后,常常走出出乎我意料的棋。基本上要好几步以后我才能理解那一步的目的。有一次双方杀得很紧张时对方打吃,我觉得它只能长出去,否则棋筋被人提了就全完了。可是墨绿没有长出去,而是长考起来。我在旁边看得著急,以为它又出现什么漏洞,就擅自帮它长了出去。等到对方下一步棋走出来,我才知道它刚才为什么要长考,也意识到我帮了倒忙。对方的下一子同时威胁到两块棋,在另一块棋补一手后,刚才接上的一子又被堵了下来。几个回合下来,墨绿损失十几目棋。在此之前,墨绿一直没有输过。由于我的帮忙,眼看它的上百连胜就要被破了。好在墨绿的棋现在已经比一般的6D★高出一截,而且我很早以前给他加的风险系数现在起了作用。墨绿下棋的最终目的是赢,赢多赢少都不重要。所以它随时都在算自己领先多少。领先多了就走风险很小的棋,平手或微微领先时就走风险相对大一点的棋。现在落后很多,到了走风险很大的棋的时候了。风险大的棋大多都是无理棋。只要对方应对正确,下无理棋的一方会损失更多的目。没想到对方在墨绿一连串的无理棋下,居然没有采取应有的手法,而是一味的退让。大约自己认为领先很多,随便收收官就可以赢了。而且,鬼使神差,对方有一步棋居然应错了次序,吃了大亏,双方的目数一下就拉近了。收官的时候墨绿又再赚了几目,最后刚好赢了半目。真悬!从那以后,我再也没有帮它走过棋了。
上面那盘棋是墨绿连胜以来赢的目数最少的一盘棋。说起赢棋目数,与墨绿下棋的人都觉得很恼火。因为收官基本都是靠死算,是它的强项。一般一盘棋到了收官阶段,它几乎可以把各种变化都考虑到,然后宣布对方输多少目。如果对方继续下,而且没有按最佳下法下,它就会重新算一遍然后宣布一个新目数。刚才还说“黑输3目半”,现在或许说“黑输5目半”,9目,13目,就这样一直收到结束。开始我给它加这个功能是觉得好玩,后来就成了一个节目,许多观战者觉得这样很好玩。不过这让输棋的那方感到很不是滋味,好象被人宣布“你死定了”,然后自己一步步朝坟墓走去。
采用选对手的办法的结果又是只赢不输。因为它实际上总是与比它弱的人下,而且又不会出现昏著。没过多久,它就升到了7D★,然后是8D★。
八.争挑战权
8D★已经有不少专业棋手。由于连胜,墨绿的名气在IGS上已经到了家喻户晓的地步。只要是它的棋,总有上百人观看,有时超过500人。它的思路与人不一样,常常在大家意想不到的地方走棋,所以看的人特别多。尤其是职业棋手,都想来研究它的棋路。它基本也不照定式走棋。如果算出来的棋路与定式相同(大部分如此),就按定式走棋。如果算出来与定式不同,它也没有一般棋手的忌讳,总是按著自己算出来的路数走,根本不管定式不定式。这样一来,它的棋中产生出很多“新”定式,这就更吸引众多专业棋手了。大家开始都以为它是某个超一流棋手。看它保持上百盘不败,大家一致认为它是李昌镐。可看它的棋路又完全不像李。而且有人观察很仔细,发现有一次墨绿在IGS下棋的时候,李昌镐正在中国下富士通决赛。所以可以断定它不是李昌镐。用同样的方法,大家很快推出它不是中日韩三国任何一个等级分排前20名的棋手。这样一来,迷团就越来越大。看它下棋和找它下棋的人也越来越多。
由于连胜,墨绿很快升到了9D★。而且在信息栏里宣布只与9D★下棋。IGS上的9D★很少,就10来个。而且大多是以前的账号。如果别的9D★宣布只与9D★下棋,也许就找不到人下了。可墨绿的上百的连胜在职业棋手中造成了很大的轰动,大家都想来找它较量一下。可是要打到9D★必需要从7D开始。有些职业九段想请IGS管理员直接给他们9D★的账号。可IGS认为这正是吸引职业棋手来下棋的好机会,于是宣布绝不破例。这样一来,一大堆想找墨绿下棋的职业棋手涌进IGS,从7D开始往上打。好象本因坊之类的头衔比赛,先在循环圈里打,打出循环圈(升成9D★)才可以同墨绿下。
从7D★要打到9D★需要下很多盘棋,职业棋手一般不愿意花时间下这些棋。于是有些账号有好几个人在下,而且都是很强的九段,大家分任务,每人必需赢多少盘。不到两个月,IGS出现了好几个新的9D★。这些人一旦打进9D★就再也不相互下棋,而是追著墨绿下。墨绿当然是来者不拒。不过这两个月以来,墨绿与另一个同时进化出来的墨绿程序一直在下棋,棋力又有了长进,已经高出了这些职业九段。所以,与这些新9D★下,又是只赢不输。虽然现在在IGS上下得少了,但由于只赢不输,积分仍然慢慢往上爬,最后终于升到了10D★。
0 评论:
发表评论