《基于一种新算法的人工智能五子棋》由会员分享,可在线阅读,更多相关《基于一种新算法的人工智能五子棋(53页珍藏版)》请在金锄头文库上搜索。
1、本科毕业设计(论文)GRADUATION DESIGN (THESIS) 题 目基于一种新算法的人工智能五子棋 学生姓名 万文韬 指导教师 余腊生 学 院 信息科学与工程学院 专业班级 物联网工程1103班 本科生院制 2015年6月 基于一种新算法的人工智能五子棋基于一种新算法的人工智能五子棋摘要五子棋是一种简单的黑白棋,历史悠久,起源于中国,后传入日本,在日本被称为“连珠”,五子棋在日本获得了长足的发展,规则进一步得到完善,而后,传遍世界,在欧美国家也有很多爱好者,他们称五子棋为“Gobang”或者FIR(five in a row)。人工智能五子棋属于人工智能中人机博弈的一种,人工智能应
2、用广泛,比如自然语言处理能帮忙建造自动翻译机器,生物模式识别能帮助实现更先进的加密方法,应用于各种需要加密的场所,语音识别技术能帮忙实现快速将语音输入准确转换为文字输入,总之,人工智能是促进未来人类科技和生活重大改变的一门学科。 本篇论文主要是有关智能五子棋的算法及其实现。在介绍完相关背景后,主要详细介绍了智能五子棋的四种算法:神经网络强化学习算法,博弈树算法,极大极小值搜索算法和-剪枝算法,真正的系统实现采用的是剪枝算法,并且在此基础上提出了自己的优化策略,实现了创新。关键词:人工智能 五子棋 算法 博弈An artificial intelligence gobang system bas
3、ed on a new arithmeticAbstractGobang is a simple kind of reversi ,it has a long history , it derives its origin from China, then it was introduced to Japan, in Japan, they call it “LianZhu”. The Gobang has got much development in Japan, its rule became complicated and then it was introduced all arou
4、nd the world,it also has many fans in Europe and America, who call it “Gobang” or “FIR”(five in a row).The artificial intelligence gobang is one kind of Man-Machine game which is also the one domain of artificial intelligence. Artificial intelligence has widespread applications, for example: natural
5、 language processing can help building the automatic translator, biological pattern recognition can help realizing more advanced cryptosystem, and speech recognition technology can help realizing change phonetic input to accurate wordy input quickly. In short, artificial intelligence is one science
6、which may make great difference in humans life and the progress of technology.This paper is to discuss the arithmetic and realization of artificial intelligence Gobang. After introducing the relevant background, it describes four different arithmetic of artificial intelligence gobang in detail: neur
7、al network reinforcement learning algorithm, game tree algorithm, minimax value search algorithm and alpha-beta pruning algorithm. The pruning algorithm has been chosen to realize the real system, and I added my own optimizing strategy on it realizing the innovation.Keyword: Artificial intelligence
8、Gobang Algorithm Game目录第1章 绪论11.1 智能五子棋研究背景与意义11.2.1 五子棋的发展现状21.2.2 人工智能的研究现状31.2.3 人机对弈的研究现状41.2.4 领域内学术会议与期刊51.3 本课题研究内容61.4 本论文组织结构7第2章 需求分析和系统设计92.1 需求概述92.1.1 任务92.1.2 目标用户及特点102.2 需求规范102.2.1 对功能的要求102.2.2 对性能的要求102.2.3对代码质量的要求112.3 运行环境132.4 结构设计132.4.1 系统结构设计132.4.2数据结构设计14第3章 神经网络强化学习算法153.
9、1 算法概述153.2 算法具体过程163.3 实现和性能213.4 本章小结22第4章 博弈树算法及其优化234.1 算法概述234.2 博弈树算法具体过程244.3 优化284.3.1 极大极小值搜索算法284.3.2 -剪枝算法304.4 本章小结32第5章 系统构建过程细节论述335.1 游戏界面335.2 游戏步骤335.3 判断棋型345.4 落子估值方式385.5 棋局估值函数415.6 -剪枝算法的伪代码:425.7 其它优化思考42第6章 结论436.1 总结436.2 展望44结束语45参考文献47第1章 绪论人工智能五子棋具有人机对弈的特征,属于人工智能的范畴,可以运用各
10、种人工智能领域的方法来处理该问题,同时由于五子棋游戏规则简单,通俗易懂,流行度高,所以人工智能五子棋研究的门槛不高,软件系统规模不大,对硬件的要求不高,单台PC机可以完成一般的测试,然其又不失重要性和典型性,以上种种都使之成为研究人工智能的很好入门选择。本章先介绍研究人工智能五子棋的背景和意义,之后较为详细的介绍目前该领域的研究现状,然后介绍该领域及相关领域的学术会议和期刊,之后介绍本课题的研究重点,最后简单介绍整篇论文的组织架构。1.1 智能五子棋研究背景与意义五子棋是一款简单益智的竞技棋类游戏,本课题研究用计算机实现五子棋博弈功能。人机博弈一直以来是人工智能的主要研究方向之一。人工智能是研
11、究,开发用于模拟、延伸和拓展人的智能的理论、方法、技术及应用系统的一门科学和技术。旨在用人工实现智能。人工智能是计算机科学的一个分支,它企图了解智能的实质,并生产出一种新的能以人类智能相似的方式做出反应的智能机器,该领域的研究包括机器人、语言识别、图像识别、自然语言处理和专家系统等。 第 0 页 共 54 页 当前人工智能分为“强人工智能”和“弱人工智能”,“强人工智能”希望探讨智能的本质,实现真正的类人智能,其研究目前处于瓶颈状态,“弱人工智能”则采用工程学方法,已解决具体问题为目的的,实现表面的貌似智能1。目前这一研究方向有众多成果,像“自然语言处理”“机器证明”“专家系统”“人机博弈”等
12、领域目前都用的是“弱人工智能”的方法,比如“神经网络算法”“遗传算法”“蚁群算法”“博弈树搜索”等等2。人机博弈是人工智能的重要分支之一,研究的是人与机器的博弈,同常的人机下棋便属于此,其已有一段历史。1997年,当时世界排名第一的国际象棋棋手加里卡斯帕罗夫以2.5:3.5(1胜2负3平)负于IBM超级计算机“深蓝”更是将人机博弈推向新的高潮。本课题便是在此背景下提出的,旨在初步学习人机博弈理论,构建一个五子棋人机博弈系统。随着改革开放的发展,中国人民的物质生活水平大大提高,开始越来越追求精神层面的享受。五子棋作为一种怡情益智类游戏,有陶冶情操,开发智力的作用,人工智能五子棋作为人机博弈的一种
13、,研究它,无疑具有相关的科学意义,对自己而言,也具有学习意义。1.2 研究现状1.2.1 五子棋的发展现状五子棋起源于中国,原始规则很简单两方棋手分别执黑白两色棋子交替落子于类似围棋的棋盘,只要有一方先走成在横、竖、斜方向上的五颗同色棋子就赢得比赛。一般是黑方现行,但是这样使得黑方总可以找到必胜下法,所以,后来五子棋规则有了很多发展变化,其目的都是为了抵消黑方的先行优势,比如:在开局后的第三手,白方拥有“三手交换”权利,即:如果白方觉得下完三手棋后黑方棋型很厉害,可以要求自己与对手黑白互换;“五手两打”即在第五手黑方应接连下两子,然后由白方决定在这两子中留下哪一子,“禁手规则”这是针对黑方的,
14、白方无禁手,黑方有“三、三”“四、四”“长连”禁手,禁手判负,黑方只能以“四、三”取胜。除了规则的发展外,五子棋的下法也不断的成熟,已经发展出各种成熟下法:在棋型中存在着:活四、冲四、活三、跳活三,二又存在好几种连活二,跳活二,大跳活二,其次还有眠二和死二。三也能分好几种:有两种类型的活三,针对它们有各自不同的防守点,另外还有眠三和死三。此外有各种开局,局中走法和做杀技巧。总之,五子棋游戏无论是规则还是走法策略现阶段都已发展的相当成熟。1.2.2 人工智能的研究现状人工智能被认为是二十一世纪三大尖端技术(基因工程、纳米科学、人工智能)之一,当前主要的研究成果主要还是集中于“弱人工智能”领域。近年来出现了一些可喜的成果:搜索引擎得到了新的发展和完善:首先是算法的不断改进,这方面的工作首推美国的谷歌公司。其次是搜索的对象得到了扩展,不再局限于传统的文本搜索,新增了图像搜索,语音搜索甚至情感搜索,可以实现“以图搜图”“用语音搜索”,以及“心理搜索”。再次是搜索领域得到拓宽,人工智能技术使得搜索引擎的搜索领域不再局限于互联网范围而是扩展到整个物联网范围和云平台,可以对各种实现了智能感知的物品实现在线状态搜索。当前学术界认为有三种发展人工智能的路线:一、以专家系统为代表的以功能模拟为目的的符号主义路线;