屏幕上的卡牌对局停在第 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 社区技术讨论