基于数学形态学的围棋棋群聚类算法

计算机围棋可以模拟人类棋手的棋群聚类能力以提高搜索效率。本研究以数学形态学为工具,在形式化基础上采用带有限制条件的膨胀运算进行棋群的初步聚类,结合其它一些启发式搜索方法完成棋群的最终聚类,并结合实战对局评价了此算法的性能,指出了此算法的应用价值。

维普资讯

计算机科学 2 0 V 13 N . 0 6 o. 3 o 9

基于数学形态学的围棋棋群聚类算法岳鹏刘洪涛邱玉辉(南大学智能软件与软件工程重点实验室重庆 4 0 1 )西 0 7 5摘要计算机围棋可以模拟人类棋手的棋群聚类能力以提高搜索效率。本研究以数学形态学为工具，在形式化基

础上采用带有限制条件的膨胀运算进行棋群的初步聚类，结合其它一些启发式搜索方法完成棋群的最终聚类，并结合

实战对局评价了此算法的性能，出了此算法的应用价值。指 关键词数学形态学，计算机围棋，聚类Cl se g r t m u t rAl o ih ofGo o psBa e n a he tc lM o pho o y Gr u s d o M t ma ia r lg

Y e g I U n— a QI u Hu UE P n A Ho g T o。 UY— i。( h y L b rt r f n el e t o t r n o t r r jc, u h s Unv r t,C o g i g4 0 1 ) T eKe a o ao y o t lg n fwaea d S f I i S wa eP oe t S twe t e s y h n qn 0 7 5 o

Ab t a t Th o u e o c n smu a eh m a ly r S g r u l s e i g a i t o i r v t e r h n fii n y sr c e c mp t rg a i lt u n p a e’ o g o p cu t rn b l y t i mp o eiss a c i g efce c .

Thssu y a n t e t a r h lg sat o,b s do h o maiain,a o t o sri e i t g o e a i t d,tkig mah mai lmo p oo ya o l a e n t ef r l t c z o d p sc n tan dd l i p r— ant n t n e g r l i a y c u t rn n g r u s n o b n swih s meo h rh u itcs a c i g me h d O c r— i o u d r o p ei n r l s e i g o o g o p,a d c m i e t o t e e rs i e r h n t o st o o m n

peet ef a lseig o og o p .Th sp p r yl kn t cu

l o b t loe au tst eag rtm’ a a lt h i l u trn ng r u s n c i a e,b n igwi at a m a,as v lae h lo ih sc p— i h cb l y n tt e s m e t on s o t i p l a i n v l e i t,a d a h a i p i t u t a p i t au . i me s c o Ke wo d M a h m a ia r h l g,C mp t rg y rs t e tc l mo p o o y o u e o,Cl s e u tr

一

1引言 围棋是一门形象思维和逻辑思维兼备的艺术，是人工也智能领域的难题之一。因为棋局状态的搜索空间巨大，似类于国际象棋程序中普遍采用的穷举式搜索难以奏效，目前比较优秀的计算机围棋的棋力都只处在“”级的阶段_, l不及人 类棋手学棋一年的水平。所以，鉴人类棋手的思维特点设借计相应的启发式算法是提高计算机围棋棋力的可能途径之一

个棋群，而棋块。和棋块。组成另一个棋群。棋块是一个

客观概念，而棋群是一个主观概念，在不同棋力的棋手眼中， 同一个盘面状态下的棋群构成方式可能是不一样的。 』,^、. .-

,,、 LL、、 ^'

,

r’

’r r\, -一，

一

'r 人

。

数学形态学 ( te t a mo p oo y自 2纪 6 Mah mai l rh l ) O世 c g O年

●1 rJ

/ 、,、, ,

代兴起以来，已广泛应用于图像处理如边缘提取、骨架提取及图像分割等各方面r,形象直观， 2它 简化了图像处理，量化并保持了物体的主要形状特征；围棋领域也有应用L。在 5]

、/

【 一 ', 【=, 、 r 【J

●, r I1

, 、

2棋局的表示、棋块与棋群棋局状态包括轮下方，棋子分布和劫点，劫点即为了防止

U ▲ 1 U’ r【.

V 、

Y ,.、= l

’

≮ Y Y nT、,

全局同形再现而规定的禁着点。特定棋局状态的棋子分布可以分解为两个二值图像的组合l, 1 l以 9路盘为例，即为两个 1×1 9 9大小的二值图像，称为黑盘面 ( l k o r, )白盘 ba b a

d B和 c面 ( i b ad wht o r,w) e。棋局上的棋子可以分解为棋块的组合，棋块指彼此直连的同色棋子。棋盘上与棋块直连的空白 交叉点称为气，围棋规则规定“气尽棋亡”所以同一棋块内的，棋子同生同死。如图 1中的。组成一个棋块，④组成另一个棋块。

图 1棋块与棋群

计算机围棋因其搜索空间巨大，有必要模仿人类棋手思维将盘面上的棋块聚类为棋群。无疑，分良好的棋群可划

以极大限制搜索空间，改善搜索方向，宏观上保证搜索结果从的合理性。组成棋群的各棋块在空间上相近，这提示可以利用数学形态学方法进行聚类。

人类棋手对棋局的感知是以棋群为基础的。棋群有别于棋块，指的是由一个或多个棋块组成的功能集合体，常常作为一

3数学形态学二维欧氏空间 e的二值图像中属于物体的像素构成。上了一个集合，原点的坐标为 (, ) X中的任一点都可以看 OO,成是一个关于原点的向量。一个数学形态学变换由原始图像博士生导师，究方向为模糊逻辑、 Agn研多 et系统、博弈

个整体参与战斗，也可能包括内部的对方死子。孤子可以

看作特殊的棋群。如图 1中的棋块o、棋块。和棋块。组成岳鹏博士生，研究方向为博弈。刘洪涛

博士生，研究方向为网格计算。邱玉辉

及网格计算等。

1 3 7

本文来源：https://www.bwwdw.com/article/sbd4.html