一项由意大利都灵大学等机构的研究者发表的论文《Optimal play in Yu-Gi-Oh! TCG is hard》。该研究针对游戏王卡片游戏中，关于计算机是否能判定某个策略为必胜策略的问题（即最优玩法的可计算性），给出了数学上“不可判定”的结论。论文中将游戏王称为当前最复杂的卡片游戏。
研究指出：无论使用多么优秀的计算机程序，都不存在一种算法可以判定游戏王中某个给定策略是否为必胜策略。

文章 → http://t.cn/AXV9psfV

此前，已证明「万智牌」的最优玩法是不可计算的。而这项研究则从数学上证明，游戏王同样潜藏着同等甚至更高的复杂性。

证明方法利用了计算理论中著名的“停机问题”。
<停机问题探讨的是：是否能在不实际运行程序的情况下，完美预测任意计算机程序最终是会正常停止，还是永远循环下去？艾伦·图灵在1936年已证明，这是一个绝对无法判定的问题。>

研究通过在游戏王对局中构建一个能再现停机问题的机制，来证明“计算机能否判定某策略为必胜策略”同样是不可能的。

具体方法是，使用游戏王的官方规则和实际卡牌，构筑出能代表计算机的卡组，从而在游戏盘面上再现图灵机。
首先，利用「八汰乌」的攻击，让对方无法抽新卡，制造出完全封锁行动的状态。在此基础上，将场地魔法“魔法都市恩底弥翁”上放置的魔力指示物，视为计算机的数据存储内存。

然后，通过「日全食之书」、「哥布林暴发户」、「神圣魔术师」、「神圣魔导王 恩底弥翁」等卡片，制造无限循环，自由增减魔力指示物的数量，从而在盘面上模拟程序的计算处理过程。此时设定一个胜利条件：如果计算处理能够完成（即停机），则跳出卡片循环，发动总攻击，赢得游戏。

如此一来，盘面就陷入了这样一种状态：我们无法知道它最终是会跳出循环获胜，还是会永远循环下去没有尽头。而根据停机问题的结论，在游戏开始前就完美预知最终结局，是不可能的。
既然计算的结局无法预先判断，那么依赖于此结局的“该策略是否为必胜策略”这一问题，也就永远无法得到解答。

也就是说，论文认为，既然能将绝对无解的停机问题完整地嵌入游戏王规则中，那么无论使用何种计算机，判定游戏王中某个策略是否为必胜策略都是不可能的（不可判定）。

超越停机问题：游戏王中“Π¹¹完全性”的证明

研究进一步证明，游戏王TCG中必胜策略的判定问题，其难度级别甚至超过了经典的停机问题，达到了任何计算机都无法解决的“Π¹¹完全”级别。

在数学领域，存在一个已被证明是Π¹¹完全性的难题，称为“NIS”。
研究团队在游戏王盘面上重现了NIS这个难题。具体来说，是通过组合“ Flint Lock”和“士气高涨”这两张卡，制造一个无限循环，使对方玩家每回合能按意愿无限恢复基本分。恢复的量即代表其选择的数字。
然后，接收对方输入的数字，并根据预设的计算机程序检查该数字是否正确。一旦发现错误，就用“闪电漩涡”清空对方场面，并直接攻击获胜。这样便制造出一种局面：对方若在某处无法给出正确答案，己方即可获胜；反之，若对方存在能无限持续输出正确答案的方法，己方则永远无法获胜。

因此，要回答“这个策略是否必胜”，就必须判断对方是否存在能无限输出正确答案的方法。
然而，判断“不存在无限延续正确答案的方法”这一问题，在数学上已被命名为“NIS”，且已被证明是任何计算机都无法解决的难题。

论文主张，既然NIS是任何现有计算机都无法解决的问题，那么针对游戏王中这个特殊盘面，要计算并判定给定策略能否获胜，同样是不可行的。

研究者还提到，此方法可能也适用于万智牌。论文中将游戏王称为当前最复杂的游戏，是因为这种方法的证明率先在游戏王上完成。这并不意味着其他卡牌游戏（如万智牌、宝可梦卡牌游戏等）不潜藏着同等的复杂性。