第14卷第1期 智能系统学报 Vol.14 No.I 2019年1月 CAAI Transactions on Intelligent Systems Jan.2019 D0:10.11992/tis.201803008 网络出版地址：http:/kns.cnki.net/kcms/detail/23.1538.TP.20190104.1204.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 mentioned in previous papers is inaccurate and much higher than the actual number of states(10).Finally,the main idea of the counting method was summarized based on dynamic programming,and illustrations for some uses of the method were provided. Keywords:computer games;Chinese chess;combinatorial counting;space complexity;dynamic programming;count- ing method;problem solving;state space 中国象棋是一种广为流传的完全知识二人零 先进的博弈引擎，计算机博弈受到人们广泛关注。 和博弈游戏，形式上与国际象棋极为相似)，在 中国象棋博弈常提及的一个问题就是中国象 博弈技术上二者也有许多共通之处。2016年以 棋空间复杂度，即中国象棋状态总数。现有文献 来，谷歌相继推出AlphaGo、AlphaGo Zero、A- 仅给出中国象棋空间复杂度数值却没有提供计算 phaZero等博弈模型，不仅在围棋领域完胜人类 棋手，在国际象棋、日本将棋上也超越了之前最 方式，同时不同文献给出的数值存在较大差异。 长期以来，中国象棋状态总数这一计数问题无人 收稿日期：2018-03-08.网络出版日期：2019-01-07 通信作者：魏印福.E-mail:wei.yinfu(@qq.com. 问津，却又莫衷一是。本文利用中国象棋棋子着
DOI: 10.11992/tis.201803008 网络出版地址: http://kns.cnki.net/kcms/detail/23.1538.TP.20190104.1204.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 dynamic 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 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. Keywords: computer games; Chinese chess; combinatorial counting; space complexity; dynamic programming; counting method; problem solving; state space 中国象棋是一种广为流传的完全知识二人零 和博弈游戏，形式上与国际象棋极为相似[1-2] ，在 博弈技术上二者也有许多共通之处。2016 年以 来，谷歌相继推出 AlphaGo[3] 、AlphaGo Zero[4] 、AlphaZero[5]等博弈模型，不仅在围棋领域完胜人类 棋手，在国际象棋、日本将棋上也超越了之前最 先进的博弈引擎，计算机博弈受到人们广泛关注。 中国象棋博弈常提及的一个问题就是中国象 棋空间复杂度，即中国象棋状态总数。现有文献 仅给出中国象棋空间复杂度数值却没有提供计算 方式，同时不同文献给出的数值存在较大差异。 长期以来，中国象棋状态总数这一计数问题无人 问津，却又莫衷一是。本文利用中国象棋棋子着 收稿日期：2018−03−08. 网络出版日期：2019−01−07. 通信作者：魏印福. E-mail：wei.yinfu@qq.com. 第 14 卷第 1 期 智 能 系 统 学 报 Vol.14 No.1 2019 年 1 月 CAAI Transactions on Intelligent Systems Jan. 2019
第1期 魏印福，等：动态规划求解中国象棋状态总数 ·109· 法特点把求解中国象棋状态总数问题分解为若干 1.2走子规则 个子问题，通过动态规划方法分别求解各个子问 车、马、炮3类棋子可以出现在棋盘的任意 题，最终准确求出中国象棋状态总数，为以后描 位置：相不能过河，只能出现在己方空间中的7个 述中国象棋状态总数提供可靠依据。同时，这种 位置，为便于下文叙述，从左到右、从上到下对 计算中国象棋状态总数的方法除了可用于计算其 “相”的可去位置依次编号为06，如图2所示。 他棋类的空间复杂度，也可以用于构造中国象棋 0 棋盘局面哈希函数、构造中国象棋残局库-等 方面。 1问题描述 1.1中国象棋棋盘棋子 5 6 中国象棋棋盘9条竖线，10条横线，总计 图2相的可去位置及其编号 90个位置910。棋子分为红黑两色，每方16枚棋 Fig.2 Xiang's positions and number 子，棋子分为7类：车、马、炮、相、士、将、卒。开 士和将只能在九宫格中，士有5个可去位置， 始局面如图1所示。 将有9个可去位置。如图3，将九宫格中的9个位 军©厢⊕将⊕厢马军 置按照从左到右、从上到下的顺序依次编号为 0~8。 炮 卒 卒 、6 卒 卒 卒 图3九宫格内位置编号 电 Fig.3 Jiugong position and number 卒的着法分为过河和未过河两种情况，过河 车马相将注相马军 卒可以出现在敌方半棋盘空间中的任意一个位 置，未过河的卒只可能出现在己方最上方2行 图1中国象棋开始局面 5列共10个位置格点上，并且每列至多有一个卒。 Fig.1 The start state of Chinese Chess 1.3问题定义 中国象棋中，“将”和“帅”、“相”和“象”、“卒” 定义中国象棋状态总数问题首先需要定义子 和“兵”描述的是同一类棋子。为叙述方便，本文 问题：给定若干棋子，在满足中国象棋规则的情 对这3类棋子分别采用“将”、“相”、“卒”的叫法。 况下，把这些棋子摆放在棋盘上，有多少种可能 为便于用公式表示，本文使用英文缩写表示 的放置方式。这里给定的每类棋子个数必然都不 相关棋子，表1描述了棋子的缩写及其含义，本文 大于开局时每类棋子的个数。中国象棋状态总数 使用缩写表示棋子，例如使用K表示红将，K表 可以用式(1)表示，式中S即为中国象棋状态总 示黑将。 数，put表示从棋型到放置方法个数的映射，棋型 表1棋子英文表示及其缩写 指14种棋子组成的14维向量，每维数字表示每 Table 1 The chess representation and their abbreviation 类棋子的个数。 棋子 英语 缩写 S= put(ChessType) (1) 将 King K Chess①peE全离棋型 士 Advisor A 关于计算的中国象棋状态总数，需要说明 相 Bishop 3点： 卒 Pawn 1)本文讨论的是中国象棋可能出现的全部状 车 Rook R 态，在每步着法都完美的情况下，从初始状态出 Horse H 发可能无法到达全部状态。 炮 Cannon 2)本文统计的状态集合中每个状态双方“将
法特点把求解中国象棋状态总数问题分解为若干 个子问题，通过动态规划方法分别求解各个子问 题，最终准确求出中国象棋状态总数，为以后描 述中国象棋状态总数提供可靠依据。同时，这种 计算中国象棋状态总数的方法除了可用于计算其 他棋类的空间复杂度，也可以用于构造中国象棋 棋盘局面哈希函数[6] 、构造中国象棋残局库[7-8]等 方面。 1 问题描述 1.1 中国象棋棋盘棋子 中国象棋棋盘 9 条竖线， 10 条横线，总计 90 个位置[9-10]。棋子分为红黑两色，每方 16 枚棋 子，棋子分为 7 类：车、马、炮、相、士、将、卒。开 始局面如图 1 所示。 卒 卒 卒 卒 卒 卒 炮 炮 炮 炮 卒 卒 卒 卒 车 马 相 士 将 士 相 马 车 车 马 相 士 将 士 相 马 车 图 1 中国象棋开始局面 Fig. 1 The start state of Chinese Chess 中国象棋中，“将”和“帅”、“相”和“象”、“卒” 和“兵”描述的是同一类棋子。为叙述方便，本文 对这 3 类棋子分别采用“将”、“相”、“卒”的叫法。 为便于用公式表示，本文使用英文缩写表示 相关棋子，表 1 描述了棋子的缩写及其含义，本文 使用缩写表示棋子，例如使用 KR 表示红将，KB 表 示黑将。 表 1 棋子英文表示及其缩写 Table 1 The chess representation and their abbreviation 棋子 英语 缩写 将 King K 士 Advisor A 相 Bishop B 卒 Pawn P 车 Rook R 马 Horse H 炮 Cannon C 1.2 走子规则 车、马、炮 3 类棋子可以出现在棋盘的任意 位置；相不能过河，只能出现在己方空间中的 7 个 位置，为便于下文叙述，从左到右、从上到下对 “相”的可去位置依次编号为 0~6，如图 2 所示。 0 1 2 3 4 5 6 图 2 相的可去位置及其编号 Fig. 2 Xiang’s positions and number 士和将只能在九宫格中，士有 5 个可去位置， 将有 9 个可去位置。如图 3，将九宫格中的 9 个位 置按照从左到右、从上到下的顺序依次编号为 0～8。 1 2 3 4 5 6 7 8 0 图 3 九宫格内位置编号 Fig. 3 Jiugong position and number 卒的着法分为过河和未过河两种情况，过河 卒可以出现在敌方半棋盘空间中的任意一个位 置，未过河的卒只可能出现在己方最上方 2 行 5 列共 10 个位置格点上，并且每列至多有一个卒。 1.3 问题定义 定义中国象棋状态总数问题首先需要定义子 问题：给定若干棋子，在满足中国象棋规则的情 况下，把这些棋子摆放在棋盘上，有多少种可能 的放置方式。这里给定的每类棋子个数必然都不 大于开局时每类棋子的个数。中国象棋状态总数 可以用式 (1) 表示，式中 S 即为中国象棋状态总 数，put 表示从棋型到放置方法个数的映射，棋型 指 14 种棋子组成的 14 维向量，每维数字表示每 类棋子的个数。 S = ∑ ChessType∈全部棋型 put( ChessType) (1) 关于计算的中国象棋状态总数，需要说明 3 点： 1) 本文讨论的是中国象棋可能出现的全部状 态，在每步着法都完美的情况下，从初始状态出 发可能无法到达全部状态。 2) 本文统计的状态集合中每个状态双方“将” 第 1 期 魏印福，等：动态规划求解中国象棋状态总数 ·109·
·110· 智能系统学报 第14卷 都是存在的，即本文计算的全部局面都是游戏尚 在倒数第2位考虑。将的位置会影响士相的摆 未结束的局面。 放，相的位置会影响未过河卒子的摆放。考虑 3)本文讨论的状态包括“将帅见面”的情况。 将、土、相、卒这4类棋子之间的互相影响关系及 在中国象棋规则中，促成“将帅见面”局面的一方 着法特点，拟定摆放顺序为：将、士、相、卒。 为输。 综上，根据先考虑受限制多的棋子再考虑受 本节对中国象棋棋子、着法进行了简要介 限制少的棋子的思路，最终摆放顺序为：将、士、 绍，对棋子、棋盘进行了一些符号约定，对问题给 相、卒、车马炮。 出了形式化描述并明确了中国象棋状态总数所包 利用分步乘法原理依次处理棋子的摆放，这 括的局面。 个过程可以对问题进行层层分解，把问题划分为 若干个有依赖关系的子问题。先摆放“将”，“将” 2问题求解 摆放完成之后，后面要摆放的“士”和“相”会受到 2.1摆放次序 “将”的影响，所以把“将”的位置作为输入参数向 计数问题的两个基本方法是分类加法和分步 后续求解模块传递。摆放“士”的时候可以根据已 乘法2。当使用分步乘法时，合理的步骤可以 摆放“将”的位置，来决定“士”可以摆放的位置有 减少分类个数，从而简便地解决计数问题。 哪些。 给定若干棋子之后计算摆放方式的个数时， 整体求解思路为：把已摆放的棋子对未摆放 摆放次序至关重要。下面举例描述摆放次序的重 的棋子的影响作为参数传递给后续子问题，摆放 要性。给定2个红车、2个红相共4枚棋子，计算 棋子时参考已摆放棋子的位置来决定当前可行的 摆放方式个数。车的位置比较随意，可以摆放在 摆放方法。 棋盘上90个格点的任意位置，相的位置限制较 本节详细描述把中国象棋摆法总数这个问题 多，只能摆放在如图2所示的7个位置上。如果 划分成将、士、相、卒、“车马炮”5个子问题，每个 先考虑相再考虑车，可知有C号×C种摆放方式； 子问题都有明确的输入，每个子问题的输出都是 而如果先考虑车再考虑相就需要分3类情况进行 摆法个数。子问题之间逐层调用，最终能够求得 讨论： 中国象棋状态总数。子问题的定义及其输入的形 1)当车占用0个相位时，车有83个位置可 式化是整个求解过程中较为关键的部分。 选，相有7个位置可选，这种情况有C×C?种 2.2.1将 局面。 先摆放好双方的“将”，再考虑子问题：在“将” 2)当车占用1个相位时，第1个车有7种相 位置确定的情况下，“士相卒车马炮”总共有多少 位可选，第2个车有83个位置可选，2个相有6个 种摆法。记此子问题为getShi(Ke,K),该子问题 位置可选，这种情况有C;×C×C名种局面。 输入KKg为红黑双方“将”的位置。 3)当车占用2个相位时，摆放方式有C× 对“将”的每一种摆放方式，将其余棋子的摆 C种。 法个数累加起来即为中国象棋状态总数。伪代码 以上3类情况摆法个数之和与“先摆放相，再 如下： 摆放车”所得结果相同，但显然第一种方法需要较 函数名称getJiang 少的分类讨论。由此例可以看出，计算状态个数 输入无： 时合理规划摆放棋子的顺序能够极大简化问题。 输出摆法种数s。 计算中国象棋状态总数时，需按照一定次序 1)s=0: 放置棋子，核心思想是“先难后易”，即先放置限 2)对于红将的每个位置K∈[0,9)： 制较多、活动范围窄的棋子，然后再放置行动灵 3)对于黑将的每个位置Kae[0,9)； 活、位置自由的棋子。 4)s+=getShi(Kg,Ka) 在以上代码中，KR表示红方将的位置，KB表 2.2问题分解 车、马、炮可以到达棋盘上的任何一个位置， 示黑方将的位置，累加双将位置确定之后“士相卒 放置最为自由，只需要知道棋盘上有多少个空白 车马炮”的摆法个数即得到中国象棋状态总数，如 格点，即可通过排列组合计算出摆法总数，因此 式(2)： 最后考虑这3种棋子的摆放。卒过河后可以到达 S= getShi(Kg,KB) (2) 敌方阵地的每一个位置，自由度占半个棋盘，放 Kx=0Ka=0
都是存在的，即本文计算的全部局面都是游戏尚 未结束的局面。 3) 本文讨论的状态包括“将帅见面”的情况。 在中国象棋规则中，促成“将帅见面”局面的一方 为输。 本节对中国象棋棋子、着法进行了简要介 绍，对棋子、棋盘进行了一些符号约定，对问题给 出了形式化描述并明确了中国象棋状态总数所包 括的局面。 2 问题求解 2.1 摆放次序 计数问题的两个基本方法是分类加法和分步 乘法[11-12]。当使用分步乘法时，合理的步骤可以 减少分类个数[13-14] ，从而简便地解决计数问题。 C 2 7 ×C 2 88 给定若干棋子之后计算摆放方式的个数时， 摆放次序至关重要。下面举例描述摆放次序的重 要性。给定 2 个红车、2 个红相共 4 枚棋子，计算 摆放方式个数。车的位置比较随意，可以摆放在 棋盘上 90 个格点的任意位置，相的位置限制较 多，只能摆放在如图 2 所示的 7 个位置上。如果 先考虑相再考虑车，可知有 种摆放方式； 而如果先考虑车再考虑相就需要分 3 类情况进行 讨论： C 2 83 ×C 2 7 1) 当车占用 0 个相位时，车有 83 个位置可 选，相有 7 个位置可选，这种情况有 种 局面。 C 1 7 ×C 1 83 ×C 2 6 2) 当车占用 1 个相位时，第 1 个车有 7 种相 位可选，第 2 个车有 83 个位置可选，2 个相有 6 个 位置可选，这种情况有 种局面。 C 2 7× C 2 5 3) 当车占用 2 个相位时，摆放方式有 种。 以上 3 类情况摆法个数之和与“先摆放相，再 摆放车”所得结果相同，但显然第一种方法需要较 少的分类讨论。由此例可以看出，计算状态个数 时合理规划摆放棋子的顺序能够极大简化问题。 计算中国象棋状态总数时，需按照一定次序 放置棋子，核心思想是“先难后易”，即先放置限 制较多、活动范围窄的棋子，然后再放置行动灵 活、位置自由的棋子。 2.2 问题分解 车、马、炮可以到达棋盘上的任何一个位置， 放置最为自由，只需要知道棋盘上有多少个空白 格点，即可通过排列组合计算出摆法总数，因此 最后考虑这 3 种棋子的摆放。卒过河后可以到达 敌方阵地的每一个位置，自由度占半个棋盘，放 在倒数第 2 位考虑。将的位置会影响士相的摆 放，相的位置会影响未过河卒子的摆放。考虑 将、士、相、卒这 4 类棋子之间的互相影响关系及 着法特点，拟定摆放顺序为：将、士、相、卒。 综上，根据先考虑受限制多的棋子再考虑受 限制少的棋子的思路，最终摆放顺序为：将、士、 相、卒、车马炮。 利用分步乘法原理依次处理棋子的摆放，这 个过程可以对问题进行层层分解，把问题划分为 若干个有依赖关系的子问题。先摆放“将”，“将” 摆放完成之后，后面要摆放的“士”和“相”会受到 “将”的影响，所以把“将”的位置作为输入参数向 后续求解模块传递。摆放“士”的时候可以根据已 摆放“将”的位置，来决定“士”可以摆放的位置有 哪些。 整体求解思路为：把已摆放的棋子对未摆放 的棋子的影响作为参数传递给后续子问题，摆放 棋子时参考已摆放棋子的位置来决定当前可行的 摆放方法。 本节详细描述把中国象棋摆法总数这个问题 划分成将、士、相、卒、“车马炮”5 个子问题，每个 子问题都有明确的输入，每个子问题的输出都是 摆法个数。子问题之间逐层调用，最终能够求得 中国象棋状态总数。子问题的定义及其输入的形 式化是整个求解过程中较为关键的部分。 2.2.1 将 先摆放好双方的“将”，再考虑子问题：在“将” 位置确定的情况下，“士相卒车马炮”总共有多少 种摆法。记此子问题为 getShi(KR, KB)，该子问题 输入 KR, KB 为红黑双方“将”的位置。 对“将”的每一种摆放方式，将其余棋子的摆 法个数累加起来即为中国象棋状态总数。伪代码 如下： 函数名称 getJiang 输入 无； 输出 摆法种数 s。 1) s = 0； 2) 对于红将的每个位置 KR∈[0, 9)； 3) 对于黑将的每个位置 KB∈[0, 9)； 4) s+=getShi(KR, KB) 在以上代码中，KR 表示红方将的位置，KB 表 示黑方将的位置，累加双将位置确定之后“士相卒 车马炮”的摆法个数即得到中国象棋状态总数，如 式 (2)： S = ∑8 KR=0 ∑8 KB=0 getShi(KR,KB) (2) ·110· 智 能 系 统 学 报 第 14 卷
第1期 魏印福，等：动态规划求解中国象棋状态总数 ·111· 2.2.2士 法个数便随之确定。求解子问题“相卒车马炮”需 在221中，在给定“将”位置的情况下，需要 要先考虑相的摆法。根据“将”是否已经放在如 计算“士相卒车马炮”有多少种摆法。当“将的位 图3的1号位置，可以确定相的可选位置的个数。 置确定后，“土”的可选位置随之确定。如果“将” 对于“相”的每一种摆法，累加“卒车马炮”的 在图3中的0、2、4、6、8号位置，则“将”占用一个 摆法个数，即得“相卒车马炮”的摆法总数。记子 士位，“士”有4个位置可选；如果“将”在1、3、5、问题“卒车马炮”的摆法个数为gtZu(BP,BPB, 7、9号位置，“将没有占领士位，士有5个位置可选。 Spaceg,Spacea)),BPR、BPs分别表示红相、黑相占 对于“士”的每一种摆法，累加“相卒车马炮” 用卒位的个数，Spaceg、Spaces分别表示红黑双方 的摆法个数，即可得到在“将”位置确定情况下“士 空白格点数。伪代码如下： 相卒车马炮”的摆法个数。记子问题“相卒车马 函数名称getXiang 炮”的摆法个数为getXiang(KRK,Spaceg,Spacea), 输入红将位置KR;黑将位置KB;红方空白 其中KR、KB输人表示红黑双方将的位置，SpaceR 格点数Spaceg;黑方空白格点数Spaces; Spaces表示双方空白格点数。getShi函数输入参 输出“相卒车马炮”的摆法总数s。 数为红将位置和黑将位置，输出“士相卒车马炮” 1)定义红相可去位置个数：若K.不在相位 摆法总数。伪代码如下： 上N=7否则N=6; 函数名称getShi 2)定义黑相可去位置个数：若Kg不在相位 输入红将位置K;黑将位置K; 上N=7否则Ng=6; 输出“士相卒车马炮”的摆法总数s。 3)s=0; 1)s=0; 4)对于红相个数的可取值BR∈{0,1,2； 2)定义红士可去位置个数：若KR不在士位 5)对于黑相个数的可取值BB∈{0,1,2；： 上N=5,否则N=4; 6对于红相占用红卒位置的个数BPR∈{0,1,2； 3)定义黑土可去位置个数：若Kg不在土位 7)对于黑相占用黑卒位置的个数BPB∈{0,1,2： 上Ng=5,否则N=4; 8)相的放法种数placeXiang=C"C"C-n 4)对于红士个数的可取值AR∈{0,1,2： C 5)对于黑士个数的可取值AB∈{0,1,2： 9)s+=placeXiangxgetZu(BP&,BP8,Spaceg-Bg, 6)红方空白格点数Space=45-1-AR: Spaceg-Ba). 7黑方空白格点数Space=45-1-A: 2.2.4卒 8)s+=CMCN.getXiang(Kg,KB.Spaceg,Spacea) 经过以上步骤，“将士相”摆放完成，“卒车马 在上述伪代码中，摆放好“士”之后，需要乘以 炮”子问题的输入包括4个变量：红相占用卒位个 “相卒车马炮”的摆法个数，“相卒车马炮”摆法个 数（可取值0、1、2）、黑相占用卒位个数（可取值 数通过getXiang函数实现。考虑已摆放的“将”、 0、1、2)、红方空白格点数、黑方空白格点数。 “士”对“相卒车马炮”的影响，可以发现后续棋子 “卒”需要分为2类进行讨论：过河卒和未过 的摆放只依赖于红将位置、黑将位置、红方空白 河卒。各方过河卒个数加上未过河卒的个数不超 格点数、黑方空白格点数4个变量。 过5，需考虑红方、黑方各自的过河卒、未过河卒 2.2.3相 共4类棋子的摆放。 经过以上两步，“将”和“士”的位置确定了，这 为便于叙述，下面进行一些符号约定： 两种棋子对后续棋子的“影响因素”包括： I)Spaceg表示黑方棋盘空白格点数，Spaceg 1)“将”可能会占用相位，影响“相”的可摆放 表示红方棋盘空白格点数； 位置的个数； 2)PR表示红方未过河卒的个数，PB表示黑方 2)红方和黑方各自的空白格点数，影响“卒车 未过河卒的个数； 马炮”的摆放。 3)P表示红方过河卒的个数，P。表示黑方过 问题转化为给定“将”的位置和红黑双方空白 河卒的个数。 格点个数之后，“相卒车马炮”有多少种摆法。 下面以红方为例，讨论过河卒和未过河卒的 “相卒车马炮”的摆法只跟4个变量有关：红 摆放。 将位置、黑将位置、红方空白格点数、黑方空白格 对于过河卒，有C种摆法，其中 点数。这4个变量一旦确定，“相卒车马炮”的摆 Spaceg-Pg表示黑方空白格点数，从这些空白格点
2.2.2 士 在 2.2.1 中，在给定“将”位置的情况下，需要 计算“士相卒车马炮”有多少种摆法。当“将”的位 置确定后，“士”的可选位置随之确定。如果“将” 在图 3 中的 0、2、4、6、8 号位置，则“将”占用一个 士位，“士”有 4 个位置可选；如果“将”在 1、3、5、 7、9 号位置，“将”没有占领士位，士有 5 个位置可选。 对于“士”的每一种摆法，累加“相卒车马炮” 的摆法个数，即可得到在“将”位置确定情况下“士 相卒车马炮”的摆法个数。记子问题“相卒车马 炮”的摆法个数为 getXiang(KR, KB, SpaceR, SpaceB)， 其中 KR、KB 输入表示红黑双方将的位置，SpaceR、 SpaceB 表示双方空白格点数。getShi 函数输入参 数为红将位置和黑将位置，输出“士相卒车马炮” 摆法总数。伪代码如下： 函数名称 getShi 输入 红将位置 KR；黑将位置 KB； 输出 “士相卒车马炮”的摆法总数 s。 1) s=0； 2) 定义红士可去位置个数：若 KR 不在士位 上 NR=5，否则 NR=4； 3) 定义黑士可去位置个数：若 KB 不在士位 上 NB=5，否则 NB=4； 4) 对于红士个数的可取值 AR∈{0, 1, 2}； 5) 对于黑士个数的可取值 AB∈{0, 1, 2}； 6) 红方空白格点数 SpaceR=45−1−AR； 7) 黑方空白格点数 SpaceB=45−1−AB； C AR NR C AB NB 8) s+= getXiang(KR, KB, SpaceR, SpaceB) 在上述伪代码中，摆放好“士”之后，需要乘以 “相卒车马炮”的摆法个数，“相卒车马炮”摆法个 数通过 getXiang 函数实现。考虑已摆放的“将”、 “士”对“相卒车马炮”的影响，可以发现后续棋子 的摆放只依赖于红将位置、黑将位置、红方空白 格点数、黑方空白格点数 4 个变量。 2.2.3 相 经过以上两步，“将”和“士”的位置确定了，这 两种棋子对后续棋子的“影响因素”包括： 1) “将”可能会占用相位，影响“相”的可摆放 位置的个数； 2) 红方和黑方各自的空白格点数，影响“卒车 马炮”的摆放。 问题转化为给定“将”的位置和红黑双方空白 格点个数之后，“相卒车马炮”有多少种摆法。 “相卒车马炮”的摆法只跟 4 个变量有关：红 将位置、黑将位置、红方空白格点数、黑方空白格 点数。这 4 个变量一旦确定，“相卒车马炮”的摆 法个数便随之确定。求解子问题“相卒车马炮”需 要先考虑相的摆法。根据“将”是否已经放在如 图 3 的 1 号位置，可以确定相的可选位置的个数。 对于“相”的每一种摆法，累加“卒车马炮”的 摆法个数，即得“相卒车马炮”的摆法总数。记子 问题“卒车马炮”的摆法个数为 getZu(BPR, BPB, SpaceR, SpaceB)，BPR、BPB 分别表示红相、黑相占 用卒位的个数，SpaceR、SpaceB 分别表示红黑双方 空白格点数。伪代码如下： 函数名称 getXiang 输入 红将位置 KR；黑将位置 KB；红方空白 格点数 SpaceR；黑方空白格点数 SpaceB； 输出 “相卒车马炮”的摆法总数 s。 1) 定义红相可去位置个数：若 KR 不在相位 上 NR=7 否则 NR=6； 2) 定义黑相可去位置个数：若 KB 不在相位 上 NB=7 否则 NB=6； 3) s=0； 4) 对于红相个数的可取值 BR∈{0, 1, 2}； 5) 对于黑相个数的可取值 BB∈{0, 1, 2}； 6) 对于红相占用红卒位置的个数 BPR∈{0, 1, 2}； 7) 对于黑相占用黑卒位置的个数 BPB∈{0, 1, 2}； placeXiang = C BPR 2 C BPB 2 C BR−BPR NR−2 C BB−BPB NB−2 8) 相的放法种数 ； 9) s+=placeXiang×getZu(BPR, BPB, SpaceR−BR, SpaceB−BB)。 2.2.4 卒 经过以上步骤，“将士相”摆放完成，“卒车马 炮”子问题的输入包括 4 个变量：红相占用卒位个 数 (可取值 0、1、2)、黑相占用卒位个数 (可取值 0、1、2)、红方空白格点数、黑方空白格点数。 “卒”需要分为 2 类进行讨论：过河卒和未过 河卒。各方过河卒个数加上未过河卒的个数不超 过 5，需考虑红方、黑方各自的过河卒、未过河卒 共 4 类棋子的摆放。 为便于叙述，下面进行一些符号约定： 1) SpaceB 表示黑方棋盘空白格点数，SpaceR 表示红方棋盘空白格点数； 2) PR 表示红方未过河卒的个数，PB 表示黑方 未过河卒的个数； P ′ R P ′ 3) 表示红方过河卒的个数， B 表示黑方过 河卒的个数。 下面以红方为例，讨论过河卒和未过河卒的 摆放。 C P ′ R 对于过河卒，有 SpaceB−PB 种摆法，其 中 SpaceB−PB 表示黑方空白格点数，从这些空白格点 第 1 期 魏印福，等：动态规划求解中国象棋状态总数 ·111·
·112· 智能系统学报 第14卷 选择P个格点分配给P个红方过河卒。 双方空白格点数4个变量； 对于红方未过河卒，需要根据相占用的卒位 4)卒的摆放，输入为红黑双方空白格点数、 个数和未过河卒的个数两个变量求出有多少种放 红黑双方相占用卒位的个数； 置方法，这个问题可以明确定义为：在2行5列 5)车马炮的摆放，输入为整个棋盘上空白格 共10个位置上，放置P个卒子，其中BP个相占 点数。 用了卒位，每列至多放置1个卒子，在这些约束下 求P个卒子的摆法总数。这个子问题解法如下： 将 假设有1个卒子放在了被占用的列上，这i个卒子 只有唯一位置。而剩下的Pi个卒子都有2个空 黑将、红将的位置 白格点可选，共计2种情况。未过河卒放法种 数如式(3)所示： 士 min(BP.P 2-C (3) 黑将、红将的位置 黑红双方空白格点数 对于卒子的每一种摆放方式，累加“车马炮” t 的摆放方式即得“将士相”确定后，“卒车马炮”的 相 摆放方式。 2.2.5车马炮 黑相、红相占用卒位的个数 黑红双方空白格点数 “车马炮”的摆放仅与一个变量有关，即整个 棋盘上空白格点数。枚举红黑双方车、马、炮的 卒 个数，使用分步乘法计算有多少种摆法，如式(4)： 22222∑vmapao(,HHCC月 2 整个棋盘上空白格点数 (4) 车马炮 jvmapao(RB,RR,HB,HR,CB,CR)函数可以使用 分步乘法实现。例如，摆完“将相士卒”之后剩余 图4各个部分的输入参数 80个空白格点，在这些空白位置上摆放2个红 Fig.4 The input of every block 车、2个红马、2个黑炮。根据分步乘法很容易得 每个子问题都有一条重要性质：输入到输出 出摆法总数为C×C×C6。jvmapao函数实现如 为单射。根据这条性质可以为每个子问题建立一 以下伪代码所示： 个映射表，保存函数输入和输出的映射关系。当 函数名称jvmapao 求解某个子问题时，先查询映射表，如果存在答 输入空白格点数Space;红黑双方的车马炮 案则不必再调用后续子问题进行求解，直接查表 的个数RB、RR、HB、HR、CR、CB 得出：如果不存在，则求解该问题并把最终结果 输出3，表示“车马炮”的摆法总数。 存储到映射表中，以备下次查询。这种方法相当 1)5=CSpoe X CSpce 于为每个子问题加一层缓存，若未命中缓存则进 2)Space=Space-Rg-Re; 行求解并使用求解结果更新缓存，若命中缓存则 3)s=sXCe×Ce-mi 直接返回缓存的答案。这种动态规划技巧又叫备 4)Space=Space-Hg-Hg: 忘录方法s,是动态规划的一种变形。 5)s=sxC0×Cae-c,0 各个子问题之间具有单向依赖性，动态规划 2.3动态规划方法加速求解 方法避免了子问题之间层层调用和重复调用。 利用2.2节中各个子问题的性质，可以对上 3实验结果与验证 述计数方法进行优化。各个部分输入参数如图4。 图4描述了中国象棋状态总数求解的5个子 实验得出中国象棋状态总数具体数值为 问题： 7547040878332418571694532043654081760159 1)将的摆放； 用科学计数法表示为7.54×109.器。现有文献中提 2)士的摆放，输入为红将、黑将的位置： 到的中国象棋状态总数如表2所示，这些结果都 3)相的摆放，输入为红将、黑将的位置、红黑 远远高估了中国象棋空间复杂度
P ′ R P ′ 选择 个格点分配给 R 个红方过河卒。 对于红方未过河卒，需要根据相占用的卒位 个数和未过河卒的个数两个变量求出有多少种放 置方法，这个问题可以明确定义为：在 2 行 5 列 共 10 个位置上，放置 P 个卒子，其中 BP 个相占 用了卒位，每列至多放置 1 个卒子，在这些约束下 求 P 个卒子的摆法总数。这个子问题解法如下： 假设有 i 个卒子放在了被占用的列上，这 i 个卒子 只有唯一位置。而剩下的 P-i 个卒子都有 2 个空 白格点可选，共计 2 P-i 种情况。未过河卒放法种 数如式 (3) 所示： min∑ (BP,P) i=0 2 P−iC P−i 5−BP (3) 对于卒子的每一种摆放方式，累加“车马炮” 的摆放方式即得“将士相”确定后，“卒车马炮”的 摆放方式。 2.2.5 车马炮 “车马炮”的摆放仅与一个变量有关，即整个 棋盘上空白格点数。枚举红黑双方车、马、炮的 个数，使用分步乘法计算有多少种摆法，如式 (4)： ∑2 RB=0 ∑2 RR=0 ∑2 HB=0 ∑2 HR=0 ∑2 CB=0 ∑2 CR=0 jvmapao(RB,RR,HB,HR,CB,CR) (4) C 2 80 ×C 2 78 ×C 2 76 jvmapao(RB, RR, HB, HR, CB, CR) 函数可以使用 分步乘法实现。例如，摆完“将相士卒”之后剩余 80 个空白格点，在这些空白位置上摆放 2 个红 车、2 个红马、2 个黑炮。根据分步乘法很容易得 出摆法总数为 。jvmapao 函数实现如 以下伪代码所示： 函数名称 jvmapao 输入 空白格点数 Space；红黑双方的车马炮 的个数 RB、RR、HB、HR、CR、CB； 输出 s，表示“车马炮”的摆法总数。 s = C RB Space ×C RR Space−RB 1) ； 2) Space=Space−RB−RR； s = s×C HB Space ×C HR Space−HB 3) ； 4) Space=Space−HB−HR； s = s×C CB Space ×C CR Space−CB 5) 。 2.3 动态规划方法加速求解 利用 2.2 节中各个子问题的性质，可以对上 述计数方法进行优化。各个部分输入参数如图 4。 图 4 描述了中国象棋状态总数求解的 5 个子 问题： 1) 将的摆放； 2) 士的摆放，输入为红将、黑将的位置； 3) 相的摆放，输入为红将、黑将的位置、红黑 双方空白格点数 4 个变量； 4) 卒的摆放，输入为红黑双方空白格点数、 红黑双方相占用卒位的个数； 5) 车马炮的摆放，输入为整个棋盘上空白格 点数。 将 士 相 车马炮 黑将、红将的位置 黑将、红将的位置 黑红双方空白格点数 卒 黑相、红相占用卒位的个数 黑红双方空白格点数 整个棋盘上空白格点数 图 4 各个部分的输入参数 Fig. 4 The input of every block 每个子问题都有一条重要性质：输入到输出 为单射。根据这条性质可以为每个子问题建立一 个映射表，保存函数输入和输出的映射关系。当 求解某个子问题时，先查询映射表，如果存在答 案则不必再调用后续子问题进行求解，直接查表 得出；如果不存在，则求解该问题并把最终结果 存储到映射表中，以备下次查询。这种方法相当 于为每个子问题加一层缓存，若未命中缓存则进 行求解并使用求解结果更新缓存，若命中缓存则 直接返回缓存的答案。这种动态规划技巧又叫备 忘录方法[15-18] ，是动态规划的一种变形。 各个子问题之间具有单向依赖性，动态规划 方法避免了子问题之间层层调用和重复调用。 3 实验结果与验证 实验得出中国象棋状态总数具体数值为 7 547 040 878 332 418 571 694 532 043 654 081 760 159， 用科学计数法表示为 7.54×1039.88。现有文献中提 到的中国象棋状态总数如表 2 所示，这些结果都 远远高估了中国象棋空间复杂度。 ·112· 智 能 系 统 学 报 第 14 卷
第1期 魏印福，等：动态规划求解中国象棋状态总数 ·113· 表2参考文献中中国象棋空间复杂度 多的棋子，后摆放约束较少的棋子，把影响后续 Table 2 The Space Complexity of the Reference Document 摆放的因素作为参数向后传递：2)在求解每个子 论文 作者 时间数值 问题时，动态规划可以减少重复计算。 Searching for Solutions A1lisV1994年1048 本文提出的计数方法可能的应用方向包括： 电脑象棋的设计与实现20 涂志坚2004年100 1)计算其他博弈游戏状态总数：2)用于构造中国 中国象棋计算机博弈关键技术 象棋棋盘局面哈希函数，建立棋盘局面和数字之 分析P四 徐心和2006年102 间的一一映射；3)寻找可暴力枚举全部状态的棋 中国象棋与国际象棋比较分析用王晓鹏2007年102 型，为构建中国象棋残局库提供依据。 如果用定长编码来描述中国象棋的一个状 参考文献： 态，只需对中国象棋状态总数取以2为底的对数， []王晓鹏，王骄，徐心和，等.中国象棋与国际象棋比较分 得到结果132.47bit,这就是描述一个棋盘状态最 析J.重庆工学院学报，2007,21(1)：71-76 少需要的bit数。若将中国象棋全部状态使用定 WANG Xiaopeng,WANG Jiao,XU Xinhe,et al.A com- 长编码存储下来，需要将状态占用bit数乘以状态 parative analysis between chess and Chinese chess[J]. 个数，结果为1.14×109TB。 Journal of Chongqing institute of technology,2007,21(1): 为佐证本文结论，使用另一种粗略方法估计 71-76 中国象棋状态总数。下面给出一种简略的计算中 [2]徐心和，郑新颖.棋牌游戏与事件对策[).控制与决策， 国象棋状态总数的方法，这种方法给出的是中国 2007,22(7):787-790 象棋状态总数的上界。 XU Xinhe,ZHENG Xinying.Card and board games and 首先，只考虑红方的棋子摆放，记为S。中国 event game theory[J].Control and decision,2007,22(7): 象棋包括红方和白方两方，所以全部状态总数为 787-790 s2。下面介绍s的计算方法。 [3]SILVER D.HUANG A.MADDISON C J,et al.Master- 将和士摆放方法为jiangShi=C;×3+C×2+Cg0 ing the game of Go with deep neural networks and tree 将士在九宫中，C。表示选定3个位置，乘以3表 search[J].Nature,2016,5297587):484-489 [4]SILVER D.SCHRITTWIESER J.SIMONYAN K.et al. 示为“将”分配3个位置中的1个位置。 Mastering the game of Go without human knowledge[J]. 相的摆放方法数为：xiang=C号+C;+C9。卒 Nature,2017,550(7676):354-359. 的摆放需要考虑过河卒和未过河卒，过河卒有 [5]SILVER D,HUBERT T,SCHRITTWIESER J,et al.Mas- 45个格点空间，未过河卒有5列，每列有2种摆 tering chess and shogi by self-play with a general rein- 放方式。故卒的摆放方式有zu=∑∑C6×C×2 forcement learning algorithm[J].arXiv:1712.01815,2017 种。车的摆放方式：jⅳ=C+C。+C。马和炮的 [6]高强，郭琛.哈希技术在中国象棋机器博弈系统中的应 摆法与车完全相同。 用研究.科学技术与工程，2008,8(17八：4869-4872 在这种简略计算方法中，忽略了棋子之间的 GAO Qiang,GUO Chen.Technology of hashing and its 互相影响，所以应该采用分步乘法的方式计算s, application research in hybrid game tree search engine of 只考虑红方共有s=jiangShi×>xiang×zuxjv3种摆法。 Chinese chess[J].Science technology and engineering, 中国象棋状态总数即为52，约为1028。可见 2008,8(17):4869-4872. 粗略估计结果与本文计算结果更为接近，即便是 [7]王骄，徐长明，徐心和.中国象棋计算机博弈残局处理系 粗略估计，现有文献中的数据都是极不准确的。 统[C]/2006中国机器博弈学术研讨会.北京，中国， 2006 4结论和展望 WANG Jiao,XU Changming,XU Xinhe.Endgame sys- tem in computer Chinese chess[C]//2006 Chinese Com- 基于动态规划的方法求解中国象棋状态总数 puter Games Seminar.Beijing,China,2006. 充分挖掘了中国象棋棋子着法规律，快速而准确 [8]吴丽贤，和力.一种中国象棋残局棋谱自动生成算法 地求出了中国象棋状态总数，为描述中国象棋空 云南民族大学学报（自然科学版），2010.19(6：435-438. 间复杂度提供了充分依据，实验证明现有文献提 WU Lixian,HE Li.An automatic generation algorithm for 供的数据远远不够准确。 the manual of Chinese chess endgames[J].Journal of Yun- 该计数方法创新点包括两方面：1)先难后 nan university of nationalities (natural sciences edition), 易，把问题分解为若干个子问题，先摆放约束较 2010,196):435-438
表 2 参考文献中中国象棋空间复杂度 Table 2 The Space Complexity of the Reference Document 论文 作者 时间 数值 Searching for Solutions[19] Allis V 1994 年 1048 电脑象棋的设计与实现[20] 涂志坚 2004 年 1060 中国象棋计算机博弈关键技术 分析[21] 徐心和 2006 年 1052 中国象棋与国际象棋比较分析[1] 王晓鹏 2007 年 1052 如果用定长编码来描述中国象棋的一个状 态，只需对中国象棋状态总数取以 2 为底的对数， 得到结果 132.47 bit，这就是描述一个棋盘状态最 少需要的 bit 数。若将中国象棋全部状态使用定 长编码存储下来，需要将状态占用 bit 数乘以状态 个数，结果为 1.14×1029 TB。 为佐证本文结论，使用另一种粗略方法估计 中国象棋状态总数。下面给出一种简略的计算中 国象棋状态总数的方法，这种方法给出的是中国 象棋状态总数的上界。 首先，只考虑红方的棋子摆放，记为 s。中国 象棋包括红方和白方两方，所以全部状态总数为 s 2。下面介绍 s 的计算方法。 jiangShi = C 3 9 ×3+C 2 9 ×2+C 1 9 C 3 9 将和士摆放方法为 。 将士在九宫中， 表示选定 3 个位置，乘以 3 表 示为“将”分配 3 个位置中的 1 个位置。 xiang = C 2 7 +C 1 7 +C 0 7 zu= ∑5 i=0 ∑5−i j=0C i 45 ×C j 5 ×2 j jv = C 2 90 +C 1 90 +C 0 90 相的摆放方法数为： 。卒 的摆放需要考虑过河卒和未过河卒，过河卒有 45 个格点空间，未过河卒有 5 列，每列有 2 种摆 放方式。故卒的摆放方式有 种。车的摆放方式： 。马和炮的 摆法与车完全相同。 在这种简略计算方法中，忽略了棋子之间的 互相影响，所以应该采用分步乘法的方式计算 s， 只考虑红方共有 s=jiangShi×xiang×zu×jv3 种摆法。 中国象棋状态总数即为 s 2 ，约为 1042.78。可见 粗略估计结果与本文计算结果更为接近，即便是 粗略估计，现有文献中的数据都是极不准确的。 4 结论和展望 基于动态规划的方法求解中国象棋状态总数 充分挖掘了中国象棋棋子着法规律，快速而准确 地求出了中国象棋状态总数，为描述中国象棋空 间复杂度提供了充分依据，实验证明现有文献提 供的数据远远不够准确。 该计数方法创新点包括两方面：1) 先难后 易，把问题分解为若干个子问题，先摆放约束较 多的棋子，后摆放约束较少的棋子，把影响后续 摆放的因素作为参数向后传递；2) 在求解每个子 问题时，动态规划可以减少重复计算。 本文提出的计数方法可能的应用方向包括： 1) 计算其他博弈游戏状态总数；2) 用于构造中国 象棋棋盘局面哈希函数，建立棋盘局面和数字之 间的一一映射；3) 寻找可暴力枚举全部状态的棋 型，为构建中国象棋残局库提供依据。 参考文献： 王晓鹏, 王骄, 徐心和, 等. 中国象棋与国际象棋比较分 析[J]. 重庆工学院学报, 2007, 21(1): 71–76. WANG Xiaopeng, WANG Jiao, XU Xinhe, et al. A comparative analysis between chess and Chinese chess[J]. Journal of Chongqing institute of technology, 2007, 21(1): 71–76. [1] 徐心和, 郑新颖. 棋牌游戏与事件对策[J]. 控制与决策, 2007, 22(7): 787–790. XU Xinhe, ZHENG Xinying. Card and board games and event game theory[J]. Control and decision, 2007, 22(7): 787–790. [2] SILVER D, HUANG A, MADDISON C J, et al. Mastering the game of Go with deep neural networks and tree search[J]. Nature, 2016, 529(7587): 484–489. [3] SILVER D, SCHRITTWIESER J, SIMONYAN K, et al. Mastering the game of Go without human knowledge[J]. Nature, 2017, 550(7676): 354–359. [4] SILVER D, HUBERT T, SCHRITTWIESER J, et al. Mastering chess and shogi by self-play with a general reinforcement learning algorithm[J]. arXiv: 1712.01815, 2017. [5] 高强, 郭琛. 哈希技术在中国象棋机器博弈系统中的应 用研究[J]. 科学技术与工程, 2008, 8(17): 4869–4872. GAO Qiang, GUO Chen. Technology of hashing and its application research in hybrid game tree search engine of Chinese chess[J]. Science technology and engineering, 2008, 8(17): 4869–4872. [6] 王骄, 徐长明, 徐心和. 中国象棋计算机博弈残局处理系 统[C]//2006 中国机器博弈学术研讨会. 北京, 中国, 2006. WANG Jiao, XU Changming, XU Xinhe. Endgame system in computer Chinese chess[C]//2006 Chinese Computer Games Seminar. Beijing, China, 2006. [7] 吴丽贤, 和力. 一种中国象棋残局棋谱自动生成算法[J]. 云南民族大学学报(自然科学版), 2010, 19(6): 435–438. WU Lixian, HE Li. An automatic generation algorithm for the manual of Chinese chess endgames[J]. Journal of Yunnan university of nationalities (natural sciences edition), 2010, 19(6): 435–438. [8] 第 1 期 魏印福，等：动态规划求解中国象棋状态总数 ·113·
·114· 智能系统学报 第14卷 [9]马麟.关于中国象棋的发展论述U求知导刊，2016(2)： [17刀徐付霞.大型动态规划的分解算法[).唐山师专学报， 31. 1998.22(5):6-9 MA Lin.The develop of Chinese chess[J].Journal of seek- XU Fuxia.Decomposable algorithm for large dynamic ing knowledge guide,2016(2):31. programming[J].Journal of Tangshan normal university, [10]黄晨.棋类游戏中的先行权.智能系统学报，2007， 1998,22(5:6-9. 2(3:91-94. [18]王军祥.动态规划算法原理及应用研究).电脑知识与 HUANG Chen.The first-move advantage in board 技术，2006(36)：150-151. games[J].CAAI transactions on intelligent systems,2007, WANG Junxiang.Research on the principle and applica- 2(3):91-94 tion of dynamic programming algorithm[J].Computer [11]王玉霞.组合计数中的映射原理及应用)，喀什师范学 knowledge and technology,2006(36):150-151 院学报，2005,26(3)：31-32 [19]ALLIS L V.Searching for solutions in games and artifi- WANG Yuxia.Mapping principle of combinational cial intelligence[D].The Netherlands:University of counting[J].Journal of Kashgar teachers college,2005, Limburg,1994 26(331-32. [20]涂志坚.电脑象棋的设计与实现D],广州：中山大学， [12]胡冠章.组合计数的群论与计算机方法J几.数学进展 2004. 1997,26(1y1-12 TU Zhijian.Design and implementation of computer Xi- HU Guanzhang.Group theory and computer methods for angqi[D].Guangzhou:Sun Yat-sen University,2004. combinatorial enumerations[J].Advances in mathematics, [21]徐心和，王骄.中国象棋计算机博弈关键技术分析]. 1997,26(1)1-12. 小型微型计算机系统，2006,27(6)：961-969 [13]曹博瑞，刘铁.映射法研究组合计数问题.文理导航， XU Xinhe,WANG Jiao.Key technologies analysis of 2017(11):4. Chinese chess computer game[J].Mini-micro systems, CAO Borui,LIU Tie.Solve combinational counting prob- 2006,27(6):961-969 lem by mapping[J].Guiding on art and science,2017(11): 4. 作者简介： [14]王跃进.映射观点下一些组合问题及其计数公式).上 魏印福，男，1993年生，硕士研究 海中学数学，2007(11上40-41. 生，主要研究方向为自然语言处理、计 算机博弈。 WANG Yuejin.Several combinational counting problem based on mapping[J].Middle school math of Shanghai, 2007(11):40-41. [15]高见元.动态规划算法的运用方法探讨几.软件导刊， 2007(10):136-138 GAO Jianyuan.Research on dynamic programming al- 李舟军，男，1963年生.教授，博 士生导师。IEEE会员，ACM会员， gorithm[J].Software guide,2007(10):136-138. AAAI会员，中国计算机学会高级会 [16]宛楠，张义.动态规划算法分析).长江大学学报（自然 员，计算机安全专业委员会常务委员， 科学版)，2013.10(7)：34-36. 主要研究方向为网络安全、数据挖掘、 WAN Nan,ZHANG Yi.The analysis of dynamic al- 自然语言处理。发表学术论文180余 gorithm[].Journal of Yangtze university (natural science 篇，其中被SCI和EI收录150余篇， edition),2013,10(7:34-36. 合著出版的2部教材分别获得部委级科技成果二、三等奖
马麟. 关于中国象棋的发展论述[J]. 求知导刊, 2016(2): 31. MA Lin. The develop of Chinese chess[J]. Journal of seeking knowledge guide, 2016(2): 31. [9] 黄晨. 棋类游戏中的先行权[J]. 智能系统学报, 2007, 2(3): 91–94. HUANG Chen. The first-move advantage in board games[J]. CAAI transactions on intelligent systems, 2007, 2(3): 91–94. [10] 王玉霞. 组合计数中的映射原理及应用[J]. 喀什师范学 院学报, 2005, 26(3): 31–32. WANG Yuxia. Mapping principle of combinational counting[J]. Journal of Kashgar teachers college, 2005, 26(3): 31–32. [11] 胡冠章. 组合计数的群论与计算机方法[J]. 数学进展, 1997, 26(1): 1–12. HU Guanzhang. Group theory and computer methods for combinatorial enumerations[J]. Advances in mathematics, 1997, 26(1): 1–12. [12] 曹博瑞, 刘铁. 映射法研究组合计数问题[J]. 文理导航, 2017(11): 4. CAO Borui, LIU Tie. Solve combinational counting problem by mapping[J]. Guiding on art and science, 2017(11): 4. [13] 王跃进. 映射观点下一些组合问题及其计数公式[J]. 上 海中学数学, 2007(11): 40–41. WANG Yuejin. Several combinational counting problem based on mapping[J]. Middle school math of Shanghai, 2007(11): 40–41. [14] 高见元. 动态规划算法的运用方法探讨[J]. 软件导刊, 2007(10): 136–138. GAO Jianyuan. Research on dynamic programming algorithm[J]. Software guide, 2007(10): 136–138. [15] 宛楠, 张义. 动态规划算法分析[J]. 长江大学学报(自然 科学版), 2013, 10(7): 34–36. WAN Nan, ZHANG Yi. The analysis of dynamic algorithm[J]. Journal of Yangtze university (natural science edition), 2013, 10(7): 34–36. [16] 徐付霞. 大型动态规划的分解算法[J]. 唐山师专学报, 1998, 22(5): 6–9. XU Fuxia. Decomposable algorithm for large dynamic programming[J]. Journal of Tangshan normal university, 1998, 22(5): 6–9. [17] 王军祥. 动态规划算法原理及应用研究[J]. 电脑知识与 技术, 2006(36): 150–151. WANG Junxiang. Research on the principle and application of dynamic programming algorithm[J]. Computer knowledge and technology, 2006(36): 150–151. [18] ALLIS L V. Searching for solutions in games and artificial intelligence[D]. The Netherlands: University of Limburg, 1994. [19] 涂志坚. 电脑象棋的设计与实现[D]. 广州: 中山大学, 2004. TU Zhijian. Design and implementation of computer Xiangqi[D]. Guangzhou: Sun Yat-sen University, 2004. [20] 徐心和, 王骄. 中国象棋计算机博弈关键技术分析[J]. 小型微型计算机系统, 2006, 27(6): 961–969. XU Xinhe, WANG Jiao. Key technologies analysis of Chinese chess computer game[J]. Mini-micro systems, 2006, 27(6): 961–969. [21] 作者简介： 魏印福，男，1993 年生，硕士研究 生，主要研究方向为自然语言处理、计 算机博弈。 李舟军，男，1963 年生，教授，博 士生导师。IEEE 会员，ACM 会员， AAAI 会员，中国计算机学会高级会 员，计算机安全专业委员会常务委员， 主要研究方向为网络安全、数据挖掘、 自然语言处理。发表学术论文 180 余 篇，其中被 SCI 和 EI 收录 150 余篇， 合著出版的 2 部教材分别获得部委级科技成果二、三等奖。 ·114· 智 能 系 统 学 报 第 14 卷
