035棋牌

2019-08-16 | 作者:微軟亞洲研究院

在《遊戲 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
[4] Game Complexity III: 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

?