当 Magic: The Gathering 遇上指数爆炸
Exponential Behavior in Magic: The Gathering

我长期痴迷于 Magic: The Gathering 的数学与计算深度,甚至决定自研规则引擎 Arcana 来探索其 AI 潜力。然而,游戏中某些卡牌的机制设计导致了令人头疼的指数级复杂度。以 Scute Swarm 和 Liliana, the Last Hope 为例,这些卡牌能引发连锁反应,使生物数量或生命值呈指数增长,给引擎的性能带来巨大挑战。在一次大规模随机测试中,仅 Liliana 的一个回合结算就耗时35秒,这揭示了指数行为对计算机科学家而言是致命的敌人。
正如我们所知,指数行为是我们这些凡俗计算机科学家的敌人。
HN 评论区
21- world2vec
题外话:刚才有一瞬间我还以为是 gwern 的网站呢。
- khaliostr
最近开源 Magic 社区似乎正在经历一场复兴,我觉得这非常酷。
Forge 已经存在很久了,但我们要通过 WASM 在浏览器中运行它,也就是 Manabrew [1]。我是维护者之一,我们主要开发它是因为想要一种更友好的方式来和朋友们一起玩 Commander 模式。
与此同时,Phase 和 Ironsmith 正在用 Rust 开发新引擎,Gorge 正在用 Go 构建引擎,同时还开发了机器人和跨引擎测试工具,大家也开始在不同项目间进行协作。
Magic 是一款实现起来极其困难的游戏,我觉得这么多人在业余时间攻克它,简直令人惊叹。
如果你喜欢 Magic 又懂软件工程,欢迎来和我们一起交流。这里有很多事情在做,也有 plenty 的空间让更多人参与进来 :)
- amluto
理论上,这个问题应该可以通过一个引擎来解决(至少大部分情况),该引擎可以追踪给定卡牌或卡牌堆(包括卡牌及其附带的指示物等)的副本数量。
我说“大部分”是因为:
- 肯定存在某种方式,可以生成 N 个带有不同数量指示物的 token 生物,使得仍然有指数级数量的不同卡牌堆。
- 一个增长足够快的牌堆可能需要指数级(甚至更多)的比特位来存储。
但至少,OP 中提到的这个特定问题是可以被解决的。