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

• 全文链接
• 请求原文

作   者：

魏印福;  李舟军; 

作者机构：

北京航空航天大学计算机学院智能信息处理研究所; 

关键词：

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

期刊名称：

智能系统学报

i s s n：

1673-4785

年卷期：

2019 年 01 期

页   码：

108-114

摘   要：

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