Research On The Complexities,Theoretical Values Of Computer Games And Some Search Algorithms

The computer game is to let computer think how to make moves in order to win the game and it is a challenging research field of artificial intelligence.Turing test is to check the intelligent level of computer by playing games.The level of computer game represents that of computer's intelligence.Making computer beat human-being is the research object of all scholars at home and abroad all the time.In 1997,the IBM supercomputer Deep Blue won the World Chess Champion Kasparov,which causes a great sensation in the world,and it suggests that computer could win human-being genius and the critical thinking of computer is closer to human-being.In 1944,Von Neuman and Morgenstern have developed a theory of two-person zero-sum games in their book Theory of Games and Economic Behavior.Chess games are concrete forms of this theory.Solving game is a challenging task in the domain of Artificial Intelligence and it is an object that all computer games' scholars are longing for.Nowadays with the rapid development of computer power,some computer games(such as Connect Four,Go-moku and Checkers and so on)have been solved.However,to some computer games with higher complexity(such as Chinese chess,Shogi,Go and so on),they are solved so hard that scholars only study solving these games' endings.It is obvious that the current computer and search algorithms can not solve these computer games.Hence,scholars must focus on researching the theory of computer games(such as their complexity,state complexity,game-tree complexity,search algorithms).This dissertation mainly does some intensive study on solving computer games.;to know how hard a computer game is solved,the computational complexity is studied comprehensively and it is proved that Chinese chess is EXPTIME-complete;to decide to choose which strategy is used to solve a computer game by the computer game's state complexity and game-tree complexity,this dissertation studies the estimating methods of computer game's two complexities of computer games;proposes an improved proof-number search that is used to solve computer games by foreign scholars;moreover,studies and discusses some common search algorithms in a global perspective;takes horn and Connect6 for examples,the specific methods used to solve these two computer games are studied.These research fruits are listed as follows,this dissertation introduces and analyzes some fundamental concepts of computational complexity,and discusses some main classes of time complexity and space complexity by examples.The classes of time complexity generally include:P,NP,NP-hard,NP-complete and EXPTIME;the classes of space complexity generally include:PSPACE,NPSPACE,PSPACE-hard and PSPACE-complete.The relation among complexity classes is analyzed in detail.What's more,a deduction is given that NP problem is in non-polynomial time;an nxn Chinese Chess position is constructed,G3 game is simulated on the position,and hence it is proved that G3 is reducible to nxn Chinese Chess in polynomial time,and then Chinese Chess is EXPTIME-complete;the estimating methods of computer game's state complexity and game-tree complexity are illustrated.On the basis of the common estimating methods of the two complexities and the feature of some computer games,some possible illegal positions are analyzed and removes in the course of estimation.The state complexities of Amazons and Surakarta are estimated in detail,and so are the game-tree complexities of Connect6 and Dots-and-Boxes;this dissertation introduces some relative theories of computer game-theoretical value,and sums up methods and core technologies used to solve Go-moku,8x8 Checkers and ending game of Go.Taking horn for example,its state complexity and game-tree complexity are estimated by which appropriate strategy is chosen to solve horn.Finally,horn is solved;the dissertation proposes a solving strategy of Connect6 based on K-in-a-row types,and expounds some algorithms that made up the strategy.The strategy includes mover generator based on K-in-a-row types,a calling algorithms(etc.alpha-beta pruning search and threats space search)strategy based on the number of threats.Taking 7x7 Connect6 openings for example,the experimental result shows that the solving ability of the strategy is strong;in terms of search algorithms,this dissertation expounds principles of Proof-number based on the AND/OR tree,summarizes the application of Proof-number search to computer game of Lazi and discusses the flaws of Proof-number and PN2 search.Moreover,this article introduces a new two-level algorithm(PN2 search's variant),i.e.PN-DFPN search,and PN2 and PN-DFPN are applied to solve some openings of Conncet6 by 7×7.The experimental result shows that PN-DFPN is more efficient than PN2.Non-cooperative dynamic games'complexities,theoretical value and their relationships are discussed.It also summarizes basic search algorithms and some advanced algorithms based on alpha-beta.Moreover,this article expounds several search algorithms which are widely applied to computer games in detail.All the algorithms,methods and conclusions proposed in this dissertation are verified reasonably and practically,which can provide a theoretical support and effective method in realizing solving computer games with higher complexity.