哪类游戏AI难度更高？用数学方法来分析一下

在《游戏 AI 的缘起与进化》一文中我们讲到，游戏 AI 的进化始终与 AI 研究相生相伴，这是由于游戏种类丰富，难度和复杂性也很多样，人工智能攻克不同类型的游戏自然也反映了 AI 研究的进展，因此长期以来游戏一直是 AI 研究的黄金测试平台。

随着人工智能逐个攻克双陆棋、国际跳棋、国际象棋、围棋等棋类游戏，AI 仍在继续挑战难度更高的游戏，例如扑克、桥牌、麻将这类不完美信息游戏。那么为什么这类游戏的难度更高呢？如何衡量不同类型游戏的复杂度和难度？在这篇文章里，我们将会为大家仔细解读。

游戏复杂度与游戏难度并不等价

首先需要提醒大家，游戏的复杂度与难度并不完全等价，游戏难度除了与游戏本身的复杂度有关以外，还与战略等多种要素相关，也就是说，数学上更复杂的游戏，玩起来不一定更难。

一般来说，我们可以根据信息的暴露程度将游戏分为两大类：完美信息游戏（Perfect-Information Games）和不完美信息游戏（Imperfect-Information Games）。如果所有的参与者，在游戏的任何阶段都可以访问所有关于游戏（包括对手）状态及其可能延续的信息，那么称这类游戏为完美信息游戏；否则称为不完美信息游戏。围棋、象棋等棋类游戏，对局双方可以看到局面的所有信息，属于完美信息游戏；而扑克、桥牌、麻将等游戏，虽然每个参与者都能看到对手打过的牌，但并不知道对手的手牌和游戏的底牌，也就是说各个对局者所掌握的信息是不对称的，因此属于不完美信息游戏。

完美信息游戏和不完美信息游戏难度的衡量指标通常是有区别的。对于完美信息游戏，通常游戏的复杂度就决定了难度，我们可以用状态空间复杂度（State-Space Complexity）和游戏树复杂度（Game-Tree Complexity）对其难度进行衡量；而对于不完美信息游戏，隐藏信息对于游戏的难度影响很大，我们可以用信息集（Information Set）数目和信息集平均大小对其难度进行衡量。

完美信息游戏：状态空间和游戏树的复杂度

状态空间复杂度（State-Space Complexity）

游戏的状态空间复杂度（SSC）是指从游戏的初始状态开始，可以达到的所有符合规则的状态的总数。例如棋类游戏中，每移动一枚棋子或捕获一个棋子，就创造了一个新的棋盘状态，所有这些棋盘状态构成游戏的状态空间。通常情况下，很难精确地计算出游戏的状态空间大小，只能给出一个粗略的估计。一种最常用的估计方法是通过包含一些不符合规则或不可能在游戏中出现的状态, 从而计算出状态空间大小的一个上界（Upper Bound）。例如在估计围棋状态数目上界的时候，允许出现棋面全部为白棋或者全部为黑棋的极端情况。

事实上，即便像井字棋这样简单的游戏，其状态空间也是很大的。井字棋的盘面上共有9（3x3）个位置，每个位置可能的取值有三种：X，O或空白，因此总的状态数目为3的9次方即19863个。当然，这其中包含许多不符合规则的状态，因为我们在这里估计的是状态空间大小的上界。由此，我们可以得到井字棋的状态空间复杂度约为10^4（即19863≈10^4）。这种计算方法可以很容易地推广到更大的棋盘和更加复杂的棋类游戏。比如围棋有361（19x19）个位置，每个位置可以放置白子或黑子或者空置，利用上述方法，可以确定围棋的状态空间复杂度约为10^172 (即3^361≈10^172)。在表1中，我们给出了常见的完美信息棋类游戏的状态空间复杂度。

图1：井字棋

游戏树复杂度（Game-Tree Complexity）

游戏树复杂度（GTC）表示某个游戏的所有不同游戏路径的数目。游戏树复杂度比状态空间复杂度要大得多，因为同一个状态可以对应于不同的博弈顺序。例如，在图2的井字棋游戏中，棋面上有两个 X 和一个 O，这个状态可能由两种不同的方式形成，具体的形成过程由第一个 X 的下子位置所决定。

图2：井字棋游戏中统一状态的不同形成过程

