人工智能专家系统论文
题 目 五子棋AI算法和网络通信的研究 学生姓名 陈维梅 学 号 200951612703 系 别 商务学院 年 级 2009 专 业 计算机科学与技术 指导教师 职 称 讲师 完成日期 2012/12/16
五子棋AI算法和网络通信的研究
摘要：
本系统将利用五子棋游戏作为研究对象，通过设计出一个能够实现两种不
同对战模式的五子棋游戏。并对所涉及到的相关技术进行初步的探讨，将重点放在人机对奕中AI算法研究方面。
游戏中提供两种选择模式：人机对战和人人对战。在人机对战中玩家通过选择不同的AI等级和电脑一决高下。在人人对战中双方可以进行下棋，悔棋但
1
要通过对方的同意。同时还可以实现在线聊天。AI的不同等级是以不同的搜索深度确定的。本系统以深度为2，3，4分别为初级，中级，高级。网络对战中则使用Socket实现点对点通信。
关键字：五子棋 、博奕AI算法、网络通信
Research the AIof Renju and the Communication
Summary:
This system will use Renju as research objects, passing to design a Renju game that can provide two kinds of dissimilarities to the play mode. to involve to of the related technique carry on the study of the first step, play more attention in the AI calculate way research aspect.
It provide two kinds of choice modes in the game:Person's machine to the war and the everyone to war.The player passes to choose the different AI grade and computer in person's machine the rightness the war a definitely superiority.Both
parties can carry on play chess in the everyone the rightness the war, the regrets chess but want to pass the approval of the other party.Can also carry out on-line chat in the meantime.AI different grade with search the depth assurance differently.This system takes depth as 2, 3, 4 is an entry-level respectively, medium class, high class.The network orders correspondence towards then using the Socket realization to order in the war to.
Key word: Renju ,AI,networks
目 录
第一章 引言……………………………………………………………........................................4 1.1问题背景……………………………………………………………………………4 1.2五子棋简介…………………………………………………………………………5 第二章 详细设计过程……………………………………………………………………………5 2.1．概要介绍…………………………………………………………………………….5 2.1.1 本程序介绍…………………………………………………………………5 2.1.2 本程序优点…………………………………………………………………5 2.2用软件工程方法学指导开发过程……………………………………………………5
2
2.2.1 问题定义………………………………………………………………………6 2.2.2 可行性研究……………………………………………………………………7 2.2.3 需求分析………………………………………………………………………8 2.2.4总体设计……………………………………………………………………….9 2.2.5 详细设计………………………………………………………………………10 2.2.6 编码和单元测试………………………………………………………………10 2.3用户界面………………………………………………………………………………10
2.4系统解析………………………………………………………………………………11 2.4.1 界面部分..............................................................................................................11 2.4.1.1 CFiveChessView的属性……………………………………………..11 2.4.1.2 CFiveChessView的函数……………………………………………..12 2.4.2 通信部分………………………………………………………………………14 2.4.3 其他部分………………………………………………………………………15 2.4.3.1 CMatch---棋盘类…………………………………………………….16 2.4.3.2 CMessg—消息类…………………………………………………….17 2.4.3.3 CComputer—电脑类…………………………………………………18 2.5．人机对战中的AI算法………………………………………………………………18 2.5.1 极大极小树…………………………………………………………………….19 2.5.2深度优先搜索（DFS）…………………………………………………………19 2.5.3 剪枝方法……………………………………………………………………….20 2.5.4 静态估值函数………………………………………………………………….21 2.5.5 AI算法的分析和改进………………………………………………………….21 2.5.5.1算法分析………………………………………………………………..22 2.5.5.2 算法改进………………………………………………………………..24
第三章 运行测试…………………………………………………………………………………25 3.1 网络部分……………………………………………………………………………...25 3.2 人机部分……………………………………………………………………………...25 第四章 总结部分…………………………………………………………………………………27 4.1 系统总结……………………………………………………………………………...29 4.2 不足说明……………………………………………………………………………...29 4.3 致谢…………………………………………………………………………………...28
参考文献…………………………………………………………………………………..29
第一章 引言
1.1 问题背景
计算机运算速度一直遵循着摩尔定律在飞速的发展，随着这些技术的快速
发展，使得大规模的运算得以在很短的时间内实现。正是基于这些技术，近年来各式各样的棋类游戏软件也纷纷出现在了电脑荧屏上，使得那些喜爱下棋，又常常苦于没有对手的棋迷们能随时过足棋瘾。所以如果能设计一款兼有人工智能和网络联机的五子棋软件则对五子棋棋迷们来说无疑是个“福音”。在人机智能方面其中战胜过国际象棋世界冠军-卡斯帕罗夫的“深蓝”便是最具说服力的代表；其它像围棋的“手淡”、象棋的“将族”等也以其优秀的人工智能深受棋迷喜爱；
3
本系统将重点放在人工智能方面，采用不同的策略将人工中的智能分为不同的等级。选择五子棋游戏作为本设计的课题，是因为该游戏的规则简单，所涉及的方向比较少。这样才能将问题的重点放在人工智能解决上，而非规则的解决，有更多的精力放在高效算法和通信过程的优化。希望能通过本次系统的设计，整合所学的知识，实现从理论到实践上的升华。
1.2 五子棋简介
下面就五子棋的背景和规则做一些简单的介绍。
五子棋是起源于中国古代的传统黑白棋种之一。现代五子棋日文称之为“连珠”，英译为“Renju”，英文称之为“Gobang”或“FIR”(Five in a Row的缩写)，亦有“连五子”、“五子连”、“串珠”、“五目”、“五目碰”、“五格”等多种称谓。 五子棋不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。五子棋既有现代休闲的明显特征“短、平、快”，又有古典哲学的高深学问“阴阳易理”；它既有简单易学的特性，为人民群众所喜闻乐见，又有深奥的技巧和高水平的国际性比赛；它的棋文化源渊流长，具有东方的神秘和西方的直观；既有“场”的概念，亦有“点”的连接。它是中西文化的交流点，是古今哲理的结晶。 五子棋的规则如下：棋盘：采用同围棋盘一样的15 路或19 路线的棋盘，为了减小问题的规模，本系统将采用15 路线的棋盘。下法：两人分别执黑白两色棋子，轮流在棋盘上选择一个无子的交叉点落子。无子的交叉点又被称为空点。输赢判断：黑、白双方有一方的5个棋子在横、竖或斜方向上连接成一线即为该方赢。
第二章 详细设计过程
2.1概要介绍
2.1.1本程序介绍
游戏中提供两种选择模式：人机对战和人人对战。在人机对战中玩家通过选择不同的等级和电脑一决高下，可以向后悔棋。在人人对战中双方通过选择一方作为服务器，通过弹出对话框设置本地应用程序监听端口，而另外一方则作为客户端，通过连接服务器选项，在弹出的对话框中设置要连接的服务器的IP地址和端口号。当双方都提示连接成功后，两方才可以进行下棋。如要悔棋则需要通
4
过对方的同意。同时还可以实现在线聊天。AI的不同等级是以不同的搜索深度确定的。本系统以深度为2，3，4分别为初级，中级，高级。网络对战中则使用Socket实现点对点通信。
2.1.2本程序特点
五子棋游戏程序由于规则简单操作简便等特点，自然就成为程序员对人工智能研究的首选对象。所以网络上关于这类的程序很多，但是由于主要都是采用搜索穷举技术作为解决方案，这将使得问题的规模变的很庞大如当搜索深度为3时，每走一步电脑在将最坏的情况下需要搜索的点将达到225*225*225=11390625个。即使采用的剪枝技术，其某些点的响应的时间也是让人无法忍受的，如开局时，因为这个时候每个点都是空的，没有可以剪枝的点，必须遍历真个盘面，所以很耗时间，大约需要30多秒的时间，这个显然是不可接受的。为了程序设计和玩家的忍受时间的需要。不得不减小深度，所以绝大部分都采用深度为2的检索，很明显深度越低系统的智力也相对的降低，需要代价的。
本程序的一个主要特点是，采用了高效的优化方法，使得在相同的搜索规模中所花费的计算时间大幅度的减小。响应时间明显得到提高。即使搜索深度达到4的时候，其响应时间在绝大部分的情况下还是可以接受的。
2.2用软件工程方法学指导开发过程
在小规模的程序开发中，很多人都不太注意用软件工程的方法学设计系统，
包括我本人，在开发一些小功能程序时总是随心所欲的添加需求：有时为了类与类之间的通信需要，往类中添加不相关的变量，直接修改变量的属性或者声明一大堆的全局变量。虽然最后系统都能够”笨重”的运行起来，但这是明显违背程序设计方法学。可维护行，易修改性严重降低。后期如果需要添加某些功能的时候将变得十分的繁琐。可以想象在多个团队一起开发的大型系统中这种粗陋的开发方法根本是行不通的。所以要养成用正确的方法指导开发过程的习惯，虽然有时候看起来有点大题小做，但我觉的这是作为一名合格的软件开发工程师所必须掌握的技能。通过长期不断的积累才能增加我们参与大型项目开发的能力。 下面对软件工程作下简单的介绍：
软件工程一直以来都缺乏一个统一的定义，很多学者、组织机构都分别给出了自己的定义：
Boehm：运用现代科学技术知识来设计并构造计算机程序及为开发、运行和维护这些程序所必需的相关文件资料。
IEEE：软件工程是开发、运行、维护和修复软件的系统方法。
Fritz Bauer：建立并使用完善的工程化原则，以较经济的手段获得能在实际机器上有效运行的可靠软件的一系列方法。
目前比较认可的一种定义认为：软件工程是研究和应用如何以系统性的、规范化的、可定量的过程化方法去开发和维护软件，以及如何把经过时间考验而证明正确的管理技术和当前能够得到的最好的技术方法结合起来。
我个人对软件工程理解是，它一种工程上的方法学，用一种有步骤，有计划的正确有效方法指导开发过程。
5