康威的生命游戏 Conway's Game of Life

康威生命游戏 Conway's Game of Life，又称康威生命棋，是英国数学家约翰·何顿·康威 John Horton Conway在1970年发明的元胞自动机。

该游戏是零玩家游戏，这意味着它的发展由其初始状态决定，不需要进一步的输入。通过创建初始配置并观察其演变，它可以与生命游戏互动。它是具有图灵完整性的，可以模拟通用构造器或任何其他图灵机。

康威生命游戏中的一种可持续繁殖模式：“高斯帕 Bill Gosper 机枪”不断制造“滑翔机”

一个河豚型繁殖者（红色）的截图，它在滑行后留下滑翔机枪（绿色），从而创建了滑翔机（蓝色）（动画）

规则

我们所说的生命游戏是一个无限的，二维正方形的栅格单元，其中的每一个是两种可能的状态中的一种，活或死的（或者填充和未填充的分别）。每个单元格都与其八个相邻的单元交互，这八个单元格是水平、垂直或对角线相邻的单元格。在每个时间步上，都会发生以下转换：

1. 当前细胞为存活状态时，当周围的存活细胞低于2个时（不包含2个），该细胞变成死亡状态。（模拟生命数量稀少）
2. 当前细胞为存活状态时，当周围有2个或3个存活细胞时，该细胞保持原样。
3. 当前细胞为存活状态时，当周围有超过3个存活细胞时，该细胞变成死亡状态。（模拟生命数量过多）
4. 当前细胞为死亡状态时，当周围有3个存活细胞时，该细胞变成存活状态。（模拟繁殖）

这些将自动机的行为与现实生活进行比较的规则可以归纳为以下内容：

1. 任何有两个或三个邻居的活细胞都可以存活。
2. 具有三个活动邻居的任何死细胞都将成为活细胞。
3. 所有其他活细胞将在下一代死亡。同样，所有其他死细胞仍保持死亡状态。

可以把最初的细胞结构定义为种子，当所有在种子中的细胞同时被以上规则处理后，可以得到第一代细胞图。按规则继续处理当前的细胞图，可以得到下一代的细胞图，周而复始。

起源

在1940年后期，约翰·冯·诺依曼 John von Neumann将生命定义为可以复制自身并模拟图灵机（作为存在物或有机体）的创造物。冯·诺依曼正在考虑一种工程解决方案，该方案将使用随机漂浮在液体或气体中的电磁成分。事实证明，当时的可用技术并不现实。乌兰姆（Stanislaw Ulam）发明了细胞自动机，旨在模拟冯·诺依曼的理论电磁构造。乌兰姆在几篇论文中讨论了使用计算机在二维格子中模拟细胞自动机。同时，冯·诺依曼（Von Neumann）尝试构建乌兰姆的细胞自动机。尽管构建成功，但他忙于其他项目，有一些细节未完成。他构造的机器很复杂，因为它还要试图模拟自己的工程设计。随着时间的流逝，其他研究人员提供了更简单的构造，并在论文和书籍中发表。 受数学逻辑问题以及部分由乌兰姆从事模拟游戏的推动，约翰·康威（John Conway）于1968年开始使用各种不同的2D细胞自动机规则进行实验。康威的最初目标是定义一个有趣且不可预测的单元自动机。因此，他希望某些配置在死亡之前能持续很长时间，而其他配置则要在不设置循环的情况下永久运行下去。在细胞自动机专家设法证明确实如此的情况下，这是一个巨大的挑战，也是多年以来的一个开放性问题。康威的《人生游戏》承认，在满足冯·诺伊曼（Von Neumann）的两个基本要求的基础上，这种配置是让人满意的。在康威生命游戏之前的结构由于是以证明为导向的，所以康威的结构旨在简化操作，而无需事先提供自动机可以持续存活的证据。 经过大量实验后，Conway仔细选择了自己的规则，以符合以下条件：

1. 不应出现爆炸性增长。
2. 应该存在小的初始模式，其结果会混乱，不可预测。
3. 冯·诺依曼通用构造函数应该有潜力。
4. 在遵守上述约束的同时，规则应尽可能简单。