与状态空间类似，游戏树复杂度的精确值也很难计算。常用的方法是估计其合理的下界：GTC≥b^p，其中 b 表示玩家每回合可用的平均合法移动数目，p 表示平均游戏长度。由此可以看出，拥有更多合法移动的游戏比合法移动较少的游戏更复杂，另外游戏的平均长度也是影响游戏树复杂度的关键因素。

根据经验，井字棋、象棋以及围棋每一步的平均合法移动数目分别为4、35和250；平均游戏长度分别为9、80和150。因此利用上面的公式，可以得出井字棋的游戏树复杂度为10^5 (即4^9≈10^5)，国际象棋是10^123 (即35^80≈10^123)，而围棋是10^360 (即250^150≈10^360)。更多完美信息棋牌类游戏的游戏树复杂度参见表1。

表1：完美信息游戏的状态空间复杂度和游戏树复杂度

在传统的完美信息棋牌游戏中，围棋不管从状态空间复杂度，还是游戏树复杂度上都远远领先其他棋牌类游戏。2017年，AlphaZero 利用 MCTS 和深度强化学习，成功解决了包括围棋在内的多个完美信息游戏。目前，学术界研究的热点则转向不完美信息游戏和即时策略游戏等。

不完美信息游戏：信息集数目和平均大小

对于不完美信息游戏，我们仍然可以同完美信息游戏一样计算其状态空间复杂度和游戏树复杂度。然而，在不完美信息游戏中，由于信息是不完全、非对称的（例如扑克和麻将中对手的手牌和游戏剩余的底牌都是未知的），因此对于参与者来说许多不同的游戏状态看起来是无法区分的。例如在扑克游戏中，自己拿了两张 K，对方拿了不同的牌对应不同的状态；但是从自己的视角看，这些状态其实是不可区分的。我们把每组这种无法区分的游戏状态称为一个信息集。

显然，对于不完美信息游戏而言，合理的游戏策略应该建立在信息集而不是游戏状态之上，因为我们依赖未知信息来细粒度出招是没有意义的。相应地，当我们衡量不完美信息游戏的难度的时候，也应该依据信息集的数目，而不是游戏状态空间的大小。信息集的数目通常小于状态空间的数目。对于完美信息游戏，由于所有信息都是已知的，每个信息集只包含一个游戏状态，因此它的信息集数目与状态空间数目是相等的。

除了信息集的数目，还有一个重要的指标：信息集的平均大小，即在信息集中平均有多少不可区分的游戏状态。以两人德州扑克为例，假定我们的手牌是 AA，考虑对手的手牌为 AK 或者 AQ 两种不同情况。因为信息不完全，我们无法区分当前局势到底处在哪个状态，因此会把两种情况都归到同一个信息集。在两人德州扑克中，信息集的大小最多为1326（从52张牌中选择2张：C_52^2），也就是约为10^3。容易看出，信息集的数目反映了不完美信息游戏中所有可能的决策节点的数目，而信息集的平均大小则反映了游戏中每个局面背后隐藏信息的数量。显然，信息集平均大小越大，其中包含的未知信息就越多，因此决策的难度就越高。事实上，信息集的平均大小直接影响采用搜索算法的可行性：当对手的隐藏状态非常多时，传统的搜索算法基本上是无从下手的。因此信息集的平均大小也可以作为游戏难度的衡量指标。

表2：不完美信息游戏的信息集数目和信息集平均大小

无限注德州扑克的信息集数目很大，但是因为只有两张不可见的牌，其隐藏信息很少，信息集的平均大小很小。桥牌和麻将由于是每个玩家手里可以有13张未知的手牌，因此隐藏信息的数量远远超过了德州扑克。表2给出了德州扑克、桥牌和麻将的信息集数目和信息集的平均大小。

如果我们以信息集数目和信息集平均大小为准则，来对比像围棋这样的完美信息游戏和表2中的几种不完美信息游戏，会得到非常有意思的结果。如图3所示，围棋和德州扑克的信息集平均大小远远小于桥牌和麻将。AI 在围棋和德州扑克上的成功很大程度依赖于搜索算法，因为搜索可以最大程度地发挥计算机的计算优势。但是因为巨大的信息集平均大小带来的环境不确定性，传统的搜索算法在桥牌和麻将面前很难发挥同样的功效。

图3：围棋、德州扑克、桥牌和麻将的信息集数目和信息集平均大小对比

