
万智牌计算复杂度分析:图灵完备与指数级行为
来源标题:Exponential Behavior in Magic: The Gathering
万智牌因其图灵完备性和复杂机制构成巨大计算挑战,现有软件实现各有缺陷。Arena卡牌目录不全且匹配机制糟糕,MTGO界面过时且用户少,Forge的AI对局质量差。作者从数学和计算角度分析了游戏的指数级行为。
以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。
多年来,我一直对《万智牌》着迷,不仅因为它是一款极具乐趣且策略深度惊人的游戏,还因为它是一个数学与计算的空间。这款游戏极其复杂,甚至图灵完备,拥有错综复杂的关键词和令人生畏的大量机制,这为在计算机上运行该游戏带来了巨大的计算挑战,更不用说让机器来玩了。目前已有多个《万智牌》的软件实现;其中最为普及的是威世智自家开发的Arena,但它存在诸多问题:卡牌目录众所周知并不完整,缺失了游戏历史中大部分的卡牌;匹配机制,尤其是排位赛的匹配,简直糟糕透顶,而且游戏性能相当差,尤其是在堆叠上有很多东西的时候。MTGO解决了卡牌目录的问题,却引入了自身的问题,包括采用率低、界面相当过时且难以使用等等。与此同时,独立实现Forge乍看之下颇有前景——但AI表现相当差,多人模式bug频出且并未真正得到支持,界面不直观,而且性能仍不理想,即便比Arena有所改进。
早在2024年,我就开始构思改进《万智牌》AI表现的方法,但直到2026年中期才开始着手任何实现工作;我先评估了Forge,然后认定将Forge提升到足以作为《万智牌》本身强化学习实验环境的性能水平并不可行,于是决定实现自己的规则引擎Arcana。我寻思着,从第一天起就把多人模式纳入设计也是个不错的附加收获和动力。
我对《万智牌》着迷的根源之一,事实上也是这款游戏迄今尚未出现真正高性能且完整的软件实现的原因之一,在于游戏中异能的性质。《万智牌》中的异能可以指数级叠加,而当任何异能触发时可能发生的不同互动数量之多,导致了一种局面:尽管原则上状态的数量可能并非不可行,但为确保没有更多副作用必须放入堆叠而所需的检查数量同样呈指数增长,而众所周知,指数行为是我们这些凡人计算机科学家的敌人。我对《万智牌》指数行为的着迷,以一种意想不到的方式反过来咬了我一口。
我曾设计过的最喜欢的套牌之一,机制上非常简单,计算复杂度上却极为残暴。它围绕一张臭名昭著的牌:Scute Swarm。要解释这套牌如何运作,我们需要先了解一些《万智牌》内部机制的背景知识。
《万智牌》的核心数量是生命;它可以被视为玩家的分数,或者玩家表现好坏的浓缩体现。每位玩家起始拥有20点生命,赢得游戏的主要方式是在自己的生命值被降到0(或以下)之前,将对手的生命值降到0(或以下)。游戏中有不同类型的卡牌可供使用,在任何给定的回合中,玩家可以使用由地——游戏中构成基础货币的卡牌类型——所提供的资源,在游戏的限制和规则范围内部署任何他们想要部署的东西。
或许最重要的卡牌类型是生物。它们相当于大多数集换式卡牌游戏中的原型卡牌,比如Pokemon;它们可以攻击对手并防御对手的攻击。Scute Swarm就是生物的一个例子。
还有衍生物,它们是特殊卡牌,由其他卡牌的异能产生,而非你打出的卡牌。你可能会用一张牌来获得一个衍生物,但你不会在你构筑的套牌中放入衍生物,也可以说你永远不会手中有衍生物。这里的实际机制有些复杂,但大体上是:衍生物是作为某种异能的结果而存在,而非直接来自玩家的手牌或牌库。
Scute Swarm或许是《万智牌》中展现指数行为的最臭名昭著的例子。它拥有这样的异能:当一张新地牌被部署时,将自身复制品的数量翻倍。实际上,这通常会被早期反制,因为《万智牌》提供了许多不同的方式来避免这种指数增长成为现实(而一旦大幅成为现实,打出Scute Swarm的人几乎 invariably 会获胜)。我意识到,如果将此与每当有新生物进入战场时便产生生命增益的卡牌结合起来,那么就会拥有指数增长的生命值。更糟的是,还可以使用一个神器,使每当任何衍生物被创造时其数量翻倍,再加上某种能持续翻倍生命增益的东西。看起来像是个相当大的漏洞,对吧?
从算术上讲,第六张地是关键。在六张地以下时,Scute Swarm生成一个普通的1/1昆虫。当有六张或更多地且异能结算时,它会生成一个具有相同地落异能的复制品。让每张地的触发在下一张地落下之前有时间结算,每一个新复制品都能为下一批助力。
假设Soul Warden和Essence Warden都在战场上。每张都会为每个新的Scute Swarm给你一点生命。加上一个生命增益翻倍器,每次到来就是四点生命,再加上一个衍生物翻倍器,每个现有的Scute Swarm会制造两个新的。在这些假设下,八次地落能给你带来什么,如下所示。
一个Scute Swarm,两个Warden,一个衍生物翻倍器,一个生命增益翻倍器。
场上已有六张或更多地。
scutes = 1 life_gained = 0 for _ in range(8): new_scutes = 2 * scutes scutes += new_scutes life_gained += 4 * new_scutes
6,561个Scute Swarm;获得26,240点生命。
(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。