自从发明以来，康威的《生命游戏》就吸引了人们的极大兴趣，这是因为模式的发展令人惊讶。生活游戏是产生并自我组织的一个例子。计算机科学，物理学，生物学，生物化学，经济学，数学，哲学和生成科学等各个领域的学者都可以用这种通过执行简单规则即可产生复杂模式的方式。生命游戏也可以用作教学分析，用于展现有些反直觉的观念，即设计和组织可以在没有设计师的情况下自发出现。例如，认知科学家丹尼尔·丹内特（Daniel Dennett）广泛使用了康威生命游戏中的 “宇宙” 的类比，来说明复杂的哲学构造（如意识和自由意志）可能从相对简单的确定性物理定律集演化而来，而这些定律可以控制我们的宇宙。 康威的生命游戏之所以受欢迎，是因为它在合适的时间出现了，新一代的廉价计算机已进入市场。生命游戏可以在这些机器上运行几个小时，否则它们将在晚上保持闲置状态。在这方面，它预示了计算机合成的后来流行。对许多人来说，生活游戏仅仅是编程挑战：一种有趣的方式来使用否则会浪费的CPU周期。对于某些人来说，生活游戏则具有更多的哲学内涵。它在1970年代及以后发展了一个团体。当前的发展已经达到在生命游戏的范围内创建计算机系统的理论仿真的程度。

模式示例

在生命游戏中会出现许多不同类型的模式，这些模式根据其行为进行分类。常见的模式类型包括：静态，从一代到下一代都不会改变；振荡态，经过有限的迭代后返回其初始状态；移动的震荡态，它们可以在整个网格中平移。

最早并且有趣的模式是在不使用计算机的情况下就被发现的。在使用方格纸，黑板和物理游戏板追踪各种小型启动配置的命运时，发现了最简单的静态和振荡态。在这项早期研究中，康威（Conway）发现R-pentomino在次数较少的迭代中无法稳定。实际上，它需要1103次迭代才能稳定下来，到那时它已拥有116个种群，并已产生了6个移动的“滑翔机”。这是有史以来发现的第一批移动的震荡态。

下面显示了上述三种模式类型的频繁出现的示例（因为它们经常从随机的细胞初始配置中出现），活细胞显示为黑色，死细胞显示为白色。周期指的是模式返回初始配置之前必须迭代的周期数。

静态示例

• 

  方块

• 

  面包

• 

  蜂巢

• 

  大船

• 

  小船

• 

  花

• 

  池塘

• 

  航空母舰

• 

  独木舟

• 

  芒果

• 

  鸭子

震荡态示例

• 

  信号灯（周期=2轮）

• 

  蟾蜍（周期=2轮）

• 

  红绿灯（周期=2轮）

• 

  烽火（周期=2轮）

• 

  脉冲星（周期=3轮）

• 

  慨影（周期=15轮）

移动的震荡态示例

• 

  滑翔机（4轮）

• 

  太空船（4轮）

不可判定性

生命游戏中的许多模式最终成为静止态、振荡态和移动的震荡态的组合; 其他模式可以被称为混沌。 一个模式可能会在很长一段时间内保持混乱，直到它最终稳定为这样一个组合。生命是无法判定的，这意味着给定一个初始模式和一个后来的模式，没有算法能够判断后来的模式是否会出现。 这是不确定问题的必然结果: 从一个最初的输入开始，在给定参数的情况下，模型是会一直运行下去还是结束运行。事实上，由于生命游戏包含一个相当于通用图灵机的模式，这个决策算法，如果它存在的话，可以用来解决停机问题，方法是将初始模式作为对应于一个通用图灵机加上一个输入的模式，将后面的模式作为对应于一个通用图灵机的停机状态的模式。 同时，一些模式永远保持着混乱的状态。 如果不是这样的话，你可以按顺序进行游戏，直到一个非混乱的模式出现，然后计算是否会出现一个后来的模式。

自我复制