回顾游戏 AI 的历史，目前大部分完美信息游戏（如国际象棋、围棋等）以及信息集平均大小较小的不完美信息游戏（如两人德州扑克和多人德州扑克等）都有了相当好的解决方法。然而，对于桥牌和麻将这类含有大量隐藏信息的不完美信息游戏，需要我们发明全新的方法论，才能有所突破，而这需要 AI 算法的研究者们持之以恒地探索。

延伸阅读：游戏难度的计算方法

定约桥牌（只考虑打牌阶段）

• 信息集数目：以防守一方为例，按照游戏轮次来计算。第一轮，每个玩家只能看到自己的13张牌，因此第一轮信息集数目为C_52^13=6.3×10^11。第二轮，每个玩家剩余12张牌，玩家只能看到自己的12张手牌以及第一轮出的四张牌，因此第二轮信息集数目为C_52^13 C_13^1 C_39^1 C_38^1 C_37^1=C_52^13 A_13^1 A_39^3。以此类推，第三轮信息集数目为C_52^13 C_13^1 C_12^1 C_39^1 C_38^1 C_37^1 C_36^1 C_35^1 C_34^1=C_52^13 A_13^2 A_39^6 … 第13轮信息集数目为C_52^13 A_13^12 A_39^36。总的信息集数目为各轮信息集的和，即C_52^13 (1+A_13^1 A_39^3+⋯+A_13^12 A_39^36)≈1.35×10^67。

• 信息集平均大小：以防守一方为例，第一轮，其他选手有13张牌，所以每个信息集大小为C_39^13 C_26^13 C_13^13。第二轮，每位对手还剩12张牌，因此每个信息集大小为C_36^12 C_24^12 C_12^12。以此类推，第13轮，每个信息集大小为C_3^1 C_2^1。对每一轮的信息集大小求平均，得到桥牌的信息集平均大小≈6.77×10^15。

麻将

• 信息集数目：每一局麻将结束的时候，底下有14张牌不会被用到，所以不考虑吃碰杠的情况下，每一局至多会进行17.5轮（136减去13x4共52张手牌再减去14张底牌，总共剩70张牌，每一轮出4张）。与桥牌类似，依然按照游戏轮次来计算。第一轮，每个玩家只能看到自己的13张牌，因此第一轮信息集数目为C_136^13(为了计算方便，不考虑重复手牌)。第二轮，由于第一轮每个玩家各出一张牌，一副麻将总共有34种不同的牌，所以第一轮出的四张牌所有可能的情况至多为34^4，因此第二轮信息集数目为C_136^13 ∙34^4。以此类推，第18轮信息集数目为C_136^13 ∙34^68。总的信息集数目为各轮信息集的和，即C_136^13 (1+34^4+⋯+34^68)≈7×10^121。

• 信息集平均大小：第一轮，除去自己13张手牌，总共剩余123张牌，每位对手13张牌，所以每个信息集大小为C_123^13 C_110^13 C_97^13（为了计算方便，不考虑重复手牌）。第二轮，除去自己13张手牌，以及第一轮出的四张牌，总共剩余119张牌，因此每个信息集大小为C_119^13 C_106^13 C_93^13。以此类推，第18轮，每个信息集大小为C_55^13 C_42^13 C_29^13。对每一轮的信息集大小求平均，得到麻将的信息集平均大小≈1.07×10^48。

参考文献：

[1]L.V. Allis, Searching for solutions in games and artificial intelligence, Ph.D.Thesis, University of Limburg, Maastricht, 1994.

[2]van den Herik, H., Uiterwijk, J. W. & van Rijswijck, J. Games solved: now and in the future. Artif. Intell. 134, 277–311 (2002).

[3]Game Complexity I: State-Space & Game-Tree Complexities

https://www.pipmodern.com/feed/state-space-game-tree-complexity

[4]Game Complexity III: Artificial Intelligence

https://www.pipmodern.com/feed/complexity-artificial-intelligence

[5]M. Johanson, Measuring the size of large no-limit poker games, Technical Report TR13-01, Department of Computing Science, University of Alberta (2013).

[6]Wiki: Game complexity

https://en.wikipedia.org/wiki/Game_complexity

你也许还想看：

感谢你关注“微软研究院AI头条”，我们期待你的留言和投稿，共建交流平台。来稿请寄：[e-mail]。