又写了一个生命游戏搜索程序

1969到1970年,在创造生命游戏的过程中,约翰·康威和他的同事们在棋盘上进行了各种试验和搜索,并发现了最初的四种飞船:滑翔机轻型飞船中型飞船重型飞船

此后二十年间,通过手动搜索,或者借助计算机的帮助,人们又发现了大量的图样:静物,振荡子,Puffer……但所发现的飞船只是以上四种飞船的组合或变种,或者只是在飞船后面添上一个 tagalong。此时没有真正的搜索程序,计算机在搜索中的用法和棋盘没有本质区别。

直到1989年,Dean Hickerson 用汇编语言写了一个叫 LS 的小程序,并用它发现了第一艘全新的飞船:64P2H1V0。此后,David Bell 又用 C 语言实现了 Dean Hickerson 的算法,写出了 lifesrc。人们用 LS 和 Dean Hickerson 发现了大量的新飞船,以及别的图样。可以说,这两个程序开启了生命游戏研究的一个新时代。

(有点想写一系列文章来详细介绍生命游戏搜索的历史……不过我懒。)

Dean Hickerson 的算法并不复杂,就是简单的回溯法。程序中每个细胞有死、活、未知三种状态。最开始的时候搜索范围内的每一个细胞都设成未知,范围外的则设为死。搜索过程就是取一个未知的细胞,给它设一个值(死或活),并根据生命游戏的规则由它的值推导出另一些细胞(此细胞的前一代、后一代、邻居等)的值,由那些值又推出更多细胞的值……如果推导的时候发现矛盾,则退回来,把原来的未知细胞换成另一个值;如果没有矛盾,则寻找下一个未知的细胞,继续此过程。

Dean Hickerson 给这个算法写了一个详细的介绍。David Bell 把这一介绍附在了 lifesrc 的源代码中。

此后又出现了很多更先进的搜索程序,比如说 David Eppstein 的专搜飞船的 gfind,以及它的诸多变种:ofind、afind、zfind、qfind 等……它们的算法也更加复杂。

(我有点后悔给 LifeFind 起这个以 find 结尾的名字了,它的算法明明更接近 lifesrc。)

我写的下面这个程序,基本就是照抄 lifesrc,只不过把用的编程语言换成了 Rust,并且编译成 WebAssembly,在浏览器中就能运行。

用法很简单,按照说明调整图样的规则、宽度、高度、周期、平移等信息,然后点击 “Set World” 来确定这些信息。然后点 “Start” 就可以搜索了。速度不快,需要耐心等待。

我基本不懂编程,写得非常糟糕,和原版的 lifesrc 相比缺少了很多功能,不过支持 isotropic non-totalistic 的规则

此外,lifesrc 给未知细胞选取的新状态总是死,我则添加了总是活、随机选取、“Smart” 三种模式;这里的 “Smart” 表示第一行/第一列的细胞随机选取,其余的细胞总是死。其实这一点也不智能,不过我想不出别的名字了。这个模式适合搜索比较窄但可能很长的图样,但未必比随机选取更快。

这个网页版比 lifesrc 慢了不少;但如果编译成机器码,在电脑上运行,会比 lifesrc 还略快一些,不过还是比 gfind 及其变种要慢很多。

源代码和具体的介绍见这里。

最后是我用这个程序找到的一艘 2c/5 飞船:

x = 38, y = 19, rule = B3/S23
5bo2bo$b2ob2o5bo6bo3bo9bo$2obo7bo5bo2b2obo7b4o$bo2b6ob3obobo11b2o4bobo
$2bo7bo4bobo2b2o2b3obo2b3ob2o$3b3o2bobo4bob3o3b2o3bo4bo3bo$5bo2bobo3bo
3b2o3bo4bobob2o$10b2ob3o2b2o4bobo4bo4bo$25bo6b3o2$25bo6b3o$10b2ob3o2b
2o4bobo4bo4bo$5bo2bobo3bo3b2o3bo4bobob2o$3b3o2bobo4bob3o3b2o3bo4bo3bo$
2bo7bo4bobo2b2o2b3obo2b3ob2o$bo2b6ob3obobo11b2o4bobo$2obo7bo5bo2b2obo
7b4o$b2ob2o5bo6bo3bo9bo$5bo2bo!