2010年5月18日，安德鲁（Andrew J. Wade）宣布了一个自我构建的模式，被称为“双子座” ，在摧毁母体的同时创建一个自我复制品。 这种模式经过3400万代的复制，使用由滑翔机制成的指令带在两个由查普曼-格林结构臂构成的稳定结构之间来回摆动。 这些，反过来，会创建新的副本的模式，并销毁以前的副本。 双子座也是一艘移动的震荡状态，是《生命的游戏》中建造的第一艘倾斜的移动的震荡状态，它既不是正交的也不是纯对角的。 2015年12月，斜对角线版的双子座建成了。 2013年11月23日，Dave Greene 在 Conway 的《生命的游戏》中制造了第一个复制因子，这个复制因子可以创建一个完整的自我拷贝，包括指令带。 2018年10月，Adam p. Goucher 完成了0E0P metacell 的建造工作，这是一个可以存储自我复制的 metacell。 这与之前的元细胞不同，比如 Brice Due 的 OTCA metapixel，它只能处理附近已经构建好的副本。 0E0P 元细胞的工作原理是使用构造臂来创建模拟编程规则的副本。 对 Conway’ s Life 或其他 Moore 邻居规则的实际模拟是通过使用具有更多状态的冯诺依曼邻域来模拟一个等价规则来完成的。 0E0P 是“ Zero Encoded by Zero Population”的缩写，这意味着0E0P 元胞不是处于“关闭”状态，而是在细胞进入“关闭”状态时自行移动，留下空白空间。

迭代

从网格上最随机的细胞初始模式中，观察者会发现人口随着时代的推移而不断变化。 从简单规则中产生的模式可以被认为是数学美的一种形式。 没有初始对称性的孤立的小亚模式趋向于对称。 一旦这种情况发生，对称性可能会增加丰富性，但它不会丢失，除非附近的子模式接近到足以干扰它。 在极少数情况下，社会最终会消亡，所有的活细胞都会消失，尽管这种情况可能不会发生很多代。 大多数最初的模式最终会结束，产生稳定的数字或模式，永远在两个或两个以上的状态之间振荡; 许多还产生一架或多架滑翔机或太空飞船，它们可以无限期地远离最初的位置。 由于基于最近邻的规则，没有任何信息能够以大于每单位时间一个单元的速率通过网格，所以这个速度被称为光的细胞自动机速度，并用 c 表示。

算法

在具有未知前景的早期模式，如 R-pentomino，使世界各地的计算机程序员编写程序来跟踪生命模式的演变。 大多数早期的算法是相似的: 它们将生命模式表示为计算机内存中的二维数组。 通常使用两个数组: 一个用于保存当前生成，另一个用于计算其后续数组。 通常0和1分别代表死细胞和活细胞。 嵌套的 for 循环依次考虑当前数组的每个元素，计算每个单元格的活动邻居，以决定后续数组的相应元素是0还是1。对于下一次迭代，数组交换角色，以便上一次迭代中的后继数组成为下一次迭代中的当前数组。 对这个基本方案进行各种小的改进是可能的，并且有许多方法可以节省不必要的计算。 如果一个单元格在上一个时间步骤中没有发生更改，而且其邻居也没有发生更改，则保证该单元格在当前时间步骤中也不发生更改。 因此，跟踪哪些区域处于活动状态的程序可以通过不更新非活动区域来节省时间。 为了避免计数循环中的决定和分支，规则可以从内域对其邻域的以自我为中心的方法重新安排到科学观察者的观点: 如果一个给定邻域的所有九个场之和为三，下一代的内域状态将是生存; 如果全场和为四，内域保持其当前状态; 每个其他和将内场置于死亡。 如果希望节省内存，可以将存储量减少到一个数组加两个行缓冲区。 一个行缓冲区用于计算一行的继承状态，然后第二个行缓冲区用于计算下一行的继承状态。 然后将第一个缓冲区写入其行，并释放以保存第三行的继承者状态。 如果使用环形数组，则需要第三个缓冲区，以便保存数组中第一行的原始状态，直到计算最后一行。 原则上，生命域是无限的，但计算机的内存是有限的。 当活动区域侵入阵列的边界时，这就会导致问题。 程序员使用了几种策略来解决这些问题。 最简单的策略是简单地假设阵列外的每个单元格都已死亡。 这是很容易编程，但会导致不准确的结果，使得活动区跨越边界。 一个更复杂的技巧是考虑将场的左右边缘结合在一起，以及顶部和底部边缘，生成一个环形阵列。 其结果是，跨越场边缘的活动区域在相反的边缘重新出现。还可以使用动态存储分配技术，创建越来越大的数组来保存生长模式。 有时对有限域上的生命进行明确的研究; 有些实现，例如 Golly，支持在标准无限域、一维无限域或有限域中进行选择，并可选择柱面、环面或Möbius strip。 或者，程序员可以放弃用二维数组表示 Life 字段的概念，而使用不同的数据结构，例如用坐标对表示活细胞的向量。 这种方法允许模式在场中不受阻碍地移动，只要人口不超过活动坐标阵列的大小。 缺点是计算生存的邻居变成了散列表查找或搜索操作，降低了模拟速度。 使用更复杂的数据结构，这个问题也可以基本上得到解决。 对于在非常长的时间深度探索大型模式，像 Hashlife 这样的复杂算法可能是有用的。 还有一种方法，也适用于其他细胞自动机，用任意的异步更新来实现生命游戏，同时仍然完全模仿同步游戏的行为。 在 Rosetta Code 中可以找到用各种编程语言(包括 c、 c + + 、 Java 和 Python)实现基本生命游戏场景的源代码示例。

