智能五子棋博弈程序的核心算法.pdf

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

1、"%%$年&月枣庄学院学报EOP#"%%$第""卷第"期JC?:>EDC3KECKH?E>-?>;LI:M;)NLQR#"">C#"智能五子棋博弈程序的核心算法董红安!，蒋秀英"（!#山东师范大学信息管理学院，山东济南"$%%!&；"#枣庄学院计算机科学系，山东枣庄"’’!(%）［摘要］人工智能是一门正在迅速发展的新兴的综合性很强的边缘科学，而博弈是人工智能的主要研究领域之一，本文通过一个五子棋博奕程序的设计，介绍了博弈程序设计的核心内容：包括博奕树搜索和估值函数两个方面#［关键词］人工智能；博弈；五子棋；博奕树；估值［中图分类号］)*+!,；-.,!#,［文献标识码

2、］/［文章编号］!%%&0’%’（’"%%$）%"0%%(!0%$!%引言人工智能是近年来很活跃的研究领域之一，计算机博奕是人工智能研究的重要分支#人工智能中大多以下棋（如象棋、围棋、五子棋等）为例来研究计算机博奕规律#五子棋是一种深受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性#这里设计和实现了一个人机博奕的五子棋程序，采用了博弈树的方法，应用了剪枝和极大极小树原理进行搜索发现最好的下子位置#介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程#!计算机博奕程序的主要内容要想实现一个让计算机能够下棋的程序，至少应具备如下五个部分［!］：

3、!#!状态表示：某种在机器中表示棋局的方法，让程序知道博弈的状态#!#"走法产生：产生合法走法的规则，以使对弈公正的进行#!#+搜索技术：从所有合法的走法中选择最佳的走法的技术#!#&估值函数：一种评估局面优劣的方法，用以同搜索技术配合做出智能的选择#!#$对弈界面：有了界面，对弈才能进行#下面分别介绍以上五个部分的设计#"棋局状态表示及相关的数据结构五子棋程序的棋盘状态及主要的数据表示如下："#!棋盘的状态用一个!$1!$的二维数组表示#"#"用数字%和!来表示不同的棋子，其中黑色棋子用“%”表示，白色棋子用“!表示#"#+没有棋子的格子用%233表示#为了在使用数

4、据时能够避免数据表示出差错，我们将棋盘状态定义成一系列便于使用的宏#下面是棋盘状态的数据表示的宏定义#4567896-:;<=>?@!,AA每一行列的棋盘交点数4567896-:;<=BC?>)+(!AA棋盘上交点总数4567896/DEBF%AA黑棋用%表示4567896GH;)I!AA白棋用!表示!［收稿日期］"%%$0%+0%,［作者简介］董红安（!,(,0），男，山东滨州人，山东师范大学信息管理学院在读硕士研究生，主要从事软件理论与技术研究#·(!·枣庄学院学报R,,T年第R期!"#$%&#’()*(’+,-../01#"#$2/345/62/7¬%/

5、%7&88用以表示棋子位值的结构｛9:*+-；9:*+0；｝)*(’+;()；/01#"#$2/345/62/7&#<7=#｛)*(’+;())/7&#;72；88棋子位置%&/)573#88走法的分数｝)*(’+>(?+；88这个结构用以表示走法9:*+<6@#&A497B3［"C@DE6’F>［］C@DE6’F>］88棋盘状态的数组G走法产生五子棋的走法产生相对简单一些，对于五子棋盘来说所有空白的交点位置都是合法的落子点（本走法是针对业余五子棋而言，而职业五子棋对奕有三·三、四·四等禁手的规则），走法产生的算法如下：%&/H3#B/#;722%IJ#>7=（#9:

6、*+172%/7［&［］C@DE6’F>］，%&/"#1/K）88"#1/K表示搜索的深度｛%&/%，A；<6&>7=#H74&/L,；88合法走法的个数$7（3%L,；%MC@DE6’F>；%NN）$7（3AL,；AMC@DE6’F>；ANN）｛（%$172%/%7［&%［］A］LL（9:*+）’()*(’+）88’()*(’+表示空白｛O"">7=（#A，%，"#1/K）88加入当前走法；&>7=#H74&/NN；｝｝3#/43&&>7=#H74&/；｝P估值函数在博弈程序的几大主要部分里，估值核心（估值函数）是与具体的棋类知识紧密结合的一部分，可以说估值函数在很

7、大程度上决定了博弈程序的棋力高低Q对于下子的重要性评分，可以从四个方向来考虑当前棋局的情况，分别为：水平、垂直、左斜、右斜Q实际上需要考虑在这四个方向上某一方所形成的子的布局的情况，对于在还没有子的地方落子以后的当前局面的评分，主要是为了说明在这个地方下子的重要性程度，在此，设定了一个简单的规则来表示当前棋面对机器方和人方的分数Q在对当前棋盘的局面进行估值之前，首先介绍一下五子棋中的常用术语：活三：由于一方走一步在无子交叉点上所形成的一个“活三”的局面，也就是G子无间隔的相连，并且此G子两端延长线上各有一个无子的交叉点与此G子紧密相连，死四：由于一方