（基础心理学专业论文）计算机围棋中的算法研究.pdf

计算机围棋中的算法研究 基础心理学专业博士研究生岳鹏 指导教师邱玉辉教授 摘要 博弈是人工智能的重要研究主题，人工智能的发展在很大程度上得益于博弈 研究的发展。作为博弈研究的主要内容之一，棋类博弈得到了满意的解决，唯一 的例外的是围棋，目前最优秀的围棋程序的水平还不及人类初级棋手。由于围棋 的搜索空间太大、计算机难于处理模糊概念且难于设计学习算法，造成了计算机 围棋程序的棋力难于提高围棋是检验人工智能发展水平的良好环境，如何提高 围棋程序的棋力是人工智能领域的一大难题。同时，开发出与人类棋手水平相当 的围棋程序也有助于对人类认知能力的理解。所以计算机围棋研究具有重要的理 论意义和实用价值。 我们首先介绍了国内外计算机围棋研究现状，包括基础算法、搜索算法和学 习算法三方面并介绍了部分计算机围棋程序，认为计算机围棋的搜索算法主要有 m i n m a x 算法、a l p h a b e t a 算法、f a i l s o f t 算法、n e g m a x 算法、n e g s c o u t 算法和m t d f 算法等等，涉及到的学习算法和理论基础主要有组合博弈理论、数学形态学、蒙 特卡罗算法、模糊学习、分治法、强化学习算法、遗传算法、神经网络、支持向 量机、贝叶斯模式分类、基于解释的泛化和并行算法等等，指出了目前研究中存 在的主要不足主要表现为局面表示法欠完善、中盘策略欠完整以及学习算法欠成 熟。 然后，我们简述了本研究的相关理论基础，包括数学形态学、有限状态机、 线性模型、感知机与遗传算法。 接着，我们阐明了本研究提出的棋手思维模型、基础算法、搜索算法、学习 算法及相应实验结果。具体说来，我们完成的主要工作与创新点包括以下几个方 面： 一、提出了一个完整的棋手思维模型。这是在提出了领土领海和领空等地域 概念、提出了局面的层次表示法、归纳并分类了大量围棋术语、提取了目标概念、 建立了目标图、总结了若干目标选择原则和走步属性并分析了棋风概念的基础上 完成的。这个模型的特点在于它的完整性和围棋术语的分类、目标选择原则与走 西南大中博f 学f j ，论文 步属性的全面性 二、设计了基于数学形态学的局面层次表示法、棋群聚类算法和地域划分算 法。这些有统一理论基础的算法计算简单，实验结果表明其效果良好。利用已有 的数学形态学理论可以设计更多有意义的启发式策略。 三、设计了p e m i s 模式编码方法。它基于模式的邻近特征、行列特征和轮廓 特征进行编码，其突出优点是与模式的黑白对称性、旋转与翻转对称性以及平移 对称性均无关，实验结果表明这种模式编码方法性能良好。在基础算法方面，我 们还设计了一种走步增量算法。 四、设计了复合目标搜索算法。我们认为复合目标可看作是由“与”或“或” 关系构成的单一目标的二维向量。复合目标搜索算法的优点是其调用的基本函数 可由单一目标搜索算法的基本函数合成。我们还比较了经典搜索算法的性能。 五、设计了p e m i s 模式库与定式库学习算法。实验结果表明了其有效性，最 终学习到的模式库与定式库占用的空间比较小。另外，还设计了z o b r i s t 定式 库学习算法，实验结果也表明了其有效性。在学习算法方面，我们还设计了棋形 与气术语的示教学习算法和棋风模型的遗传学习算法。 六、开发了以此棋手思维模型为核心的计算机围棋程序s h o u t g o ，实现了上 述各算法。s h o u t g o 认为棋手拥有模式库和定式库，有各自的棋风；棋手在完成 棋群聚类和地域划分后，在目标选择原则的指引下以对方最后所下之子为焦点进 行目标猜测，同样在目标选择原则及棋风的指引下生成特定目标，继而以目标为 导向在各自的模式库和定式库推荐走步的作用下进行搜索发现走步，再根据走步 属性选取特定走步，如果目标不成功或无可行走步。则重新进行地域划分或根据 其它决策原则生成其它目标，直到发现合适走步：在这一过程中，模式库和定式 库影响了走步的推荐。棋风影响了目标之间的跳转。 - 最后，我们探讨了棋手思维模型的评价，走步增量算法与走步扫描算法的关 系、数学形态学方法在基础算法中的应用、劫与共活现象对搜索的影响、搜索树 特点与心理因素的关系、搜索时间估计、局面评价函数、目标搜索的可学习性以 及棋风建模等问题，并探讨了机器学习方法在计算机围棋中的应用可能性，提出 了进一步的研究计划。 计算机围棋研究作为人工智能领域的一个分支，与心理学有着天然联系。我 们在研究过程中，特别强调以人类棋手为本的原则，力求棋手思维模型与人类棋 手真实思维过程的高度契合，力求其学习算法的完善。我们今后的研究重点将在 学习算法上，能象人类棋手一样地不断地学习，计算机围棋才有希望。 关键词计算机围棋，棋手思维模型，搜索算法，学习算法 t h e s t u d yo fa l g o r i t h m si nc o m p u t e rg o m a j o r g e n e r a lp s y c h o l o g y r e s e a r c hd i r e c t i o na r t i f i c i a li n t e l l i g e n c e s u p e r v i s o r p r o f y u h u iq i u p h d c a n d i d a t e p e n gy u e a b s t r a c t g a m ei so n eo ft h ei m p o r t a n ts u b i e c t so fa r t i f i c i a li n t e l l i g e n c e ( a i ) a n da i s d e v e l o p m e n tc o n t r i b u t e st ot h ed e v e l o p m e n to ft h es t u d yo fg a l n eg r e a t l y a so n eo f t h em a i ns r b i e c t so f g a m e ，t h eb o a r dg a m eh a sb e e ns t u d i e dt h o r o u g h i y e x c e p tf o rg o 1 1 璩l e v e lo ft h em o s te x c e l l e n tg op r o g r a m si sl o w e rt h a nt h ei e v e lo ft h ep r i m a r y h u m a np l a y e r 砒p r e s e n t b e e a u s eo ft h et o ol a r g es e a r c hs p a c ei nc o m p u t e rg o ， c o m p u t e ri sh a r dt og e th o l do ft h ef u z z yc o n c e p to fg 0 t h e r e f o r e t h el e 、；e lo f c o m p u t e rg oi sh a r dt or i 辩。g 0i san i c e re n v i r o n m e n tt oi n s p e c tt h ed e v e l o p m e n t l e v e lo f a i i ti sap u z z l ei na r t i f i c i a ii n t e l l i g e n c ea b o u th o wt oi m p r o v et h ec a p a b i l i t y i nt h ec o m p u t e rg op r o g r a m s a tt h es a l u et i m e i ti sh e l p f u lt oc o m p r e h e n dt h eh u m a n c o g n i t i o nt h a td e v e l o pt h ec o m p u t e rg op r o g r a m s w h o s el e v e li se q u a lt oh u m a n s t h e r e f o r e 。t h es t u d yo f c o m p u t e rg oi si m p o r t a n tb o t hi nt h e o r ya n di np r a c d c e a tf i r s t , w cr e v i e wt h es t u d yo fc o m p u t e rg oi nt h ew o r l df r o mt h ea s p e c t so fh a s i s a l g ：o r i t h m , s e a r c ha l g o r i t h ma n dl e a r n i n ga l g o r i t h m , a n dt h e nw ei n t r o d u c es o m e p r o g r a m so f c o m p u t e rg o s e a r c ha l g o r i t h m si nc o m p u t e rg oc h i e f l yi n e l u d em i n m a x a l g o r i t h m 、a l p h a b e t aa l g o r i t h m 、f a i l s o f la l g o r i t h m 、n e g a m a xa l g o r i t h m 、n e g a s c o u t a l g o r i t h ma n dm t d fa l g o r i t h m l e a r n i n ga l g o r i t h m sa n dt h e o r i e si nc o m p u t e rg o i n v o l v ec o m b i n a t o r i a lg a m e st h e o r y , m a t h e m a t i cm o r p h o l o g y , m o n t e - c a r l oa l g o r i t h m , f u z z yl e a r n i n g , d i v i d ea n dc o n q u e r , r e i n f o r c e m e n tl e a r n i n g , g e n e t i ca l g o r i t h m , n e u r a l n e t w o r k , s u p p o r tv e c t o rm a c h i n e ，b a y e s i a np a u e r nc l a s s i f i c a t i o n ，g e n e r a l i z a t i o nb y e x p l a i n i n g ，p a r a l l e la l g o r i t h m ，a n ds oo n a tp r e s e n t , t h em a i n l yd e f e c t sr e s tw i t ht h e d e f i c i e n tm e t h o di nr e p r e s e n t a t i o no f p o s i t i o n ，i n c o m p l e t et a c t i c so f m i d d l eg a m e ，a n d i m m a t u r el e a r n i n ga l g o r i t h m s u b s e q u e n t l y , w ei n t r o d u c et h er e l a t i v et h e o r yi nt h i ss t u d y , i n c l u d i n gm a t h e m a t i c s m o r p h o l o g y , f i n i t es t a t em a c h i n e ，l i n e a rm o d e l ，p e r c e p t i o n , a n dg e n e t i ca l g o r i t h m a f t e rt h a t 。w ei n t r o d u c et h ep l a y e r st h i n k i n gm o d e l ，b a s i sa l g o r i t h m ，s e a r c ha l g o r i t h m a n dl e a r n i n ga l g o r i t h mi nt h i ss t u d y , a n dt h er e s u l to fe x p e r i m e n t so ft h e s ea l g o r i t h m s i nd e t a i l , t h em a j o rc o n t r i b u t i o n so ft h i ss t u d ya r e 1 p u tf o r w a r da ni n t e g r a t e dp l a y e r st h i n k i n gm o d e l w ed ot h i sa f t e rp o t t i n gf o r w a r d t h em e t h o do f e r a r c h i c a lr e p r e s e n t a t i o no f p o s i t i o n ，g e n e r a l i z i n ga n dc l a s s i f y i n gp l e n t y o tg ot e r m s ，e x t r a c t i n gt a r g e tn o t i o n , s e t t i n gu pt a r g e tg r a p h 。s u m m a n z m gs o m et a r g e t c h o i c e si m i n c i p l ea n dm o v ea t t r i b u t e s a n da n a l y z i n gt h en o t i o no fp l a y e r ss t y l e 1 1 1 e m o d e l 。sc h a r a c t e r i s t i c sa r ec o m p r i s e do fi n t e g r a t i o n , a n dc o m p l e t e n e s so ft h e c l a s s i f i c a t i o no f g ot e r m s 。t a r g e tc h o i c ep r i n c i p l e sa n dm o v ea t t r i b u t e s 2 d e s i g na l le r a r c h i c a lr e p r e s e n t a t i o no fp o s i t i o n ，g oc l u s t e ra l g o r i t h ma n da r e a p a r t i t i o n sb a s e do nm a t h e m a t i cm o r p h o l o g y t h e s ea l g o r i t h m sb a s e do l lu n i t e dt h e o r y a r es i m p l ea n dh a v en i c e re f f e c tt e s t e db yt h ee x p e r i m e n t m o r em e a n i n g f u lh e u r i s t i c t a c t i c sw i l lb ei n t r o d u c e db yu t i l i z i n gt h ee x i s t i n gm a t h e m a t i cm o r p h o l o g ym e t h o d s 3 d e s i g n ap a t t e r ne n c o d i n gm e t h o di n d e p e n d e n to fs y m m e t r y ( p e m i s ) i t s a d v a n t a g e sa r ee n c o d i n gb a s e do na d j a c e n tc h a r a c t e r , q u e u ec h a r a c t e ra n df i g u r e c h a r a c t e ro fp a t t e r n , w h i l ei r r e l e v a n tt ob l a c k w h i t e s y m m e t r y , r o t a t i o na n d t r a n s p o s i t i o ns y m m e t r y , a n dt r a n s l a t i o ns y m m e t r yo ft h ep a t t e m t h ee x p e r i m e n t s h o w st h a tt h em e t h o dw o r k sw e l l i na d d i t i o n ，w ed e s i g nam o v ei n c r e m e n ta l g o r i t h m a sab a s i sa l g o r i t h m 4 d e s i g nac o m p o u n dt a r g e ts e a r c ha l g o r i t h m w et h i n kt h a tac o m p o u n dt a r g e ti s c o m p o s e do fs i m p l e xt a r g e t si nt w od i m e n s i o n sb ya n do ro rl o g i c i t sa d v a n t a g e s l i eo nt h a ti t sb a s i cf u n c t i o nm a yb ec o n s t i t u t e do ft h eb a s i cf u n c t i o n so fs i m p l e xt a r g e t s e a r c h a l g o r i t h m f u r t h e r m o r e , w ec o m p a r et h ep e r f o r m a n c e so fc l a s s i cs e a r c h a l g o r i t h m s 5 d e s i g nap a t t e r n j o s e k il i b r a r yl e a r n i n ga l g o r i t h mb yp e m i s t h ee x p e r i m e n ts h o w s t h a ti tw o r kw e l l ，a n dt h el e a r n e dl i b r a r yo c c u p i e di nas m a l ls t o r a g ea r e a w ed e s i g na j n s e k il i b r a r yl e a r n i n ga l g o r i t h mb yz o b r i s tt o o ，a n di tw o r k sw e l l m o r e o v e r , w e d e s i g nag os h a p ea n dl i b e r t yt e r ml e a r n i n ga l g o r i t h mb yt e a c h i n g , a n dap l a y e r ss t y l e l e a r n i n ga l g o r i t h mb yg e n e t i ca l g o r i t h m 6 d e v e l o pac o m p u t e rg op r o g r a mn a m e ds h o u t g ow h o s ee l e i st h ep l a y e r s t h i n k i n gm o d e l ，a n dp u tt h e s ea l g o r i t h m si n t op r a c t i c e s h o u t g od e e m st h a tah u m a n p l a y e ro w nap a t t e m j o s e k il i b r a r ya n dr e s p e c t i v es t y l e a f t e rm a k i n gg oc l u s t e ra n d p a r t i t i o n i n gt h ea r e a ，ap l a y e rc a r lp r o c e e dt od ot a r g e tg u e s s ，f o c u s i n go nt h el a s ts t o n e o ft h eo p p o n e n tb yt a r g e tc h o i c ep r i n c i p l e l i k e w i s e ，l e db yt a r g e tc h o i c ep r i n c i p l ea n d r e s p e c t i v es t y l e ，ap l a y e rc a ng e n e r a t en e wt a r g e t s ，a n dt h e np i l o t e db yt h et a r g e t a b s i r a c l s e a r c h i n gm o v ew i 山t h ee f f b c to fr e c o m m e n d a b l 0m o v ep u tb yr e s p e c t i v ep a r e m l i b r a r y j o s e k il i b r a r y , ap l a y e rc a l ls e l e c tas p e c i a lm o v eb a s e do nm o v ea t t r i b u t e s i f t h et a r g e ti su n s u c c e s s f u l ，o rt h e r ei sn of e a s i b l em o v e ，w en e e dt op a r t i t i o na r e a sa g a i n o rg e n e r a t eo t h e rt a r g e t sb a s e do no t h e rd e c i s i o np r i n c i p l e s ，u n t i lf i n d i n gs u i t a b l em o v e d u r i n gt h i sc o u r s e ，t h ep a t t c m j o s e k il i b r a r yw i l la f f e c tt h er e c o m m e n d a t i o no fm o v e 。 w h i l et h ep l a y e c ss t y l em o d e la f f e c t st h es w i t c ho f t a r g e t s f i n a l l y , w ed i s c u s st h ee v a l u a t i o no ft h eh u m a nt h i n k i n gm o d e l s t h er e l a t i o nb e t w e e n m o v ei n c r e m e n ta l g o r i t h ma n dm o v e s c a n n i n ga l g o r i t h m ，t h ea p p l i c a t i o no f m a t h e m a t i c sm o r p h o l o g ym e t h o d si nt h eb a s i sa l g o r i t h m ，t h ee f f e c to ns e a r c h i n gb yk o a n ds e k ip h e n o m e n o n , t h er e l a t i o n s h i pb e t w e e nc h a r a c t e r so fs e a r c h i n gt r e e sa n d p s y c h o l o g yf a c t o r s ，e s t i m a t i o n o fs e a r c h i n gt i m e , p o s i t i o ne v a l u a t i o nf u n c t i o n , f e a s i b i l i t yo ft h et a r g e ts e a r c ha n dp l a y e r ss t y l em o d e lb u i l d i n ge t e ；a tt h es a m et i m e ， w ed i s c u s st h ea p p l i c a t i o np o s s i b i l i t ya b o u tt h em e t h o do ft h em a c h i n el e a r n i n gi n c o m p u t e rg o ，a n dp u ts t u d yp l a nf o r w a r d a sab r a n c ho f a i ，c o m p u t e rg oi sr e l a t e dw i t hp s y c h o l o g yn a t u r a l l y i nt h es t u d y , w e e m p h a s i z et h ep r i n c i p l eo ft a k i n gh u m a np l a y e r sa sm o d e le s p e c i a l l y , a n dt h ei d e n t i t y w i t hh u m a np l a y e r s t h i n k i n g ，a n dt h ep e r f e c t i o no fi t sl e a r n i n ga l g o r i t h m o u rf u t u r e w o r kw i l lf o c u so nt h el e a r n i n ga l g o r i t h m o n l yw h e nt h ec o m p u t e rg op r o g r a mc a n l e a r ns o m e t h i n g j u s tl i k eah u m a np l a y e r , c o m p u t e rg oi sh o p e f u l k e yw o r d s ：c o m p u t e rg o ，p l a y e r st h i n k i n gm o d e l ，s e a r c ha l g o r i t h m , l e a r n i n g a l g o r i t h m 4 图目录 图2 i 棋盘与棋子3 馐j2 - 24 ；e 3 图2 - 3 禁着点一4 图2 4 劫4 图2 5n e u r o g o 的系统架构1 6 图3 1 结构元素2 l 图3 - 2 有限状态机2 2 图3 - 3 感知机2 3 图4 - l 棋块2 8 图4 2 棋群2 8 瞎j4 - 3 领t 2 9 图年4 领海2 9 图4 5 领空2 9 图4 - 6 棋势3 0 图4 - 7 局面的层次表示法二o3 l 图4 - 8 复合目标3 6 图4 9 对抗得逞后效原则3 7 图4 - l o目标图3 8 圈4 - i i棋手思维模坦4 0 图5 1 位棋盘4 l 图 图 图 5 2 7 次膨胀运算后 5 3 分步膨胀图 5 - 4 棋群聚类结果。 图5 5 图5 - 6 圈5 7 图7 i 图7 2 地域划分结果一 4 3 4 5 ，4 7 单色模式编码 双色模式编码 走步历史不同的同+ 局面 5 l 。5 3 线性模型与互层感知机的遗传算法的比较9 2 表2 1 表5 i 表5 - 2 表6 - i 表7 1 表7 - 2 表目录 部分计算机围棋程序及其作者 不同大小的p e m i s 模式编码性能。 走步增最算法与走步扫描算法的时间性能比较5 9 经典搜索算法的性能比较 p e m i s 模式库与定式库学习算法的性能8 3 z o b r i s t 定式库学习算法的性能。 算法3 一l 算法5 1 算法5 2 算法5 3 算法5 - 4 算法5 5 算法5 - 6 算法5 7 算法6 - l 算法6 2 算法6 3 算法6 4 算法6 - 5 算法6 - 6 算法6 - 7 算法6 - 8 算法6 - 9 算法6 - 1 0 算法7 1 算法7 - 2 算法7 3 算法7 _ 4 算法7 - 5 算法7 - 6 遗传算法。 算法目录 局面的层次表示法 棋群聚类算法 领土算法 领海算法 4 3 4 6 单色模式p e m i s 编码算法5 l 双色模式p e m i s 编码算法 走步增量算法 m i n m a x 算法 n e g a m a x 算法 a l p h a b e n _ m i n m a x 算法 a l p h a b e t an e g a m a x 算法 f a i l s o f lm i n m a x 算法 6 2 6 3 6 4 6 1 ； 6 6 f a i l s o f i _ n e g a m a x 算法 m t d f 算法 单一目标搜索之m i n m a x 算法 复合目标搜索算法的基本函数 定式库与模式库学习算法 7 6 8 0 8 2 定式库与模式库学习算法的p e m i s 值对插入函数 定式库与模式库学习算法的z o b r l s t 值对插入甬数 术语的示教学爿算法 线性模型的遗传算法 三层感知机的遗传算法 8 4 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工 作及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地 方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含 为获得西南大学或其他教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的 说明并表示谢意。 学位论文作者：羼r 9 b签字日期：参) 年p 月“、日 学位论文版权使用授权书 本学位论文作者完全了解西南大学有关保留、使用学位论文的规 定，有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允 许论文被查阅和借阅。本人授权西南大学研究生院可以将学位论文的 全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫 描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书，本论文：口不保密， 口保密期限至年月止) 学位论文作者签名- 易舯易 导师签名： 签字日期：一 年护月，r 日 签字日期： 学位论文作者毕业后去向： 工作单位：耍蕉至区盟匡瞳 通讯地址：拉篚壹酉蘧星匿! 垦医瞳 膳日 邮编：! ! q 鲤0 第1 章绪论 1 1 研究意义 博弈是人工智能的重要研究主题，人工智能的发展在很大程度上得益于博弈研究的发展。 1 9 9 7 年著名的深蓝电脑战胜国际象棋世界冠军卡斯帕罗夫成为轰动一时的新闻事件f i 】。可以 说。作为博弈研究的主要内容之一，棋类博弈得到了满意的解决，唯一的例外的是围棋，目 前最优秀的围棋程序的水平还不及人类初级棋手。 围棋是搏弈的一种。属双人零和博弈。它起源于3 0 0 0 多年前的中国，充分体现了东方人 的智慧，盛行于中日韩，逐渐在欧美流行。它比国际象棋复杂得多，正因为此，很多人工智 能学家、心理学家【2 3 】和数学家【4 8 】也投入到了计算机围棋研究领域。计算机围棋这个名称 来自于c o m p u m rg o 的直译。略显生硬。简单地说，计算机围棋就是结合人工智能技术教计 算机下围棋，以达到与人类棋手相抗衡的目的。 围棋是简单而复杂的。围棋的规i f j t t i 简单。但是它产生的组合变化数是巨大的，一个小 小的局部也町能让棋手长考一两个小时。以1 9 路围棋为例，共有3 6 1 个交叉点，不考虑禁着 点和伞局同形再现等情况，由于每个交叉点有黑、白，空3 种可能，所以组合变化数有3 种，这个数字比宇宙中的原子总数还要大。 围棋是精确而模糊的。崮棋最终以双方占有地域的多少论胜负，棋手在行棋过程中也常 常考虑一手棋的价值大小，这都是精确的计算过程。但棋手同时也具有一系列的模糊概念， 如评价棋形特点的轻、重、厚、薄等等，这些概念对于计算机来说不容易直接处理。 围棋是普通而神奇的。围棋是一种游戏，对于人类来说掌握它并不难，赛场上学棋数年 的少年棋手与长期活跃在一线的中坚棋手相抗衡的局面已屡见不鲜，所以说围棋是酱通的。 但是，计算机围棋发展到今天棋力还非常低，这就突显了电脑和人脑的本质区别，对于人脑 来说很简单的任务对于电脑来说可能非常复杂，在这个意义上可以说围棋是神奇的。 由于围棋的搜索空间太大、计算机难于处理模糊概念且难于设计学习算法，造成了计算 机围棋程序的棋力难于提高。围棋是检验人工智能发展水平的良好环境，如何提高围棋程序 的棋力是人工智能领域的一大难题。同时，开发出与人类棋手水平相当的围棋程序也有助于 对人类认知能力的理解。所以计算机围棋研究具有重要的理论意义和实用价值 1 2 研究内容 在充分了解国内外计算机围棋研究现状的基础上，本研究呸持以人类棋手为本的原则 提出一个完整的棋手思维模型，据此设计相应基础算法、搜索算法和学习算法并予以实现 同时设计相应实验比较其性能。 1 3 研究方法 充分阅读计算机围棋文献、围棋类书籍和棋评，并结合内省法体会棋手的思维过程，与 其它计算机嘲棋研究者密切交流，提出棋手思维模璎。在掌握经典笄法的基础上努力创新， 设计有效且实用的基础算法、搜索算法和学爿算法，并采用易于维护的面向对象语言予以实 现，同时设计实验测试算法有效性并比较各算法的时问和宅间性能。 1 4 论文结构 本章为绪论。 第2 章介绍了国内外计算机围棋研究现状。在这一章我们首先简单介绍了围棋规则。然 后重点介绍了计算机围棋中的算法和几个强棋力程序，并指出了目前研究中存在的不足。 第3 章简述了本研究的相关理论基础。包括应用于局面表示法、棋群聚类算法和地域划 分算法的数学形态学。应用于定式库和模式库学习的有限状态机理论，应用于棋风建模的感 知机和线性模型，以及用于调节模型参数的遗传算法。 此后各章包括了我们的主要研究工作。s h o u t g o 是本研究所开发的计算机围棋程序，实 现语言为c + + ，它的语法直观明了，在阐述相关数据结构或算法时，将以代码与注释相结 合的方式说明。以示清晰。 第4 章介绍了s h o u t g o 提出的棋手思维模型。我们遵循循序渐进的原则，从基本概念、 局面表示法、丽棋术语的分类、目标图、目标选择原则、走步属性、棋风等方面一一介绍， 直至棋手思维模型的提出。 第5 章阐明了s h o u t g o 中的基础算法。包括局面的层次表示法、棋群聚类算法、地域划 分算法、模式编码方法和走步增量算法及相应实验。 第6 章阐明了s h o u t g o 中的搜索算法。首先介绍了多种经典搜索算法，然后介绍了单一 和复合目标搜索算法及相应实验。 第7 章阐明了s h o u t g o 中的学习算法。包括模式库与定式库学习算法、术语示教学习算 法和棋风的遗传学) | 算法及相廊实验。 第8 章为总结与展望。总结了本研究的主要工作和创新点以及s h o u t g o 的特点。探讨了 棋手思维模穗的评价、走步增_ 最算法与走步于= i 描算法的关系、数学形态学方法在基础算法中 的应用、劫与共活现象对搜索的影响、搜索树特点与心理凼素的关系、搜索时间估计、局面 评价函数、目标搜索的可学封性以及棋风建模等问题，并探讨了机器学习方法在计算机 h 棋 中的应用可能性，提出了进一步的研究计划。 2 第2 章研究现状 2 1 什么是围棋 通用的围棋棋盘为1 9 路，盘而有纵横各1 9 条等距离、垂直交叉的平行线，共构成3 6 1 个交叉点，也称为点( p o i n t ) 为方便定位，某些交叉点标有小圆点或加粗处理，称为星位， 中央的星位称为天元。棋子( s t o n e ) 分黑白两色。如图2 i 所示。 srop0n mlkjihgfedcba srqp0nmlkj1hgfedcba 图2 1 棋盘与棋子 sr 口p0nmlkjrhgfedcbasrqp0nmlkjih6fedcba srop0nmlkj1hgfedcba srop0nmlkjihgfedcba 图2 - 2 气 对局时，对局双方各执一色棋子，黑先白后，交替下子每次只能下一子：棋子下在棋 盘的点上，棋子下定后不得向其它点移动：轮流下子是双方的权利，但允许任何一方放弃下 12345678901 2 3 4 5 6 7 8 9 i 2 3 4 567890t2 3 4 5 6 7 8 9 1234567890123456789 2 3 4 5 6 7 89n挖坞峙m培坞 1 2 3 4 5 6 7890123456789 西南大学博l 学衍论文 子权( p a s s ) 。 当一个棋子下在棋盘卜，与它直接相邻的窄点是这个棋子的气( 1 i b e r t y ) 。与棋子紧邻的点 上如果有同色棋子存在，则它们相瓦连接成一个不可分割的键体，称为棋块( b l o c k ) ：它们的 气也应一并计算。与棋子紧邻的点卜如果有异色棋子存在，这口气便不复存在。如所有的气 均为对方所占据，便呈无气状态。无气状态的棋f 不能在棋j i ； 上存活。如图2 2 所示左侧为 一个合法局面，右侧为其中的一个棋块的气。即。处。 把无气之子提出盘外的手段叫提子( k i l l ) 。下于后，如果对方棋子无气，应立即提取：如 果双方棋子都晕无气状态，应立即提取对方无气之子。对于棋盘上的任何一点，如某方下子 后该子立即晕无气状态，但同时又不能提取对方的棋子，则这个点