代码实现

Netlogo代码实现

Netlogo源代码

setup运行初始状态

代码整体分为两部分，setup和go部分。其中setup进行环境的初始化，go进行持续运行。

setup部分

setup的核心代码如下：

patches-own[living]

to setup
   clear-all
   reset-ticks
   ask patches[       
    if random-float 1 < 0.5 [    #以0.5的概率设置白格，黑白格比例为1:1,可以在实际中将0.5改为其他值，来模拟不同黑白格比例
      set pcolor white
    ]
    set living 0
  ]
end

to go
  ask patches[
    set living count neighbors with [pcolor = black]
  ]
  ask patches[
    ifelse pcolor =  black[
      if living > 3 or living < 2[
        set pcolor white
      ]
    ][
      if living = 3[
        set pcolor black
      ]
    ]
  ]
  tick
end

go部分

go按钮在创建之时就设定了持续执行，因此程序会一直进行下去。在每一轮中，程序都会遍历每个格，来判断每个格周围的存活数量。如果黑格周围存活数不等于3，其将死亡，表现为由黑格转为白格。若一个白格周围存活数正好是3，会变为黑色，即为存活状态。在棋盘上所有格子均判断完一轮后，由于设定了持续执行，程序会再次进行遍历，不断循环下去。随着迭代次数的增加，整个环境也会趋于较稳定状态。go部分的核心代码如下：

运行过程

  ask patches[
    ifelse pcolor =  black[
      if living > 3 or living < 2[
        set pcolor white
      ]
    ][
      if living = 3[
        set pcolor black
      ]
    ]
  ]

Python代码实现

import numpy as np
import matplotlib.pyplot as plt
class GameOfLife(object):
  def __init__(self, cells_shape):
    """
    Parameters
    ----------
    cells_shape : 一个元组，表示画布的大小。
    Examples
    --------
    建立一个高20，宽30的画布
    game = GameOfLife((20, 30))    
    """
    # 矩阵的四周不参与运算
    self.cells = np.zeros(cells_shape)
    real_width = cells_shape[0] - 2
    real_height = cells_shape[1] - 2   
    self.cells[1:-1, 1:-1] = np.random.randint(2, size=(real_width, real_height))
    self.timer = 0
    self.mask = np.ones(9)
    self.mask[4] = 0  
  def update_state(self):
    """更新一次状态"""
    buf = np.zeros(self.cells.shape)
    cells = self.cells
    for i in range(1, cells.shape[0] - 1):
      for j in range(1, cells.shape[0] - 1):
        # 计算该细胞周围的存活细胞数
        neighbor = cells[i-1:i+2, j-1:j+2].reshape((-1, ))
        neighbor_num = np.convolve(self.mask, neighbor, 'valid')[0]
        if neighbor_num == 3:
          buf[i, j] = 1
        elif neighbor_num == 2:
          buf[i, j] = cells[i, j]
        else:
          buf[i, j] = 0
    self.cells = buf
    self.timer += 1  
  def plot_state(self):
    """画出当前的状态"""
    plt.title('Iter :{}'.format(self.timer))
    plt.imshow(self.cells)
    plt.show()
  def update_and_plot(self, n_iter):
    """更新状态并画图
    Parameters
    ----------
    n_iter : 更新的轮数
    """
    plt.ion()
    for _ in range(n_iter):
      plt.title('Iter :{}'.format(self.timer))
      plt.imshow(self.cells)
      self.update_state()
      plt.pause(0.2)
    plt.ioff()
