五子棋计算机博弈系统的研究与设计-张效见.docx

《五子棋计算机博弈系统的研究与设计-张效见.docx》由会员分享，可在线阅读，更多相关《五子棋计算机博弈系统的研究与设计-张效见.docx（75页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 保密期限 : 硕士学位论文 五子棋计算机博弈系统的研究与设计 Research and Design of the Gomoku Computer-Game System 学 号 E14201067 姓 名 张效见 学位类别 工学硕士 学 科 专 业 (工程领域） 计算机应用技术 指导教师 李龙澍教授 完成时间 2017年 5月 答辩委员会 i-n 独创性声明 本人声赌錢酵錄文是本人辟师指导下进行贿究 I作及取得的 研究成果。据我所知，以文中特别加以标注和致谢的地方外，论文中不包含其 他人已经絲或鮮賴研究成果，也不包含为获得安徽大学賴他教育机构的 学位或证书 舰的雜。与我 -同工 _啦財 鐘

2、的絲贡献均已 在论文中作了明确的说明并表示谢意。 学位论文作者签名：嚴访办 签 字 日 期 ： 年 e月以日 学位论文版权使用授权书 本字位论文作者完全了解安徵大学有关健、使鮮位论文的般，有权 保留并 _冢有关部 n或机機交论文岐特和磁盘，允絲文被查阅和借 阅。本人授权錄大抖以将学位论文齡部或部分内容编人有关麵库进行检 索 可以采用獅、 _卩触鮮复制手賴存、汇编学位论文。 (保密的学位论文在解密后适用本授权书 ） 学位论文作者签名： _为 导师签名 签字曰期：州年吃月比日 签 字 日 期 ： 年 政 日 Y3214287 计算机博弈是人工智能领域最具挑战的研宄分支之一。它是研宄人脑思维的 载体

3、，是计算机技术与博弈论相结合的产物，是人工智能领域的 试验田 ，被 誉为人工智能的 果蝇 。因此，有关计算机博弈的理论与实践研宄，将可以促 进人工智能的发展。在计算机博弈中，棋类博弈是其研宄热点之一，因为人们相 信存在于棋类博弈中的智能信息或许可以应用到人类智能活动中。 五子棋博弈是棋类博弈中至关重要的组成部分，其普及程度仅次于国际象 棋。它具有聚集博弈典型意义、容易深入研宄、博弈结果直观反应机器智能程度 等优点。因此可以把五子棋博弈作为计算机博弈的典型代表之一，对其进行深入 研宄，从而促使计算机博弈理论和实践研宄的发展，进而推动人工智能事业不断 地前进。 本文以五子棋为载 体对计算机博弈相关

4、理论与技术进行了分析与研宄。针对 传统 Alpha-Beta剪枝算法搜索效率较低以及博弈水平不髙的问题，提出了一种基 于连续冲四搜索的 Alpha-Beta剪枝算法以及基于搜索限定的 Alpha-Beta剪枝算 法；针对传统基于棋型估值函数的参数主要由经验获得并通过手工进行调整，存 在人为不确定性的问题，提出了一种新的自适应惯性权重混沌粒子群算法 (A New Chaos Particle Swarm Optimization Based Adaptive Inertia Weight, CPSO-NAIW),并把它首次应用到五子棋估值函数参数优化问题中。实验结果表 明，本文提出的改进 Alp

5、ha-Beta剪枝算法有效地提高了搜索效率和博弈水平；采 用本文提出的 CPSO-NAIW算法优化后参数的五子棋博弈系统的博弈水平得到 了很大提升。 本文首先介绍了计算机博弈相关概念与技术，然后分析了五子棋博弈组成要 素并利用事件对策论对其进行数学建模，研究了五子棋博弈中的搜索算法以及估 值函数，最后对系统进行了设计与实现。 本文核心技术与创新点如下： (1) 提出了一种基于连续冲四搜索的 Alpha-Beta剪枝算法。根据五子棋博弈 的特点，在 Alpha-Beta剪枝算法中引入连续冲四搜索这种强有力的进攻手段，并 采用搜索范围限定以及对连续冲四成功进行保存，当下次遇到相同局面时，优先 对存

6、储的连续冲四着法进行搜索的连续冲四启发方法，以减少无用和重复搜索。 该算法提高了搜索效率和博弈水平。 (2) 提出了一种基于搜索限定的 Alpha-Beta剪枝算法。根据五子棋落子比较 集中和脱离战场思想，对棋盘搜索区域进行划分，并根据不同搜索区域落子对局 面的影响程度采用不同的搜索深度，以减少无用搜索。该算法在不影响博弈水平 的情况下，提高了搜索效率。 (3) 提出了一种新的自适应惯性权重混沌粒子群算法 (CPSO-NAIW)。 该算法 从惯性权重的调整以及如何摆脱局部极值两个方面入手来改善粒子群算法 (Particle Swarm Optimization, PSO)的性能。首先采用粒子相

7、对于群体极值位置的 距离对权重进行动态调整，把权重的变化与粒子的位置状态信息关联起来的方 法，减少了算法陷入局部极值的概率，然后在算法陷入局部极值时，对群体极值 位置进行混沌优化，以 使粒子搜索局部极值外的新邻域和新路径，增强了算法跳 出局部极值的可能，最后把 CPSO-NAIW算法首次应用到五子棋估值函数的参数 优化问题中，以解决传统估值参数仅通过手工调整，存在人为不确定的问题。采 用该算法优化后参数的五子棋博弈系统的博弈水平有显著提升。 本文以五子棋为载体对计算机博弈中至关重要的搜索算法以及估值函数进 行了相关研究与改进。在搜索算法方面，提出了一种基于连续冲四搜索的 Alpha-Beta剪

8、枝算法以及基于搜索限定的 Alpha-Beta剪枝算法。在估值函数方面， 提出了一种 CPSO-NAIW算法，并把它首次应用到估值函数的参数优化问题中。 实验结果表明，两种改进的 Alpha-Beta剪枝算法有效地提高了搜索效率和博弈水 平，应用 CPSO-NAIW算法优化后参数的五子棋博弈系统的博弈水平具有明显优 势。 关键词 ： 计算机博弈；五子棋； Alpha-Beta剪枝算法；粒子群算法；自适应 惯性权重；混沌；连续冲四；搜索限定； ABSTRACT The computer game is one of the most challenging research branches i

9、n the field of artificial intelligence. It is the carrier of studying human thinking and combination of computer technology and game theory. The computer game is named as the fruit bat and test in artificial intelligence field of artificial intelligence. Therefore, the theory and practical research

10、on computer game will promote the development of artificial intelligence. The chess game is one of the most important area in computer game research, because people believe the intelligent information in chess game perhaps can be applied to human intelligence activities. Gomoku game is a crucial par

11、t in chess game. The popularity of Gomoku game is only second to international chess game. It has the advantages of gathering the typical significance of game, easily studying further, the direct response of machine intelligent degree. Therefore, the Gomoku game can be regarded as a typical example

12、of computer game. The research of Gomoku game can promote the development of computer game theory and practical research, and continually move the cause of artificial intelligence forward. In this thesis, we analyzes the theories of Gomoku and techniques of computer game. According to the traditiona

13、l Alpha-Beta pruning algorithm search efficiency is low and the level of game is not high, we propose a Alpha-Beta pruning algorithm based on victory by continuous four and a Alpha-Beta pruning algorithm based on search limited. Because of the chess-type parameter of the traditional valuation functi

14、on need to experience and adjusted by hand. This thesis proposed a new chaos particle swarm optimization based adaptive inertia weight (CPSO-NAIW), and first applied to the parameter optimization of valuation function problem. The experimental results show that the improved Alpha-Beta pruning algori

15、thm can effectively improve the search efficiency and the level of game. The level of game of Gomoku game system with the parameters optimize by CPSO-NAIW algorithm have been improved greatly. This thesis first introduces the concept and technology related to computer game. Then, we analyzes the ele

16、ments of Gomoku and uses event game theory to build the math model, study the search algorithm and valuation function in Gomoku game. Finally, we design and achieve Gomoku game system. The core technology and innovation of this thesis is the following: (1) This thesis proposed an Alpha-Beta pruning

17、algorithm based on victory by continuous four. According to the characteristics of Gomoku game, the victory by continuous four is powerful attack in the Alpha-Beta pruning algorithm, and use the search scope limit and save the success of the victory by continuous four. When the next same situation,

18、the priority of the storage of the victory by continuous four, to reduce the useless and repeat search. The algorithm improves the search efficiency and the level of the game. (2) In this thesis, an Alpha-Beta pruning algorithm based on search limited is proposed. According to the place the pieces o

19、n the board is comparatively centralized and detached from the battlefield idea, a search area to be divided on the board. In order to reduce the useless search, the influence to the situation of place the pieces on the different search area to made the search depth is different. The algorithm impro

20、ves the search efficiency without affecting the level of game. (3) A new chaos particle swarm optimization based adaptive inertia weight (CPSO-NAIW) is proposed. This algorithm improves the performance of particle swarm optimization (PSO) from two aspects: the adjustment of inertia weight and how to

21、 get rid of local extremum. Firstly, the algorithm adjust weight according to the distance of the particle relative to the position of the swarm extreme value. And connect weights change to the position information of a particle. It can reduce the probability of the algorithm falling into local opti

22、mum. Then, when the algorithm falls into local optimal value, the strategy of chaos optimization is introduced to adjust the position of the particles extreme value so that the particles can search the new neighorhood and path. The probability of the new algorithm gets rid of the local extremum is i

23、ncreaseed. Finally, the CPSO-NAIW algorithm is first applied to the parameter optimization problem of Gomoku valuation function to solve the uncertain problems of traditional valuation parameters only by manual adjustment. The level of game of Gomoku game system with the parameters is optimized by C

24、PSO-NAIW algorithm has obvious advantages. In this thesis, taking Gomoku as a carrier, we research and improve vital search algorithm and valuation function in computer game. In the aspect of search algorithm, this thesis proposed an Alpha-Beta pruning algorithm based on victory by continuous four a

25、nd Alpha-Beta pruning algorithm based on search limited. In the aspect of the valuation function， a CPSO-NAIW algorithm is proposed and applied to the parameter optimization problem of the valuation function for the first time. The experimental results show that the two improved Alpha-Beta pruning a

26、lgorithm effectively improves the search efficiency and the level of game, the level of game of Gomoku game system with the parameters is optimized by CPSO-NAIW algorithm has obvious advantages. Keywords: Computer Game; Gomoku Game; Alpha-Beta Pruning Algorithm; Particle Swarm Optimization Algorithm

27、; Adaptive Inertia Weight; Chaotic; Victory by Continuous Four; Search Limited; m-n . 1 u研宄背景 . 1 1.2研宄现状 . 4 1.3研宄意义 . 5 1.4本文工作 . 6 1.4.1研究内容 . 6 1.4.2论文组织结构 . 7 第二章计算机博弈基本概念与技术 . 9 2.1基本概念与技术 . 1 2.1.1博弈树 . 10 2.1.2复杂度 . 11 2.1.3 递归 . 12 2.1.4 015 . 12 2.2研究对象及分析 . 13 2.2.1对象分类 . 13 2.2.2本文研宄对象 .

28、 14 2.3本章小结 . 14 第三章五子棋计算机博弈建模 . 15 3.1 五子棋术语 . . . . . 15 3.2五子棋规则 . . . 16 3.3五子棋博弈系统组成要素 . 17 3.3.1知识表示 . 18 3.3.2着法生成 . 18 3.3.3搜索算法 . 18 3.3.4估值函数 . 19 3.4五子棋博弈过程建模 . 19 3.5本章小结 . 21 第四章 Alpha-Beta剪枝算法搜索优化 . 22 4.1基本搜索算法介绍 . 22 4.1.1盲目搜索算法 . 23 4.1.2极大极小算法 . 27 4.1.3 Alpha-Beta 剪枝算法 . 29 4.1.4

29、Alpha-Beta剪枝算法效率 . 30 4.2基于连续冲四搜索的 Alpha-Beta剪枝算法 . 30 4.2.1连续冲四与相关优化 . 30 4.2.2算法描述 . 32 4.2.3实验设计与分析 . 34 4.3基于搜索限定的 Alpha-Beta剪枝算法 . 37 4.3.1搜索限定 . 37 4.3.2算法描述 . 38 4.3.3实验设计与分析 . 39 4.4本章小结 . 40 第五章基于 CPSO-NAIW算法的估值函数参数优化 . 42 5.1估值函数 . 43 5.2 CPSO-NAIW 算法 . 44 5.2.1粒子群算法 . 44 5.2.2自适应惯性权重 . 45

30、 5.2.3基于混沌优化摆脱局部极值的方法 . 46 5.3基于 CPSO-NAIW算法的估值函数参数优化算法 . . . 47 5.3.1个体编码和种群初始化 . 47 5.3.2适应度函数的计算方法 -锦标赛法 . 47 5.3.3算法描述 . 48 5.4实验设计与分析 . 49 5.5本章小结 . 51 第六章五子棋博弈系统设计与实现 . 52 6.1系统设计 . 52 6.1.1系统总体结构 . 52 6.1.2系统流程图 . 53 VII 6.2系统实现 . 54 6.2.1运行环境与实现技术 . 54 6.2.2系统界面 . 55 6.3本章小结 . 56 第七章总结与展望 . 57 7.1本文的主要贡献与结论 . 57 7.2未来工作与展望 . 59 参考文献 . 60 附录 A:图索引和表索引 . 63 mm . 64 攻读硕士期间发表的论文、科研项目及获奖情况 . 65