※ 引述《jerry78424 (青松碧涛)》之铭言：
: 游研社
: AI 认为万智牌是世界上最复杂的游戏
: 作者：跳跳 16小时前
: 全文约 1100 字，阅读只需要 3 分钟。
: AI 们在游戏领域也不是事事顺心。
: AI 们（准确来说是它们背后的开发者们）一直在想方设法破解人类们的游戏。它们最大的胜利都是在完全信息——也就是对战双方都能知道所有信息——的棋类游戏上，随着算法的演进，它们在更加复杂、信息不对称的某些游戏，比如《DOTA2》上，也取得了一定的成果。
: 但是就在最近，美国康奈尔大学的 AI 开发者们无奈地承认，他们没法用 AI 算出万智牌的最优解——在论文中他们写道：“（游戏的一系列结构）确定了万智牌是目前已知计算最复杂的现实游戏”。
: 万智牌是一款历史悠久的桌游。1993 年，理查德·加菲设计出这款世界上第一个真正意义上的 TCG，迄今已经近 30 年历史了，这期间设计师们为这款游戏推出了 20000 多张卡牌和近百种独特的机制。
: 万智牌这么多年设计了大量机制各异的卡牌
: 康奈尔大学的AI开发者们发现，如此众多的卡牌和机制让这款游戏的复杂度几乎高于已知的任何游戏。在万智牌规则下的卡牌互动可以复原出一种通用的图灵机 UTM（2，18）——代表着这款游戏规则的复杂度已经达到了计算复杂度的上限。这与“AI 无法对围棋进行穷举”有不小的区别，对围棋的无法穷举只说明我们能提供给 AI 的时间和资源不够，而复杂度达到上限说明从本质上来讲，我们目前所知的算法无法算出游戏的最优解。
: 除了游戏足够复杂，AI 还面临着游戏中可能存在的各种逻辑陷阱：比如最简单、也最具破坏力的回合内循环。万智牌中有诸多可以达成“我的回合中可以做无限件事”的卡牌组合，比如经典的双身恼人鬼可以让玩家无限复制生物牌；比如莎妃旭日泰坦能够实现“牺牲自己-复活”的无限循环。
: 分裂双身与恼人鬼，很简单就能达成无限复制循环
: 这些无限循环都是有意义的，万智牌中没有规则禁止玩家达成无限循环。在正常对战中往往就是玩家口头上说一句“我无限了你是不是该认输了”，但是对于计算机而言，它们会真的一遍一遍计算这种无限。这倒并不会让现代计算机 AI 崩溃，但是会极大改变其算法，让它们更加难以判断潜在的胜负机率。
: 并不是万智牌中的所有卡组都是这样，游戏中也有很多简单易判断机率的卡组。但是只分析简单卡组恐怕很难说算是“攻克”了这款游戏，往往世界级比赛中选手们使用的顶尖卡组都是比较复杂、也就是 AI 难以计算机率的。
: 研究人员目前的结论是：“万智牌不符合计算机科学家在对游戏建模时常做的假设”。不过他们也没有打算就此放弃，既然现存的模型都不合适，那就新建一些模型——在论文结尾，他们指出，目前的图灵机模型必然不足以分析所有游戏，一个拥有基本水准的玩家就能做出胜过这些 AI 模型的分析，这些复杂度更高的游戏可能更适合“超级图灵”模型——他们希望关于万智牌的研究能帮助后来者完善对于游戏的 AI 分析模型。
又是一篇胡扯的农场文章...
原论文在这里 https://arxiv.org/abs/1904.09828
首先作者并不是康乃尔大学的，并不是文章在arXiv上就代表作者是康乃尔大学的。
再来作者也不是“AI开发者”，也没有“无奈的承认无法算出MTG最佳解”，他们的目的
就是证明MTG是个难到电脑算不出来的游戏，怎么会无奈呢 XD
首先承认一下我没打过MTG，所以我也没有详细的看完这篇文章，不过根据我的理解这篇
论文并不能得出“AI几乎不可能打败人类玩家”的结论。首先我们看看这篇文章具体的结
论:
“给定一个残局，算出谁能赢下这场游戏”的算法并不存在。
但这代表人类写不出魔风的AI吗？AlphaGo也没有算出谁100%会赢啊，但它打败了所有的
职业棋士。所以“找不出最佳解”跟“无法打败人类玩家”其实没有什么直接关系...
当然这篇论文某种程度上证明了魔法风云会非常非常难，因为即使像围棋这么难的游戏，
只要拥有足够的时间，电脑还是能够穷举出所有的可能性，并且得出谁会赢的结论。
(地球会不会先毁灭先不谈 XD)
但这篇文章说明了我们无法用图灵机(电脑的理论模型)对魔风做同样的事情
接下来谈一下这篇文章具体是怎么证明的。学资工的同学可能会在离散数学课听到所谓
的“停机问题”，也就是“判断一支程式会不会停”，而一个著名的结论是图灵机算不
出这个问题的答案。这篇文章的逻辑是“如果我有个算MTG残局的算法，我就可以拿
它来算出停机问题的答案”，这显然不可能，所以我们想要的算法不可能存在。
(也就是所谓的reduction)
而具体的做法是，假设我们想要算程式A能不能停下来，我们根据A设定出一个残局，在
这个残局下两个玩家能做的事情完全固定(透过一张叫Wild Evocation的卡达成)，并且
这个唯一的选择会对应程式的一步 (准确来说是四个回合对应UTM的一步...)
也就是说，盘面状态对应了程式的内部状态(可以想成是内存+指令位置)，而玩家的行
动对盘面的改变会恰好对应程式的一步对其内部状态的改变。因此跑这个残局其实等同
于“模拟程式的进行”。
如果程式本身会停，那相应的残局最后会停下来并且使得先手玩家胜利；
如果程式本身不会停，那相应的残局也不会停，根据规则无穷循环和局。
因此如果我们能设计一个算法算出任何残局的结果，那么这个算法也能用来判断任
何程式会不会停，与事实矛盾。
基本上就是这样，有兴趣的再麻烦自己看论文吧 XD
总之这只是一个理论上的结果，首先打赢对手并不需要最优解，再来我们在现实中可能
也不会达到这么麻烦的残局，所以这跟魔风的AI设计应该真的没有什么关系。

