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

• 作者: 李舟军 魏印福
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: 计算机博弈 中国象棋 组合计数 空间复杂度 动态规划 计数算法 问题求解 状态空间
• 年，卷（期）: 2019,（1）
• 页码范围: 108-114
• 页数: 7页
• 分类号: TP301.6
• 字数: 5627字
• 语种: 中文
• DOI: 10.11992/tis.201803008

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	李舟军	北京航空航天大学计算机学院智能信息处理研究所	136	2221	23.0	43.0
2	魏印福	北京航空航天大学计算机学院智能信息处理研究所	1	1	1.0	1.0