计算机博弈是一种对策性游戏,是人工智能的主要研究领域之一.它涉及人工智能中的搜索方法、推理技术和决策规划等。目前广泛研究的是确定的、二人、零和、完备信息的博弈搜索。文中通过一个黑白棋程序的设计,将生成的博弈树节点的估值过程和对博弈树搜索过程相结合,采用传统的Alpha—Beta剪枝和极大一极小原则方法给出了博弈程序设计的核心内容：包括博弈树搜索和估值函数两个

维普资讯 www.1mpi.com

第

7期 2 0 1月 07 年

计算机技术与发展 C OMP T RT C N L Y Y A DD V I}ME 3 U E E H O C3 N E E￣ P N￣ -

V 1 7。L o1 . N . JI 2 0 a.{7 1 )

博弈算法在黑白棋中的应用 杜秀全，家兴程 (安徽大学计算智能与信号处理教育部重点实验室，安徽合肥 2 0 3 ) 30 9 摘要：计算机博弈是一种对策性游戏，是人工智能的主要研究领域之一.它涉及人工智能中的搜索方法、推理技术和决策

规划等。目前广泛研究的是确定的、、=人零和、完备信息的博弈搜索。文中通过一个黑白棋程序的设计，将生成的博弈树

节点的估值过程和对博弈树搜索过程相结合，采用传统的Al a B t剪枝和极大一极小原则方法给出了博弈程序设计的 p— ea h 核心内容：包括博弈树搜索和估值函数两个方面，出了对原算法的一种改进，提该算法提高了搜索速度。实验结果验证了算法的有效性。 关键词：博弈树；黑白棋；估值函数；人工智能 中图分类号： P 1 . T 3 11 文献标识码： A文章编号：63 69 (0 70—0 1 0 17 2 X 2 0 )1 26 3

Ga e。 a i g Al o ih i a k a d W h t e sAp lc to m。 Ply n g r t m n Bl c n ieCh s p i a in DU u q a, Xi—u n CHE NG— ig Jaxn i ( n t f d ct n Ke a oaoyo tl et o uiga dS nl Miir o uai, yL brtr fne i n mp t n i a sy E o I l g C n g Poes g A hi i ri, f 30 9 C i ) rcsi, n u Unv s yHe i 0 3, hn n e t e2 a Abt c: ecmptr a—p y giagmeo o nemes r n n f h lo tia itl ec eerha .tivle sr tTh a o ue me l i a f u t g an s c r aueado eo eHa r ric lnel n ers c】 I no s t j a f i i g a黜 v e o i, ei o—ma i n l nn t . tt ep e n, d l su y t es l bscg me l ig ta i d tmf ae t e - r￣ n g d c

in& n s kn a dpa i ec A h rs t wi y td h i e ai a—pa n h t s ee i t, g n g e e mp y n wo pr s n z,o l ei omaing e l ig sac . r u ha b c n i h s rc d r e i, t d cd t eg me l i o .∞ c mpe f r t a—p yn e rh Tho g l k a d wht c esp o e u ed s n i r u e h a—pa n t n o m a a e g no yg po rmmig c r n e tb h rc s fet t g te po u t n te fg me— lyn oitv lea d t ete fg e— lyn rga n oec tn ytep o eso si i h rd ci reo a o ma n o—pa ig p n au n h reo a m—pa i g sac u e ta to a Alh—Bea p u iga d tep icpeo erh,sd rdi n l p i a t r nn n h rn il fmac mi )— nmeh d t n rd c h e bigp o rrmf gc r o tn, t o oito u et egm￣l rg ar i 0 ecn e t n n

i ld gt e re f a e ly gs￣c n a ainfn t n p t owad te l r h i rv me t t o i c es .a c i n u i e m—p i c n h t og a n e h a dv l t ci, u r r g i m o e n h dwhc i r e m r hn u o u o f h a o t mp me hn a, g se a,hee ei na eutv l a￣ i fet p e t xp rme tlr l al t t efc . s d s Ke r s:reo a e pa i; lc n t hese au t nfncin;rica n el n e y wod te f m— lyn b ka d whi c s;v la i u t g g a e o o atf ilitlge c i i

0引言

() 1我方胜 C1 0则 C>, 2=一C< 0 1; () 2敌方胜 C 2> 0则 C1一 C, 2< 0;

人工智能是近年来很活跃的研究领域之一，计算机博弈是人工智能研究的重要分支…。黑白棋在国外是一种深受大众广泛喜爱的游戏，其规则

简单，变化多端，非常富有趣味性和消遣性。黑白棋程序设计是用编程的方法教会电脑下棋，使之可以与对手对抗。这里采用 Vsa C+ i l u+60设计博弈黑白棋程序， .应用了 Apa B t剪枝和 l—e h a极大一极小原则进行搜索最佳位置。

() 3平局 C 1=0则 C, 2=0。在程序设计过程中，采取“大一极小( n—Ma)极 Mi x分析法”即在博弈树的搜索过程中，,估值函数 E(7反映 . 2 )双方赢得的大小，从我方出发，可取估值函数l为： 2 I E( )= C (, l>0 1 )C得分，<0 C1失分。 双方都根据“极大一极小”的原则，在按照博弈规则

生成的博弈树中，选取最佳步l, 3即： J

1博弈算法 在博弈( a l i ) G me a n中只有“、二方， P yg敌我”并且他们的利益是完全对立的，其赢得函数和为零： 1 C+C 2=0。

我方最佳棋步： n[ .]在我方得分 c最大，取] E( ), x a z 1 扩展“节点；或” 敌方最佳棋步： nn E(]在我方得分 C最小，取 f[ ), i 1 扩展“”与节点。

其中： 1 C为我方赢得(利益) C为敌方赢得 (;2利益)。 因此只有三种情况出现：

收期： 0一 4 o稿日 2 6 o一 7 o 作者简介：全( 8一，安徽拿杜秀 1 2 )男， 9椒人，硕士研究生，研究肯I t i] 为智能计算理论与应用、化方法；优程家兴，教授，博导，研究方向为 智能计算与优化方法等。

2极大一极小原则 例：初始棋局如图 1所示。 由极大~极小原则可以形成如图 2所示的搜索树。 结果应下 E3 C。或 3