人工智能实验报告.docx

人工智能实验报告.docx

《人工智能实验报告.docx》由会员分享，可在线阅读，更多相关《人工智能实验报告.docx（6页珍藏版）》请在冰点文库上搜索。

人工智能实验报告

《人工智能》课外实践报告

项目名称：

剪枝法五子棋

所在班级：

2013级软件工程一班

小组成员：

李晓宁、白明辉、刘小晶、袁成飞、程小兰、李喜林

指导教师：

薛笑荣

起止时间：

2016-5-10——2016-6-18

项目基本信息

项目名称

五子棋

项目简介

智力小游戏作为人们日常休闲娱乐的工具已经深入人们的生活，五子棋更成为了智力游戏的经典，它是基于AI的αβ剪枝法和极小极大值算法实现的人工智能游戏，让人们能和计算机进行对弈。

这个项目我们实现了当人点击“开始”按钮时，开始下棋，当人的棋子落时，计算机会根据算法进行最佳路径计算，然后落子下棋。

任何一方赢了都会弹出哪方赢了。

然后单击重新开始。

任务分工

李晓宁1白明辉1：

负责界面实现和估值函数设计文档整理

刘小晶2袁成飞1：

负责极小极大值算法的设计与实现

李喜林9程小兰4：

负责αβ剪枝法的设计与实现

一、系统分析

背景

设计背景

智力小游戏作为人们日常休闲娱乐的工具已经深入人们的生活，五子棋更成为了智力游戏的经典，它是基于AI的αβ剪枝法和极小极大值算法实现的人工智能游戏，让人们能和计算机进行对弈。

能使人们在与电脑进行对弈的过程中学习五子棋，陶冶情操。

并且推进人们对AI的关注和兴趣。

可行性分析

通过研究，本游戏的可行性有以下三方面作保障

（1）技术可行性

本游戏采用Windowsxp等等系统作为操作平台，使用人工智能进行算法设计，利用剪枝法进行编写，大大减少了内存容量，而且不用使用数据库，便可操作，方便可行，因此在技术上是可行的。

（2）经济可行性

开发软件：

SublimText

（3）操作可行性

该游戏运行所需配置低、用户操作界面友好，具有较强的操作可行性。

数据需求

五子棋需要设计如下的数据字段和数据表：

1.估值函数：

估值函数通常是为了评价棋型的状态，根据实现定义的一个棋局估值表，对双方的棋局形态进行计算，根据得到的估值来判断应该采用的走法。

棋局估值表是根据当前的棋局形势，定义一个分值来反映其优势程度，来对整个棋局形势进行评价。

本程序采用的估值如下：

?

状态?

眠二?

假活三?

眠三?

活二?

冲四?

假活三?

活三?

活四?

连五?

分值?

2?

4?

5?

8?

12?

15?

40?

90?

200

一般来说，我们采用的是15×15的棋盘，棋盘的每一条线称为一路，包括行、列和斜线，4个方向，其中行列有30路，两条对角线共有58路，整个棋盘的路数为88路。

考虑到五子棋必须要五子相连才可以获胜，这样对于斜线，可以减少8路，即有效的棋盘路数为72路。

对于每一路来说，第i路的估分为E（i）=Ec（i）-Ep（i），其中Ec（i）为计算机的i路估分，Ep（i）为玩家的i路估分。

棋局整个形势的估值情况通过对各路估分的累加进行判断，即估值函数：

72

F（n）=ΣE（i）

i=1

极小极大值算法:

极大极小搜索算法就是在博弈树在寻找最优解的一个过程，这主要是一个对各个子结点进行比较取舍的过程，定义一个估值函数F（n）来分别计算各个终结点的分值，通过双方的分值来对棋局形势进行分析判断。

以甲乙两人下棋为例，甲为max，乙为min。

当甲走棋时，自然在博弈树中寻找最大点的走法，轮到乙时，则寻找最小点的走法，如此反复，这就是一个极大极小搜索过程，以此来寻找对机器的最佳走法。

?

αβ剪枝法:

