War chess gaming has so far received insufficient attention but is a significant component of turn-based strategy games (TBS) and\nis studied in this paper. First, a common gamemodel is proposed through various existing war chess types. Based on the model, we\npropose a theory frame involving combinational optimization on the one hand and game tree search on the other hand. We also\ndiscuss a key problem, namely, that the number of the branching factors of each turn in the game tree is huge. Then, we propose\ntwo algorithms for searching in one turn to solve the problem: (1) enumeration by order; (2) enumeration by recursion. The main\ndifference between these two is the permutation method used: the former uses the dictionary sequence method, while the latter\nuses the recursive permutation method. Finally, we prove that both of these algorithms are optimal, and we analyze the difference\nbetween their efficiencies. An important factor is the total time taken for the unit to expand until it achieves its reachable position.\nThe factor, which is the total number of expansions that each unit makes in its reachable position, is set. The conclusion proposed\nis in terms of this factor: Enumeration by recursion is better than enumeration by order in all situations.
Loading....