《人工智能导论》课程报告
课题名称： 五子棋
姓名: X X 学号：114304xxxx 课题负责人名（学号）： X X114304xxxx 同组成员名单（学号、角色）： x x1143041325 XXX1143041036
指导教师： 张建州 评阅成绩： 评阅意见：
提交报告时间：2014年 1 月 9 日 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
五子棋
计算机科学与技术 专业 学生 XXX 指导老师
张建州
[摘要] 人类之所以不断在进步，是因为我们人类一直不断的在思考，五子棋游戏程序的开发符合人类进步也是促进人类进步的一大动力之一。五子棋游戏程序让人们方便快捷的可以下五子棋，让人们在何时都能通过下棋来提高逻辑思维能力，同时也培养儿童的兴趣以及爱好，让孩子更加聪明。
同时，五子棋游戏程序的开发也使得五子棋这个游戏得到了广泛的推广，让世界各地的人们知道五子棋，玩上五子棋，这已经不是局限。五子棋游戏程序使得越来越多的人喜欢上了五子棋，热爱下五子棋，它是具有很好的带动性的。
关键词：五子棋
进步
思考
-1- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
目录
《人工智能导论》课程报告 ..................................................................................0 1 引言 .....................................................................................................................3
1.1 五子棋简介 ...........................................................................................3 1.2 五子棋游戏的发展与现状 ......................................................................3 2 研究问题描述......................................................................................................4
2.1 问题定义 ...................................................................................................4 2.2 可行性研究 ...............................................................................................4 2.3 需求分析 ...................................................................................................5 2.4 总体设计 ...................................................................................................5 2.5 详细设计 ...................................................................................................6 2.6编码和单元测试 ........................................................................................6 3 人工智能技术......................................................................................................6 4 算法设计 .............................................................................................................7
4.1α-β剪枝算法 .............................................................................................7 4.2极大极小树 ................................................................................................7 4.3深度优先搜索（DFS） .............................................................................8 4.4静态估值函数 ............................................................................................9 5 软件设计和实现 ..................................................................................................9
5.1 数据结构定义 ...........................................................................................9 5.2 程序流程图 .............................................................................................17 6 性能测试 ...........................................................................................................18
6.1 程序执行结果 .........................................................................................18 7 总结 ...................................................................................................................21 参考文献 ...............................................................................................................21
-2- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 1 引言
1.1 五子棋简介
五子棋是一种两人对弈的纯策略型汉族棋类益智游戏，棋具与围棋通用，由中国汉族人发明，起源于中国上古时代的传统黑白棋种之一。主要流行于华人和汉字文化圈的国家以及欧美一些地区。
容易上手，老少皆宜，而且趣味横生，引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。已在各个游戏平台有应用。
古代五子棋棋盘与围棋棋盘是通用的，汉魏时为十七路（17×17）棋盘，至南北朝时即已流行十九路（19×19）棋盘，直至1931年出现所谓五子棋专用棋盘。
1.2 五子棋游戏的发展与现状
目前，连珠这一棋类运动已迅速在国际上发展起来。外国人都十分看好这一不起眼的智力游戏，并认为五子棋不仅能提高思维、开发智力、手脑并用、修身养性 而且富含哲理，具有东方的神秘和西方的直观，是中西文化的交汇点。许多国家的人对五子棋都有不同的爱称，例如韩国人把五子棋称之为“情侣棋”，言下之意是情人之间下五子棋有利于增加情感的交流；欧洲人称之为“中老年棋”，表示五子棋适合中老年人的生理特点和思维方式；美洲人喜欢将五子棋称之为“商业棋”，就是说商人谈生意时可一边下棋一边谈生意，棋下完了生意也谈成了。由此可见，尽管国度不同，语言各异，但人们都可以借助五子棋这一简单而又深奥的棋艺进行交流、比赛，增进友谊。
当前，有４０多个国家和地区都在下五子棋，并有各种规模和级别的比赛。１９８９年８月在日本京都、１９９１年８月在俄罗斯联邦的莫斯科、１９９３年８月在瑞典、１９９５年８月在爱沙尼亚的塔林分别举行了第
一、
二、
三、四届世界锦标赛。除第三届的冠军是爱沙尼亚人之外，其余三届的冠军都是日本人。五子棋 的世界锦标赛，每两年举办一次，其申国竞争也十分激烈。日本目前拥有自己的五子棋职业棋手，并且对连珠（五子棋）技术的研究也相当普遍和全面，就水平也正在日益增强。同时，五子棋的理论研究与探索也呈现蓬勃发展的势头，从１８５８年第一部五子棋专著问世以来，目前，全世界有２０００多种五子棋的书籍及期刊，分别以日文、俄文、英文、瑞典文及中文出版发行。五子棋在我国的北京、上海、天津、云南、浙江、广东、四川、湖北、辽宁、新疆、河北等省（区）市都有很大的发展。北京多次举办了北京地区的五子棋赛，如“思曼杯”、“京空杯”、“奇奇童杯”、“北京第六届民族团结杯”和“北京第四岂民族运动会”的五子棋比赛。上海地区举办了“上文杯”五子棋大赛。云南省以及其他省市亦举办过许多五子棋比赛。所有这些赛事都越来越多地吸引了无数人的关注，表明了根植于中国的五子棋有着广泛的群众基础，
-3- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 是群众喜闻乐见的体育活动。
而现在，很多很多游戏平台上面都有五子棋游戏供我们玩，任何游戏平台上面只要有棋牌类游戏的，那么它就有五子棋在里面，网络五子棋比赛，在联众，263，QQ游戏，UC里进行了10几年了可见，五子棋游戏在网络上面是非常火暴的，而且在棋牌游戏里面玩家人数排名总会占到很前面，不愧是风靡全球的棋牌游戏啊！在未来中，将会有越来越多的人关注五子棋，喜欢五子棋，那么将其变为商业化也会越来越多，而且还可以以教育孩子的方式来将其嵌套进去，或者用来做测试等等，可以说以后的五子棋游戏会是那么的精彩，那么的让人憧憬。那么对于它的游戏开发和发展也将会上升到举足轻重的地位去，它的发展会是相当之快的，就让我们拭目以待吧。
2 研究问题描述
2.1 问题定义
问题定义的一个的关键问题是“要解决的问题是什么”，这个是这个阶段必须要明确要回答的问题。在没将问题定义好，试图准备下个阶段的任务。这明显是不成熟，甚至不可能的事。
本次系统设计中首先明确了需要解决的问题是五子棋AI算法，基本的要求是设计一款能够实现人机对战、人人对战和禁手的五子棋游戏，提供一些基本的操作如退出系统，向后悔棋等操作，重点是放在AI算法的研究。而并不是美工设计，也不是为了提供各种操作丰富的接口。主要是通过这种可视化的界面探讨AI，当然增加可玩性和美工会给系统润色不少。
上面只是很粗略的明确大概的方向，严格按照软件工程的方法这个阶段需要生产一份书面报告。需要通过对系统的实际用户访问调查，扼要地写出他对问题的理解，并在用户和使用部门负责人的会议上认真讨论这份书面报告，澄清含糊不精的地方，改正理解不正确的地方，最后得出一份双方都满意的文档。本系统的需求很少也很明显了。
2.2 可行性研究
这个阶段要回答的关键问题：“对于上一个阶段所确定的问题是否可行？”为了回答这个问题，我们需要进行一次大大压缩和简化了的系统分析和设计的过程，也就是在较抽象的高层次上进行的分析和设计的过程。
可行性研究应该比较简短，这个阶段的任务不是具体解决问题，而是研究问题的范围，探索这个问题是否值得去解，是否有可行的解决办法。
可行性研究应该比较简短，这个阶段的任务不是具体解决问题，而是研究问题的范围，探索这个问题是否值得去解，是否有可行的解决办法。可行性研
-4- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 究以后的那些阶段将需要投入要多的人力物力。及时中止不值得投资的工程项目，可以避免更大的浪费。
根据这些基本的概念，我在技术上主要是通过相关文档资料的查找后确定可行性，凭着大学期间打下厚实的专业科基础，特别是数据结构和算法，能够在这段时间理解通透并应该有所改进，后来证明是对的。利用剩下时间也应该来说也比较充裕的。经济上暂不考虑。
下面主要从技术上进行分析：
工具: Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaSE, JavaEE, JavaME）的总称。Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。所以用java来编写是一个很好的选择。
算法：在这图论搜索技术这方面，前人已有很成熟的算法。如粗糙的有深度优先算法(DFS)和广度优先算法(BFS)这两个基本的算法，关键需要解决的是能够设计出一种高效的剪枝函数，减小搜索问题的规模。目前博弈类游戏中的人工智能基本都采用极大极小值方法这对我来说是个挑战，而剪枝的则采用Alpha-Beta，通过丰富的文档资料初步了解到这些技术已经很成熟了。我们有信心能解决好这个问题。
2.3 需求分析
人工智能的第一大成就是下棋程序，在下棋程度中应用的某些技术，如向前看几步，把困难的问题分解成一些较容易的子问题，发展成为搜索和问题归纳这样的人工智能基本技术。今天的计算机程序已能够达到下各种方盘棋和国际象棋的锦标赛水平。但是，尚未解决包括人类棋手具有的但尚不能明确表达的能力。如国际象棋大师们洞察棋局的能力。另一个问题是涉及问题的原概念，在人工智能中叫做问题表示的选择，人们常能找到某种思考问题的方法，从而使求解变易而解决该问题。到目前为止，人工智能程序已能知道如何考虑它们要解决的问题，即搜索解答空间，寻找较优解答。
在设计本系统时考虑到用户需要的是一个操作简便界面简单的游戏软件，同时要提供人机和人人这样的功能，特别是人机部分，要考虑到不同级别的用户，电脑智能不能太低需要有一定的智能下棋功能等等。所以采用α-β剪枝法算法时就是为了达到这些目标。
2.4 总体设计
这个阶段必须回答的关键问题是：“概括地说，应该如何解决这个问题？”
-5- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 首先，应该考虑几种可能的解决方案。如，目标系统的一些主要功能是用计算机自动完成还是用人工完成；如果使用计算机，那么是使用批处理方式还是人机交互方式；信息存储使用传统的文件系统还是数据库„„。通常至少应该考虑下述几类可能的方案：
低成本的解决方案。系统只能完成最必要的工作，不能多做一点额处的工作。本系统的最基本要求就是能够实现必要的操作，其他额外的一些工作在后面完成
中等成本的解决方案。这样的系统不仅能够很好地完成预定的任务，使用起来很方便，而且可能还具有用户没有具体指定的某些功能和特点。虽然用户没有提出这些具体要求，但是系统分析员根据自己的知识和经验断定，这些附加的能力在实践中将证明是很有价值的。
这个成本方案在完成上面的低成本方案后添加的。如增加保存棋局，美化界面，实现观看电脑与电脑之间的对战等功能。
高成本的“十全十美”的系统。这样的系统具有用户可能希望有的所有功能和特点。
结构设计的一条基本原理就是程序应该模块化，也就是一个大程序应该由许多规模适中的模块按合理的层次结构组织而成。总体设计阶段的第二项主要任务就是设计软件的结构，也就是确定程序由哪些模块组成以及模块间的关系。通常用层次图或结构图描绘软件的结构。
2.5 详细设计
总体设计阶段以比较抽象概括的方式提出了解决问题的办法。详细设计阶段的任务就是把解法具体化，也就是回答下面这个关键问题：“应该怎样具体地实现这个系统呢？”
这个阶段的任务还不是编写程序，而是设计出程序的详细规格说明。这种规格说明的作用很类似于其他工程领域中工程师经常使用的工程蓝图，它们应该包含必要的细节，程序员可以根据它们写出实际的程序代码。
2.6编码和单元测试
这个阶段的关键任务是根据以上阶段分析的软件模型，编写各个功能模块。
要注意的是程序的扩张性和可读性。以便以后软件的升级修改。同时要仔细的测试每个功能编写好的功能模块。
3 人工智能技术
人工智能也就是所谓的AI(Artificial Intelligence)，它是一门很抽象的技术，
-6- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 AI程序的编写不需要依据任何既定的思考模式或者规则。尤其是游戏中的AI可以完全依程序设计者本身的思考逻辑制作。我个人认为人工智能的核心应该是使计算机具有自动的处理事件的能力，而我们的所有的研究也应该围绕着这一方向。我们今天讨论的是策略类的人工智能。
策略类人工智能可以说是AI中比较复杂的一种，最常见的策略类AI游戏就是棋盘式游戏。在这类游戏中，通常的策略类AI程序都是使计算机判断目前状况下所有可走的棋与可能的获胜状况，并计算当前计算机可走棋步的获胜分数或者玩家可走棋步的获胜分数，然后再决定出一个最佳走法。本课程设计是基于AI中α-β剪枝算法的五子棋的博弈游戏，下面让我们来具体介绍一下相关的内容。
4 算法设计
4.1α-β剪枝算法
我们的程序主要是用α-β剪枝法实现的。其基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了搜索效率。具体的剪枝方法如下：
(1) 对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为α剪枝。
(2) 对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为β剪枝。
4.2极大极小树
目前绝大部分的博弈类游戏中的人工算法都采用这种方法。假设己方为MAX点，对方则为MIN点。如果当层的节点为奇数时那么就为MAX层，同样为偶数时就为MIN层。当在MAX层时，该层的值就应该为下一个MIN层中的最大一个的值。当在MIN层是，该层的值就应该为它子层MAX的最小的一个。通俗的说就是当轮到我方时，我们就应该选择一个最有利于我们的点，预测对方可能下的最有利他方的点（相对我方来说就是最坏的点）。这样反复计算下去就能够得到根节点的最大值，这个点也就是我们最佳下棋点。在计算这个点时可以很明显的看出这是一个不断递归的过程，到达叶子节点时根据相关
-7- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 的计算规则算出该值然后向上一层不断的返回。下图中矩形代表极大层，椭圆代表极小层。
4.3深度优先搜索（DFS）
在图论中有两个很重要的遍历的方法，一个是深度优先搜索（DFS）,另外一个是广度优先搜索(BFS).这两个方法的主要区别在于下一个节点的选择。DFS首先选择它的连接节点，若它的下个节点已经全部被遍历过或者不存在的话。则向上返回到上一个节点，在遍历其他的未被访问过的点。很容易想到这要用到堆栈结构，使用一个递归来实现。而BFS则是逐个的遍历它的联接接点，将已经访问过的点放入队列中。然后再依次取出继续这个过程。
DFS遍历过程如下：
首先从A点出发访问它的领接点B，因为B的领接点C,F均未被访问过，所以B点选择C（当然也可以选择F点）作为下一个要访问的点，C点的领接点是D,F选择下个节点D，而D的邻接点只有一个E且未被访问过，就将E作为了它下个节点。这时因为E已经没有可访问的邻点，所以向上一层返回到D，发现D也已经没有可访问的点了，继续向上层返回到C，由于C的邻节点F未被访问过，那么就访问F。所以整个过程的遍历结果为：
-8- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 ABECFD 。
BFS的遍历过程为ABECFD。
4.4静态估值函数
当极大极小树到达叶子节点时，需要估算一下当前盘面的值。这个就根据某个计算规则计算也即是估值函数。因为这个值是已经确定的所以称为静态。
当只有一个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物” 就给他50，否则给予10。
当两个点时，并且相邻的无对方的棋子或者不是边界等“阻碍物”给予1000，若存在一方有“阻碍物”则给以100，否则给予10。
当是活三的时候给予3600，当存在一边被堵时，就给予500。否则给予10。 当是活四的时候给以500000，当一边被堵时，给予50000。否则给予10 当是五连子的时候就给予最高分1000000。 最后判断是否是己方的，若不是则给予负号。
静态估值函数会很严重的影响到算法的智能，所以可根据在下棋的过程中不断的做出调整，使其更加的合理。根据一些测试，这组静态估值函数能够很好的反映棋盘重要性指标。
5 软件设计和实现
5.1 数据结构定义
本程序定义15*15的五子棋棋盘，实现算法，在算法中采用的数据结构包括：int isCheOn[][]描述当前棋盘，0表示黑子，1表示白字，2表示无子；int pre[][]用来记录棋点的x，y坐标。
由于本课程设计是基于Java语言开发的，在Java中只能用类来表示并实现所定义的数据结构。所以下面将用类来描述相应的数据结构及算法：
public cla ChePanel extends JPanel{ private ImageIcon map;
//棋盘背景位图
private ImageIcon blackche;
//黑子位图
private ImageIcon whiteche;
//白子位图
public int isCheOn [][];
//棋局
protected boolean win = false;
// 是否已经分出胜负
protected int win_bw;
// 胜利棋色
protected int deep = 3, weight = 7;
// 搜索的深度以及广度
public int drawn_num = 110;
// 和棋步数
int che_num = 0;
// 总落子数目
-9- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
public int[][] pre = new int[drawn_num + 1][2];
// 记录下棋点的x,y坐标
最多 (drawn_num + 1) 个
public int sbw = 0;
//玩家棋色黑色0，白色1
public int bw = 0;
// 当前应该下的棋色
0：黑色(默认)， 1：白色
// 边界值,用于速度优化
protected int x_max = 15, x_min = 0;
protected int y_max = 15, y_min = 0;
protected boolean able_flag = true;
// 是否选择禁手标志 0:无禁手
1:有禁手(默认
private int h;
//棋子长
private int w;
//棋子宽
private int insx;
//插入棋子的位置
private int insy;
private Point mousePoint;
//鼠标当前位置
private int winer;
//获胜方
private boolean humanhuman=false;
//是否是人人对弈
private int plast=0;
//走了几步了，
public int BLACK_ONE;
//0表黑子
public int WHITE_ONE;
//1表白子
public int NONE_ONE;
//2表无子
public int N;
//棋盘边长
//---------搜索当前搜索状态极大值-//
//alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝
//beta 祖先节点得到的当前最大最小值，用于beta 剪枝。
//step 还要搜索的步数
//return 当前搜索子树极大值
protected int findMax(int alpha, int beta, int step) {
int max = alpha;
if (step == 0) {
return evaluate();
}
int[][] rt = getBests(1sbw) == 1)
//电脑可取胜
return 100 * ( getMark(1) + step*1000 );
isCheOn[x][y] = 11);
isCheOn[x][y] = 2;
// 还原预设边界值
x_min=temp1;
x_max=temp2;
y_min=temp3;
y_max=temp4;
if (t > max)
max = t;
//beta 剪枝
if (max >= beta)
return max;
}
return max;
}
//-----------------------搜索当前搜索状态极小值--//
//alpha 祖先节点得到的当前最小最大值，用于alpha 剪枝
//beta 祖先节点得到的当前最大最小值，用于beta 剪枝
//step 还要搜索的步数
//return 当前搜索子树极小值。
protected int findMin(int alpha, int beta, int step) {
int min = beta;
if (step == 0) {
return evaluate();
}
int[][] rt = getBests(sbw);
for (int i = 0; i
int x = rt[i][0];
int y = rt[i][1];
int type = getType(x, y, sbw);
if (type == 1)
//玩家成5
return -100 * ( getMark(1) + step*1000 );
// 预存当前边界值
int temp1=x_min,temp2=x_max,temp3=y_min,temp4=y_max;
isCheOn[x][y] = sbw;
resetMaxMin(x,y);
int t = findMax( alpha, min, stepbwf);
if(able_flag && bwf==0 && (type_1 == 20 || type_1 == 21 || type_1 == 22)) // 禁手棋位置,不记录
continue;
rt[n][0] = i;
rt[n][1] = j;
rt[n][2] = getMark(type_1) + getMark(type_2);
n++;
-12- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
}
// 对二维数组排序
Arrays.sort(rt, new ArrComparator());
int size = weight > n? n:weight;
int[][] bests = new int[size][3];
System.arraycopy(rt, 0, bests, 0, size);
return bests;
} //----------------------------计算指定方位上的棋型-------------------//
// x,y 方向线基准一点。
//ex,ey 指定方向步进向量。
// k 棋子颜色，0：黑色，1：白色
// 该方向上的棋子数目 以及 活度
private int[] count(int x, int y, int ex, int ey, int bwf) {
// 该方向没意义,返回0
if( !makesense(x, y, ex, ey, bwf))
return new int[] {0, 1};
// 正方向 以及 反方向棋子个数
int rt_1 = 1,rt_2 = 1;
// 总棋子个数
int rt = 1;
// 正方向 以及 反方向连子的活度
int ok_1 = 0,ok_2 =0;
// 总活度
int ok = 0;
// 连子中间有无空格
boolean flag_mid1 =false,flag_mid2 = false;
// 连子中间空格的位置
int flag_i1 = 1,flag_i2 = 1;
if (isCheOn[x][y] != 2) {
throw new IllegalArgumentException(\"position x,y must be empty!..\");
}
int i;
// 往正方向搜索
for (i = 1; x + i * ex = 0 && y + i * ey = 0; i++) {
if (isCheOn[x + i * ex][y + i * ey] == bwf)
rt_1++;
-13- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
// 位置为空,若中空标志为false,则记为中空并继续搜索
否则,break
else if(isCheOn[x + i * ex][y + i * ey] == 2) {
if(!flag_mid1) {
flag_mid1 = true;
flag_i1 = i;
}
else
break;
}
// 位置为对方棋子
else
break;
}
// 计算正方向活度,,
// 最后一个位置不超过边界
if (x + i * ex = 0 && y + i * ey = 0) {
// 最后一个位置为空位 +1活
if( isCheOn[x + i * ex][y + i * ey] == 2) {
ok_1++;
// 若是在尾部检测到连续的空格而退出搜索,则不算有中空
if(rt_1 == flag_i1)
flag_mid1 = false;
// 若中空的位置在4以下 且 棋子数>=4,则这一边的4非活
if(flag_mid1 && rt_1 > 3 && flag_i1
ok_1--;
}
}
// 最后一个位置不是空格,且搜索了2步以上,若前一个是空格, 则不算中空,且为活的边
else if( isCheOn[x + i * ex][y + i * ey] != bwf && i >= 2)
if(isCheOn[x + (i-1) * ex][y + (i-1) * ey] == 2) {
ok_1++;
flag_mid1 = false;
}
}
// 最后一个位置是边界
搜索了2步以上,且前一个是空格, 则不算中空,且为活的边
else if(i >= 2 && isCheOn[x + (i-1) * ex][y + (i-1) * ey] == 2) {
-14- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
ok_1++;
flag_mid1 = false;
}
// 往反方向搜索
for (i = 1; xi * ex
if (isCheOn[xi * ey] == bwf)
ey >= 0) {
rt_2++;
else if(isCheOn[xi * ey] == 2) {
if(!flag_mid2) {
flag_mid2 = true;
flag_i2 = i;
}
else
break;
}
else
break; } // 计算反方向活度
if (xi * ex >= 0 && yi * if( isCheOn[xi * ey] == 2) {
ok_2++;
if(rt_2 == flag_i2)
flag_mid2 = false;
if(flag_mid2 && rt_2 > 3 && flag_i2
ok_2--;
} } else if( isCheOn[xi * ey] != bwf && i >= 2 )
if(isCheOn[x(i-1) * ey] == 2) {
ok_2++;
flag_mid2 = false;
} } else if(i >= 2 && isCheOn[x(i-1) * ey] == 2) { ok_2++; flag_mid2 = false; }
-15-
课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
//------------------分析棋子类型
// 两边都没中空,直接合成
if( !flag_mid1 && !flag_mid2 ) {
rt = rt_1 + rt_21;
// 判断中间的纯连子数,在5以上,直接返回; 为4,返回活4;
if(temp >= 5)
return new int[] {temp, 2};
if(temp == 4)
return new int[] {temp, 2};
// 先看有没死4,再看有没活3,剩下只能是死3
if(rt_1 + flag_i21 >= 4)
return new int[] {4, 1};
if(rt_1+flag_i2-1 == 3 && ok_1 > 0 || rt_2+flag_i1-1 == 3 && ok_2 > 0)
return new int[] {3, 2};
return new int[] {3, 1};
}
// 有一边有中空
else {
// 总棋子数少于5,直接合成
if( rt_1 + rt_21, ok_1 + ok_2};
// 多于5,先找成5,再找活4,剩下的只能是死4
else {
if(flag_mid1 && rt_2 + flag_i11, ok_2 + 1};
if(flag_mid2 && rt_1 + flag_i21, ok_1 + 1};
if(flag_mid1 && (rt_2 + flag_i11 == 4 && ok_1 == 1 || flag_i2 == 4) )
-16- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
}
}
} return new int[] {4, 2};
return new int[] {4, 1}; 5.2 程序流程图
-17- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 6 性能测试
6.1 程序执行结果
1.初始界面
2.人机博弈
3.人人博弈
-18- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
4.禁手选择
5.悔棋选择
-19- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163
6.规则界面
-20- 课程名称：人工智能原理及其应用 学生姓名：何兵 学生学号：1143041163 7 总结
本程序是使用α-β搜索的算法完成的一个简单的五子棋博弈游戏。虽然α-βAlpha-Beta已经尽力做到细致、全面，但由于α-β搜索存在博弈树算法中普遍存在的一个缺点¬一随着搜索层数的增加，算法的效率大大下降。所以该搜索的效率还是不怎么理想，五子棋程序的“智力”也不高。因此可以在上述程序的基础上，针对五子棋本身的特点和规律对α-β搜索算法进行优化与修正，比如用启发式搜索。还有就是虽然使用了禁手思维的算法，但是这并不能平衡先后手之间的差距，依然是“先行必胜”，这个问题还有待进一步解决。
参考文献
[1] 明日科技.Java项目案例分析.清华大学出版社
[2]（美）埃克尔著 陈昊鹏 译.Java编程思想.机械工业出版社 -21-
读书的好处
1、行万里路，读万卷书。
2、书山有路勤为径，学海无涯苦作舟。
3、读书破万卷，下笔如有神。
4、我所学到的任何有价值的知识都是由自学中得来的。——达尔文
5、少壮不努力，老大徒悲伤。
6、黑发不知勤学早，白首方悔读书迟。——颜真卿
7、宝剑锋从磨砺出，梅花香自苦寒来。
8、读书要三到：心到、眼到、口到
9、玉不琢、不成器，人不学、不知义。
10、一日无书，百事荒废。——陈寿
11、书是人类进步的阶梯。
12、一日不读口生，一日不写手生。
13、我扑在书上，就像饥饿的人扑在面包上。——高尔基
14、书到用时方恨少、事非经过不知难。——陆游
15、读一本好书，就如同和一个高尚的人在交谈——歌德
16、读一切好书，就是和许多高尚的人谈话。——笛卡儿
17、学习永远不晚。——高尔基
18、少而好学，如日出之阳；壮而好学，如日中之光；志而好学，如炳烛之光。——刘向
19、学而不思则惘，思而不学则殆。——孔子
20、读书给人以快乐、给人以光彩、给人以才干。——培根
