精品最强围棋软件Zen的开发历程译自《碁世界月刊》.docx
- 文档编号:16396194
- 上传时间:2023-07-13
- 格式:DOCX
- 页数:16
- 大小:38.78KB
精品最强围棋软件Zen的开发历程译自《碁世界月刊》.docx
《精品最强围棋软件Zen的开发历程译自《碁世界月刊》.docx》由会员分享,可在线阅读,更多相关《精品最强围棋软件Zen的开发历程译自《碁世界月刊》.docx(16页珍藏版)》请在冰点文库上搜索。
精品最强围棋软件Zen的开发历程译自《碁世界月刊》
最强围棋软件Zen的开发历程-译自《碁世界月刊》
最强围棋软件Zen的开发历程-译自《碁世界月刊》
ZEN受让四子战胜武宫这一历史性事件,让大家对计算机围棋又产生了很大的兴趣,以前转载过一篇《计算机围棋的发展概况——国立台湾大学研究报告》,棋友反映资料不够新,这次我特意找到《碁世界月刊》关于ZEN的特别报道,分享给棋友。
译自:
碁世界月刊2012年六月号「电脑围棋特集」对电脑来说,围棋是一种既漫长又困难的游戏。
因为围棋的变化数量比起西洋棋或是将棋多很多,局面判断也很困难。
过去的围棋程式是希望藉著把围棋知识塞入其中而能做出正确的形势判断来胜出,然而这样的做法却很难突破业余初段的程度。
更糟的是,在国际的电脑围棋竞争中,日本总是只能步他国之后尘。
在2006年,出现了电脑围棋之**,就是大家明白了蒙地卡罗演算法这种统计搜寻手法在电脑围棋运算中非常有效。
所谓的围棋蒙地卡罗演算法,就是在某个局面下以乱数的方式反覆模拟下到终局的状况几十万次。
从这几十万次的模拟计算中挑出机率上最容易获胜的著手,并针对其中有力的著手进行更深更多的计算,这样就很容易发现好棋。
藉著这样的方式,电脑围棋的棋力一举突破的业余初段的境界。
Zen的开发历程Zen就是尾岛阳儿先生以上述年表一个人开始开发的程式。
尾岛先生虽然是永远带著太阳眼镜而产生出独特气氛的人物,事实上他也是游戏业界中名不虚传的天才程式师。
在尾岛先生开始开发围棋程式后没多久,蒙地卡罗演算法这种崭新的手法非常有效之态势也逐渐明朗起来。
这可以说是佳妙的命运相会。
吸收新手法优点的尾岛先生又逐渐加上自己独特的心思,并且藉著踏实的努力让Zen持续变强。
终於在2009年替日本创下首次拿下令人引颈期盼的国际大赛冠军。
而加藤英树先生也是尽早导入蒙地卡罗法而开发出名为「不动碁」的厉害程式,但他很快就看清光靠自己一人绝对无法到达世界最强的水准,所以找了尾岛先生来一起组成开发小组。
这就是TeamDeepZen的诞生由来。
虽然Zen原本的规格是只用一台电脑就能运作,但加藤先生又将它修改成可以在多台电脑上平行运算,而将棋力再提升了一子左右的程度。
加藤先生除了平行运算以外,也分担了其他伴随运用而产生的杂务工作,而让尾岛先生能够花更多的精力在改善Zen上面。
如果没有加藤先生的助力,Zen的进化程度可能就不会像现在这麼顺利。
在这个小组成立后,Zen的棋力就以每年变强一子半的速度增长下去。
虽然因为Zen的出现,使得日本在电脑围棋中到达了世界领先的程度,但欧美各国也是仍然热烈地开发突破,所以Zen的对手们也是非常厉害。
看起来,以世界最强为目标的竞争情势,一定会持续下去。
Zen开发者的感想尾岛阳儿:
我会为了不让竞争对手的软体追上Zen而持续努力下去。
但基本上的开发感觉不是以「软体vs人类」为目标,而是「日本的软体vs世界各国的软体」。
我的认知是,和人类之间的胜负结果是伴随上述目标达成之后的附属品。
加藤英树:
四子打赢武宫九段时,真的让我吓了一跳。
现在藉由平行运算的方式仅使Zen的棋力增强一子而已,所以我希望能提升到二子的程度。
古娄
计算机围棋的发展概况——国立台湾大学研究报告
颜士净国立台湾大学资讯工程研究所博士班研究生
许舜钦国立台湾大学资讯工程系教授
摘要
计算机对局是人工智能领域中相当重要的一个分枝。
而在围棋方面,由于它本身的特质,使得计算机围棋在继西洋棋、象棋之后,成为人工智能中一个相当引人注目的新挑战。
在本篇文章当中,我们首先简单介绍围棋的特性和计算机围棋的基本原理。
再简述推动计算机围棋进步的重要比赛。
经由了解这些比赛,可大略知道一些较强程序的发展情形,而后再进一步介绍这些程序的特性及其优缺点。
最后我们根据各程序的发展情形,概略分析计算机围棋未来的发展空间。
一、围棋简介
1.1起源
围棋是起源于中国的一种棋戏,相传是数千年前由尧所发明。
虽然发明围棋的确实日期已不可考,但可以确定的是早在公元前十世纪,围棋已经广为流行。
目前围棋在许多东方国家都很盛行,而且也渐渐推广到全世界。
事实上,围棋在许多人的心中,不仅仅是娱乐,由于其本身的许多特质,早已被看做是一种艺术。
围棋吸引人的地方除了是因为它的规则简单及变化复杂,可供人们发挥最大的自由想象创造空间外,另一方面也是由于它已被研究了数千年,许许多多的战术观念及思考方法已被研究开发出来,人们可经由学习这些东西而迅速地进入围棋的世界。
1.2基本规则及棋力计算方式
围棋可以说是两个人在棋盘上争地的游戏。
两人分持黑白,轮流将棋子下在棋盘的空点上。
在棋盘上的每个棋子的邻接点若为空点,则称是这颗棋子的气点,当棋子的气点全被对方占据时,则此棋子必须被对方提取。
某些提子的时候,会产生同型反复的情况,此时为避免同型反复而无法解决,规定当刚提吃对方一颗棋子时,不可马上提回,必须间隔一手之后才可提回。
最后胜负的决定则是根据棋局终了时,计算双方所占有的地域的大小来决定。
以上为基本的围棋规则,详细完整的围棋规则可以参考应昌期围棋教育基金会的”计点制围棋规则”[围棋基金会1995]。
目前世界上一般通用的棋力计算方式是用级跟段来表示棋力的强弱。
图一说明级与段表示棋力的方式。
级较段为弱,一般所称的入门的初学者大约是九级以外的棋力,而段位以上的棋力则可算是对围棋的各种技巧已有相当的了解,普通人要到达段位的棋力,是要花上相当大的时间与精力的。
而在棋力差距方面,在业余的棋力中,相差一级约相差一子的力量,例如三级约可让七级先在棋盘上摆四子(围棋中的术语称让四子为相差四先的手合)。
而在业余中差三段约相差一子的力量,例如五段约可让一段先在棋盘上摆二子。
在职业中则是差五段约相差一子的力量,所以职业九段可让职业一段两子。
目前世界上职业九段的棋士并不多,而一般来说,由于围棋的各种理论已被发展得相当完备,职业九段对棋局的看法,都可视为是对的。
二、计算机围棋的基本原理
运用计算机来下围棋,似乎是一个很直接的想法,因为围棋的规则很简单,胜负定义也很明确,棋盘上每点的状态也只有黑子、白子和空点三种,这些都和计算机本身的特性相符合。
另一方面也是由于它已被全世界研究了数千年,许许多多的战术观念及思考方法已被研究开发出来,这些几乎可以看做是真理的理论,都是可以在发展计算机围棋时去应用或参考的。
但是计算机围棋的发展过程,却没有想象中顺利,虽然围棋规则很简单,但是由于盘面广大(一般的对局棋盘是19×19),实际上对局时的变化却比其它的棋戏复杂得多。
例如西洋棋或象棋,已能藉由一些简单的推理与深度的搜寻思考而达到相当高的棋力,但这种方法却不太适合应用在围棋这种高复杂度的棋戏中。
A.Samuel估计checker的复杂度大约是10的40次方[Samuel,1959],而A.Newll估计西洋棋的复杂度大约是10的120次方[Newelletal.,1958]。
这两种棋戏的复杂度虽然已是天文数字,但比起围棋的复杂度则要小得多了,Brown及Dowsey估计围棋所有可能的变化大约是10的700次方[BrownandDowsey81]。
由于围棋的复杂度太高,如果仅用穷举搜寻的技巧,并不能得到我们要的结果,因此我们必需要发展其它策略来帮助制作计算机围棋程序。
直观上来说,最直接的制作计算机围棋程序的方式,就是直接用计算机去仿真人类下棋的思考方式,这也是现今的计算机围棋程序最常用的方法。
就人们下棋思考方向而言,选择着点时大都根据该点是否利于占地、是否利于攻防、是否有关死活等,因此我们必须找出一条设计之途来模拟这种思路。
以下我们就借着分析人类下棋的思考模式来说明一般计算机围棋程序的制作方法。
就占地而言,围棋中有所谓「金角、银边、铜肚皮」之理论。
角隅的下法我们可藉由建立定石数据库来选择着点,边上地域之争夺则可另建一套拆边系统,中央则因不易围取,需要多个较复杂的子系统来帮助判断攻击,例如藉由攻击对方而围到中空,此在多次的对局中屡有所见,是以足可弥补「铜肚皮」的小瑕疪。
就棋块或大龙攻防方面而言,程序必须要有辨认一块棋的能力,且还要能”看”出周遭状况而得悉安危与否。
因此在程序中建有一”块”棋的数据结构,用来获得这块棋的种种信息,诸如它所包含的棋串、占地数目、本身涵盖的区域大小等。
又为找出有利的攻防点,程序必须建立类似雷达网的系统,由一棋块为根据向外层层扩散,以得知何处有敌子,何处有援军,是否已被包围等等。
另外为了仿真人类棋手的视觉效果,也必须开发出一种影响力评估值的方法,藉由此方法,可加强计算机围棋程序对于判断模样、棋块安危和占地数目的能力。
而当棋局中短兵相接,牵涉到死活纠缠的状况时,就需要有一搜寻分析系统,借着搜寻的细算功能,判断棋子是否可以吃到(或逃出),以及如何去吃(如何逃出)与吃(逃)该棋串之价值大小。
此一攻杀细算模块为任何围棋程序所必备[Hsuetal.,1994][HsuandLiu,1991][HwangandHsu,1994]。
三、计算机围棋比赛简介目前世界上较为人知的计算机围棋比赛共有五个:
应氏杯﹑FOST杯﹑奥林匹亚杯﹑北美杯及欧洲杯。
而其中较大型的比赛为应氏杯和FOST杯,以下就这两个比赛作一简单的介绍。
3.1应氏杯世界计算机围棋比赛
应氏杯主要是由应昌棋围棋教育基金会所主办的,为第一个全世界性的计算机围棋比赛[许1989]。
应氏杯比赛主要包括两个部份,计算机对计算机比赛和计算机对人脑比赛,其中人脑指的是青少年高段棋士。
应昌棋围棋教育基金会主要宗旨是推广围棋,其并为围棋修订了一套完整的围棋规则,也就是俗称的计点制,是公认较为完备的围棋规则。
应氏杯的初赛于每年七月在台湾举行,通过初赛者可获得旅费补助。
而决赛则因为为了推广围棋运动,自1990年起,于每年十一月分别在世界各不同大都市举行。
比赛的赛程安排是采瑞士制,而规则是用计点制围棋规则,详细的参加办法可洽应昌棋围棋教育基金会。
为了鼓励人们从事计算机围棋方面的研究,基金会给予在应氏杯中计算机对计算机的比赛的前三名奖金分别如下:
冠军是二十万台币、亚军是四万台币、季军则是二万台币。
而计算机对人脑的比赛的奖励则视局差而定,详细的情形如表二所示。
目前为止举办过的比赛的时间地点及比赛成绩如表三所示[许1989][Fotland1996]。
为方便阅读起见,表三根据比赛成绩只列出前三名及比赛的时间地点。
表二应氏杯计算机对人脑的比赛的奖励
手合须赢场数奖金(NT)备注
让十六手三战两胜100,0001991年由MarkBoon赢得
让十四手三战两胜150,0001995年由陈志行赢得
让十二手三战两胜200,0001995年由陈志行赢得
让十手三战两胜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尚未有人赢得
分先七战四胜40,000,000尚未有人赢得
表三应氏杯历年之比赛结果
时间地点第一名第二名第三名
1985台北王若曦曹国明AllanScarff
1986台北杜贵崇刘东岳BruceWilcox
1987台北王若曦刘东岳陈开佑
1988台北林和芳刘东岳MarkBoon
1989台北MarkBoonBruceWilcox陈克训
1990北京MarkBoon陈克训JanuszKraszek
1991新加坡MarkBoon陈克训刘东岳
1992东京陈克训陈志行MarkBoon
1993成都陈志行JanuszKraszek陈克训
1994台北陈克训DavidFotland陈志行
1995汉城陈志行MichaelResis陈克训
1996广州陈志行陈克训高国元
3.2FOST杯世界计算机围棋比赛
FOST杯是由日本的FusionofScienceandTechnologyorganization在1995年开始举办的,举办的时间地点大约是每年的九月在日本东京地区举行。
1997年将在日本名古屋举行。
FOST杯所提供的奖金如下:
冠军是两百万日币、亚军是五十万日币、季军则是二十万日币。
比赛是采用日本棋院的围棋规则,详细有关此比赛的细节可参考[Fotland1996]。
目前为止举办过的比赛的时间地点及比赛成绩如表四。
另主办单位为测试前几名的棋力,亦举办计算机对人脑的比赛,而两届的冠军陈志行教授的围棋程序HandTalk在经过测试后,在1995年给予日本棋院的五级棋力证书(约等于台湾九级棋力),而在1996年则获得日本棋院的四级棋力证书(约等于台湾八级棋力),由于HandTalk在近几年的各项比赛均拔得头筹,HandTalk可说是目前为止棋力最强的计算机围棋程序。
表四FOST杯历年之比赛结果
时间地点第一名第二名第三名
1995东京陈志行MichaelResisDavidFotland
1996东京陈志行MichaelResisDavidFotland
4.各计算机围棋程序概况
自1969年Zobrist完成第一个可与人对下的程序以来[Zobrist,1970],世界各地研究计算机围棋的人就越来越多,表五中为一些较为著名的程序。
由于计算机围棋尚在发展阶段,各程序所使用的方法并不相同,特别是近年来在前述比赛中前几名的程序,都是发展约十年的程序,故都有其特色和独到之处。
以下我们就分别介绍并讨论他们所使用的方法。
表五一些较著名的围棋程序程序名称
作者
单位HandTalk
陈志行
广东省中山大学
中国
GoIntellect
陈克训
UniversityofNorthCarolina
美国
Go4++
MichaelReiss
UnistatLimited
英国
ManyFaces
DavidFortland
H.P.Inc.
美国
Stone
高国元
国立台湾大学
台湾
Jimmy
颜士净
国立台湾大学
台湾
Dragon
刘东岳
国立台湾大学
台湾
Archmage
严礽麒
国立台湾大学
台湾
StarofPoland
JanuszKraszek
UniversityofSlupsk
波兰
IGO
NoriakiSanechika
AILanguageResearchInstitute
日本
Goliath
MarkBoon
UniversityofAmsterdam
荷兰
Nemesis
BruceWilcox
TOYOGOInc.
美国4.1.1许舜钦的学生们所制作的程序
由于计算机围棋比赛最早是在台湾所发起的,这也促成台湾在八十年代研究计算机围棋的风气。
在其中一个较具代表性的研发小组为台湾大学资讯工程系许舜钦教授所领导的计算机围棋研发小组,在小组中曾代表参加计算机围棋比赛的包括王若曦、曹国明、高国元、刘东岳、严礽麒和颜士净,他们所制作的围棋程序都可说都是计算机围棋发展过程中重要的里程碑,这些程序中又以Dragon程序最为知名。
Dragon程序最著名的特色应该是它的棋串攻杀系统,此系统可说是充分发挥了计算机的特色,主要的做法是采用选择式搜寻法配合启发式的策略来计算棋串的攻杀。
因为是具备相当完整的搜寻模块,所以在棋串攻杀时偶而会下出一些连有段棋士都意想不到的好棋出来。
另外再配合根据丰富的比赛经验所制作的相当完备的棋型数据库,所以至今仍然可说是一个相当优秀的计算机围棋程序[HsuandLiu,1991]。
4.1.1许舜钦的学生们所制作的程序
由于计算机围棋比赛最早是在台湾所发起的,这也促成台湾在八十年代研究计算机围棋的风气。
在其中一个较具代表性的研发小组为台湾大学资讯工程系许舜钦教授所领导的计算机围棋研发小组,在小组中曾代表参加计算机围棋比赛的包括王若曦、曹国明、高国元、刘东岳、严礽麒和颜士净,他们所制作的围棋程序都可说都是计算机围棋发展过程中重要的里程碑,这些程序中又以Dragon程序最为知名。
Dragon程序最著名的特色应该是它的棋串攻杀系统,此系统可说是充分发挥了计算机的特色,主要的做法是采用选择式搜寻法配合启发式的策略来计算棋串的攻杀。
因为是具备相当完整的搜寻模块,所以在棋串攻杀时偶而会下出一些连有段棋士都意想不到的好棋出来。
另外再配合根据丰富的比赛经验所制作的相当完备的棋型数据库,所以至今仍然可说是一个相当优秀的计算机围棋程序[HsuandLiu,1991]。
4.1.2陈志行教授的Handtalk程序
目前公认最强的计算机围棋程序应该是陈志行教授的计算机程序HandTalk,陈教授本来是广东中山大学的教授,本身的围棋棋力约有业余五段,几年前为了专心发展计算机围棋程序,申请退休并成立研发小组,专心研究计算机围棋[黄1996]。
关于HandTalk程序的内容,由于相关的程序内容及研究方法发表的并不多,现今外界对此程序的了解仅限于在比赛时与陈教授讨论所得。
以下是我们在几次比赛中与陈教授讨论所得的心得。
HandTalk程序是由汇编语言所撰写,所以它的执行速度很快,而程序本身也不大。
由于程序并不大,可以推测出其所运用到的棋型数据也并不多,而且很可能是采用rule-based的方法。
HandTalk在大多数的情况下都不会失误,陈教授本人曾提到他是用到一种类似人在下围棋时常用到的方法“手割“,来帮助判断的。
另HandTalk的定石资料也很少,这是根据我们实际测试所得到的结果。
HandTalk与其它的程序明显不同的地方是它的攻杀能力特别强,在大多数的比赛中,都可以吃掉对方几块棋而获胜。
这应该是由于程序的棋块安危判断能力,形势判断系统,眼位判断能力和棋型比对系统都很强的关系。
有关这些系统的好坏,跟设计者的棋力非常有关,陈教授本身近职业水平的棋力,显然对HandTalk程序的撰写很有帮助。
4.1.3陈克训教授的GoIntellect程序
GoIntellent也是近年来全世界数一数二的程序,有关GoIntellect的内容,陈克训教授有相当多的著作发表[Chen,1989][Chen,1990],GoIntellect由于经过多年的发展,在对局时很少出错,可说是发展的相当良好的程序。
最近GoIntellect改进较多的地方约有下列三点:
(a)精良的数据库及棋步产生系统。
(b)更快的局部攻杀系统。
(c)根据全局搜寻系统所建立的棋步选择系统。
4.1.4MichaelReiss的Go4++程序
MichaelReiss在1983年开始发展计算机围棋程序,而在最近开始有很好的表现,一度被HandTalk视为最强劲的对手。
Go4++程序的棋力与它的设计者MichaelReiss并没有很大差距,这是较为特别的地方[BurmeisterandWiles]。
MichaelReiss的主要观念是使用一些简单的算法去计算大量的信息,而不像一般计算机围棋程序大都是用一些复杂的算法去计算少量的信息。
举例来说,Go4++程序在产生一个棋步之前,会先用十五个基本的棋型比对出大约五十个候选棋步,再用会用全局搜寻的方式去考虑产生一个棋步,但所用的评估函数却很简单:
主要是考虑地域问题。
这种方式跟一般制作其它棋类的方式较为接近,此方法的好处是对于模样的感觉很有帮助,而且不需要很复杂的评估函数。
坏处则是需要很大的计算量,程序运作需要一台很快速的计算机。
Go4++目前的最大优点是它对有关地域的好点不容易失误,这是因为它考虑的候选棋步较多,且有进行全局搜寻的关系。
而它的弱点则是处理棋块攻杀的方式较弱,常会发生因为判断错误而放弃一重要的棋块,此缺点使得Go4++在最近的棋赛吃亏不少[BurmeisterandWiles]。
4.1.5DavidFotland的TheManyFacesofGo程序
TheManyFacesofGo(MFG)是最早商业化的软件之一,在国际网络围棋(IGS)上亦可看到它的踪影,发展至今也有十多年的历史,程序本身是用C语言撰写,程序大小约四万行[BurmeisterandWiles]。
MFG的特色之一是它有一个很好的棋型发展系统,目前为止它的棋型数据库约包括1200个8×8的棋型和6900个5×5的棋型,要妥善运用这么多棋型,并不是一件容易的事。
首先是棋型的来源,MFG有一个棋型编辑系统,可以用手动的方式来剪贴下所需的棋型。
Fotland本来的构想是让高段棋士与MFG对奕,再从对奕的棋谱中剪贴下所需的棋型,但后来Fotland却发现最好的棋型撷取地方是IGS上的高段棋士对奕的棋谱。
再来是当这么多棋型要运用在程序中时,所需的计算量是很大的,例如要在一个19×19的棋盘比对1000个棋型,用普通的方式可能要三百万个运算,MFG将棋型编译成为用位数组表示,如此便可用平行位比对的方式进行计算,可将计算量降到350,000[Fotland1996]。
4.1.6高国元的Stone程序
高国元本来也是台大信息许舜钦教授的学生,后来到北卡大成为陈克训教授的博士班研究生,所以他的程序可说是综合两者之所长。
高国元目前所作的研究中部份是有关计算机围棋的官子,这个研究的主要的方法是将组合对局理论(combinatorialgametheory)应用在计算机围棋的官子上,目前相关的一些结论是组合对局理论应用在收小官时,可以得到非常好的效果。
5.结论及未来展望
我们将计算机围棋发展至今的一些代表性程序的棋力统计于图六,这些程序为陈志行教授的HandTalk、陈克训教授的GoIntellect、MarkBoon的Goliath和许舜钦教授的学生们所制作的程序(包括王若曦、曹国明、高国元、刘东岳、严礽麒和颜士净)。
从图六我们可以看出在计算机围棋发展初期的八十年代,围棋程序以大约每年两级的速度在进步,而到了九十年代计算机围棋已发展到某一程度,但仍以大约每年一级的速度在稳定进步中,由此看来,计算机围棋目前仍在稳定发展之中,另一方面,在前述文章中,由各围棋程序各有特色看来,计算机围棋还有相当大的发展空间。
综合上述两点,再根据我们本身对计算机围棋的了解,我们推测计算机围棋的棋力大约在公元两千年前后,可以到达日本棋院的初段棋力(约台湾的五级左右)。
图六计算机围棋棋力进步情形(棋力/年份)
参考文献
[许1989]许舜钦,计算机围棋在台湾的回顾与前瞻,中国工程师学会,日本分会,1989年学术研讨会论文集,1989。
[围棋基金会1995]应昌期围棋教育基金会,计点制围棋规则,1995年版。
[黄1996]黄天源,比朝阳更绚烂的黄昏,羊城晚报,港澳海外版,1996/11/15。
[Allisetal.,1991]L.V.Allis,VanDenHerik,andH.J.Herschberg.HeuristicProgramminginArtificialIntelligence2,EllisHorwood1991.
[Berli
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 碁世界月刊 精品 最强 围棋 软件 Zen 开发 历程 世界 月刊