《人工智能导论》课程报告课题名称：五子棋姓名: X X 学号：114304xxxx课题负责人名（学号）： X X114304xxxx同组成员名单（学号、角色）：x x1143041325XXX1143041036指导教师：张建州评阅成绩：评阅意见：提交报告时间：2014年 1 月 9 日五子棋计算机科学与技术专业学生XXX 指导老师张建州[摘要]人类之所以不断在进步，是因为我们人类一直不断的在思考，五子棋游戏程序的开发符合人类进步也是促进人类进步的一大动力之一。
五子棋游戏程序让人们方便快捷的可以下五子棋，让人们在何时都能通过下棋来提高逻辑思维能力，同时也培养儿童的兴趣以及爱好，让孩子更加聪明。
同时，五子棋游戏程序的开发也使得五子棋这个游戏得到了广泛的推广，让世界各地的人们知道五子棋，玩上五子棋，这已经不是局限。
五子棋游戏程序使得越来越多的人喜欢上了五子棋，热爱下五子棋，它是具有很好的带动性的。
关键词：五子棋进步思考目录《人工智能导论》课程报告 01 引言 (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)1 引言1.1五子棋简介五子棋是一种两人对弈的纯策略型汉族棋类益智游戏，棋具与围棋通用，由中国汉族人发明，起源于中国上古时代的传统黑白棋种之一。
主要流行于华人和汉字文化圈的国家以及欧美一些地区。
容易上手，老少皆宜，而且趣味横生，引人入胜；不仅能增强思维能力，提高智力，而且富含哲理，有助于修身养性。
已在各个游戏平台有应用。
古代五子棋棋盘与围棋棋盘是通用的，汉魏时为十七路（17×17）棋盘，至南北朝时即已流行十九路（19×19）棋盘，直至1931年出现所谓五子棋专用棋盘。
1.2 五子棋游戏的发展与现状目前，连珠这一棋类运动已迅速在国际上发展起来。
外国人都十分看好这一不起眼的智力游戏，并认为五子棋不仅能提高思维、开发智力、手脑并用、修身养性而且富含哲理，具有东方的神秘和西方的直观，是中西文化的交汇点。
许多国家的人对五子棋都有不同的爱称，例如韩国人把五子棋称之为“情侣棋”，言下之意是情人之间下五子棋有利于增加情感的交流；欧洲人称之为“中老年棋”，表示五子棋适合中老年人的生理特点和思维方式；美洲人喜欢将五子棋称之为“商业棋”，就是说商人谈生意时可一边下棋一边谈生意，棋下完了生意也谈成了。
由此可见，尽管国度不同，语言各异，但人们都可以借助五子棋这一简单而又深奥的棋艺进行交流、比赛，增进友谊。
当前，有４０多个国家和地区都在下五子棋，并有各种规模和级别的比赛。
１９８９年８月在日本京都、１９９１年８月在俄罗斯联邦的莫斯科、１９９３年８月在瑞典、１９９５年８月在爱沙尼亚的塔林分别举行了第一、二、三、四届世界锦标赛。
除第三届的冠军是爱沙尼亚人之外，其余三届的冠军都是日本人。
五子棋的世界锦标赛，每两年举办一次，其申国竞争也十分激烈。
日本目前拥有自己的五子棋职业棋手，并且对连珠（五子棋）技术的研究也相当普遍和全面，就水平也正在日益增强。
同时，五子棋的理论研究与探索也呈现蓬勃发展的势头，从１８５８年第一部五子棋专著问世以来，目前，全世界有２０００多种五子棋的书籍及期刊，分别以日文、俄文、英文、瑞典文及中文出版发行。
五子棋在我国的北京、上海、天津、云南、浙江、广东、四川、湖北、辽宁、新疆、河北等省（区）市都有很大的发展。
北京多次举办了北京地区的五子棋赛，如“思曼杯”、“京空杯”、“奇奇童杯”、“北京第六届民族团结杯”和“北京第四岂民族运动会”的五子棋比赛。
上海地区举办了“上文杯”五子棋大赛。
云南省以及其他省市亦举办过许多五子棋比赛。
所有这些赛事都越来越多地吸引了无数人的关注，表明了根植于中国的五子棋有着广泛的群众基础，是群众喜闻乐见的体育活动。
而现在，很多很多游戏平台上面都有五子棋游戏供我们玩，任何游戏平台上面只要有棋牌类游戏的，那么它就有五子棋在里面，网络五子棋比赛，在联众，263，QQ游戏，UC里进行了10几年了可见，五子棋游戏在网络上面是非常火暴的，而且在棋牌游戏里面玩家人数排名总会占到很前面，不愧是风靡全球的棋牌游戏啊！在未来中，将会有越来越多的人关注五子棋，喜欢五子棋，那么将其变为商业化也会越来越多，而且还可以以教育孩子的方式来将其嵌套进去，或者用来做测试等等，可以说以后的五子棋游戏会是那么的精彩，那么的让人憧憬。
那么对于它的游戏开发和发展也将会上升到举足轻重的地位去，它的发展会是相当之快的，就让我们拭目以待吧。
2 研究问题描述2.1 问题定义问题定义的一个的关键问题是“要解决的问题是什么”，这个是这个阶段必须要明确要回答的问题。
在没将问题定义好，试图准备下个阶段的任务。
这明显是不成熟，甚至不可能的事。
本次系统设计中首先明确了需要解决的问题是五子棋AI算法，基本的要求是设计一款能够实现人机对战、人人对战和禁手的五子棋游戏，提供一些基本的操作如退出系统，向后悔棋等操作，重点是放在AI算法的研究。
而并不是美工设计，也不是为了提供各种操作丰富的接口。
主要是通过这种可视化的界面探讨AI，当然增加可玩性和美工会给系统润色不少。
上面只是很粗略的明确大概的方向，严格按照软件工程的方法这个阶段需要生产一份书面报告。
需要通过对系统的实际用户访问调查，扼要地写出他对问题的理解，并在用户和使用部门负责人的会议上认真讨论这份书面报告，澄清含糊不精的地方，改正理解不正确的地方，最后得出一份双方都满意的文档。
本系统的需求很少也很明显了。
2.2 可行性研究这个阶段要回答的关键问题：“对于上一个阶段所确定的问题是否可行？”为了回答这个问题，我们需要进行一次大大压缩和简化了的系统分析和设计的过程，也就是在较抽象的高层次上进行的分析和设计的过程。
可行性研究应该比较简短，这个阶段的任务不是具体解决问题，而是研究问题的范围，探索这个问题是否值得去解，是否有可行的解决办法。
可行性研究应该比较简短，这个阶段的任务不是具体解决问题，而是研究问题的范围，探索这个问题是否值得去解，是否有可行的解决办法。
可行性研究以后的那些阶段将需要投入要多的人力物力。
及时中止不值得投资的工程项目，可以避免更大的浪费。
根据这些基本的概念，我在技术上主要是通过相关文档资料的查找后确定可行性，凭着大学期间打下厚实的专业科基础，特别是数据结构和算法，能够在这段时间理解通透并应该有所改进，后来证明是对的。
利用剩下时间也应该来说也比较充裕的。
经济上暂不考虑。
下面主要从技术上进行分析：工具: Java是一种可以撰写跨平台应用软件的面向对象的程序设计语言，是由Sun Microsystems公司于1995年5月推出的Java程序设计语言和Java平台（即JavaSE, JavaEE, JavaME）的总称。
Java 技术具有卓越的通用性、高效性、平台移植性和安全性，广泛应用于个人PC、数据中心、游戏控制台、科学超级计算机、移动电话和互联网，同时拥有全球最大的开发者专业社群。
在全球云计算和移动互联网的产业环境下，Java更具备了显著优势和广阔前景。
所以用java来编写是一个很好的选择。
算法：在这图论搜索技术这方面，前人已有很成熟的算法。
如粗糙的有深度优先算法(DFS)和广度优先算法(BFS)这两个基本的算法，关键需要解决的是能够设计出一种高效的剪枝函数，减小搜索问题的规模。
目前博弈类游戏中的人工智能基本都采用极大极小值方法这对我来说是个挑战，而剪枝的则采用Alpha-Beta，通过丰富的文档资料初步了解到这些技术已经很成熟了。
我们有信心能解决好这个问题。
2.3 需求分析人工智能的第一大成就是下棋程序，在下棋程度中应用的某些技术，如向前看几步，把困难的问题分解成一些较容易的子问题，发展成为搜索和问题归纳这样的人工智能基本技术。
今天的计算机程序已能够达到下各种方盘棋和国际象棋的锦标赛水平。
但是，尚未解决包括人类棋手具有的但尚不能明确表达的能力。
如国际象棋大师们洞察棋局的能力。
另一个问题是涉及问题的原概念，在人工智能中叫做问题表示的选择，人们常能找到某种思考问题的方法，从而使求解变易而解决该问题。
到目前为止，人工智能程序已能知道如何考虑它们要解决的问题，即搜索解答空间，寻找较优解答。
在设计本系统时考虑到用户需要的是一个操作简便界面简单的游戏软件，同时要提供人机和人人这样的功能，特别是人机部分，要考虑到不同级别的用户，电脑智能不能太低需要有一定的智能下棋功能等等。
所以采用α-β剪枝法算法时就是为了达到这些目标。
2.4 总体设计这个阶段必须回答的关键问题是：“概括地说，应该如何解决这个问题？”首先，应该考虑几种可能的解决方案。
如，目标系统的一些主要功能是用计算机自动完成还是用人工完成；如果使用计算机，那么是使用批处理方式还是人机交互方式；信息存储使用传统的文件系统还是数据库……。
通常至少应该考虑下述几类可能的方案：低成本的解决方案。
系统只能完成最必要的工作，不能多做一点额处的工作。
本系统的最基本要求就是能够实现必要的操作，其他额外的一些工作在后面完成中等成本的解决方案。
这样的系统不仅能够很好地完成预定的任务，使用起来很方便，而且可能还具有用户没有具体指定的某些功能和特点。
虽然用户没有提出这些具体要求，但是系统分析员根据自己的知识和经验断定，这些附加的能力在实践中将证明是很有价值的。
这个成本方案在完成上面的低成本方案后添加的。
如增加保存棋局，美化界面，实现观看电脑与电脑之间的对战等功能。
高成本的“十全十美”的系统。
这样的系统具有用户可能希望有的所有功能和特点。
结构设计的一条基本原理就是程序应该模块化，也就是一个大程序应该由许多规模适中的模块按合理的层次结构组织而成。
总体设计阶段的第二项主要任务就是设计软件的结构，也就是确定程序由哪些模块组成以及模块间的关系。
通常用层次图或结构图描绘软件的结构。
2.5 详细设计总体设计阶段以比较抽象概括的方式提出了解决问题的办法。
详细设计阶段的任务就是把解法具体化，也就是回答下面这个关键问题：“应该怎样具体地实现这个系统呢？”这个阶段的任务还不是编写程序，而是设计出程序的详细规格说明。
这种规格说明的作用很类似于其他工程领域中工程师经常使用的工程蓝图，它们应该包含必要的细节，程序员可以根据它们写出实际的程序代码。