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

摘要：

中国象棋空间复杂度是分析中国象棋博弈难度的重要指标,中国象棋空间复杂度分析是一个计数问题,即求解中国象棋状态总数.根据中国象棋棋子的着法特征,该问题可分解为若干子问题,利用动态规划分别解决这些子问题,能够求出中国象棋状态总数的精确解.实验得出中国象棋状态总数约为7.54×1039 88,过去许多文献描述的中国象棋状态总数是不准确的,远远高估了中国象棋状态总数.基于动态规划的计数方法也可以用于计算其他棋类的空间复杂度,也能够用于寻找空间复杂度较低的残局棋型,为构建中国象棋残局库提供依据.

关键词：计算机博弈、中国象棋、组合计数、空间复杂度、动态规划、计数算法、问题求解、状态空间

所属期刊栏目：14

分类号：TP301.6(计算技术、计算机技术)

在线出版日期：2019-03-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共7页

页码：108-114