五子棋计算机博弈系统的研究与设计

发布时间：2018-06-05 18:05

本文选题：计算机博弈 + 五子棋　；参考：《安徽大学》2017年硕士论文

【摘要】：计算机博弈是人工智能领域最具挑战的研究分支之一。它是研究人脑思维的载体,是计算机技术与博弈论相结合的产物,是人工智能领域的"试验田",被誉为人工智能的"果蝇"。因此,有关计算机博弈的理论与实践研究,将可以促进人工智能的发展。在计算机博弈中,棋类博弈是其研究热点之一,因为人们相信存在于棋类博弈中的智能信息或许可以应用到人类智能活动中。五子棋博弈是棋类博弈中至关重要的组成部分,其普及程度仅次于国际象棋。它具有聚集博弈典型意义、容易深入研究、博弈结果直观反应机器智能程度等优点。因此可以把五子棋博弈作为计算机博弈的典型代表之一,对其进行深入研究,从而促使计算机博弈理论和实践研究的发展,进而推动人工智能事业不断地前进。本文以五子棋为载体对计算机博弈相关理论与技术进行了分析与研究。针对传统Alpha-Beta剪枝算法搜索效率较低以及博弈水平不高的问题,提出了一种基于连续冲四搜索的Alpha-Beta剪枝算法以及基于搜索限定的Alpha-Beta剪枝算法;针对传统基于棋型估值函数的参数主要由经验获得并通过手工进行调整,存在人为不确定性的问题,提出了一种新的自适应惯性权重混沌粒子群算法(A New Chaos Particle Swarm Optimization Based Adaptive Inertia Weight,CPSO-NAIW),并把它首次应用到五子棋估值函数参数优化问题中。实验结果表明,本文提出的改进Alpha-Beta剪枝算法有效地提高了搜索效率和博弈水平;采用本文提出的CPSO-NAIW算法优化后参数的五子棋博弈系统的博弈水平得到了很大提升。本文首先介绍了计算机博弈相关概念与技术,然后分析了五子棋博弈组成要素并利用事件对策论对其进行数学建模,研究了五子棋博弈中的搜索算法以及估值函数,最后对系统进行了设计与实现。本文核心技术与创新点如下:(1)提出了一种基于连续冲四搜索的Alpha-Beta剪枝算法。根据五子棋博弈的特点,在Alpha-Beta剪枝算法中引入连续冲四搜索这种强有力的进攻手段,并采用搜索范围限定以及对连续冲四成功进行保存,当下次遇到相同局面时,优先对存储的连续冲四着法进行搜索的连续冲四启发方法,以减少无用和重复搜索。该算法提高了搜索效率和博弈水平。(2)提出了一种基于搜索限定的Alpha-Beta剪枝算法。根据五子棋落子比较集中和脱离战场思想,对棋盘搜索区域进行划分,并根据不同搜索区域落子对局面的影响程度采用不同的搜索深度,以减少无用搜索。该算法在不影响博弈水平的情况下,提高了搜索效率。(3)提出了一种新的自适应惯性权重混沌粒子群算法(CPSO-NAIW)。该算法从惯性权重的调整以及如何摆脱局部极值两个方面入手来改善粒子群算法(Particle Swarm Optimization,PSO)的性能。首先采用粒子相对于群体极值位置的距离对权重进行动态调整,把权重的变化与粒子的位置状态信息关联起来的方法,减少了算法陷入局部极值的概率,然后在算法陷入局部极值时,对群体极值位置进行混沌优化,以使粒子搜索局部极值外的新邻域和新路径,增强了算法跳出局部极值的可能,最后把CPSO-NAIW算法首次应用到五子棋估值函数的参数优化问题中,以解决传统估值参数仅通过手工调整,存在人为不确定的问题。采用该算法优化后参数的五子棋博弈系统的博弈水平有显著提升。本文以五子棋为载体对计算机博弈中至关重要的搜索算法以及估值函数进行了相关研究与改进。在搜索算法方面,提出了一种基于连续冲四搜索的Alpha-Beta剪枝算法以及基于搜索限定的Alpha-Beta剪枝算法。在估值函数方面,提出了一种CPSO-NAIW算法,并把它首次应用到估值函数的参数优化问题中。实验结果表明,两种改进的Alpha-Beta剪枝算法有效地提高了搜索效率和博弈水平,应用CPSO-NAIW算法优化后参数的五子棋博弈系统的博弈水平具有明显优势。
[Abstract]:Computer game is one of the most challenging research branches in the field of artificial intelligence. It is the carrier of human brain thinking, the product of the combination of computer technology and game theory. It is the "experiment field" in the field of artificial intelligence and is known as the "fruit fly" of artificial intelligence. Therefore, the theoretical and practical research on the computer game will be able to promote artificial intelligence. The chess game is one of the hotspots in the computer game, because it is believed that the intelligence information that exists in the chess game may be applied to the human intelligence activity. The chess game is the most important part of the chess game, and its popularity is second only to the chess. It has a typical gathering game. Therefore, the game can be regarded as one of the typical representative of the computer game, so we can make a thorough study of the game, so as to promote the development of computer game theory and practice research, and then push the cause of artificial intelligence to advance continuously. This paper analyzes and studies the related theory and technology of computer game. Aiming at the problem of low search efficiency and low game level of traditional Alpha-Beta pruning algorithm, a Alpha-Beta pruning algorithm based on continuous punching four search and a Alpha-Beta pruning algorithm based on search limit are proposed. The parameters of the estimation function are mainly obtained by experience and adjusted by hand. A new adaptive inertia weight chaotic particle swarm optimization (A New Chaos Particle Swarm Optimization Based Adaptive Inertia Weight, CPSO-NAIW) is proposed, and it is used for the first time in the function parameter of the Gobang estimation function. The experimental results show that the improved Alpha-Beta pruning algorithm proposed in this paper can effectively improve the search efficiency and the game level. The game level of the five chess game system which is optimized after the optimization of the CPSO-NAIW algorithm proposed in this paper has been greatly improved. This paper first introduces the related concepts and techniques of computer game, Then it analyzes the elements of the chess game and uses the event game theory to model it, studies the search algorithm and the valuation function in the chess game, and finally designs and implements the system. The core technology and innovation of this paper are as follows: (1) a Alpha-Beta pruning algorithm based on continuous four search is proposed. According to the features of the chess game, the Alpha-Beta pruning algorithm is introduced in the Alpha-Beta pruning algorithm to search for this powerful attack method, and the search scope is limited and the continuous impulse four is saved successfully. When the next situation comes into the same situation, a continuous impulse four heuristic method for searching the stored continuous flushing method is given to reduce the continuous impulse. The algorithm improves the search efficiency and the game level. (2) a Alpha-Beta pruning algorithm based on the search limit is proposed. The search area is divided according to the focus of the checkerboard and the idea of disengagement from the battlefield, and different search is used to search the situation according to the different search area. Depth, in order to reduce the useless search. The algorithm improves the search efficiency without affecting the game level. (3) a new adaptive inertia weight chaotic particle swarm optimization (CPSO-NAIW) algorithm is proposed. The algorithm improves the particle swarm optimization (Particle Swarm Opt) from the adjustment of the inertia weight and how to get rid of the local extremum. The performance of imization, PSO). Firstly, the weight is dynamically adjusted by the distance between the particle relative to the group extremum position, and the method of correlation between the weight change and the position state information of the particle is used to reduce the probability of the algorithm falling into the local extremum. Then, when the algorithm falls into the local extremum, the chaotic optimization of the position of the population extremum is carried out. In order to make the particle search the new neighborhood and new path outside the local extremum, the possibility of the algorithm to jump out of the local extremum is enhanced. Finally, the CPSO-NAIW algorithm is first applied to the parameter optimization problem of the five chess estimation function, so as to solve the traditional estimation parameter only by manual adjustment, there is a human uncertainty problem. The algorithm is used to optimize the parameters of five. The game level of the sub chess game system has been significantly improved. In this paper, the search algorithm and the estimation function of the computer game are studied and improved by using the Gobang as the carrier. In the search algorithm, a Alpha-Beta pruning algorithm based on the continuous scour four search and the Alpha-Beta scissors based on the search limit are proposed. In the estimation function, a CPSO-NAIW algorithm is proposed and applied to the parameter optimization problem of the estimation function for the first time. The experimental results show that the two improved Alpha-Beta pruning algorithms can effectively improve the search efficiency and game level, and use the CPSO-NAIW algorithm to optimize the game water of the five chess game system after the parameter optimization. Leveling has obvious advantages.
【学位授予单位】：安徽大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【相似文献】