if __name__ == '__main__':
  game = GameOfLife(cells_shape=(60, 60))
  game.update_and_plot(200)

以上代码在安装相应的库后复制粘贴便可运行。

Python运行结果

相比较Netlogo与Python实现，可以看出，python实现首先需要构建运行环境，再实现功能，最终实现的功能也并没有NetLogo丰富，建议从NetLogo实现开始。

衍生

自从生命诞生以来，新的类似的细胞自动机已经被开发出来。 标准的生命游戏象征为 b3 / s23。 如果一个细胞恰好有三个邻居，它就会出生; 如果有两个或三个活着的邻居，它就会存活下来，否则就会死亡。 第一个数字，或者数字列表，是一个死亡细胞出生所需要的数字。 第二组是活细胞存活到下一代的必要条件。 因此，b6 / s16意味着”如果有六个邻居，则一个细胞出生; 如果有一个或六个邻居，则细胞继续存活”。 二维网格上的细胞自动机，即可以这样描述的细胞自动机称为类生命细胞自动机。 另一个常见的类生命自动机，Highlife，是由规则 b36 / s23描述的，因为除了原始游戏的 b3 / s23规则外，还有六个邻居，导致了一个新生命的诞生。 Highlife 以其频繁出现的复制因子而闻名。 推广的类生命细胞自动机也是存在的。这2^18条不同的规则中的绝大多数产生的宇宙要么太混乱，要么太荒凉，以至于不能引起人们的兴趣，但是大部分宇宙的确显示出有趣的行为。 进一步的推广产生了各向同性规则空间，有2^102个可能的 CA 规则(Conway’s Life 也是其中之一)。 这些规则使用与类生命游戏规则相同的方形网格和相同的八格邻域，并且在旋转和反射下同样不变。 然而，在各向同性规则中，在确定一个细胞的未来状态时，可以考虑相邻细胞之间的相对位置，而不仅仅是相邻细胞的总数。 （此处图片上传失败） 康威的规则也可以被广义化，以至于有三个或更多的状态，而不是只有两个状态，活的或死的。 然后，状态转换由一个配置系统或一个为每个状态指定单独转换规则的表来确定; 例如，Mirek’ s Cellebration 的多色规则表和 Weighted Life 规则系列每个都包含相当于 Conway’ s Life 的样本规则。 与分形和分形系统有关的模式也可以在某些类似生命的变化中观察到。 例如，自动机 b 1 / s12在应用于单个活细胞时，会产生4个非常接近谢尔宾斯基三角形的值。 在 Conway 的《生命游戏》中也可以观察到这种谢尔宾斯基三角形，通过检测一长串单细胞厚度的活细胞的长期生长，以及在 Highlife、Seeds (b2/s)和 Wolfram的Rule 90中观察到。 移民是也一种变换形式，非常类似于康威的生命游戏，除了有两个状态，通常表示为不同的颜色。 每当一个新细胞出生时，它都处于开启状态。 这个特性可以用来检查游戏中可移动的震荡状态和其他物体之间的相互作用。另一种类似的变体叫做 QuadLife，涉及四种不同的状态。 当一个新的细胞从相邻的三个不同的细胞中诞生时,它会呈现第四个值，否则，就像 Immigration 一样，它会呈现大多数值。 除了细胞之间的差异外，这两种变异的行为都与生命相同。

音乐

各种音乐创作技术都会使用康威的生命游戏。特别是在 MIDI旋律中，有各种各样的程序可以从生命游戏中产生的模式中发出声音。

参见

sequence 真因子数列 人工生命 Glory Season 荣耀之季 兰顿蚂蚁 电子发生器 反应扩散系统

参考文献

---

本中文词条由11795用户参与编译，Ilseyao1980审校，用户:薄荷:薄荷编辑，欢迎在讨论页面留言。

本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。