算法与理论计算机2019arxiv.org
Magic: The Gathering 是图灵完备的
Magic: The Gathering is Turing Complete
进阶 · 约 45 分钟读完前置知识：图灵机与可计算性基础、不可判定性概念、万智牌基本规则与卡牌机制
导读
这篇论文证明《万智牌》（Magic: The Gathering）在允许使用特定卡牌组合时是图灵完备的：玩家可以搭建出一台能模拟图灵机的牌局，因此从原则上说，万智牌不存在能判定任意局面胜负的通用算法，游戏整体是不可判定的。作者通过构造性地给出卡牌组合来实现这一模拟。
HN 关注点：HN 读者一方面惊叹于用卡牌游戏规则搭建图灵机的巧妙构造，另一方面也讨论这类结果早已在玩家圈流传、以及万智牌作为 AI 下一个挑战的复杂度。
HN 评论精选
这几条评论里：补充 4
补充结果并非全新，此前已在社区流传并上过 HN
我觉得这条能上新闻只是因为论文挂到了 arXiv 上，这个结果其实早就有人知道了。比如一年前就有过相关提交：https://news.ycombinator.com/item?id=15712377
yorwba查看英文原文
I guess this is newsworthy because a paper was put on arXiv, but the result has been known for a while. See e.g. this submission a year ago: https://news.ycombinator.com/item?id=15712377
补充万智牌是非确定、部分可观测、对抗性的巨大动作空间，是 AI 的下一个难题
关于 AI 的一些想法：在象棋、围棋和星际争霸1之后，万智牌绝对是 AI 值得挑战的下一个游戏。虽然存在一些固定的打法套路，但可能的动作空间极大，而且卡牌之间有大量协同互动需要考虑。从 AI 的角度看，万智牌还非常难，因为它是：非确定性的、部分可观测的、对抗性的。
vaylian查看英文原文
Some thoughts about AI: After Chess, Go and StarCraft 1, Magic is definitely an interesting game for AI to tackle next. While there are certain play patterns, the space of potential actions is extremely large and there is a great number of synergistic interactions between cards that needs to be taken into account. From an AI perspective Magic is also very hard because it is: * Non-deterministic * Partially observable * Antagonistic
补充演示显示机器搭好后玩家没有选择余地，状态演化是确定性的
这里有个演示：https://www.youtube.com/watch?v=pdmODVYPDLA 看之前我没意识到——有意思的是，虽然棋盘状态极其复杂，但游戏状态和动作是确定性的，比如机器搭好之后玩家其实没有任何可做的选择。
bentona查看英文原文
Here's a demo: https://www.youtube.com/watch?v=pdmODVYPDLA Didn't realize this before watching, but it's interesting that there's an incredibly complicated board state but the game state / actions are deterministic, e.g. the players don't have any choices about what to do once the machine is set up.
补充用具体无限 combo 例子说明万智牌规则为何能产生图灵完备所需的无限计算
我一直在想万智牌有那么多无限连招。在一副卡牌种类丰富的牌组里，你很可能无意中就凑出一个无限 combo。给不玩的人解释：最经典的无限 combo 用两张牌，第一张说“每当你获得生命时，对手失去等量生命”，第二张说“每当对手失去生命时，你获得等量生命”。这两张牌单独组合什么也不做……直到你获得生命或对手受到伤害，之后它们的组合效果会形成连锁反应，一直重复到对手死亡、你获得与其生命等量的生命。万智牌里有各种各样的无限 combo：有的是一张“横置产生一点法术力”的生物配合一张“支付法术力以重置一个生物”的牌，从而无限次地横置与重置；有的把牌退回手牌再重施，靠重施获得的资源再退回手牌再重施；还有的从弃牌堆里反复循环一张牌。没有单卡无限 combo（那大概过不了测试），但双卡 combo 很多，三卡、四卡 combo 的数量则组合式地增长。我觉得从计算的角度看，图灵完备和“能构造出无限 combo”的能力之间有某种相似性。
swagasaurus-rex查看英文原文
I was thinking about how Magic the Gathering has so many infinite combos. In a deck with a wide variety of cards, you're likely to be able to accidentally construct an infinite combo. For those who don't play, the most iconic infinite combo involves two cards, the first says "Whenever you gain life, an opponent loses that much life.", the second card says "Whenever an opponent loses life, you gain that much life." These cards, when combined, do nothing... until you gain a life or an opponent takes damage. Then their effects combined means a chain reaction that repeats until your opponents are dead and you have gained as much life as they had. There's a variety of infinite combos in MTG. Some of them involve a creature that says "Tap to add mana to your mana pool" combined with another card that says "Pay mana to untap a creature", allowing you to tap and untap an infinite number of times. Some infinite combos involve returning a card to your hand, and recasting it which gives you the resources you need to return it to your hand and recast again. Some infinite combos involve looping a card from your discard pile repeatedly. There are no one-card infinite combos (that would likely not make it past the testers), but there are plenty of two-card infinite combos, and an combinatorically increasing number of three and four card infinite combos. I think there is some similarity computationally speaking between turing completeness, and the ability to construct an infinite combo in a game like MTG. An infinite allows you (the player) to continue taking the same action over and over again, accumulating some game resource in the process. This bears resemblance to the infinite tape Turing envisioned, a way to hold data. Player actions are much analogous to the instruction set. Infinites that are optional for the player (not all infinites in MTG are optional once the pieces are on the board) can also stand in for conditional statements - a key requirement of turing completeness. I'd be interested in seeing the bare minimum number of cards required to generate turing completeness. If anybody else knows more about this domain, I would love to hear their opinions.
相关资源
从这篇论文所有 HN 讨论帖的全部评论里整理出来的链接。
- 视频与演讲
- 评论区提到的论文
- Hanabi 挑战：AI 研究的新前沿被提到 2 次
历次讨论
- 2019Hacker News 讨论帖192 分 · 192 评
- 2022Hacker News 讨论帖11 分 · 1 评
- 2023Hacker News 讨论帖23 分 · 5 评
同领域还值得读
哲学家为何应关注计算复杂性
Why Philosophers Should Care About Computational Complexity (2011)
Scott Aaronson 的这篇长文论证计算复杂性理论（如 P vs NP、停机问题的复杂度视角）对哲学问题（如知识的本质、中文房间、水槽论证等）具有实质意义，而不仅是技术细…
算法与理论计算机2015 · 552 分 · 120 评进阶 · 约 90 分钟编辑精选通信的数学理论
A Mathematical Theory of Communication
是香农1948年的《通信的数学理论》，为通信建立数学框架：把信息量定义为不确定性或自由度（信息熵），并讨论信源编码、信道容量与可靠传输。
算法与理论计算机2020 · 495 分 · 91 评进阶 · 约 120 分钟编辑精选物理、拓扑、逻辑与计算：罗塞塔石碑
Physics, Topology, Logic and Computation: A Rosetta Stone (2009)
用范畴论充当“罗塞塔石碑”，试图在量子物理、拓扑、逻辑与计算四个领域之间建立统一的结构性类比：物理中的量子过程、拓扑中的配边、逻辑中的证明和计算中的程序，都可被视为某类范畴中的态…
算法与理论计算机2009 · 390 分 · 55 评 · 引用 13专业 · 约 180 分钟编辑精选一种快速、极小内存的一致性哈希算法
A Fast, Minimal Memory, Consistent Hash Algorithm
论文给出一种快速、省内存的一致哈希方案，目标是在桶数量变化时保持较小的键迁移成本，同时降低计算和内存开销。
算法与理论计算机2014 · 327 分 · 57 评 · 引用 4进阶 · 约 25 分钟编辑精选第五个 Busy Beaver 值的确定
Determination of the fifth Busy Beaver value
宣布确定了第五个 Busy Beaver 值 BB(5)：即 5 状态图灵机中停机前运行步数最多的机器（Champion）在 47,176,870 步后停机。
算法与理论计算机2025 · 288 分 · 116 评 · 引用 1专业 · 约 75 分钟编辑精选