在《游戏 AI 的缘起与进化》一文中我们讲到,游戏 AI 的进化始终与 AI 研究相生相伴,这是由于游戏种类丰富,难度和复杂性也很多样,人工智能攻克不同类型的游戏自然也反映了 AI 研究的进展,因此长期以来游戏一直是 AI 研究的黄金测试平台。 随着人工智能逐个攻克双陆棋、国际跳棋、国际象棋、围棋等棋类游戏,AI 仍在继续挑战难度更高的游戏,例如扑克、桥牌、麻将这类不完美信息游戏。那么为什么这类游戏的难度更高呢?如何衡量不同类型游戏的复杂度和难度?在这篇文章里,我们将会为大家仔细解读。 游戏复杂度与游戏难度并不等价
对于不完美信息游戏,我们仍然可以同完美信息游戏一样计算其状态空间复杂度和游戏树复杂度。然而,在不完美信息游戏中,由于信息是不完全、非对称的(例如扑克和麻将中对手的手牌和游戏剩余的底牌都是未知的),因此对于参与者来说许多不同的游戏状态看起来是无法区分的。例如在扑克游戏中,自己拿了两张 K,对方拿了不同的牌对应不同的状态;但是从自己的视角看,这些状态其实是不可区分的。我们把每组这种无法区分的游戏状态称为一个信息集。 显然,对于不完美信息游戏而言,合理的游戏策略应该建立在信息集而不是游戏状态之上,因为我们依赖未知信息来细粒度出招是没有意义的。相应地,当我们衡量不完美信息游戏的难度的时候,也应该依据信息集的数目,而不是游戏状态空间的大小。信息集的数目通常小于状态空间的数目。对于完美信息游戏,由于所有信息都是已知的,每个信息集只包含一个游戏状态,因此它的信息集数目与状态空间数目是相等的。 除了信息集的数目,还有一个重要的指标:信息集的平均大小,即在信息集中平均有多少不可区分的游戏状态。以两人德州扑克为例,假定我们的手牌是 AA,考虑对手的手牌为 AK 或者 AQ 两种不同情况。因为信息不完全,我们无法区分当前局势到底处在哪个状态,因此会把两种情况都归到同一个信息集。在两人德州扑克中,信息集的大小最多为1326(从52张牌中选择2张:C_52^2),也就是约为10^3。容易看出,信息集的数目反映了不完美信息游戏中所有可能的决策节点的数目,而信息集的平均大小则反映了游戏中每个局面背后隐藏信息的数量。显然,信息集平均大小越大,其中包含的未知信息就越多,因此决策的难度就越高。事实上,信息集的平均大小直接影响采用搜索算法的可行性:当对手的隐藏状态非常多时,传统的搜索算法基本上是无从下手的。因此信息集的平均大小也可以作为游戏难度的衡量指标。 表2:不完美信息游戏的信息集数目和信息集平均大小无限注德州扑克的信息集数目很大,但是因为只有两张不可见的牌,其隐藏信息很少,信息集的平均大小很小。桥牌和麻将由于是每个玩家手里可以有13张未知的手牌,因此隐藏信息的数量远远超过了德州扑克。表2给出了德州扑克、桥牌和麻将的信息集数目和信息集的平均大小。 如果我们以信息集数目和信息集平均大小为准则,来对比像围棋这样的完美信息游戏和表2中的几种不完美信息游戏,会得到非常有意思的结果。如图3所示,围棋和德州扑克的信息集平均大小远远小于桥牌和麻将。AI 在围棋和德州扑克上的成功很大程度依赖于搜索算法,因为搜索可以最大程度地发挥计算机的计算优势。但是因为巨大的信息集平均大小带来的环境不确定性,传统的搜索算法在桥牌和麻将面前很难发挥同样的功效。 图3:围棋、德州扑克、桥牌和麻将的信息集数目和信息集平均大小对比 回顾游戏 AI 的历史,目前大部分完美信息游戏(如国际象棋、围棋等)以及信息集平均大小较小的不完美信息游戏(如两人德州扑克和多人德州扑克等)都有了相当好的解决方法。然而,对于桥牌和麻将这类含有大量隐藏信息的不完美信息游戏,需要我们发明全新的方法论,才能有所突破,而这需要 AI 算法的研究者们持之以恒地探索。
参考文献: [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 Complexitieshttps://www.pipmodern.com/feed/state-space-game-tree-complexity [4]Game Complexity III: Artificial Intelligencehttps://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 complexityhttps://en.wikipedia.org/wiki/Game_complexity