Turn-based War Chess Model And Its Search Algorithm Per Turn

Turn-Based War Chess gaming(TBW)has so far received insufficient attention but is a significant component of turn-based strategy games(TBS).There is no common game model proposed through various existing war chess types,which limits the research of war chess game.With the blossoming of mobile games,TBS games will have greater potential for development in the areas of touch-screen operation,lightweight,fragmented time,and so on.However,the AI of modern TBS games is generally not so intelligent,of which the fundamental reason is that the AI in its local battle(TBW)is not so intelligent.How to improve the TBW's artificial intelligence,thus improving the vitality of the entire TBS game industry,is an urgent problem that until now has been overlooked.A TBW game is essentially the compound of combinational optimization laterally and game tree search vertically,which can be regarded as a programming problem of multiagent collaboration in stages and can be seen as a tree search problem with huge branching factor.Thus,the expansion and development of the traditional systems hidden behind TBW games will make the research more meaningful than the game itself.Nowadays a new round of weak artificial intelligence researches based on big data,cloud computing and machine learning are booming,which makes it possible to improve the TBW's artificial intelligence using more effective technology.In the thesis the characteristics of TBW are analyzed systematically,based on which the game tree theory is chosen as a main method to treat the machine game of TBW.First,a common game model is proposed through various existing war chess types.Based on the model,we propose a theory frame involving combinational optimization on the one hand and game tree search on the other hand.We also discuss a key problem,namely,that the number of the branching factors of each turn in the game tree is huge.Then,we propose two algorithms,that is,enumeration by order and enumeration by recursion,for searching in one turn to solve the problem and deeply analyze their performance and applicability respectively.Then to reduce the redundant plans,two sets of optimization strategies are proposed: the simplification of unit moving range,and the simplification of search space.These two strategies can greatly improve the search efficiency without changing the effective search space,which is proved both theoretically and experimentally.Finally,the theory of dynamic shortest path tree(DSPT)is introduced into the calculation of dynamic moving range which is a time-consuming operation.A new method,that is,the improved algorithm of multi-node removed dynamic algorithm of shortest path tree(MRDA_SPT),is proposed.It is proved theoretically and experimentally that the efficiency of the new algorithm is better than that of other existing methods and it can significantly improve the efficiency of calculating the moving range.The research results of this thesis are as follows:(1)A common game model of TBW and its theory frame are proposed.The results show that TBW is essentially a kind of two-person zero-sum game with perfect information.Because that all the units can move in each round,and their moving sequences are sensitive,TBW generates a game tree with huge branch coefficient which is calculated theoretically in this thesis.By comparing with other classic board games,we find that the branch coefficient of TBW will be increased with the number of the units and the moving range of each unit.(2)The single round search algorithm of TBW is proposed,and the completeness proof and the performance comparison are finished.Single round search is the core procedure of the expansion of the game tree's root,whose efficiency is also a key indicator of the performance of the whole war chess game.According the units' order priority or behavior priority,the single round search algorithm is divided into:(1)enumeration by order;and(2)enumeration by recursion.The main difference between these two is the permutation method used: the former uses the dictionary sequence method,while the latter uses the recursive permutation method.Finally,we prove that both of these algorithms are optimal,and we analyze the difference between their efficiencies.An important factor(ops1)is the total time taken for the unit to expand until it achieves its reachable position.The factor,which is the total number of expansions that each unit makes in its reachable position,is set.The conclusion proposed is in terms of this factor: Enumeration by recursion is better than enumeration by order in all situations.(3)Two optimization strategies are put forward on the problem of high computational complexity and computational redundancy in the single round search:(1)simplifying the calculation of the unit's moving range;and(2)dividing and simplifying the search space.Through theoretical and experimental verification,it is proved that these two strategies can improve the search efficiency significantly without changing the effective search space.(4)The improved algorithm of multi-node removed dynamic algorithm of shortest path tree(MRDA_SPT)is proposed.In order to speed up the calculation of dynamic moving range which is a time-consuming operation,the theory of dynamic shortest path tree(DSPT)is introduced.It is proved theoretically and experimentally that the efficiency of the new algorithm is better than that of other existing methods.(5)DR_SPT algorithm,which is based on the improved algorithm of MRDA_SPT,is proposed.It can calculate unit's moving range dynamically and efficiently and its high efficiency is verified by experiments.Then the overall efficiency of TBW search is improved.