Research And Design Of The Gomoku Computer-Game System

The computer game is one of the most challenging research branches in 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 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 part 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 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 traditional 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 function 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 algorithm 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 elements 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 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,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 on 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 improves 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 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 optimum.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 increaseed.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 CPSO-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 and 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 algorithm 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.