生命游戏模拟程序：上帝之数的Java代码亦可见

最初由Tomas G.于2006年4月1日发表。Tomas G.是生命游戏模拟软件Golly的作者之一，也参与了生命游戏的许多重要发现。 在《生命游戏》之外，他最广为人知的成就是证明了魔方的“神数”是20。

该算法的发明者是比尔。 他也是生命游戏中许多重要模式的发现者，其中包括第一个无限生长模式——滑翔机枪。

原文地址：An for Space and Time

原文和附件中的Java代码也可以在这个repo中找到：/mafm/

加速一个缓慢的程序既有趣又困难。 但有时新方法可以带来令人惊讶的改进。

加速一个缓慢的程序既有趣又困难。 通常，您能做的最好的事情就是使用常量使运行速度提高两倍或最多四倍； 例如，许多读者可能已经自己实现了约翰·康威的《生命游戏》。 该程序利用位运算的加速效果是非常明显的。 。 但有时采用新的算法，仅仅添加一些简单的优化就可以带来惊人的改进。 他发明的一种简单的“”算法结合了四叉树和记忆化，大大加快了生命游戏模拟器的进化速度。 在这篇文章中，我将从最简单的生命游戏模拟程序开始，一步步介绍这个算法，解释它的工作原理，并用这个算法推演一些“生命游戏小宇宙”到万亿代、亿万年。 细胞。

马丁·加德纳 ( ) 自 1970 年 10 月起在《科学美国人》上发表的《生命游戏》专栏影响了一代程序员； 生成一个由二维生命体组成的神奇世界只需要一些简单易实现的规则。 所谓生命游戏（图1）是一种单人游戏，其中有一个无限的二维网格。 这个网格中的每个网格都居住着一个活细胞（图中黑色圆圈表示）或死细胞。 。 任何有两个或三个活邻居的活细胞（即其周围直接相连和对角相连的八个细胞）将保持不变，少于两个或多于三个会导致细胞死亡。 任何具有三个活邻居的细胞都会生成一个新的活细胞。 这些规则是全线同时执行的（译者注：而不是顺序执行）。 这些规则可以产生一些进行稳定、有规律振荡的生命形式——宇宙中有自行移动的“滑翔机”和“船”，也有无限生长或完全死亡的生命形式。 最初的状态只有九个活细胞，经过数千代的进化，产生了一个混乱的活动区域，不断地喷出滑翔机和一个大型稳定的“动物园”。

图 1：生活中的一些例子。 左边是稳定的“面包”图案。 左上方是周期 2 振荡器“闪烁”的两个阶段。 从左下到右上的对角线是“滑翔机”飞行过程中的四个阶段。

“生命游戏”最简单的实现就是用两个二维数组来表示宇宙的一部分。 每一代，统计旧数组中每个单元格的存活邻居，将模拟的结果按照规则放入数组中，然后将新数组的内容复制回旧数组并更新屏幕。 这种方法有几个缺点：游戏宇宙越大，程序模拟就越慢； 但如果游戏宇宙太小，就会影响其中生命的发展。 改造算法的第一步就是用无限的宇宙代替有限的宇宙； 无边意味着它在任何给定时刻都是有限的，但在需要时可以无限扩展。 我使用称为“四分之一树”的简单树表示（参见图 2）。

图 2：4 x 4 网格的四叉树表示，其上绘制有“面包”图案。

在这个四叉树中，每个节点对应于平面上的一个正方形“块”。 树的叶节点对应于只有一个单元的“块”，1（活着）或0（死）。 非叶子节点表示的每个大正方形区域由其四个子节点表示的区域组成，这些子节点根据它们相对于大正方形中心的方向来命名：西北的小正方形称为nw，东北方的小广场称为ne。 ，等等等等。 我们将节点到叶节点的距离称为级别（叶节点位于级别 0）。 第 n 层的节点表示边长为 2^n 的正方形。

