任何曾经尝试过玩的人 万智牌：聚会 或者听朋友向他们解释它必须考虑所有复杂规则和更令人困惑的卡片的学习曲线。人类玩家可能不是唯一感到不知所措的人： 一篇新的研究论文 认为游戏非常复杂，甚至在某些情况下计算机理论上无法弄清楚如何获胜。
一组研究人员认为 万智牌：聚会 事情是如此复杂，在某些情况下，计算机不可能找到一种万无一失的获胜方法。他们写道：“这种结构表明《万智牌》是文献中已知的计算最复杂的现实世界游戏。”
该团队包括棋盘游戏设计师亚历克斯·丘吉尔、佐治亚理工学院研究员斯特拉·比德曼和宾夕法尼亚大学沃顿商学院预算模型计划高级分析师奥斯汀·赫里克，他们想看看这个幻想到底有多复杂。纸牌游戏是从计算的角度来看的。 他们最终发现了什么 那是 万智牌：聚会 它不仅比大多数其他游戏更复杂，而且在某些情况下实际上是不可计算的。目前尚不清楚到底有多少这样的情况，但目前可以想象，在某些比赛中，算法无法找出获胜的最佳路径。
该研究基于对两套遗留代码进行编码 万智牌：聚会 卡片，涵盖游戏的整个历史，不包括某些被禁止的卡片，并创建一个数学模型来在游戏规则的背景下解释卡片，以根据打出的卡片和顺序返回未来的棋盘状态。正如您从下面的牌组列表中看到的那样，所使用的牌是游戏历史上一些较复杂的牌。
例如，清洁光束会对目标生物和与其具有相同颜色的其他生物造成两次伤害。与此同时，如果您控制每种基本地类型的地和每种颜色的生物，联盟胜利会自动让您赢得游戏。然后是幻象增益，这是一种光环，会自动附加到对手使用的每个新生物上并将其置于您的控制之下。这些卡片效应与其他效应相结合，创造了足够多的替代可能行动方案，以至于研究团队的模型无法返回结果。
在国际象棋中，计算一方如何获胜需要消耗大量资源。国际象棋的前两步走完后，有 400 种不同的可能结果。 第六次之后，有1.21亿 。不过，理论上仍然可以计算。根据这些研究人员发现的不可计算的案例，情况并非如此 万智牌：聚会 ，尽管事实上它是一款使用预制牌组的两人零和游戏，这使其在该领域目前研究的所有其他游戏中独一无二。
作者写道：“这是第一个结果，表明存在一种现实世界的游戏，其获胜策略的确定是不可计算的。”
当然，这并不适用于任何游戏 万智牌：聚会 。研究人员根据某些要求探索了一套非常具体的牌组和起手牌。例如，套牌“专门使用具有强制效果的牌”，这意味着它们不包括玩家可以从各种可能结果中进行选择的牌。但根据传统格式的规则，所有使用的牌都是锦标赛合法的。
虽然这项研究对博弈论和计算机科学研究具有潜在影响，但它也清楚地表明了发现的巨大潜力 魔法 。 “最优战略游戏的全部复杂性仍然是一个悬而未决的问题，就像许多其他计算方面一样 魔法 ，”他们的作者写道。 “例如，在万智牌的某些棋盘状态下，玩家似乎有无限多的可用动作……[这]有可能极大地影响我们理解游戏并将其建模为一种计算形式的方式。”
最终，它似乎适合一款基于多元宇宙的游戏，其规则具有无限的可塑性。
[更新 - 6:16, 5/8/19]： 出版后不久，亚历克斯·丘吉尔 论文作者之一回应道 唐泽 在一封电子邮件中进一步澄清了该小组的调查结果。
“ 我们已经证明的是“在万智牌游戏中找到最佳走法”的操作， 在最坏的情况下，无法计算，”他说。 “ 在某些情况下，尽管它们非常人为，但事实证明没有算法可以确定是否存在获胜的举动。事实上，由于我们消除了所有玩家的选择，我们已经证明了一些稍微更强的东西：在一般情况下，算法不可能查看棋盘状态并查看游戏是否有可能结束。”
他接着说：
“ 这就是计算机科学家在谈论算法的复杂性时所关心的。该算法在几乎所有情况下都可能很容易解决，但我们已经证明，最坏的情况也非常困难。”
“这对实践中玩游戏的影响很小，但它确实对潜在的人工智能设计师有启发。也许任何要为万智牌编写人工智能的人都不会通过尝试详尽地计算当前棋盘状态的所有可能后果来让人工智能选择下一步行动——那太疯狂了。他们会使用启发法和经验法则来最好地猜测如何玩。我们的论文只是证明穷举计算方法绝对不是可行的方法，因为它实际上是不可能的（在某些情况下）。”
留言