（通信与信息系统专业论文）基于认知科学的计算机围棋博弈问题的研究.pdf

j 华东师范大学学位论文原创性声明 郑重声明：本人呈交的学位论文基于认知科学的计算机围棋博弈问题的研 究，是在华东师范大学攻读硕士壤判( 请勾选) 学位期间，在导师的指导下 进行的研究工作及取得的研究成果。除文中已经注明引用的内容外，本论文不包 含其他个人已经发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和 集体，均已在文中作了明确说明并表示谢意。 作者签名： 日期：加f 。年，月声日 华东师范大学学位论文著作权使用声明 基于认知科学的计算机围棋博弈问题的研究系本人在华东师范大学攻读 学位期间在导师指导下完成的硕士催塑一( 请勾选) 学位论文，本论文的研究成 果归华东师范大学所有。本人同意华东师范大学根据相关规定保留和使用此学位 论文，并向主管部门和相关机构如国家图书馆、中信所和“知网 送交学位论文 的印刷版和电子版；允许学位论文进入华东师范大学图书馆及数据库被查阅、借 阅：同意学校将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索， 将学位论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位 论文。 本学位论文属于( 请勾选) ( ) 1 经华东师范大学相关部门审查核定的“内部 或“涉密学位论文， 于 年月日解密，解密后适用上述授权。 ( ) 2 不保密，适用上述授权。 导师签名本人签名会锄 力吼。年f 1 月；矿日 “涉密”学位论文应是已经华东师范大学学位评定委员会办公室或保密委员会审定过的学 位论文( 需附获批的华东师范大学研究生申请学位论文“涉密”审批表方为有效) ，未 经上述部门审定的学位论文均为公开学位论文此声明栏不填写的，默认为公开学位论文， 均适用上述授权) 摘要 认知科学是2 0 世纪世界科学标志性的新兴研究门类，它作为探究人脑工作 机制的前沿性尖端学科，已经引起了全世界科学家的广泛关注。由于在视觉表现 形式上具有抽象、复杂的特性，计算机围棋正在成为认知科学研究的重要方向和 工具。 近年来，研究者大多采用m o n t ec a r l o 似c ) 、u p p e rc o n f i d e n c eb o u n d sa p p l i e d t ot r e e sc o c t ) 、a l lm o v e sa sf i r s t ( a m a f ) 等不包含任何围棋知识的统计算法解 决围棋对弈问题。本文则以不同的角度，通过研究围棋棋手的知识结构、表述形 式、思维模型等，提出了一系列基于模拟人类棋手思考方式，量化棋手模糊判断 结果的计算机围棋解决方案，不但有助于围棋程序棋力的提高，更有助于提升对 人类认知能力的理解，促进认知科学的研究、发展，具有重要的创新意义和实用 价值。 论文具体的创新内容如下： 1 对棋块的气划分等级。根据分级结果，可以判断棋块的安全程度，确定 捕获目标，产生候选着点并对其排序。通过m e m o r y e n h a n c e dt e s td r i v e r ( m r d ( f ) ) 算法对候选点依次进行搜索，寻找出正确的捕获棋步。实验结果表明 其效果较好，可以应用于计算机围棋实战中。这也为第三章计算厚势价值时确定 有效子数做了必要的准备。 2 对厚势价值进行量化。与传统的计算完全控制点的数量不同，本文提出 了厚势的影响有如控制概率在二维空间的弥散，所有空点被控制的概率总和即为 此厚势价值的思想，并为此设计了一种棋子影响函数，建立了一种计算厚势价值 的数学模型；尝试将厚势的价值分为基本值和附加值两部分，进而动态地调整不 同棋力下对厚势价值的不同判断，模拟了人类棋手对厚势的感觉；利用简单遗传 算法对模型参数进行分级优化，获得了各个棋力层次下的厚势价值量化模型。 实验结果表明该模型达到了较高精度，可以应用于计算机围棋序盘、中盘、 收官等模块中，为第四章量化棋局形势的程序设计提供了基础。 3 提出了一种对棋局形势进行量化评价的方法，采用获胜概率表征量化结 果。通过模拟人类棋手判断形势的思考方式，以领先目数和棋局进展程度作为获 胜概率的计算依据，并结合多级种群竞争消亡算法对模型参数进行了优化。当围 棋程序的棋力发生变化时，只需相应调整模型中的参数，因此模型可以适用于不 同棋力层次，具有较强的移植性和较高的普适性，在实验中取得了较好的效果， 华东师范大学博士学位论文 为第五章程序选择、确定最佳棋步奠定了基础。 这种根据围棋知识构建模型、利用遗传算法确定参数的方法也可以应用于其 他计算机博弈问题的解决。 4 提出了一种计算机围棋中盘着手策略，包括棋步产生、评估和确定的方 法。通过计算实地价值、战略价值、棋形价值和后续价值，对候选棋步进行初始 评估。根据目的性差异，将棋步分为进攻和防御两部分；并结合获胜概率，计算 攻防力度调整权值，从而动态调整攻击和防御棋步的评估值，寻找出最佳棋步。 此方法既模拟了人类棋手在落子前的思考过程，又发挥了计算机擅于运算的特 长，将动态分析、静态搜索和知识库的应用相结合，体现出一定层次的智能。 5 开发了一个计算机围棋博弈系统c o g n i t i v e g o ，将上述内容整合实现。每 当落子前，c o g n i t i v e g o 先根据模式库寻找一些可能的着点，继而根据自身棋力， 对双方的实地、厚势、棋块强弱进行判断，并结合判断结果调整下一步棋的目标 方向。在此过程中，模式库影响候选棋步的推荐，形势判断则影响目标之间的转 换。 综上所述，本文主要采用模拟人类棋手思考过程，建立相应模型的方式对计 算机围棋相关问题进行研究，其研究方法和成果对于提升计算博弈智能，促进认 知科学发展具有现实的应用价值和理论意义。 关键词：认知科学，计算机围棋，厚势价值量化，形势判断，获胜概率 h a b s t r a c t c o g n i t i v es c i e n c ei sas y m b o l i ce m e r g i n gr e s e a r c hf i e l do fw o r l ds c i e n c ei nt h e 2 0 mc e n t u r y a sa ne x p l o r a t o r ys u b j e c tf o c u s m go nt h ew o r k i n go fh u m a nb r a i n , i th a s a r o u s e dw i d ea t t e n t i o nf r o ma l la r o u n dt h ew o r l d c o m p m e rg oh a sb e c o m ea n i m p o r t a n tt o o l i nc o g n i t i v es c i e n t i f i cr e s e a r c hd u et oi t sv i s u a l a b s t r a c t n e s sa n d c o m p l e x i t y i nr e c e n ty e a r s ，r e s e a r c h e r sh a v eb e e ns o l v i n gg og a m ep r o b l e m sb yu s i n gt h e a l g o r i t h m si n c l u d i n gn og ok n o w l e d g es u c ha sm c ，u c t , a m a f ，e t c t h i sp a p e r p r e s e n t sas e r i e so fg og a m er e s o l u t i o n sb a s e do nt h es i m u l a t i o no fh u m a np l a y e r s t h i n k i n gm e t h o da n dq u a n t i z a t i o no ft h eg e n e r a lj u d g m e n tb ya n a l y z i n gt h e k n o w l e d g es t r u c t u r e ，e x p r e s s i o ns t y l ea n dt h i n k i n gm o d eo fg op l a y e r s i ti sn o to n l y h e l p f u lf o ri m p r o v i n gt h el e v e lo ft h eg op r o g r a m , b u ta l s o f o rp r o m o t i n gt h e c o g n i t i v ea b i l i t yo ft h eh u m a nb e i n g s ，w h i c hh a si n n o v a t i v es i g n i f i c a n c ea n d u t i l i t a r i a nv a l u ei n t h er e s e a r c ha n dd e v e l o p m e n to fc o g n i t i v es c i e n c e 1 鬈 t h ei n n o v a t i v et h i n k i n gi sa sf o l l o w s ： 1 s e tl e v e l s f o r t h eg r o u p s l i b e r t i e s a c c o r d i n gt ot h el e v e l s ，t h e g r o u p s s a f e n e s sc a nb ej u d g e d , t h et a r g e tc a nb ef e da n dt h ec a n d i d a t em o v e sc a nb e g e n e r a t e da n ds o r t e d s e a r c ht h ec a n d i d a t em o v e si ns e q u e n c eb ym t d ( f ) a l g o r i t h mt of i n dt h eb e s tc a p t u r em o v e t h er e s u l ts h o w st h em e t h o dh a sg o o de f f e c t a n dc a nb ea p p l i e di nt h er e a lg a m eo fc o m p u t e rg o ，w h i c hl a y sg r o u n d w o r kf o r d e f m i n g e f f e c t i v en u m b e ro fs t o n e sw h e nc a l c u l a t i n gt h es t r o n gg r o u p sv a l u e 2 q u a n t i z et h ev a l u eo ft h es t r o n gg r o u p s i n s t e a do ft h et r a d i t i o n a lw a yo f c a l c u l a t i n gt h ec o n t r o l l e dp o i n t s ，t h i sp a p e rp r e s e n t sat h e o r yt h a tt h ei n f l u e n c eo ft h e s t r o n gg r o u p sr e s e m b l e st h ed i f f u s i o no fc o n t r o lp r o b a b i l i t yi nt h et w o d i m e n s i o n a l s p a c ea n dt h es u mo ft h ec o n t r o lp r o b a b i l i t yo ft h eu n o c c u p i e dp o i n t se q u a l st ot h e v a l u eo ft h es t r o n gg r o u p a ni n f l u e n c ef u n c t i o na n dam a t h e m a t i c a lm o d e la r e e s t a b l i s h e dt op r o v ei lw ca t t e m p tt od i v i d et h ev a l u eo ft h es t r o n gg r o u p si n t ot h e b a s i cv a l u ea n dt h ea d d e dv a l u e ，a n dt h e nf u r t h e ra d j u s tt h ej u d g m e n t so ft h ev a l u eo f t h es t r o n gg r o u p sa n ds i m u l a t et h es e n s eo fh u m a n p l a y e r st o w a r dt h es t r o n gg r o u p s f i n a l l y , t h es i m p l eg e n e t i ca l g o r i t h mi su s e dt oo p t i m i z et h em o d e l sp a r a m e t e rb y m 华东师范大学博士学位论文 l e v e la n dt h es t r o n gg r o u pq u a n t i z a t i o nm o d e l so fd i f f e r e u tg ol e v e l sa r eo b t a i n e d t h ee x p e r i m e n t a lr e s u l ts h o w st h em o d e li so fh i g ha c c u r a c ys ot h a ti tc a nb e a p p l i e di ns t a r t i n gg a m e ，m i d d l eg a m ea n de n dg a m eo ft h ec o m p u t e rg oa n dp r o v i d e t h eb a s i sf o rt h es t a t i ce v a l u a t i o np r o g r a ma n df o u n d st h eb a s i sf o rt h es u b s e q u e n t p r o g r a md e s i g no fq u a n t i z i n gt h eg a m es i t u a t i o n 3 b a s e do nt h ea b o v em o d e l ，aq u a n t i z a t i o nm e t h o di sp r e s e n t e dt oe v a l u a t et h e s i t u a t i o na n dw i n n i n gp r o b a b i l i t yi su s e dt os h o wt h er e s u l t so fq u a n t i z a t i o n t h e p a r a m e t e r sa r eo p t i m i z e db ys i m u l a t i n gh u m a np l a y e r st h i n k i n gm e t h o d ，t a k i n gt h e l e a d i n gp o i n t sa n dg a m ep r o c e s sa st h ec a l c d a t i n gb a s i so fw i n n i n gp r o b a b i l i t ya n d c o m b i n i n gs p e c i e sc o m p e t e - d i co u ta l g o r i t h m s t h ep a r a m e t e r si nt h em o d e lc a nb e a d j u s t e da c c o r d i n gt od i f f e r e n tg ol e v e l ss ot h a tt h em o d e lc a ns u c c e s s f u l l yc o p e 、j l ，i m v a r i o u sg ol e v e l s ，w h i c hb o a s t sg o o dp o r t a b i l i t ya n du n i v e r s a l i t ya n do b t a i n s s a t i s f y i n gr e s u l t si nt h ee x p e r i m e n t t h em e t h o dw h i c he s t a b l i s h e sm o d e lb yg ok n o w l e d g ea n dd e f i n e sp a r a m e t e r s b yg e n e t i ca l g o r i t h mc a na l s ob ea p p l i e di no t h e rc o m p u t e rg a m e s t h u si tl a y st h e f o u n d a t i o nf o rt h es u b s e q u e n tp r o g r a m st os e l e c ta n dd e f i n et h eb e s tm o v e 4 am i d d l eg a m es t r a t e g yi nc o m p u t e rg oi n c l u d i n gm e t h o d so fg e n e r a t i n g ， e v a l u a t i n ga n dd e f i n i n gm o v e si sp r e s e n t e d t h ec a n d i d a t em o v e sa r ei n i t i a l l y e v a l u a t e db ya s s e s s i n gt h ev a l u e so ft e r r i t o r y , s t r a t e g y , s h a p ea n di n f l u e n c e t h e m o v e sa r ed i v i d e di n t oa t t a c k i n ga n dd e f e n d i n gm o v e sa c c o r d i n gt ot h ed i f f e r e n c eo f t h ep u r p o s e s c o m b i n i n g 、7 l ，i n lw i n n i n gp r o b a b i l i t y , t h es t r e n g t ho fa t t a c ka n dd e f e n s e i sc a l c u l a t e da n dt h ew e i g h tv a l u ei sa d j u s t e d ，a n dt h e nt h ew e i g h tv a l u e so fa t t a c k i n g a n dd e f e n d i n gm o v e sa r ed y n a m i c a l l ya d j u s t e ds ot h a tt h eb e s tm o v ei so b t a i n e d t h i s m e t h o dd o e sn o to n l ys i m u l a t et h et h i n k i n gp r o c e s so fh u m a n p l a y e r sb u ta l s om a k e s f u l l p l a yo ft h ec a l c u l a t i n ga d v a n t a g eo ft h ec o m p u t e rt oc o m b i n et h ed y n a m i c a n a l y s i s ，s t a t i cs e a r c ha n dk n o w l e d g eb a s e ，w h i c hs h o w st h ei n t e l l i g e n c eo ft h e c o m p u t e r 5 c o g n i t i v e g o ，ac o m p u t e rg og a m es y s t e mi sd e v e l o p e db yi n t e g r a t i n gt h e a b o v e c o g n i t i v e g os e a r c h e ss o m ep o s s i b l em o v e sa c c o r d i n gt ot h ep a t t e r nl i b r a r y b e f o r ep l a y i n ge a c hm o v e ，a n dt h e nm a k ef u r t h e rj u d g m e n t sa b o u tt h et e r r i t o r y , s t r o n g g r o u p sa n dg r o u ps t r e n g t ho f b o t hs i d e sa c c o r d i n gt oi t sg ol e v e l a f t e rt h a t , i ta d j u s t s i v t h es u b j e c td i r e c t i o no ft h en e x tm o v eb yt h ej u d g m e n tr e s u l t d u r i n gt h ep r o c e s s ，t h e p a a e ml i b r a r yh a si n f l u e n c eo nt h er e c o m m e n d a t i o no f t h ec a n d i d a t em o v e sw h i l et h e t r a n s f o r m a t i o no ft h es u b j e c ti si n f l u e n c eb yt h ep o s i t i o n a la n a l y s i s i nc o n c l u s i o n , t h i sp a p e rr e s e a r c h e so nt h ec o m p u t e rg op r o b l e mm a i n l yb y e s t a b l i s h i n gt h em o d e lb a s e do ns i m u l a t i n gt h et h i n k i n gp r o c e s so f t h eh u m a np l a y e r s t h er e s e a r c hm e t h o da n dr e s u l t sh a sa c a d e m i ca n dp r a c t i c a lv a l u ei np r o m o t i n g c o m p u t e rg a m ei n t e l l i g e n c ea n dt h ed e v e l o p m e n to fc o g n i t i v es c i e n c e k e yw o r d s ：c o g n i t i v es c i e n c e ，c o m p u t e rg o ，q u a n t i z a t i o no ft h es t r o n gg r o u p s v a l u e ，p o s i t i o n a la n a l y s i s ，w i n n i n gp r o b a b i l i t y v 目录 摘j i 蕈i a b s t r a c t i i i 第一章绪论1 1 1 研究背景1 1 1 1 围棋简介1 1 1 2 计算机围棋简介3 1 1 3 计算机围棋的意义6 1 2 计算机围棋的研究现状7 1 3 论文的研究思路与内容安排9 第二章吃子问题求解模型的构造1 1 2 1 前言1 1 2 2 确定捕获对象和捕获方法l l 2 - 2 1 简单吃子法1 1 2 2 2 捕获对象的确定1 3 2 2 3 气的分级15 2 2 4 候选点的产生。1 7 2 3 搜索算法与走法排序2 l 2 3 1m t d ( f ) 搜索算法2 1 2 3 2h a s h 表的迭代与走法排序2 2 2 3 3 考虑对手最强的反抗路径2 2 2 4 实验结果与分析2 4 2 5 小结2 5 第三章厚势价值量化模型的构造2 7 3 1 前言2 7 3 2 厚势价值量化的理论基础2 7 3 3 厚势价值的量化3 0 3 3 1 影响函数3 0 3 3 2 厚势价值量化模型i ：f e n c e 、k m n a b l e 3 9 3 3 3 厚势价值量化模型i i ：f e n c ec o g n i t i v e 。4 1 3 4 实验结果与分析5 2 3 5 小结5 3 第四章获胜概率量化模型的构造5 5 4 1 前言5 5 华东师范大学博士学位论文 4 2 获胜概率模型的意义5 5 4 3 获胜概率计算模型i ：l a u r e lm i d g a m e 一5 6 4 3 1 棋局进展程度一5 7 4 3 2 领先目数5 7 4 3 3 获胜概率模型6 l 4 4 获胜概率计算模型i i ：l a u r e lc o g n i t i v e 6 3 4 4 1 计算方法6 3 4 4 2 参数优化6 6 4 5 实验结果与分析7 3 4 6 小结7 5 第五章c o g n i t i v e g o 着手选择与系统集成7 7 5 1 前言。7 7 5 2 系统界面和功能7 7 5 3 着手选择8 0 5 3 1 着手生成8 1 5 3 2 着手评估8 2 5 3 3 评估值修正8 2 5 3 4 最佳棋步的确定8 4 5 4 小结8 4 第六章总结和展望8 7 6 1 总结8 7 6 2 展望8 8 附录1 围棋业余5 段段位证9 1 附录2 围棋业余5 段段位证书。9 1 附录3 本文所涉及的各模型信息表9 2 攻读博士学位期间发表和完成的论文9 3 参考文献9 5 致谢1 0 2 第一章绪论 第一章绪论 1 1 研究背景 认知科学是一门研究人类感知和思维信息处理过程的学科。作为2 0 世纪世 界科学标志性的新兴研究门类，它为揭示人脑的工作机制这一最大的宇宙之谜作 出了不可磨灭的贡献，已经引起了全世界科学家们的广泛关注。 认知科学的主要内容包括：感觉的输入、复杂问题的求解、人类个体和人类 社会的智能活动、人类智能和机器智能的性质等，涉及计算机学、心理学、神经 生理学、人类学、哲学、语言学等多门学科。由于认知系统的复杂性，需要对它 进行多维度、全方位的综合研究；不同专业背景的研究者，对认知科学所采取的 具体研究方法也各有不同。 从上世纪6 0 年代开始，棋类被用来作为人类思维的研究对象。国际象棋是 早期研究的热门课题，通过优秀的评估函数和搜索算法，程序棋力非常高【l 】，1 9 9 7 年，著名的计算机国际象棋程序“深蓝”战胜世界冠军卡斯帕罗夫成为轰动一时 的新闻事件【2 】。与国际象棋不同，围棋棋局状态的搜索空间巨大，计算机难以处 理模糊概念并且没有合适的评估函数用于修剪，因此类似于国际象棋程序中使用 的搜索、评估、模式匹配技术在围棋中无法取得良好的效果，计算机围棋程序的 棋力也难以得到提高。 与国际象棋程序战胜人类世界冠军的成绩相比，围棋程序在经过五十年的研 究后，在标准1 9 路棋盘上竟然都达不到业余1 段的水平，这是对每个认知科学 研究者的挑战。围棋是研究认知科学的良好工具，开发出高水平的围棋程序有助 于对人类认知能力的理解。 计算机围棋期待着新的思想和新的模型。新思想和新模型不但能提升计算机 围棋棋力，也将认知科学带来许多重要方法和理论，产生广泛而深远的社会影响 和学术影响。 1 1 1 围棋简介 围棋起源于中国古代，是一种策略性二人棋类游戏；它将科学、艺术和竞技 三者融为一体，不但是一种游戏，更是一种艺术，一种文化。古人常以“琴棋书 域 论及一个人的才华和修养，其中的“棋”就是指围棋。 华东师范大学博士学位论文 围棋的规则如下： ( 1 ) 棋盘：标准的围棋棋盘由1 9 条距离相等、垂直交叉的平行线组成，共构成 3 6 1 个交叉点。其中一些特殊交叉点上标有小圆点，称为星位。中央的星位 又称天元。如图1 1 中，圆圈标记的点即为星位；其中，棋盘中央的a 点为 天元。 ( 2 ) 落子：对局双方各执一色棋子，黑先白后，交替下子，每次只能下一子。棋 子下在棋盘的点，落子后，不能向其他位置移动。 ( 3 ) 气：一个棋子在棋盘上，与它直线紧邻的空点便是这个棋子的“气 。如 果在棋子直线紧邻的点上有己方棋子存在，那么它们便相互连接成一个不可 分割的整体，称为棋块：它们的气也应一并计算。如果棋子直线紧邻的点上 有对方棋子存在，那么这口气就不复存在。如果所有的气均被对方所占据， 棋块就呈无气状态。无气状态的棋子不能在棋盘上存在。如图1 1 中，方块 标记的点是黑子b 的气位，b 位黑棋共有4 口气。由于黑子c 和d 紧邻， 因此它们组成一个棋块，三角形标记的点是棋块c d 的气位，共有6 口气。 “) 提子：把无气之子提出盘外的手段叫“提子”。落子后，如果对方棋子无气， 此时不论己方棋子是否有气，都应立即提取对方无气的棋子。 ( 5 ) 禁着点：如果一方落子后该子立即呈无气状态，同时又不能提取对方的棋子， 这个点，叫做“禁着点”：即这一点禁止被提方下子。如图1 1 中，黑子e 的4 口气都被白棋占据，它将被白棋提起。提子后，e 位就是黑棋的禁着点。 ( 6 ) 劫：为了防止棋局反复，规则禁止全局同形再现。例如：图1 1 中，黑棋可 于g 位提起白子f ；但根据提子规则，白棋也能于f 位将黑子g 提回。如果 没有特殊规定，棋局将出现反复，无法正常进行。因此规定一方提子后另一 方需要至少间隔一手才能在此局部重新提子；这种现象称为劫。 ( 7 ) 终局：棋局进展至双方都同意落子完毕时为终局；另外，对局中有一方中途 认输也为终局。终局后，除去贴目，占据交叉点多的一方即取得胜利。 2 第一章绪论 bc d efg h】x毛l麓kopqr s t 一、j 一、 一、 v、 ，、 ， i 一叠一 i 7 二盈气l 二叠h 二 r v l 一 r - | 羞 锚 j 一一e 吲 a j、 、 罗 、， x 矿 盔刍 ，妒 di菱上薹 ，拶￥矽 一、 a 、 一、一 、 ， 1罗q妒 ，、 ， abcd ef6 hjklm拜op q rst j 图1 1 围棋简介图 f i g 1 1f i g u r eo f g o 1 1 2 计算机围棋简介 关于计算机围棋的著作最早出现于2 0 世纪6 0 年代。1 9 6 2 年，h r e m u s 曾 经使用围棋来作为机器学习问题的研究对象【3 】。1 9 6 8 年，a l b e r tz o b r i s t 在他的博 士论文中描述了一个基于模式识别的围棋程序【4 邓】，这也是最早能够下完整盘棋 的程序。1 9 7 2 年，被称为计算机围棋之父的w a l t e rr e i t m a n 和b r u c ew i l c o x 开 始将围棋作为研究对象，并将他们编写的程序命名为r e i t m a n - w i l c o x 和 i n t e r i m 2 【7 ，8 ，9 1 。 r e i t m a n 和w i l c o x 认为，计算机围棋是认知和知识的综合。程序中应当尽量 获得与高水平棋手相当的认知水平，识别并存储围棋知识。其中，着手决策知识 包括如何捕获对方棋子，如何围空等内容；形势判断知识包括如何确定棋块属性 3 均墟玎：乌圬m蛤技n9 g 7 5 in辱3瓠l 坞擂口坫塔m坞控n埒9 8 7 6 s 3 2 i 华东师范大学博士学位论文 等内容；通过将这些知识加以综合，最终选择出最佳落子点。 i n t e r i m 2 程序的棋力较低，大约只有2 7 级【l o 】。因此它对计算机围棋的认 识并不全面。 随着1 9 8 5 年第一届“应氏杯 国际计算机围棋赛以及1 9 8 9 年第一届计算机 奥林匹克竞赛的举办，计算机围棋的影响越发广泛，世界上许多国家的机构或个 人都加入到计算机围棋的研究中，涌现出了诸如e x p l o r e r l l l , 1 2 , 1 3 , 1 4 , 1 5 、g o i n t e l l e c t 1 6 , 1 7 , 1 5 , 1 9 , 2 0 、g 0 4 抖【2 1 1 、手谈 2 2 , 2 3 、m a n yf a c e so f g o 2 4 , 2 5 , 2 6 1 、g n u g o 2 7 、 m o g o 2 8 2 9 】等许多棋力较强的围棋程序。综合以上各个强力程序的特点可以得 出，一个典型的计算机围棋程序通常包括以下3 个方面： ( 1 ) 获取信息： 在确定着手前，计算机围棋程序需要获取棋局的各项信息。这些信息包括： 棋串：由同色棋子紧密相连所构成的整体称为棋串。 有哪些棋串? 分别由哪些棋子构成? 每个棋串由多少棋子构成? 每个棋串有多少口气? 棋串的战术性：它是否战术稳定? 棋块：由相邻棋串构成的整体称为棋块。 有哪些棋块? 分别由哪些棋串构成? 棋块是否具有眼位? 如果有，有几个眼? 棋块的位置：它是否与模样或者实地相连? 棋块的安全性：棋块的敞开度是多少? 是否会受攻击? 如果受到攻 击，成功逃脱的可能性是多少? 死活： 棋块的眼位：它是否已经具备至少两个明确的眼位? 棋块与其他己方活棋的距离有多远? 是否易于连接? 实地： 双方已经确定的实地分别有哪些? 各有多少目? 双方潜在的实地分别有哪些? 各有多少? 势力： 如何划分双方的势力范围? 我方可以打入对方的哪些势力范围? 我方哪些势力范围会被敌方打入? 4 第一章绪论 根据获取的上述信息，程序可以确定下一步选择方向，进而生成相应的着手。 例如：如果一个棋块有两个明确的眼位，即它是活棋，则立刻放弃对此棋块的后 续搜索；如果一个敌方棋块没有眼位，并且敞开度较低，则立即搜索进攻棋步， 试图将吃捕获或者通过攻击获取利益。 ( 2 ) 生成着手 着手，也称着法，指当前可供选择的棋步。着手的生成通常考虑以下1 5 个 方面： 定式库：存储大量定式的数据库。在棋局初期，尤其是各角部的定型中， 需要利用定式库，进行模式匹配。 布局库：存储大量布局着法的数据库。在棋局初期，尤其是各边的定型 中，采用布局库进行模式匹配，效果较好。 模式库：存储大量模式的数据库。对于一些基本模式( 例如：无忧角两 翼张开的棋形) ，将其形状和价值存储于数据库中。实战遇到相同棋形， 可以直接对其进行赋值，从而提升运算速度。另外，模式库也能帮助解 决一些简单的吃子及死活问题。 扩张己方模样：采用拆边、争夺中央控制点等方法，增大己方模样的规 模。 削减对方模样：采用侵消的方法，减小对方模样的规模；或采用打入的 方式，直接将对方的模样彻底破坏。 吃子着点：通过第一步获取的信息，判断哪些棋子容易被捕获。如果是 己方棋子，寻找出逃着点：如果是对方棋子，寻找捕获棋步。 死活着点：通过第一步获取的信息，判断哪些棋块存在死活问题。如果 是己方棋块，寻找做活着点；如果是对方棋块，寻找杀伐棋步。 攻防着点：通过第一步获取的信息，判断哪些棋块安全度较低，容易遭 受攻击。如果是己方棋块，寻找防守着点；如果是对方棋块，寻找进攻 棋步。 实地价值：棋步使实地增加的目数。 厚势价值：棋步形成厚势，或者使厚势影响范围扩大的价值。 棋形价值：棋步使己方获得好形或破坏对方棋形。 劫争：打劫时，需要如何考虑寻找劫材，是否应劫，以及是否消劫等问 题。 5 华东师范大学博士学位论文 稳健着法：当己方取得优势时，需要采用安全的着法，快速定型，消除 各种不安定因素，以求稳妥获得胜利。 胜负手：当己方劣势时，需要采用激烈的着法，挑起争端，扩大棋盘， 创造逆转的良机。 搜索深度：根据时间限制，选择合适的搜索深度。 所有着手和目标都生成好之后，接下来需要对生成着手进行选择。例如：当 前局面下有某一棋步能扩张己方实地，另一棋步能破坏对方模样，应当如何选 择? 此时，通常采用对各候选棋步进行评分，分数最高者即为最佳棋步的方法。 根据各种规则对棋步进行评分的过程称为着手评估。 ( 3 ) 评估着手 首先，计算着手的实地价值，主要考虑己方增加的目数和使对手减少的目数。 其次，计算着手的势力价值，主要考虑己方厚势影响值的增量和使对方厚势影响 值减弱的数量。最后，根据分断联络、攻防组合、战术效果等着手目标，对评估 值进行修正。 1 1 3 计算机围棋的意义 在对认知科学的研究中，计算机围棋是一个重要工具 3 0 3 1 , 3 2 1 。 人类的认知系统与真实世界总在不断产生相互作用，认知科学的目标就是发 掘这种相互作用的机制和规律。因此，认知科学的实验不能太过复杂，必须保证 实验中能清楚地考察到研究对象的认知能力；与此同时，为了模拟真实世界的复 杂性，实验却又必须选择特别复杂的领域。因此，研究对象的复杂性既不能太高， 也不能过低。另外，保持真实世界的特征也是认知研究的一大要求。认知实验中， 研究对象所采用的知识，必须能代表人类世界所使用的知识。 l o n g s t o n 论证了围棋正是真实世界的一个简化【3 ”。与其它游戏相比，围棋 具有以下优势： 围棋在视觉上的表现形式( 例如：某个点是白子、黑子或者是空点) 必须通 过抽象的方式，而不能简单、直观的进行理解。因此，对局者必须具备识别