（在四分之一树上）模拟生命最暴力的方法是编写一个递归函数，要么就地更新四分之一树，要么返回一个全新的树。 这里我使用后者。 如果返回的树（根节点）也处于同一级别，则算法将非常简单。 不幸的是，如果没有额外的信息，这是不可能的。 这是因为该节点的邻居也会影响其下一代边界单元的计算。 一种解决方案是传入同一层的所有相邻节点； 另一种解决方案是维护相邻节点指针。 不过，我选择了更简单的做法：函数只需要返回节点中心区域的演化结果。 例如，函数输入的节点在第二层，代表一个4 x 4的正方形，返回的节点在第一层，代表可以直接从这个4计算出来的下一代2 x 2区域x 4 平方。 再比如，如果输入节点的第五层代表一个32 x 32的区域，则将返回中心第四层的16 x 16区域的下一代。 这样，假设您喜欢使用它，您就可以在不可变的数据结构上进行函数式编程。

大多数树上的递归算法都会遍历所有子树，然后合并结果。 如果我做同样的事情，请参阅代码片段 1，将会出现图 3 所示的空白。 我们需要一些更先进的方法。 当前递归调用中已经存在的节点无法使用，而是需要翻译出一些新的临时节点来获得我们需要的中心区域的演化结果。

// 代码段 1

class Node {
   Node nextGeneration() {
      if (level == 2) {
         ... do base case through normal simulation ...
      } else {
         return new Node(nw.nextGeneration(), ne.nextGeneration(),
                       sw.nextGeneration(), se.nextGeneration()) ;
      }
   }
}

图 3：简单递归算法失败的原因。 外面的黑框代表节点的边缘； 四个红色框是它的子节点。 现在我想计算下一代的图中的蓝色盒子区域，但是四个红色盒子节点的中心是绿色盒子，它们加在一起并不是需要的蓝色盒子。

总共需要创建9个新的二级子节点节点。 事实上，这些节点是由原始节点的第三级子节点组成的。 我们将这9个节点组合成4个重叠的一级子节点，然后用它们进行递归。 这4个一级子节点的进化结果节点放在一起就成为原节点的进化结果节点。

图 4：上述空白问题的解决方案。 将现有节点的部分重新组合成新的节点来计算我们想要计算的节点的下一代。 蓝色框依然是我们要计算的面积； 我把它分成了四个绿色节点。 我们可以从原始节点的子节点构建 9 个红色节点，并且可以从这些红色节点的组合计算出 4 个蓝色节点。 （译者注：原文可能有错误。）

在代码片段 2 中，为了实用性，我做了一个小小的让步。 每当我知道一棵树完全为空时，我就会通过共享节点来构建它，见图4。（译者注：该实现确实会处理空节点，但在代码片段2中没有反映出来。）当我计算下一代任何节点，我首先检查它是否为空，如果是，则立即返回一个空子树。

// 代码段 2

Node centeredSubnode() {
   return new Node(nw.se, ne.sw, sw.ne, se.nw) ;
}
Node centeredHorizontal(Node w, Node e) {
   return new Node(w.ne.se, e.nw.sw, w.se.ne, e.sw.nw) 
;
}
Node centeredVertical(Node n, Node s) {
   return new Node(n.sw.se, n.se.sw, s.nw.ne, s.ne.nw);
}
Node centeredSubSubnode() {
   return new Node(nw.se.se, ne.sw.sw, sw.ne.ne, 
se.nw.nw) ;
}
Node nextGeneration() {
   if (level == 2) {
      ... do base case through normal simulation ...
   } else {
      Node n00 = nw.centeredSubnode(),
           n01 = centeredHorizontal(nw, ne),
           n02 = ne.centeredSubnode(),
           n10 = centeredVertical(nw, sw),
           n11 = centeredSubSubnode(),
           n12 = centeredVertical(ne, se),
           n20 = sw.centeredSubnode(),
           n21 = centeredHorizontal(sw, se),
           n22 = se.centeredSubnode() ;
      return new Node(
         new Node(n00, n01, n10, n11).nextGeneration(),
         new Node(n01, n02, n11, n12).nextGeneration(),
         new Node(n10, n11, n20, n21).nextGeneration(),
         new Node(n11, n12, n21, n22).nextGeneration());
   }
}

