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

第 14 卷第 1 期 智　能　系　统　学　报 Vol.14 No.1 2019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019 DOI: 10.11992/tis.201803008 网络出版地址: /kcms/detail/23.1538.TP1204.002.html 动态规划求解中国象棋状态总数 魏印福，李舟军 （北京航空航天大学 计算机学院智能信息处理研究所，北京 100191 ） 摘 要：中国象棋空间复杂度是分析中国象棋博弈难度的重要指标，中国象棋空间复杂度分析是一个计数问 题，即求解中国象棋状态总数。根据中国象棋棋子的着法特征，该问题可分解为若干子问题，利用动态规划分 别解决这些子问题，能够求出中国象棋状态总数的精确解。实验得出中国象棋状态总数约为7.54×1039.88 ，过去 许多文献描述的中国象棋状态总数是不准确的，远远高估了中国象棋状态总数。基于动态规划的计数方法也 可以用于计算其他棋类的空间复杂度，也能够用于寻找空间复杂度较低的残局棋型，为构建中国象棋残局库提 供依据。 关键词：计算机博弈；中国象棋；组合计数；空间复杂度；动态规划；计数算法；问题求解；状态空间 中图分类号：TP301.6 文献标志码：A 文章编号：1673−4785(2019)01−0108−07 中文引用格式：魏印福, 李舟军. 动态规划求解中国象棋状态总数[J]. 智能系统学报, 2019, 14(1): 108–114. 英文引用格式：WEI Yinfu, LI Zhoujun. A method for calculating the total number of states of Chinese chess on the basis of dy- namic programming[J]. CAAI transactions on intelligent systems, 2019, 14(1): 108–114. A method for calculating the total number of states of Chinese chess on the basis of dynamic programming WEI Yinfu，LI Zhoujun (The Institute of Intelligent Information Processing, School of Computer Science and Engineering, Beihang University, Beijing 100191, China) Abstract : 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