魏印福，李舟军

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

中国象棋是一种广为流传的完全知识二人零和博弈游戏，形式上与国际象棋极为相似[1-2]，在博弈技术上二者也有许多共通之处。2016年以来，谷歌相继推出AlphaGo[3]、AlphaGo Zero[4]、AlphaZero[5]等博弈模型，不仅在围棋领域完胜人类棋手，在国际象棋、日本将棋上也超越了之前最先进的博弈引擎，计算机博弈受到人们广泛关注。

中国象棋博弈常提及的一个问题就是中国象棋空间复杂度，即中国象棋状态总数。现有文献仅给出中国象棋空间复杂度数值却没有提供计算方式，同时不同文献给出的数值存在较大差异。长期以来，中国象棋状态总数这一计数问题无人问津，却又莫衷一是。本文利用中国象棋棋子着法特点把求解中国象棋状态总数问题分解为若干个子问题，通过动态规划方法分别求解各个子问题，最终准确求出中国象棋状态总数，为以后描述中国象棋状态总数提供可靠依据。同时，这种计算中国象棋状态总数的方法除了可用于计算其他棋类的空间复杂度，也可以用于构造中国象棋棋盘局面哈希函数[6]、构造中国象棋残局库[7-8]等方面。

1 问题描述

1.1 中国象棋棋盘棋子

中国象棋棋盘9条竖线，10条横线，总计90个位置[9-10]。棋子分为红黑两色，每方16枚棋子，棋子分为7类：车、马、炮、相、士、将、卒。开始局面如图1所示。

图 1 中国象棋开始局面Fig. 1 The start state of Chinese Chess

中国象棋中，“将”和“帅”、“相”和“象”、“卒”和“兵”描述的是同一类棋子。为叙述方便，本文对这3类棋子分别采用“将”、“相”、“卒”的叫法。……