·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 卷