αβ剪枝算法简单来说，就是在搜索过程中减少一定的冗余现象，如已经找到极大值，执行该走法就可以获胜，则无须再往下进行搜索比较，此过程即为剪枝。

对于极大的MAX结点，称为α剪枝；反之为β剪枝。

具体规则可以简单描述如下：

?

α剪枝：

对于极大值层结点的α值如果不小于它的任一祖先极小值层结点的β值，即α（后续层）≥β（祖先层），则可中止该极大值层中这个MAX节点以下的搜索过程，这个MAX节点最终的倒推值就确定为这个α值。

?

β剪枝：

对于极小值结点层的β值如果不大于它任一祖先极大值层结点的α值，即α（祖先层）≥β（后续层），则可中止对该极小值层中这个MIN节点以下结点的搜索，这个MIN节点最终的倒推值就确定为这个β值。

[2]?

αβ剪枝可以进一步进行改进，在走棋过程中，在中心先下的一方往往有一定的优势，双方的搏斗纠缠都是在争夺最佳位置，可以考虑从中心往外螺旋进行扩展搜索；另外由于防守的需要，落子的位置通常也是在彼此下子的附近，因此可以优先考虑在这些位置进行搜索，也就是对落子位置进行排序预先搜索，更进一步的缩减冗余现象，进而提高搜索效率和行棋质量。

事务需求

此游戏主要应用于人类与计算机的对弈功能。

具体功能如下所述：

1.人：

点击开始找位置下棋

2.计算机：

算法设计最佳位置搜索下棋

3.规则：

五子成珠，先者为胜。

完整性及安全性要求

系统的安全性对系统是否正常使用具有重要意义，为了实现游戏的安全性，在程序设计方面主要采用两个步骤:

一是操作平台的兼容性，二是代码实现的安全性。

操作平台的兼容性:

为了防止有的浏览器因为不兼容而产生错误和系统安全，我们做了浏览器的兼容性检测。

代码实现的安全性:

为了防止一些代码执行存在的风险，我们应用最安全，最原生态的JS来实现界面和算法的实现。

二、游戏实现

开发环境

硬件环境

开发过程中，所使用的硬件环境：

计算机一台

软件环境

在以上硬件的基础上，开发系统必须所具备的软件系统，应该包括以下几个方面：

操作平台：

MicrosoftWindowsxp

开发语言：

HTML5CSS3javascript

系统流程图

根据系统模块，得出总系统流程图如下：

总体流程图：

用JSP实现的界面

1、主界面

2、开始电脑下棋

3、一轮之后

4、人胜利

5、电脑胜利

6、人悔棋

7、人认输

三、问题及解决方法

1.在编写代码时发现代码明明没有错误，可就是运行不出来，结果就不得不重新敲一次，最后才发现标点符号不是在英文状态下。

2.在使用插件和JS的框架时出现兼容问题，在讨论和搜索方法之后，好不容易搞定了。

总的来说，本游戏整体性能不够完整，安全系数一般,并不是那么完整，但是根据我们的努力，还是解决了一部分的问题。

四、课外实践总结

这一学期刚开始，老师就布置下此次课外实践的任务，但当时我们并不在意，想着还早，再加上刚接触这门学科，根本不知从何入手，直到最后，再过几天就要交作品了，我们才真正慌起来，对于五子棋我们是熟悉的，但没想到运用AI的剪枝法做起来是那么难，因为算法的设计如果不完全就会导致出现粗物，还有内存溢出问题，刚开始我们组的同学就像无头苍蝇一样乱撞，总是找不到重心，通过大家一致的研究算法本身和集体讨论估值函数的设计，然后上网查资料，我们设计了算法，然后不断的优化修改，终于达到理想效果，然后开始实现代码。

勤奋对于团队是至关重要的，需要大家的共同的努力，不断修改，从中发现缺点与不足，不断改进才能完成任务。

所以小组中的每个成员的能力与协作能力也是很重要的。

最后呢，在实习中发现自己的确定和不足，并努力学习加以改正，在开发一个项目时一定要先做好规划，按照系统的开发过程，详细地写好每一个必要的文档。