7000只僵尸拖垮程序:人一眼能赢,电脑为什么卡死

7000只僵尸拖垮程序:人一眼能赢,电脑为什么卡死

游戏开发Rust算法系统架构

数据源:HN + web research

屏幕上的卡牌对局停在第 58 回合。一方场上挤着 7,258 只僵尸,防守方只剩 31 点血。只要派出 16 只僵尸冲过去,战斗就结束了。规则程序单次结算卡了 35 秒,最后只派出一只僵尸摸了一下对手。

这是开发者 Levi Neuwirth 测试规则引擎 Arcana 时的遭遇。他用 Rust 语言写了这套引擎,用来测试卡牌 AI 算法。他安排了 64 套主流牌组,运行了 403,200 局自动化对战。测试跑完,9 个任务撞上两小时上限,被系统强制中止。

代码本身没有任何死循环。真正拖垮系统的,是卡牌机制引发的指数级膨胀。成千上万个生物同时挤在场上,微观穷举瞬间吃光了算力。

万智牌在数学上早就被证明图灵完备。但工程落地是另一套维度的挑战。人类一眼就能算清胜负,程序却要为每个生物重新扫描全场。玩家喊一句全员进攻,落到代码里就是几百万个分支。

8 次落地下出 6000 害虫,卡牌效果开始指数狂飙

万智牌诞生于 1993 年。每张卡牌都带有特殊规则,能随时改写基础规则。当几张具有连锁效应的卡牌凑在一起时,数值会迅速脱缰。

卡牌「群行虫群」(Scute Swarm)是典型代表。只要场上下下一块地,它就会复制一个自己。一个变两个,两个变四个,每一次行动都在翻倍。

测试中它与回血单卡、随从翻倍神器凑在了一起。连续 8 次下地后,场上生出了 6,561 只虫群。玩家生命值甚至冲到了 26,240 点。正常比赛只有 20 点血,这个数字击穿了常规桌游的承载极限。

生长曲线对比 图:Scute Swarm 与莉莲娜徽记的指数增长对比,纵轴每格代表十倍膨胀。来源:Levi Neuwirth

人类面对面打牌时,拿两个骰子代表几千只虫子就能结案。程序却必须在内存里,为 6,561 个实体逐一分配数据结构。

一回合算 35 秒,翻倍机制把内存吃空了

虫群虽然凶猛,一张清场法术就能解决。真正把引擎拖垮的,是旅法师角色莉莲娜的终极技能。这项技能会在场外留下一个无法消除的永久徽记。

徽记规则很简短:每个自己回合结束,制造现有僵尸数加 2 的新僵尸。下一轮僵尸数量等于上一轮的两倍加二。仅仅经过 8 次结算,场上就累积出 510 只僵尸。

即便对手施放法术清场,印在指挥官区的徽记依然无损。下个回合两只新僵尸入场,翻倍链条重新启动。这种无法消除的自增循环,成了规则系统的噩梦。

Neuwirth 调出卡死对局进行逐帧分析。第 52 回合,单次徽记结算耗时 1.72 秒。第 54 回合,耗时增加到 7.78 秒。第 56 回合,耗时直接飙升到 35.15 秒。

结算耗时曲线 图:场上僵尸数量每次翻倍,单次状态结算耗时扩大约 4.5 倍。来源:Levi Neuwirth

僵尸数量翻倍,单次结算耗时扩大约 4.5 倍。算法复杂度呈现超线性恶化。新生物入场后,引擎都要遍历全场,校验所有被动技能。成千上万个对象两两相交,让规则验证变成了计算泥潭。

手握 7000 僵尸大军,搜索上限却只够派单兵

战局推进到第 58 回合,僵尸总数达到 7,258 只。防守方只剩 31 点生命,场上没有足够的阻挡者。只要 16 只僵尸冲过去,造成的 32 点伤害就足以拿下比赛。

荒诞的一幕在此时发生了。AI 思考良久,最终只派出一只攻击力为 2 的小僵尸。它软绵绵地打了一下对手的随从。坐拥七千大军的优势方,主动放弃了斩杀机会。

对局回放界面 图:第 58 回合回放界面,单堆僵尸达到 7,234 只,对手仅剩 31 点生命值。来源:Levi Neuwirth

症结出在方案生成器的保护逻辑上。几千个生物进攻多个目标,组合空间呈天文数字膨胀。为了防止超时,作者在代码里设置了 1,024 条方案上限。

生成器优先列举单兵进攻方案。当场上有 7,258 只僵尸时,仅单兵出击的排列就塞满了 1,024 个名额。包含全员出击的群体进攻方案,排在后面根本没机会生成。

第 44 回合有 58 个生物,生成了 229 种方案。其中有 4 种方案包含了多个生物协同进攻。到了第 50 回合方案顶死在上限,多生物方案归零。防范卡死的保护逻辑,反过来遮蔽了制胜选择。

人类靠直觉一眼看穿,电脑在几百万个分支里迷路

人类选手面对这种局面,处理逻辑截然不同。就算场上有一万只僵尸,人类也不会去算每个僵尸的站位。总攻击力远超对方血量,直接全员进攻就能以常量时间结束战斗。

计算机程序缺乏这种宏观抽象能力。引擎严格遵循微观视角,老老实实把每个实体解构成数据结构。当只有几只生物互相对攻时,这种遍历确保了判定的绝对精准。

规模一旦突破临界点,微观穷举就会变成沉重负担。每个合规的细碎循环累加在一起,耗光了所有算力。电脑并未变笨,它只是困在了无意义的微观细节里。

理论完备与工程可行,中间隔着一道深沟。万智牌允许卡牌随意改写底层行为,赋予了牌局无限生机。这种自由一旦碰上指数繁殖,就将规则模拟推向了失控边缘。

给战场设定 500 熔断线,让失控实验重新运转

为了让大规模自动化测试跑下去,Neuwirth 实施了工程修补。他在环境中引入了熔断规则:永久物超过 500 个,判定失控并记平局。

熔断机制生效后,测试立刻恢复了运转。原本卡死两小时的对局,新机制仅耗时 0.16 秒。它在 576 个永久物处被安全中止。为无限膨胀设定物理边界,是保障全局进度的首要手段。

更深度的重构也在推进。引擎开始对高频触发状态进行缓存,避免每次生成衍生物都重扫全场。方案生成算法也预留了名额,优先把全军出击等宏观选项塞进队列。

7,258 只僵尸跑死程序的事故,标出了规则模拟与真实智能的边界。计算机在微观分支上疾速遍历,人类依靠宏观常识切中要害。规则允许指数级无限繁衍时,缺乏宏观视角的代码注定失控。它算清了每一个微小的分支,却被自己吐出的数字海洋死死困住。

参考链接:

  • Levi Neuwirth 技术博客原文
  • Arcana 开源规则引擎代码仓库
  • Hacker News 社区技术讨论