五子棋算法的研究与思考

通过对五子棋算法的研宄,探讨在博弈算法设计中优化的一些基本思路,并对其他棋类博弈算法提出一些思考和展望。

维普资讯 http://doc.guandang.net

第2 5卷第 2期20 06年 6月

计算

技

术与 自动化

Vo . I25. No. 2

C mp t g Te h oo y a d Au o t n o u i c n lg n t ma i n o

J n . .2 00 6

文章编号： 0 3 1 9 2 0 ) 2—0 7 0 1 0—6 9 ( 0 6 0 01 4

五子棋算法的研究与思考朱全民，陈松乔(中南大学信息科学与工程学院，南长沙湖 408 ) 1 0 3

摘要：通过对五子棋算法的研宄，讨在博弈算法设计中优化的一些基本思路，探并时其他棋类博弈算法提出一些思考和展望。

关键词：子棋；大极小搜索；索优化五极搜中图分类号： P 0 . T 3 I6文献标识码： A

Go a g r t m s a c nd Thi k b ng Al o ih Re e r h a nZ HU a— n, HEN o g qa Ou n mi C S n— io( a e fIfr n eS i c n n ier g C nrl o t i r t . h n s a 4 0 8, hn ) Acd myo oma c c n ea dE gn ei, e t u hUnv s y C a g h 1 0 3 C ia n e n aS ei

Ab t a t Th a e i l k ss in i c rs a c e n Go a g ag rt m e r h,a d q e t f r p i zn n c e s a s sr c: e p p r ma y ma e ce t i ee r h so b n l o i n f h sac n u ss o t o miig o h s me g

i e e a ag rt m .Ths wi r g a o tt ik n r s e t n o h r c e sg mea g r h . n g n r l l o ih i l b i b u h n sa d p o p cso t e h s a lo i m l n tKe r s g b n l o ih; i ywo d: o a g ag r m M n—ma e r h ag r h; h s a p i z t n t x s a c lo i m c e s g me o t t mi i ao

1引言 五子棋是起源于中国古代的传统黑白棋种之现代五子棋日文称之为“珠”英译为“ e—连， R n j”英文称之为“ o a g或“ I ( iei o u,

G b n” F R” Fv naR w一

总是希望下一步是儿子节点中取值最大者，而另一方恰恰相反。这便形成了极大极小过程 j 2。其算法框架如下： Ma D为搜索的最大深度； x oe pn表存放未被扩展的节点； c sd表存放已扩展的节点； le o dph为深度变量； et f为定义好的局面评价函数；

。

的缩写 )亦有“五子”“子连”“珠”“,连、五、串、五目”“目碰”“格”多种称谓…。五子棋不、五、五等仅能增强思维能力，高智力，且变化多端，常提而非

富有趣味性和消遣性，因此为人民群众所喜闻乐见。本文在研究博弈机器人系统过程中，五子棋对博弈算法进行了一些有效的研究，设计和实现一个人机对弈的五子棋程序。

s为初始节点； T表示博弈树； 第一步： S点出发按宽度优先的方法，从节生成规定深度范围的博弈树。 初始化博弈树；pn () c sd=( o e一 s; l e: ); or p a eet ’

n pn表的第一个节点—o e i n可直接判定赢、 f 输或平局 te hnfn一 -。/。 ( ) I。一 oo - 2

. ’

2极大极小搜索算法博弈程序的任务就是对博弈树进行搜索找出当前最优的一步行棋。对博弈树进行极大极小搜索 ( x—Mi)可以达到这一目的。极大极小搜 Ma n,索，因为博弈双方所要达到的目的相反，方要是一寻找的利益恰是一方失去的利益，以博弈的一方所收稿日期： 0 6 3 1 2 0—0—2

e e[ i e pn ( ) l n s x ad n;a d n,;a d n, p n; d ( iT) d ( io e ) a d n,lsd;rmo e n,o e ) d ( coe ) e v ( p n;Jd p h: de h+ 1 et pt

u t p n表为空 o e t>MaD; nio e l r ph d x 第二步：该博弈树，对自底向上逐级计算每个

基金谍题：南省自然科学基金资助项 l(号：4 5 0 4 )湖=编={ 0 5 4 0 9作者简介：全民 ( 9 8 )男，南长沙人，士研究生，究方向：件工程 ( ma:h q ami@ 1 3 cm)陈松乔 (9 O )男朱 16一，湖

硕研软 E i zu un n 6 .o; l 14一，湖南长沙人，授，士生导师。究方向：教博研软件工程。