《最强围棋软件Zen的开发历程-译自《碁世界月刊》》由会员分享，可在线阅读，更多相关《最强围棋软件Zen的开发历程-译自《碁世界月刊》（26页珍藏版）》请在金锄头文库上搜索。
1、最强围棋软件Zen的开发历程-译自碁世界月刊 ZEN受让四子战胜武宫这一历史性事件，让大家对计算机围棋又产生了很大的兴趣，以前转载过一篇计算机围棋的发展概况国立台湾大学研究报告，棋友反映资料不够新，这次我特意找到碁世界月刊关于ZEN的特别报道，分享给棋友。译自：碁世界月刊年六月号电脑围棋特集对电脑来说，围棋是一种既漫长又困难的游戏。因为围棋的变化数量比起西洋棋或是将棋多很多，局面判断也很困难。过去的围棋程式是希望藉著把围棋知识塞入其中而能做出正确的形势判断来胜出，然而这样的做法却很难突破业余初段的程度。更糟的是，在国际的电脑围棋竞争中，日本总是只能步他国之后尘。在年，出现了电脑围棋之*，就是大
2、家明白了蒙地卡罗演算法这种统计搜寻手法在电脑围棋运算中非常有效。所谓的围棋蒙地卡罗演算法，就是在某个局面下以乱数的方式反覆模拟下到终局的状况几十万次。从这几十万次的模拟计算中挑出机率上最容易获胜的著手，并针对其中有力的著手进行更深更多的计算，这样就很容易发现好棋。藉著这样的方式，电脑围棋的棋力一举突破的业余初段的境界。的开发历程就是尾岛阳儿先生以上述年表一个人开始开发的程式。尾岛先生虽然是永远带著太阳眼镜而产生出独特气氛的人物，事实上他也是游戏业界中名不虚传的天才程式师。在尾岛先生开始开发围棋程式后没多久，蒙地卡罗演算法这种崭新的手法非常有效之态势也逐渐明朗起来。这可以说是佳妙的命运相会。吸收
3、新手法优点的尾岛先生又逐渐加上自己独特的心思，并且藉著踏实的努力让持续变强。终於在年替日本创下首次拿下令人引颈期盼的国际大赛冠军。而加藤英树先生也是尽早导入蒙地卡罗法而开发出名为不动碁的厉害程式，但他很快就看清光靠自己一人绝对无法到达世界最强的水准，所以找了尾岛先生来一起组成开发小组。这就是的诞生由来。虽然原本的规格是只用一台电脑就能运作，但加藤先生又将它修改成可以在多台电脑上平行运算，而将棋力再提升了一子左右的程度。加藤先生除了平行运算以外，也分担了其他伴随运用而产生的杂务工作，而让尾岛先生能够花更多的精力在改善上面。如果没有加藤先生的助力，的进化程度可能就不会像现在这麼顺利。在这个小组成立
4、后，的棋力就以每年变强一子半的速度增长下去。虽然因为的出现，使得日本在电脑围棋中到达了世界领先的程度，但欧美各国也是仍然热烈地开发突破，所以的对手们也是非常厉害。看起来，以世界最强为目标的竞争情势，一定会持续下去。开发者的感想尾岛阳儿：我会为了不让竞争对手的软体追上而持续努力下去。但基本上的开发感觉不是以软体人类为目标，而是日本的软体世界各国的软体。我的认知是，和人类之间的胜负结果是伴随上述目标达成之后的附属品。加藤英树：四子打赢武宫九段时，真的让我吓了一跳。现在藉由平行运算的方式仅使的棋力增强一子而已，所以我希望能提升到二子的程度。古娄 计算机围棋的发展概况国立台湾大学研究报告颜士净 国立台
5、湾大学资讯工程研究所博士班研究生许舜钦 国立台湾大学资讯工程系教授摘 要计算机对局是人工智能领域中相当重要的一个分枝。而在围棋方面，由于它本身的特质，使得计算机围棋在继西洋棋、象棋之后，成为人工智能中一个相当引人注目的新挑战。在本篇文章当中，我们首先简单介绍围棋的特性和计算机围棋的基本原理。再简述推动计算机围棋进步的重要比赛。经由了解这些比赛，可大略知道一些较强程序的发展情形，而后再进一步介绍这些程序的特性及其优缺点。最后我们根据各程序的发展情形，概略分析计算机围棋未来的发展空间。一、围棋简介1.1 起源围棋是起源于中国的一种棋戏，相传是数千年前由尧所发明。虽然发明围棋的确实日期已不可考，但可
6、以确定的是早在公元前十世纪，围棋已经广为流行。目前围棋在许多东方国家都很盛行，而且也渐渐推广到全世界。事实上，围棋在许多人的心中，不仅仅是娱乐，由于其本身的许多特质，早已被看做是一种艺术。围棋吸引人的地方除了是因为它的规则简单及变化复杂，可供人们发挥最大的自由想象创造空间外，另一方面也是由于它已被研究了数千年，许许多多的战术观念及思考方法已被研究开发出来，人们可经由学习这些东西而迅速地进入围棋的世界。1.2 基本规则及棋力计算方式围棋可以说是两个人在棋盘上争地的游戏。两人分持黑白，轮流将棋子下在棋盘的空点上。在棋盘上的每个棋子的邻接点若为空点，则称是这颗棋子的气点，当棋子的气点全被对方占据时，
7、则此棋子必须被对方提取。某些提子的时候，会产生同型反复的情况，此时为避免同型反复而无法解决，规定当刚提吃对方一颗棋子时，不可马上提回，必须间隔一手之后才可提回。最后胜负的决定则是根据棋局终了时，计算双方所占有的地域的大小来决定。以上为基本的围棋规则，详细完整的围棋规则可以参考应昌期围棋教育基金会的”计点制围棋规则”围棋基金会1995。目前世界上一般通用的棋力计算方式是用级跟段来表示棋力的强弱。图一说明级与段表示棋力的方式。级较段为弱，一般所称的入门的初学者大约是九级以外的棋力，而段位以上的棋力则可算是对围棋的各种技巧已有相当的了解，普通人要到达段位的棋力，是要花上相当大的时间与精力的。而在棋力
8、差距方面，在业余的棋力中，相差一级约相差一子的力量，例如三级约可让七级先在棋盘上摆四子（围棋中的术语称让四子为相差四先的手合）。而在业余中差三段约相差一子的力量，例如五段约可让一段先在棋盘上摆二子。在职业中则是差五段约相差一子的力量，所以职业九段可让职业一段两子。目前世界上职业九段的棋士并不多，而一般来说，由于围棋的各种理论已被发展得相当完备，职业九段对棋局的看法，都可视为是对的。二、计算机围棋的基本原理运用计算机来下围棋，似乎是一个很直接的想法，因为围棋的规则很简单，胜负定义也很明确，棋盘上每点的状态也只有黑子、白子和空点三种，这些都和计算机本身的特性相符合。另一方面也是由于它已被全世界研究
9、了数千年，许许多多的战术观念及思考方法已被研究开发出来，这些几乎可以看做是真理的理论，都是可以在发展计算机围棋时去应用或参考的。但是计算机围棋的发展过程，却没有想象中顺利，虽然围棋规则很简单，但是由于盘面广大（一般的对局棋盘是1919），实际上对局时的变化却比其它的棋戏复杂得多。例如西洋棋或象棋，已能藉由一些简单的推理与深度的搜寻思考而达到相当高的棋力，但这种方法却不太适合应用在围棋这种高复杂度的棋戏中。A.Samuel估计checker的复杂度大约是10的40次方Samuel, 1959，而A.Newll估计西洋棋的复杂度大约是10的120次方Newell et al., 1958。这两种棋
10、戏的复杂度虽然已是天文数字，但比起围棋的复杂度则要小得多了，Brown及Dowsey估计围棋所有可能的变化大约是10的700次方Brown and Dowsey 81。由于围棋的复杂度太高，如果仅用穷举搜寻的技巧，并不能得到我们要的结果，因此我们必需要发展其它策略来帮助制作计算机围棋程序。直观上来说，最直接的制作计算机围棋程序的方式，就是直接用计算机去仿真人类下棋的思考方式，这也是现今的计算机围棋程序最常用的方法。就人们下棋思考方向而言，选择着点时大都根据该点是否利于占地、是否利于攻防、是否有关死活等，因此我们必须找出一条设计之途来模拟这种思路。以下我们就借着分析人类下棋的思考模式来说明一般计
11、算机围棋程序的制作方法。就占地而言，围棋中有所谓金角、银边、铜肚皮之理论。角隅的下法我们可藉由建立定石数据库来选择着点，边上地域之争夺则可另建一套拆边系统，中央则因不易围取，需要多个较复杂的子系统来帮助判断攻击，例如藉由攻击对方而围到中空，此在多次的对局中屡有所见，是以足可弥补铜肚皮的小瑕疪。就棋块或大龙攻防方面而言，程序必须要有辨认一块棋的能力，且还要能”看”出周遭状况而得悉安危与否。因此在程序中建有一”块”棋的数据结构，用来获得这块棋的种种信息，诸如它所包含的棋串、占地数目、本身涵盖的区域大小等。又为找出有利的攻防点，程序必须建立类似雷达网的系统，由一棋块为根据向外层层扩散，以得知何处有敌
12、子，何处有援军，是否已被包围等等。另外为了仿真人类棋手的视觉效果，也必须开发出一种影响力评估值的方法，藉由此方法，可加强计算机围棋程序对于判断模样、棋块安危和占地数目的能力。而当棋局中短兵相接，牵涉到死活纠缠的状况时，就需要有一搜寻分析系统，借着搜寻的细算功能，判断棋子是否可以吃到(或逃出)，以及如何去吃(如何逃出)与吃(逃)该棋串之价值大小。此一攻杀细算模块为任何围棋程序所必备Hsu et al., 1994 Hsu and Liu, 1991 Hwang and Hsu, 1994。三、计算机围棋比赛简介目前世界上较为人知的计算机围棋比赛共有五个：应氏杯FOST杯奥林匹亚杯北美杯及欧洲杯。
13、而其中较大型的比赛为应氏杯和FOST杯，以下就这两个比赛作一简单的介绍。3.1 应氏杯世界计算机围棋比赛应氏杯主要是由应昌棋围棋教育基金会所主办的，为第一个全世界性的计算机围棋比赛许 1989。应氏杯比赛主要包括两个部份，计算机对计算机比赛和计算机对人脑比赛，其中人脑指的是青少年高段棋士。应昌棋围棋教育基金会主要宗旨是推广围棋，其并为围棋修订了一套完整的围棋规则，也就是俗称的计点制，是公认较为完备的围棋规则。应氏杯的初赛于每年七月在台湾举行，通过初赛者可获得旅费补助。而决赛则因为为了推广围棋运动，自1990年起，于每年十一月分别在世界各不同大都市举行。比赛的赛程安排是采瑞士制，而规则是用计点制
14、围棋规则，详细的参加办法可洽应昌棋围棋教育基金会。为了鼓励人们从事计算机围棋方面的研究，基金会给予在应氏杯中计算机对计算机的比赛的前三名奖金分别如下：冠军是二十万台币、亚军是四万台币、季军则是二万台币。而计算机对人脑的比赛的奖励则视局差而定，详细的情形如表二所示。目前为止举办过的比赛的时间地点及比赛成绩如表三所示许 1989 Fotland 1996 。为方便阅读起见，表三根据比赛成绩只列出前三名及比赛的时间地点。表二 应氏杯计算机对人脑的比赛的奖励手合 须赢场数 奖金(NT) 备注让十六手 三战两胜 100,000 1991年由Mark Boon赢得让十四手 三战两胜 150,000 1995年由 陈志行 赢得让十二手 三战两胜 200,000 1995年由 陈志行 赢得让十手 三战两胜 250,000 尚未有人赢得让八手 三战两胜 400,000 尚未有人赢得让七手 三战两胜 550,000 尚未有人赢得让六手 三战两胜 700,000 尚未有人赢得让五手 三战两胜 850,000 尚未有人赢得让四手 三战两胜 1,000,000 尚未有人赢得让三手 三战两胜 2,000,000 尚未有人赢得让两手 三战两胜 5,000,000 尚未有人赢得让一手 三战两胜 10,000,000 尚未有人赢得让先 五战三胜 20,000,000 尚未有人赢得分先 七
