四国军棋游戏复杂度研究

邓 红

（无锡机电高等职业技术学校，江苏 无锡 214028）

0 引言

目前，对于部分完全信息游戏，已经得到了理论解，如五子棋[1]、四子棋[2]、西洋跳棋[3]；对于一些状态复杂度较高的完全信息游戏，如中国象棋、国际象棋和围棋等，研究人员也开发出了可以战胜人类顶级玩家的程序，完全信息游戏的研究不断取得新突破[4]。而在非完全信息游戏研究方面，除少数较为简单的游戏外，较为复杂的非完全信息游戏，还未出现可以完全战胜人类顶级玩家的程序。四国军棋游戏是典型的非完全信息游戏。国内的研究人员已经对四国军棋的博弈问题进行了一些研究[5-8]，提出了如多棋子协同博弈、UCT 算法应用、定式库的设计和研究、无约束推理、有约束推理等办法，但四国军棋的空间和时间复杂度较高，导致四国军棋的研究较为困难，因此有必要通过理论研究，对非完全信息游戏复杂度进行分析，为非完全信息游戏的破解提供支撑。

1 完全信息游戏复杂度的研究情况

1.1 状态复杂度

状态复杂度是指游戏对战过程中出现的所有局面的总数。国内外对完全信息游戏的研究较早，一些比较经典的游戏，如国际象棋、中国象棋、日本将棋和围棋[9-11]，均有研究人员对其状态复杂度进行了相关研究，如表1 所示。

表1 常见游戏的状态复杂度

以围棋为例，围棋共有19×19 即361 个位置，每个位置上可以是黑子、白子或者空置，所以围棋的状态复杂度为3361≈10172。该估算方法包含了一些围棋规则不允许的状态和不可能出现的状态，即10172是围棋出现的所有状态的上限，完全信息游戏状态复杂度计算方法如公式（1）所示。

其中，SSC 为状态复杂度，S 为每个位置可能的状态数，L 表示位置总数。

表1 为常见游戏的状态复杂度，由于围棋的棋盘较大、规则灵活，导致其状态复杂度最高、且无法精密计算出合法局面。在2007 年，Jonathan-Schaeffer 等[3]通过证据计算法等得到了西洋跳棋的理论解，并计算出西洋跳棋共有5×1020个合法的局面。

每个完全信息游戏的棋盘大小、游戏规则、棋子种类、棋子个数等各不相同。对于较为简单的游戏，计算机程序可以计算出所有的局面，因此计算机程序可以处于不败之地。而对于较为复杂的游戏[12-13]，如围棋、象棋等，计算机还没有能力计算出可能出现的所有局面，因此只能粗略估算可能的局面总数，增加了计算机程序设计的难度。

1.2 博弈树复杂度

博弈树复杂度是某个游戏所有不同游戏路径的数目。博弈树复杂度比状态复杂度要大得多，因为同一个状态可以对应不同的博弈顺序。以井字棋游戏为例（如图1 所示），当盘面中有两个X 和一个O 时，如果第一个玩家下X 的位置不同，则可能由不同的方式组成。

图1 井字棋

研究人员通常使用平均合法移动数目和平均游戏长度相乘的积，来估算博弈树复杂度的下限[14]，完全信息游戏的博弈树复杂度计算方法如公式（2）所示。

其中，GTC 为博弈树复杂度，b 为玩家每回合可用的平均合法移动数，p 表示平均游戏长度。

根据下棋的经验，国际象棋和围棋每次平均合法移动数分别为35 和250[15]；平均游戏长度分别为80 和150。根据公式（2）推算，国际象棋的博弈树复杂度为3580≈10123，即10123；围棋的博弈树复杂度为250150≈10360，即10360。常见的完全信息游戏的博弈树复杂度如表2 所示。

表2 常见游戏的博弈树复杂度

2 非完全信息游戏复杂度的研究

2.1 非完全信息游戏的特点

完全信息游戏的信息和规则对所有人都是透明的，是研究机器博弈理想的试验田。近年来，研究人员发现非完全信息游戏能更好地模拟现实世界，研究成果有助于解决实际问题，本文以典型的不完全信息游戏牌棋类为例，总结出不完全信息游戏有下述几个特点。

