Programmable Cellular Automata
Ahmed Khalifa, Muhammad Umair Nasir, Matthew Siper, Steve James, Julian Togelius
cs.NE, cs.AI, cs.FL, cs.LG
2026-09-05
把元胞自动机拆成Python局部函数、可选全局函数和决策函数,用Claude 4.8 Opus进化。塞尔达零全局函数可玩率为0,加一条异步全局函数后可到99%。
元胞自动机靠格子之间的局部规则长出复杂结构,游戏里从 SimCity 到洞穴地图都用过。规则难写。Neural Cellular Automata 把规则换成卷积,表达力上来了,人读不懂。进化可以搜规则,搜出来的东西往往还是一堆权重。
马耳他大学、纽约大学和 Witwatersrand 把 CA 改写成可编程的:每个模块是一段 Python。局部函数看 3×3 Moore 邻域,全局函数(可选)看整张图,决策函数只吃这些函数的输出、不直接看格子,写出下一时刻的单元格。局部保持同步更新。全局改成异步,好让「已经放了一个玩家」这种计数立刻传到下一个格子。若全局计数同步冻结在 0,决策函数会在每个空位都塞一个玩家。
染色体是 l 个局部函数 + g 个全局函数 + 1 个决策函数,全部是 Python 字符串。写成代码而不是卷积核,是为了让人能读,也是为了让代码模型直接当变异算子用。交叉用均匀交叉,整段函数从父母之一抽。变异用 Claude 4.8 Opus,上限 4096 token,并且把其余函数和当前适应度当作上下文,逼模型改出能配得上现有模块的新函数。
适应度先看可玩性,再看多样性。每个生成器在 n=30 个固定随机初态上跑,每个初态最多 m=100 步;全部可玩才把输出之间的距离加进适应度,否则多样性一项是 0。这是级联适应度,避免一堆不可玩但彼此不同的垃圾图拿到高分。
实验落在 PCG Benchmark 三个游戏上。Binary 是 14×14 迷宫,要全连通且最短路至少 28 格。Zelda 是 11×7 地牢,至少 1 个玩家、1 把钥匙、1 扇门、3 个敌人,取钥匙再出门至少 18 步。Sokoban 是 5×5,1 个玩家、箱子和目标数量相等,A 解至少 10 步。超参扫 l∈{1,5,10,50}、g∈{0,1,5},3 个游戏 × 4 × 3 = 36 组,每组 5 个种子,共 180 次进化。种群 40、精英 10%、50 代、锦标赛规模 7、函数级变异率 10%。
全局函数是过不过关的开关,局部函数数量几乎不是。
| 游戏 | 0 个全局(l=1/5/10/50) | 1 个全局 | 5 个全局 |
| Binary | 100% / 100% / 97% / 99% | 98-100% | 98-100% |
| Zelda | 0% / 0% / 0% / 0% | 99% / 46% / 70% / 98% | 93% / 100% / 99% / 67% |
| Sokoban | 2% / 16% / 0% / 11% | 96% / 96% / 97% / 100% | 99% / 99% / 97% / 98% |
Zelda 在纯局部条件下四档全是 0,加一条全局函数后最高到 99%±1%。Sokoban 纯局部最高 16%±32%,加一条就到 96% 以上。Binary 太简单,纯局部已经接近满分。局部函数加到 50 并不稳定:Zelda 在 5 个全局、50 个局部时只有 67%±34%,5 个局部加 5 个全局反而是 100%。
迭代次数也降了。Sokoban 纯局部平均要 90-100 步,等于基本跑满预算;1 个全局函数、10 个局部函数时只要 6.863±4.806 步。Zelda 没有全局函数时表里是空的,因为根本找不到可玩关。Binary 反而在 1 个局部、0 个全局时最快(6.903±0.934 步),多加模块有时更慢,进化会把功能拆散或留下低效函数。
多样性数字不好看。PCG Benchmark 判定「互不相同」的比例全在 30% 以下,Sokoban 多数只有 7-12%。适应度却能到约 1.7,因为多样性项用的是距离,不是互异比例。Zelda 的最强生成器(50 局部 + 1 全局)视觉上更糟:把地图清空,再随机摆玩家、钥匙和门。多样性指标看的是最短路,物品换位置就能过关,关卡看起来却很无聊。
进化反复发现同一类函数。全局侧出现最多的是计数(Binary / Zelda / Sokoban 分别占 61%、61%、43%),其次是连通域大小。局部侧也是邻域计数最常见(100%、85%、66%),等于把 CA 收成「看周围有几个同类格子再决定」。这些函数平均只有大约 5 行。
对做程序化关卡生成的人,这篇把一个老观察写硬了:计数和连通这类全局量,用局部传播要横穿整张图,步数至少跟边长一个量级;给决策函数一条异步计数,问题直接变简单。用 Python 而不是卷积核,进化出来的规则人能读,三个游戏里反复出现同一批函数,等于顺便告诉你这些游戏的约束到底卡在哪。
它没有宣称打败了 NCA 或手工 CA。比较的是有没有全局函数、局部函数该设多少个。对只关心可玩性的小地图,1 条全局函数往往够用,50 条局部函数没有系统性好处。
函数每次只作用在一种格子上,写不了「玩家到钥匙的 BFS」。作者说这是为了让函数保持简单,但也把能搜到的程序空间砍窄了。
多样性目标没对准视觉差异。Zelda 过了路径长度就过关,生成器学会刷空房间加随机物品。作者建议改用 quality-diversity,这篇没做。
全局函数已经不是经典 CA。异步更新让计数立刻可见,这是性能来源,也是对「纯局部计算」的让步。隐状态通道、让函数返回 Dijkstra 图、把 LLM 输出卡到 128 token,都只在讨论里提了,没有实验。变异绑定 Claude 4.8 Opus,换模型会不会搜到同一批函数,未知。