动态规划求解中国象棋状态总数

中国象棋空间复杂度是分析中国象棋博弈难度的重要指标，中国象棋空间复杂度分析是一个计数问题，即求解中国象棋状态总数。根据中国象棋棋子的着法特征，该问题可分解为若干子问题，利用动态规划分别解决这些子问题，能够求出中国象棋状态总数的精确解。实验得出中国象棋状态总数约为7.54×1039.88，过去许多文献描述的中国象棋状态总数是不准确的，远远高估了中国象棋状态总数。基于动态规划的计数方法也可以用于计算其他棋类的空间复杂度，也能够用于寻找空间复杂度较低的残局棋型，为构建中国象棋残局库提供依据。
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 (1039.88). Finally, the main idea of the counting method was summarized based on dynamic programming, and illustrations for some uses of the method were provided