游研社
AI 认为万智牌是世界上最复杂的游戏
作者：跳跳 16小时前
全文约 1100 字，阅读只需要 3 分钟。
AI 们在游戏领域也不是事事顺心。
AI 们（准确来说是它们背后的开发者们）一直在想方设法破解人类们的游戏。它们最大的胜利都是在完全信息——也就是对战双方都能知道所有信息——的棋类游戏上，随着算法的演进，它们在更加复杂、信息不对称的某些游戏，比如《DOTA2》上，也取得了一定的成果。
但是就在最近，美国康奈尔大学的 AI 开发者们无奈地承认，他们没法用 AI 算出万智牌的最优解——在论文中他们写道：“（游戏的一系列结构）确定了万智牌是目前已知计算最复杂的现实游戏”。
万智牌是一款历史悠久的桌游。1993 年，理查德·加菲设计出这款世界上第一个真正意义上的 TCG，迄今已经近 30 年历史了，这期间设计师们为这款游戏推出了 20000 多张卡牌和近百种独特的机制。
万智牌这么多年设计了大量机制各异的卡牌
康奈尔大学的AI开发者们发现，如此众多的卡牌和机制让这款游戏的复杂度几乎高于已知的任何游戏。在万智牌规则下的卡牌互动可以复原出一种通用的图灵机 UTM（2，18）——代表着这款游戏规则的复杂度已经达到了计算复杂度的上限。这与“AI 无法对围棋进行穷举”有不小的区别，对围棋的无法穷举只说明我们能提供给 AI 的时间和资源不够，而复杂度达到上限说明从本质上来讲，我们目前所知的算法无法算出游戏的最优解。
除了游戏足够复杂，AI 还面临着游戏中可能存在的各种逻辑陷阱：比如最简单、也最具破坏力的回合内循环。万智牌中有诸多可以达成“我的回合中可以做无限件事”的卡牌组合，比如经典的双身恼人鬼可以让玩家无限复制生物牌；比如莎妃旭日泰坦能够实现“牺牲自己-复活”的无限循环。
分裂双身与恼人鬼，很简单就能达成无限复制循环
这些无限循环都是有意义的，万智牌中没有规则禁止玩家达成无限循环。在正常对战中往往就是玩家口头上说一句“我无限了你是不是该认输了”，但是对于计算机而言，它们会真的一遍一遍计算这种无限。这倒并不会让现代计算机 AI 崩溃，但是会极大改变其算法，让它们更加难以判断潜在的胜负机率。
并不是万智牌中的所有卡组都是这样，游戏中也有很多简单易判断机率的卡组。但是只分析简单卡组恐怕很难说算是“攻克”了这款游戏，往往世界级比赛中选手们使用的顶尖卡组都是比较复杂、也就是 AI 难以计算机率的。
研究人员目前的结论是：“万智牌不符合计算机科学家在对游戏建模时常做的假设”。不过他们也没有打算就此放弃，既然现存的模型都不合适，那就新建一些模型——在论文结尾，他们指出，目前的图灵机模型必然不足以分析所有游戏，一个拥有基本水准的玩家就能做出胜过这些 AI 模型的分析，这些复杂度更高的游戏可能更适合“超级图灵”模型——他们希望关于万智牌的研究能帮助后来者完善对于游戏的 AI 分析模型。

那炉石呢？

炉石的话AI会无法理解为什么对面又可以这样

需要拜拜的游戏

炉石打右手就好 没难度阿嬷都会玩

如果有天deepmind派出阿发magic去打MTG一定很有趣

炉石的话，你要怎么教AI面对几乎不可能出现的牌？

对啊 怎么没有用AI玩炉石的新闻 难道也是训练不起来?

从机器的角度，获得随机一张牌的复杂度靠杯高

随机牌也是当下环境的牌，其实几百张牌对AI是小case啦，像文中MTG这种无限才是比较麻烦的，因为有些无限是玩家会做但有些不会做，但AI却无法分别，不过我觉得AI做个100次就可以视为无限了，再看是否有获得大量资源来判断是否会赢

AI:欸干他作弊 作弊阿

游戏王试过了吗

AI卒于卡地

1993 30年

AI打炉石应该讨不到太多好处 算多可能还是自己吓自己每手都是最优姐还是会输在右手

打一场是这样 但打100场 打1000场 AI不可能算不出炉石有最佳解 因为玩家就已经在用最佳解了 加上炉石又不能对手回合做事情 也不能搞无限 纯运气的东西只要算出机率 除非你把把都神抽不然总有一天会输 这跟AI玩德州朴克或21点一样意思呀

alphastone: 对啊~你又可以了

不就是循环崩溃吗？ 一直执行重复动作

玩家的最佳解不一定真的是最佳解 只是人类了解范围内的最佳解 像围棋已经也是认为有最佳解的解法 阿法狗还是下出人类无法理解的最佳解 AI说不定就是被智慧诅咒 考虑的太多反而无法下手

获胜条件太多样可能也是原因 如果AI只会计算不让自己的血量低于0 那就很有可能被抽爆磨爆或是其他条件的组合技解决

麻烦在无限循环吧，碰到就卡死了

裁判主办会作弊的游戏当然难赢

这种含运气成份的游戏无法屌虐另一方吧

问题就是人类可以阅读文字，非常容易理解各种规则，ai是靠大量尝试去理解，一张卡的效果ai用几亿次可能都还不了解规则

AI只是无法理解规则外的胜利模式吧 像是无限loop会逼对面认输 但是对于AI它不知道怎么处理这种状况

游戏王ai可以ㄇ

等一下，这篇是讲"MTG is Turing complete"那篇论文吗是的话内容也错太多了吧= =作者没有一个是Cornell的，然后内容也跟AI没啥关系阿..

另外就是文字理解 毕竟人类的语言对于电脑而言是非常不严谨的相同卡片效果的描述在人类不介入的状况下AI可能做出人类无法接受的见解

围棋也被说过 结果..

结果就是内文说的呀，概念完全不同

实体卡片上的效果说明跟电脑化后逻辑判断有出入这连炉石里都被笑称为考古题了，30年份卡池就更不用说

这篇大概是抄esportstalk的，那里也说是康奈尔大学，可能是看到网页底下说arxiv是康奈尔的商标就误会了

其实说穿了也只是训练AI需要人力介入的部分过多 如果时间成本允许下仍然可以实现啦 这点跟过去靠穷举破解棋类游戏是一样的状况

游戏王那满满的卡面文字和盖牌的无法预期和发动时机才最难

炉石打头萨脚本最佳解 打头

cock magic

游戏王我只记得ygopro的ai玩主流牌有够无解==

可是MTG会一直出新牌啊 穷举破解法赶得上吗

MTG的EDH赛制扯到团战更难算,所以常常在说来打EDH必须先把处理器规格上调(也总会被练上来)

先拔掉所有卡禁让高端玩家打几场比赛试试就知道了。棋类短时间就频繁增减禁手或规则，不相信会好破解。魔法风云会就是一张牌一种规则，规则效果可能部分重复，牌面有一点点不同就要整套重算，那维度大上棋类太多。

炉石没有绝对的无限啊

游戏王的ai是要很会说书吗

别再贴来源不明的农场文了好吗

游戏王才是最难的吧

AI:为什么对方可以自己编规则?

不是阿 炉石随机性那么高的游戏 你才练一千场不可能知道每手的判断是否正确好吗随机性影响的反馈太多了 可能要多加好几个零的次数才有可能测出正确的反馈吧

炉石AI只会：你又可以了? 离谱至极