The Total Number Calculation of States of Chinese Chess Based on the Dynamic Programming of Computer Games

The space complexity of Chinese chess is a primary index for analyzing the complexity of Chinese chess, which is a counting problem of calculating the number of states of Chinese chess. Given the features of Chinese chess, this problem can be divided into several subproblems that can be solved by dynamic programming to obtain a precise solution of the total number of states of Chinese chess. Our results show that the total number of states of Chinese chess mentioned in previous papers is inaccurate and much higher than the actual number of states. Finally, the main idea of the counting method was summarized based on dynamic programming, and illustrations for some uses of the method were provided.