到目前为止我的算法还没有起到任何作用。 它占用更多空间，运行速度更慢，并且会创建一堆需要回收的新节点。 其递归流程也很复杂。 但所有这些问题只需两步即可解决：节点合并和记忆。

四叉树（见图 5）比简单的四叉树占用更多的空间（尽管它只是一个巨大的常数）； 例如，存储一个256 x 256的宇宙，只有两个状态为0和1的叶子节点，总共有65535个，非叶子节点有16384+4096+1024+256+64+16+4+1个，即21845。每个节点代表的内容是无法修改的，所以多个节点内容相同是完全没有意义的！ 所有1叶节点可以合并为一个公共1叶节点； 类似地，所有左上角为1、其他角为0的节点也可以合并为一个公共节点，一直合并到根节点。 为了合并这些节点，需要打开一个哈希表。 节点合并完成后，一个节点的内容就可以完整地用该节点的指针来表示（包括用于比较），因此节点的哈希函数可以利用四个子节点的地址进行一些运算。 这有点类似于Java的字符串函数。 这时，不可修改的数据结构的优势就体现出来了。

图 5：另一个玛土撒拉。 （译者注：原文可能有错误，这张图中的图案是图2所示的面包，不是玛土撒拉。）

节点合并本身就是一种强大的节省空间的方法。 生命游戏宇宙中的所有空白区域都将合并为少数节点。 所有常见的生命形式，例如滑翔机和方块，也将被合并到一小组公共节点中。 事实上，近年来建造的一些巨型生命体只能以四分之一树的形式储存，因为它们太大，不利于在RLE中传播。

更好的是，即使您使用的是 C++，该哈希表也可以在需要时轻松进行垃圾收集。 只需创建一个新的空哈希表，将其与当前合并的哈希表交换，从新的根节点开始重新合并，并删除旧哈希表中但不在新哈希表中的所有节点。 （译者注：也就是说，从新的根节点开始遍历树，没有遍历到的节点被删除。）

我们用一个类实现节点合并，其中我为哈希函数提供必要的基础设施，并重写负责创建每个节点实例的工厂方法。

解决了空间问题后，我们对函数进行了小修改，以优化时间。 这个小修改就是所谓的“记忆化”。 （也就是说，我们存储计算结果以供下次使用，而不是下次重新计算。）记忆化是缓存函数的返回值，以便在使用完全相同的参数再次调用该函数时可以使用它。 考虑一个记忆中的经典问题：斐波那契函数。 如果我们直接递归，我们会得到示例 1(a) 中所示的代码。 由于斐波那契函数呈指数增长，因此对该函数的调用次数也呈指数增长。 但是添加一个简单的数组作为缓存，例如示例1(b)，其运行时间变得线性。 当然，还有更快的方法来计算斐波那契数列（译者注：比如矩阵快速求幂），但这个想法很有用。

// 例 1：

// (a) 递归方法

int fib(int n) {
   if (n < 3)
      return 1 ;
   return fib(n-1) + fib(n-2) ;
}
// (b) 使用缓存的线性时间版本

int cache[] ;
int fib(int n) {
   if (n < 3)
      return 1 ;
   if (cache[n])
      return cache[n] ;
   return cache[n] = fib(n-1) + fib(n-2) ;
}

为了记住该函数，我添加了一个指向每个节点的指针来保存执行它的结果。 如果该指针非空，则它包含结果节点。 它是一个使记忆成为可能的纯函数。 带来的速度提升足以抵消返回下层节点带来的低效率。 实现此扩展的类是。

到目前为止，我们的算法并不正确。 当运行一些大型且规则的图形时，速度极快的普通算法无法运行它。 例如，当运行经典的饲养员模式时，即使细胞数量呈二次方增长，其运行时间也与进化代数呈线性关系。 但我们之前所做的所有工作都是为了一个重大改进：时间压缩。