alphago不是穷举法吧不太懂为何玩家没赢会无穷循环游戏内部没有结束无穷循环的判定吗?像是围棋的打结规则那样

如果你是说游戏内对loop的规则的话是玩家必须直接喊出要做的loop数量(取捷径,当然这是实体牌的做法),而形成强制的无穷循环时若所有玩家都无法停止则和局,若有玩家有其他选择能做的话,印象中好像是主动玩家(该

在一回合出现 消耗资源b产生资源a->消耗资源a产生资源b这样就无限了吧

回合玩家)优先要把循环停下来(这个有点忘了现在问题是在电子版上要判定形成无穷循环会有问题吧MTG电子版的loop要全程自己按

疴……那就ai养好后再写个if?XD

对AI不熟,但要判断无穷循环这个好像也是个大问题?

我也不熟，不过可以想见最基本就穷举残局状况手动写if来判断问题是如果不靠手动要AI自己判断残局，不知道该怎么养可能首先会从重复行为下手吧

那看起来就是,如果是玩家要进行N次重复操作这个很好判断,但遇到那种强制型的loop(先不考虑能不能中断)判断会有问题

可是判断是否在无穷循环里，一样能达到判出和局的要求啊

问题就在无穷循环这件事本身不可能靠自身判断出来

有可能会先穷举列出但不给ai看，要ai自己判断是不是然后根据判断给分，慢慢养出(选出)接近穷举（判断100%正确）的ai

https://i.imgur.com/13kz15e.jpg比较经典的无法停止循环举例就像是,在场上没有其他可放逐目标的状况下连拍三张这个,会导致2压掉1,然后3压

楼主就说判断自己是否在无穷循环里很简单了，难的是预测

掉2让1回来,1再压掉3让2回来压掉1 (loop如果有其他目标可以选的状况会被迫做其它选择来中断

围棋也有循环劫啊 但现在看来不是问题

围棋不太一样的地方是，规则很明确定义结的状况与应对，而且他只有一种状况

我现在其实有点混乱，我想确认一下MTG的token有数量上限吗? 围棋不成问题应该是因为盘面大小固定，所以可以保证在有限步数内达到循环，但这篇论文似乎用了token来表示tape上的内容，而且似乎没有假设上限，使得可能的状态无限多

没有上限

阿发够不是穷举喔，是算机率的

没有上限

我文章应该没说AlphaGo是穷举吧...

推原po大神是说现在有闲情逸致做这种研究也是蛮厉害的…

推认真

这研究也不能说没意义 如果结果是可以的话代表推翻了长久以来的理论

残局要看多残啊 只有动了一步也是残局那当然是不存在这个算法但如果倒数有限步 当然是找的到算法的 人脑都可以算了

alphaGo就是靠随机减少对穷举的需求啊，这只是因为游戏结构不同

围棋才是公认最难的

深度学习其实比较像直觉 他不需要算出有没有无穷 只评估胜率高的作法 后续就可以再用别的方式去模拟这些作法