智能五子棋博弈程序的核心算法_董红安

《智能五子棋博弈程序的核心算法_董红安》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2005年4月枣庄学院学报Apr.2005第22卷第2期JOURNALOFZAOZHUANGUNIVERSITYVol.22NO.2智能五子棋博弈程序的核心算法12董红安,蒋秀英(1.山东师范大学信息管理学院,山东济南250014;2.枣庄学院计算机科学系,山东枣庄277160)[摘要]人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学,而博弈是人工智能的主要研究领域之一,本文通过一个五子棋博奕程序的设计,介绍了博弈程序设计的核心内容:包括博奕树搜索和估值函数两个方面.[关键词]人工智能;博弈;五子棋;博奕

2、树;估值[中图分类号]TP319;G891.9[文献标识码]B[文章编号]1004-7077(2005)02-0061-050引言人工智能是近年来很活跃的研究领域之一,计算机博奕是人工智能研究的重要分支.人工智能中大多以下棋(如象棋、围棋、五子棋等)为例来研究计算机博奕规律.五子棋是一种深受大众广泛喜爱的游戏,其规则简单,变化多端,非常富有趣味性和消遣性.这里设计和实现了一个人机博奕的五子棋程序,采用了博弈树的方法,应用了剪枝和极大极小树原理进行搜索发现最好的下子位置.介绍五子棋程序的数据结构、评分规则、胜负判

3、断方法和搜索算法过程.1计算机博奕程序的主要内容[1]要想实现一个让计算机能够下棋的程序,至少应具备如下五个部分:1.1状态表示:某种在机器中表示棋局的方法,让程序知道博弈的状态.1.2走法产生:产生合法走法的规则,以使对弈公正的进行.1.3搜索技术:从所有合法的走法中选择最佳的走法的技术.1.4估值函数:一种评估局面优劣的方法,用以同搜索技术配合做出智能的选择.1.5对弈界面:有了界面,对弈才能进行.下面分别介绍以上五个部分的设计.2棋局状态表示及相关的数据结构五子棋程序的棋盘状态及主要的数据表示如下:2.1

4、棋盘的状态用一个15×15的二维数组表示.2.2用数字0和1来表示不同的棋子,其中黑色棋子用“0”表示,白色棋子用“1表示.2.3没有棋子的格子用0xFF表示.为了在使用数据时能够避免数据表示出差错,我们将棋盘状态定义成一系列便于使用的宏.下面是棋盘状态的数据表示的宏定义.#defineGRID_NUM19//每一行列的棋盘交点数#defineGRID_COUNT361//棋盘上交点总数#defineBLACK0//黑棋用0表示[收稿日期]2005-03-09[作者简介]董红安(1969-),男,山东滨州人,山

5、东师范大学信息管理学院在读硕士研究生,主要从事软件理论与技术研究.·61·枣庄学院学报2005年第2期#defineWHITE1//白棋用1表示#defineNOSTONE0xFFtypedefstruct_stoneposition//用以表示棋子位值的结构{BYTEx;BYTEy;}STONEPOS;typedefstruct_stonemove{STONEPOSStonePos;//棋子位置intScore//走法的分数}STONEMOVE;//这个结构用以表示走法BYTEm_RenjuBoard[GRI

6、D_NUM][GRID_NUM]//棋盘状态的数组3走法产生五子棋的走法产生相对简单一些,对于五子棋盘来说所有空白的交点位置都是合法的落子点(本走法是针对业余五子棋而言,而职业五子棋对奕有三·三、四·四等禁手的规则),走法产生的算法如下:intCreatePossibleMove(BYTEpositon[][GRID_NUM],intdepth)//depth表示搜索的深度{inti,j;m_nMoveCount=0;//合法走法的个数for(i=0;i

7、NUM;j++){if(position[i][j]==(BYTE)NOSTONE)//NOSTONE表示空白{AddMove(j,i,depth)//加入当前走法;nMoveCount++;}}returnnMoveCount;}4估值函数在博弈程序的几大主要部分里,估值核心(估值函数)是与具体的棋类知识紧密结合的一部分,可以说估值函数在很大程度上决定了博弈程序的棋力高低.对于下子的重要性评分,可以从四个方向来考虑当前棋局的情况,分别为:水平、垂直、左斜、右斜.实际上需要考虑在这四个方向上某一方所形成的子的布

8、局的情况,对于在还没有子的地方落子以后的当前局面的评分,主要是为了说明在这个地方下子的重要性程度,在此,设定了一个简单的规则来表示当前棋面对机器方和人方的分数.在对当前棋盘的局面进行估值之前,首先介绍一下五子棋中的常用术语:活三:由于一方走一步在无子交叉点上所形成的一个“活三”的局面,也就是3子无间隔的相连,并且此3子两端延长线上各有一个无子的交叉点与此3子紧密相连,死四:由于一方走·