（1）掌握有限信息。玩家一般只掌握己方的信息，不清楚对手和友军的信息。（2）状态复杂度和博弈树复杂度较高。因为信息缺失，一方对整个局面的判断不准确，导致游戏复杂度大幅增加。（3）存在诸多不确定性。玩家掌握的信息可能是错误的，根据错误信息推算出的结果也是不准确的。（4）合作较为困难。友军之间掌握的信息不对称，战略和战术意图不一致，导致相互合作较为困难。（5）贴近现实世界。不完全信息游戏相较于完全信息游戏，更好地模仿了现实世界场景，不仅考验玩家的技术，也考验其心理素质。

四国军棋游戏是典型的非完全信息游戏，其特点如下：（1）棋子初始摆放限制较少，对棋子行走的规则限制少；（2）棋盘较大，共四方，每方共30个棋位（5 个行营、9 个公路棋位、16 个铁路棋位），公共部分铁路棋位9 个，合计129 个棋位；（3）棋子种类和数量多，每方有12 种25 个棋子，四方合计有100 个棋子。

2.2 四国军棋游戏的状态复杂度

在开局方面，四国军棋和中国象棋比较相似，对战各方首先进行排兵布阵，四个方位的玩家需要将己方棋子排列在25 个棋位上（5 个行营不放棋子），开局时盘面上棋子最多（4 个玩家×25 个棋子/方=100 颗棋子），状态最为复杂，开局后棋子逐渐减少，状态复杂度降低。

首先分析一个玩家的状态复杂度，其棋位上可能是四个玩家中的任意一种棋子，再推理出整个游戏的状态复杂度，即非完全信息游戏的状态复杂度，如公式（3）所示。

其中，SSC 为状态复杂度，S 为玩家每个位置上可能的状态数，L 表示位置总数，N 为玩家数。

四国军棋游戏中，任一棋位上的棋子可能是己方12 种棋子，也可能是其他三方的12 种棋子；一方的位置总数为30 个。由此推算出四国军棋的状态复杂度为（12×4）4×30≈10201。

对比表1 中其他游戏的状态复杂度，四国军棋的状态复杂最高，计算机不可能使用完全列举法来求理论解，因此必须结合四国军棋游戏特点，寻找出相应的状态分析办法来求解。

2.3 四国军棋游戏的博弈树复杂度

四国军棋游戏中，玩家知道己方棋子类型，再通过行棋规则、拼杀结果获取另外三方棋子的部分信息，棋盘上所有棋子类型共48 种，结合完全信息游戏中博弈树复杂度的计算规则，得出非完全信息游戏的博弈树复杂度，如公式（4）所示。

其中，GTC 为博弈树复杂度，S 为玩家每个位置可能的状态数，b 为玩家每回合可用的平均合法移动数，p 表示平均游戏长度，N 为玩家数。

四国军棋游戏的平均分支为90，平均一局共有120 步[15]，根据公式（4），推算出四国军棋的博弈树复杂度：（48/4×90）120≈10360。对比表2 中其他游戏的博弈树复杂度，四国军棋和围棋的博弈树复杂度最高为10360，远高于其他棋牌类游戏。

四国军棋游戏的博弈树复杂度和围棋相同，虽然目前没有计算机程序和搜索算法可以遍历其博弈树的所有节点，但是已经出现的完全信息游戏-围棋程序AlphaGo 和不完全信息游戏-日本麻将SUPIX 程序，战力均能和人类顶级玩家相媲美，研究人员可以结合深度学习，开发出越来越强的四国军棋游戏程序。

3 结语

本文通过完全信息游戏中状态复杂度和博弈树复杂度，总结出完全信息游戏复杂度的计算方法，再结合非完全信息游戏特点，提出非完全信息游戏的复杂度计算方法，并推算出四国军棋游戏有序的状态和博弈树复杂度。非完全信息游戏更接近现实世界，而四国军棋游戏是一种典型的非完全信息游戏，推算出四国军棋游戏复杂度，有助于四国军棋游戏的破解，可为解决现实生活中的很多复杂问题提供参考。