之前我们提到过，我们会将一些复杂的图运行到数万亿代中。 在现代 CPU 上，即使数到一万亿也会花费大量时间； 然而，算法运行乘法器并输出最终细胞计数 1,302,083,334,180,208,337,404 只需要不到一秒的时间。 我们只需要对当前的代码做一点小小的修改。 （您可能想停下来看看您是否可以自己找出这种优化方法。）

最后的优化是改变递归函数的演化代数。 目前，它被称为一次只进化一代，这样即使它更快（比蛮力模拟），运行时间至少是线性的，即使它进化出一个空白的宇宙，也需要线性时间。 现在，我们将该函数重写为随着层数增加而增加的进化代数。 也就是说，第二层的4x4节点各进化1代，与之前相同； 第三层8x8节点各进化2代； 第8层节点各进化64代。

这个改变似乎把递归函数简化了很多，因为下一代的计算也会覆盖之前需要写很多函数的翻译节点。 代码片段三是简化的代码。 完整的实现在类中（参见 zip 附件）。 这里提供的代码总是根据当前级别调整步长； 您可以将其更改为针对固定级别以上的节点运行旧版本的函数，而针对较低级别的节点运行新版本的函数。 如果需要更大的步长，可以通过调用该方法轻松增加根节点的层数。

// 代码段 3

Node horizontalForward(Node w, Node e) {
   return node(w.ne, e.nw, w.se, e.sw).nextGeneration();
}
Node verticalForward(Node n, Node s) {
   return node(n.sw, n.se, s.nw, s.ne).nextGeneration();
}
Node centeredForward() {
   return node(nw.se, ne.sw, sw.ne, se.nw).nextGeneration() ;
}
Node nextGeneration() {
   if (level == 2) {
      ... do base case through normal simulation ...
   } else {
      Node n00 = nw.nextGeneration(),
           n01 = horizontalForward(nw, ne),
           n02 = ne.nextGeneration(),
           n10 = verticalForward(nw, sw),
           n11 = centeredForward(),
           n12 = verticalForward(ne, se),
           n20 = sw.nextGeneration(),
           n21 = horizontalForward(sw, se),
           n22 = se.nextGeneration() ;
      return new Node(
         new Node(n00, n01, n10, n11).nextGeneration(),
         new Node(n01, n02, n11, n12).nextGeneration(),
         new Node(n10, n11, n20, n21).nextGeneration(),
         new Node(n11, n12, n21,  n22).nextGeneration());
   }
}

就是这样。 这段代码在加速最常见的图形演变方面非常出色。 在最初的“预热”阶段，它会比暴力算法运行得慢，因为它需要存储哈希表，然后它会运行得非常快，并且进化代数的数量随着时间呈指数级增长。

让我们回到最初。 2000年12月，Nick Gotts在邮件列表中发布了一个新的、美妙的图案（译者注：这个好像还没有统一的中文翻译……）他非常有信心这个图案的增长会是正方形的。 ，但又不太确定，所以他问是否有人可以跑一会儿。 当时我刚刚写完一个快速的暴力游戏生命模拟器，并且已经了解了足够多的具体信息，由于 Bill 的原始代码只能在非常罕见的 Lisp 机器上运行，所以我决定尝试自己编写一个。 利用上面提到的各种不成熟的想法的融合，我成功地将它进化了数万亿代，并证明它在这个范围内以平方水平生长。 这种图案展现了美妙的分形之美，但只有在进化足够多的世代并且宇宙能够足够缩小的情况下才能看到这些。

我还发现了一种新的玛士撒拉（）（一种小型但活跃的生物体，可以移动很长一段时间才变得稳定），它有 12 个细胞，寿命超过 12,000 代。 其他人也用它来研究更大结构的模式，例如图灵机模拟器、注册机和新的航天器速度。

真正有趣的是算法，我必须为此感谢比尔，我把所有的功劳和功劳都归功于他。 如果你想亲自尝试这个算法，可以点击这个链接//golly/下载开源软件Golly。

它是一种独特的算法，可以记住生命游戏宇宙四叉树上的进化函数。 同样的技术也可以应用于其他领域。

单击此处下载本文的附件。

托马斯是 的技术总监。 他的电子邮件地址是。