AI 认为万智牌是世界上最复杂的游戏

AI 们在游戏领域也不是事事顺心。

AI 们（准确来说是它们背后的开发者们）一直在想方设法破解人类们的游戏。它们最大的胜利都是在完全信息——也就是对战双方都能知道所有信息——的棋类游戏上，随着算法的演进，它们在更加复杂、信息不对称的某些游戏，比如《DOTA2》上，也取得了一定的成果。

但是就在最近，美国康奈尔大学的 AI 开发者们无奈地承认，他们没法用 AI 算出万智牌的最优解——在论文中他们写道：「（游戏的一系列结构）确定了万智牌是目前已知计算最复杂的现实游戏」。

万智牌是一款历史悠久的桌游。1993 年，理查德·加菲设计出这款世界上第一个真正意义上的 TCG，迄今已经近 30 年历史了，这期间设计师们为这款游戏推出了 20000 多张卡牌和近百种独特的机制。

万智牌这么多年设计了大量机制各异的卡牌

康奈尔大学的AI开发者们发现，如此众多的卡牌和机制让这款游戏的复杂度几乎高于已知的任何游戏。在万智牌规则下的卡牌互动可以复原出一种通用的图灵机 UTM（2，18）——代表着这款游戏规则的复杂度已经达到了计算复杂度的上限。这与「AI 无法对围棋进行穷举」有不小的区别，对围棋的无法穷举只说明我们能提供给 AI 的时间和资源不够，而复杂度达到上限说明从本质上来讲，我们目前所知的算法无法算出游戏的最优解。

电脑试用的一套卡组

除了游戏足够复杂，AI 还面临着游戏中可能存在的各种逻辑陷阱：比如最简单、也最具破坏力的回合内循环。万智牌中有诸多可以达成「我的回合中可以做无限件事」的卡牌组合，比如经典的双身恼人鬼可以让玩家无限复制生物牌；比如莎妃旭日泰坦能够实现「牺牲自己-复活」的无限循环。

分裂双身与恼人鬼，很简单就能达成无限复制循环

这些无限循环都是有意义的，万智牌中没有规则禁止玩家达成无限循环。在正常对战中往往就是玩家口头上说一句「我无限了你是不是该认输了」，但是对于计算机而言，它们会真的一遍一遍计算这种无限。这倒并不会让现代计算机 AI 崩溃，但是会极大改变其算法，让它们更加难以判断潜在的胜负概率。

并不是万智牌中的所有卡组都是这样，游戏中也有很多简单易判断概率的卡组。但是只分析简单卡组恐怕很难说算是「攻克」了这款游戏，往往世界级比赛中选手们使用的顶尖卡组都是比较复杂、也就是 AI 难以计算概率的。

研究人员目前的结论是：「万智牌不符合计算机科学家在对游戏建模时常做的假设」。不过他们也没有打算就此放弃，既然现存的模型都不合适，那就新建一些模型——在论文结尾，他们指出，目前的图灵机模型必然不足以分析所有游戏，一个拥有基本水准的玩家就能做出胜过这些 AI 模型的分析，这些复杂度更高的游戏可能更适合「超级图灵」模型——他们希望关于万智牌的研究能帮助后来者完善对于游戏的 AI 分析模型。