康威生命游戏是如何搭建计算机的？

男娘i 2023-01-17 08:52 201阅读 0赞

2020年4月，数学家约翰·康威（John H. Conway）因新冠肺炎去世。大家回顾康威教授平生贡献时，不可避免要提到伟大、深刻的“康威生命游戏”（Conway’s Game of Life）。康威生命游戏规则极简，内涵却无比丰富，可演变出震撼人心的宏大场景。其中，程序员最为之着迷的，是由PhiNotPi、El’endia Starman、 K Zhang等人组成的极客团队耗时一年半创建的史诗巨作——他们用康威生命游戏搭建了一台名为“俄罗斯方块处理器”（Tetris Processor）的通用计算机，并成功地在其中运行了俄罗斯方块程序。

下图是“俄罗斯方块处理器”运行俄罗斯方块程序时的内存快照（每行左侧的数字对应于具体的内存地址；蓝色方块代表1，白色方块代表0；向内存地址01传送数值指令，可操作正在下落的俄罗斯方块）：

![v2-2883aba223a2affa014515dd9ea928b1_b.jpg][] ![v2-2883aba223a2affa014515dd9ea928b1_720w.jpg][] 构建在康威生命游戏基础上的俄罗斯方块（内存快照）

一个最初用于模拟细胞繁衍衰亡的二维数学模型，是如何支撑起建造一台通用计算机的重任的？很多人知道，康威生命游戏是图灵完全的，建造计算机在理论上的确可行。但理论和现实之间大概隔了十七八块CPU的复杂度。没有强悍的工程能力和扎实的基础知识，是没法完成这种宏大工程的。

中文世界里介绍这个项目的技术文章不多，有的浅尝辄止，有的语焉不详。这里，我试着把那群极客搭建“俄罗斯方块处理器”的技巧梳理一下，争取将其中比较重要的工程原理和技术逻辑讲清楚。

## 30万亿个网格上的工程师思维 ##

康威生命游戏在2维网格里模拟细胞的繁衍和衰亡，规则非常简单：死亡细胞周围有3个存活细胞时，该细胞就诞生为新的存活细胞；存活细胞周围有2个或3个存活细胞时，该细胞就保持存活，否则就死去。两条简单规则创造了千变万化的新世界。人们很快发现，在康威生命游戏里可以创造出特别有趣的图案模式，比如著名的滑翔机（glider）图案：

![v2-627ae588d453836eefa9c2ad734e85fa_b.gif][]

![v2-627ae588d453836eefa9c2ad734e85fa_b.jpg][]

滑翔机

滑翔机图案只有5个存活细胞，却非常重要，是构造更复杂图案的核心构件。康威生命游戏里，许多经典图案模式都比滑翔机复杂很多倍。但，你能想象那群极客搭的“俄罗斯方块处理器”有多少个细胞吗？

**“俄罗斯方块处理器”在康威生命游戏中运行时，占用约30万亿个网格的矩形区域，初始状态包含超过292亿个存活细胞！**

别惊讶，我没开玩笑！这么复杂的图案在康威生命游戏中长什么样？下图左侧是 “俄罗斯方块处理器”在康威生命游戏中的全貌，蓝色表示存活细胞，白色表示死亡细胞。右上是这台计算机的核心部分被放大8倍的结果，右下是这台计算机某个局部被放大2000多倍的样子——即便放大了2000多倍，那个局部还是包含了大约 20万个存活细胞！

![v2-e16894dda70c178ad94fb6bea731a688_b.jpg][] ![v2-e16894dda70c178ad94fb6bea731a688_720w.jpg][] “俄罗斯方块处理器”的全貌和局部放大

天哪！在30万亿个网格上绘制图案，还要让这个图案可以像通用计算机那样编程或玩游戏……这是人力可以完成的任务吗？

太复杂？计算机工程师并不怕复杂，因为我们有引以为傲的思维法宝：建立抽象层级。

严格地说，“俄罗斯方块处理器”并非直接在康威生命游戏的巨大网格上设计、绘制出来的。这么复杂的工程，要先从高得多的抽象层级开始，首先建立高层级的完整模式，然后再用自动化的工具将其转译为低层级的表示——对，没错，这和我们先用高级语言编程，再用编译器将高级语言翻译成机器语言是一个道理。每个抽象层级之间，通用的转译或编译工具起到隔离复杂度的作用。

![v2-626ff6d7d4af134cc5a62a4af76f2e68_b.jpg][] ![v2-626ff6d7d4af134cc5a62a4af76f2e68_720w.jpg][] “俄罗斯方块处理器”的抽象层级

简单说，有人先设计了一个适合搭建计算机的生命游戏规则——导线世界游戏（Wireworld）。利用导线世界游戏搭建计算机绝对不会夸张到需要几百亿个存活细胞。基于这一工作的启发，极客们另行设计了一种游戏——多规则生命游戏（VarLife）。多规则生命游戏既容易表达电路逻辑，又容易被转译为康威生命游戏。基于多规则生命游戏，极客创造了系统时钟、逻辑门、算术逻辑单元、计数器、存储器……然后搭建出一台高抽象层级的通用计算机。

接下来，只要有一种自动化方法，将多规则生命游戏搭建的计算机转译为康威生命游戏的规则，不就大功告成了吗？确实如此。不过，发现转译工具的过程可不简单。这里要感谢康威生命游戏世界里一个像上帝样的存在——OTCA metapixel单元细胞。有关这个上帝般的存在，我们后面再详细解释。

也就是说，在康威生命游戏中搭建计算机仅需三步：

*  第一步：在导线世界游戏里做原型验证。
 *  第二步：在多规则生命游戏里搭建高层级的通用计算机。
 *  第三步：使用OTCA metapixel单元细胞转译第二步的结果，得到低层级实现。

注：必须说明的是，借助OTCA metapixel转译并非搭建计算机的唯一方案。甚至，OTCA metapixel本身的冗余成分还会让转译后的计算机显得过度臃肿。已存在好几种不同类型的图灵机实现，可以作为搭建计算机的基础架构。参见：

[Universal computerconwaylife.com][Universal computer_conwaylife.com]

## 在导线世界游戏里搭建计算机 ##

在虚拟世界中搭建计算机，最直观的思路就是用某种机制模拟电流与电子元件。例如，《我的世界》游戏提供了红石电路（Redstone circuits）这种足以模拟电流、电路的机制，玩家就在其基础上创建了许多台有趣的通用计算机。

康威生命游戏里，最像电流的可能就是各种尺寸的滑翔机了。但直接用滑翔机搭建电路的挑战还是太大。1987年，Brian Silverman为了更好地模拟计算机电路，创造了导线世界游戏（Wireworld）。与康威生命游戏一样，导线世界游戏也是一种仅有几条规则的细胞自动机：

*  空细胞总保持不变。
 *  蓝色细胞代表电子头部，每次迭代都会变成红色细胞。
 *  红色细胞代表电子尾部，每次迭代都会变成黄色细胞。
 *  黄色细胞代表导体，每次迭代时，如果周围有1个或2个相邻细胞是蓝色，就变成蓝色细胞，否则就保持原样。

很容易基于这四条简单规则构建一根允许电流通过的导线：

![v2-7841189b94c7109ba52040e874d2b339_b.gif][]

![v2-7841189b94c7109ba52040e874d2b339_b.jpg][]

导线

把导线绕一个或大或小的圈子，就成了可以连续发射不同频率脉冲的系统时钟：

![v2-733bbfa37d58a475ead19afe0590f718_b.gif][]

![v2-733bbfa37d58a475ead19afe0590f718_b.jpg][]

系统时钟

导线中增加一个巧妙的“C”形连接，可以做成只允许电流从一个方向通过的二极管：

![v2-7716991c55f21482414e65edb2afc4e0_b.gif][]

![v2-7716991c55f21482414e65edb2afc4e0_b.jpg][]

二极管

“或”门是一个十字型结构，一个或两个输入信号都可以激发输出信号：

![v2-716706c5f73026f56c5ae7421d5dcfc7_b.gif][]

![v2-716706c5f73026f56c5ae7421d5dcfc7_b.jpg][]

“或”门

“与”门稍微复杂些。只有单个输入信号时，电流或者被十字结构阻挡，或者在环路中自己阻挡自己。两侧都有输入信号时，环路电流的一个分支恰巧被另一个信号阻挡，另一分支得以形成输出信号：

![v2-ed42d3f09d71c0aae1472708d34654eb_b.gif][]

![v2-ed42d3f09d71c0aae1472708d34654eb_b.jpg][]

“与”门

“异或”门是一个简单的方环，单个输入信号可以通过，两个输入信号同时进入则就相互阻挡，无法形成输出：

![v2-6d213221ead3bd75326c5ff0c397d8bb_b.gif][]

![v2-6d213221ead3bd75326c5ff0c397d8bb_b.webp][]

“异或”门

触发器电路拥有存储或重置一个二进制位的逻辑功能，是很多复杂电路结构的基本单元，也是实现内存的基础。在触发器电路里，下端输入信号负责激活触发器，引起持续输出的信号，上端输入信号负责重置触发器，终止信号的输出：

![v2-5e37bf2ffd7767622d03e25336cd3631_b.gif][]

![v2-5e37bf2ffd7767622d03e25336cd3631_b.jpg][]

触发器

在下面这个加法器里，两个输入数字A和B（二进制取值分别为011和110）按低位到高位顺序，逐位从左边上下两条导线进入算术单元。算术单元内部，左侧的异或门负责计算当前位的求和结果A XOR B，下侧的与非门利用A AND NOT (A XOR B)计算是否进位，中间的触发器负责存储进位标志，另有一个与非门负责在需要时重置触发器。计算结果以低位到高位次序从右侧导线输出（结果为1001）：

![v2-a611d2f191bf8cd78846417b8f97fabf_b.gif][]

![v2-a611d2f191bf8cd78846417b8f97fabf_b.jpg][]

加法器

触发器可以用来搭建内存（RAM）单元。那么，能长期保存信息的只读存储器（ROM）该怎么搭建呢？下图中，左边是存储在ROM中的二进制位0，右边是二进制位1。二者仅有一个差别：中间的小方盒右侧是否长了“小耳朵”，有耳朵的是0，没耳朵的是1。查询信号从右下输入进来，如果ROM单元里存储的是1，就会有信号从右上输出：

![v2-15fc72ec776d52126fadedc0d94d86dd_b.gif][]

![v2-15fc72ec776d52126fadedc0d94d86dd_b.jpg][]

ROM单元结构

下图是拥有2个地址位置（A0和A1），每个地址位置可存储2个二进制位的微型 ROM。查询指令通过右下方不同线路进行寻址，查询结果的各个二进制位从右上方相应线路输出：

![v2-1516e4d4526f8f8b7dc76487b37bd0a4_b.gif][]

![v2-1516e4d4526f8f8b7dc76487b37bd0a4_b.jpg][]

ROM

有了这些基础单元，就可以在导线世界游戏里搭建计算机了。David Moore与 Mark Owen成功地搭建过一台可以寻找并显示质数的导线世界游戏计算机：

![v2-5e298ebf27e771af8f3c72c1024a5f92_b.jpg][] ![v2-5e298ebf27e771af8f3c72c1024a5f92_720w.jpg][] 导线世界游戏计算机

这台导线世界游戏计算机在具体实现上做了相当多的功能简化：整部计算机没有内存，程序代码（机器指令）就保存在寄存器里。更厉害的是，CPU的指令集只有一条MOV指令，不仅数据读写用MOV指令实现，算术、分支等操作同样通过MOV 指令实现。这是因为，寄存器R53-R62内置了算术运算、逻辑运算等功能，事实上起到算术逻辑单元的作用；而寄存器R63则兼具程序计数器和跳转指令的功能。可以说，这是个高度凝练的RISC架构指令集。

此外，为了用十进制显示质数，这台计算机还花大力气实现了5个十进制数字的虚拟“显示器”。每个数字都是一个用导线世界游戏搭建的“7段液晶显示器”。计算机中内置了二进制到BCD码（用4位二进制来存储1位十进制的编码方式）的转换器以及BCD码到7段显示器的解码器。每个十进制数字对应的解码器正好是一个 10x7的ROM单元。

## 神一样的OTCA metapixel ##

看来，同样是细胞自动机类型的生命游戏，只要规则合适（比如，导线世界游戏的规则就是专门为搭建计算机设计的），我们就可以在工程角度找到可行的实现路径。更进一步，如果我们已经在某个规则合适的游戏中搭建好了计算机，那只要存在一个“编译器”，帮我们把计算机在该游戏中的表示，转换为康威生命游戏中的等价表示，不就大功告成了吗？

最理想的情况是存在一一对应的转换关系，直接把某种生命游戏中的每个细胞，映射为康威生命游戏中的一个单元结构。

等等，上面这句话好像蕴藏着什么了不起的大道理。假如康威生命游戏中存在某种单元结构，可以表达任何一种其他生命游戏的细胞逻辑……那，康威生命游戏不就成了一种“生命游戏的生命游戏”了吗？我们不就可以在康威生命游戏中模拟运行其他生命游戏了吗？更进一步，我们不也可以在康威生命游戏中模拟运行康威生命游戏自己了吗？

在一个世界中克隆这个世界自身，这个设定听上去相当科幻。对非专业人士而言，似乎是个了不起的大话题。B站有个用康威生命游戏模拟康威生命游戏的视频，留言和弹幕里，就尽是一片膜拜之声，大家直接联想到哲学、宗教、宇宙学和科幻小说。其实，大可不必过度解读。在计算机科学的世界里，“自己创造自己”“自己定义自己”“自己运行自己”的例子比比皆是：Windows系统上可以运行 Windows系统的模拟器，C语言可以编写C语言的编译器，JavaScript可以实时解释运行JavaScript代码，函数可以调用自己也可以成为传递给自己的参数……

当然，要在康威生命游戏中找到这样一种有能力表达其他规则的“单元细胞”，绝非易事！康威教授1970年就公开了生命游戏的设计，直到1996年，David Bell才创建出第一种单元细胞——p5760。p5760的大小为500x500个网格，初始状态有 4761个存活细胞。p5760可以还原康威生命游戏中细胞的迭代规则。也就是说，我们可以用一组p5760还原出一模一样的康威生命游戏来。

p5760单元细胞具备里程碑意义，但实际使用时存在很多困难。首先，p5760的死亡或存活状态很难辨识。我们必须每隔5760次迭代就检查一下单元细胞左上角两个特别小的船形标志中间，是否正好有一个滑翔机飞过。有，代表单元细胞存活。无，代表单元细胞死亡。其次，p5760只支持原生的康威生命游戏规则，无法自定义规则。

经过数年的技术探索，2005年，Brice Due终于设计出上帝级别的单元细胞——OTCA metapixel!

我们先在下图中直观感受一下这个边界大小为2058x2058的单元细胞长什么样（图中，左边是OTCA metapixel死亡时的样子，右边是存活时的样子）：

![v2-196608519c26fd05d41b54d823743cb9_b.jpg][] ![v2-196608519c26fd05d41b54d823743cb9_720w.jpg][] OTCA metapixel的死亡和存活状态

每个死亡（off）状态的单元细胞共包含23920个微观尺度的存活细胞。每个存活（on）状态的单元细胞通过射向中央的一组射线，将整个单元细胞的宏观结构 “染”色。于是，OTCA metapixel的死亡和存活状态在宏观尺度上一目了然，与康威生命游戏的微观结构一致。

我们放大一些，看看OTCA metapixel的左下角藏有什么好东西：

![v2-9f494ebf044ca0b60620128924cd3083_b.jpg][] ![v2-9f494ebf044ca0b60620128924cd3083_720w.jpg][] OTCA metapixel规则控制面板

这里竟藏有一个可以配置单元细胞规则的控制面板！OTCA metapixel支持基于邻接计数的各种生命规则。控制面板上，字母B对应0~8共9个开关，字母S也对应 0~8共9个开关。这些开关是什么意思呢？

原生的康威生命游戏主要由两条规则构建：一，死亡细胞周围有3个存活细胞时就诞生为新细胞；二，存活细胞周围有2或3个存活细胞时就保持存活，否则死亡。这两条规则可以简记为B3/S23（其中，B代表出生，S代表存活）。通过修改B或S 后面的数字，就可以创建出不同的生命游戏。例如，把B1、B2、S3这三个开关打开，我们就创建了规则B12/S3，这意味着：死亡细胞周围有1或2个存活细胞时才诞生为新细胞，而存活细胞周围有3个存活细胞时才保持存活。

使用OTCA metapixel时，我们可以通过小尾巴形状的图形开关（开和关的状态在微观结构上只相差一个细胞）设置好具体规则，然后把一组OTCA metapixel单元细胞平铺成矩阵样的网格。实际运行时，每个单元细胞会自动检查周围8个邻接单元细胞的死亡或存活状态，然后根据规则开关的设定来决定自己是生是死。

听上去很厉害的样子！感觉每个OTCA metapixel单元细胞都是一个可配置的小型自动机。那么，实际运行时每个OTCA metapixel单元细胞到底是如何检查邻接单元细胞的状态，又是如何根据自己的配置开关完成状态切换的呢？我给OTCA metapixel的主要功能区域加了一些注释：

![v2-3017c0aefa08986372fb0f78ccd48513_b.jpg][] ![v2-3017c0aefa08986372fb0f78ccd48513_720w.jpg][] OTCA metapixel各功能区域

OTCA metapixel周边有8个输入输出用的I/O接口。通过这些接口，单元细胞用滑翔机做消息，将自己的状态通知给8个邻接单元细胞。同时，单元细胞也接收8个邻接单元细胞的状态更新。左侧规则控制面板旁边，有一个纵向的消息信道。这其实是一个小型的，带同步功能的指令分发器和接收器。围绕OTCA metapixel一圈的，是一条空旷的正方形轨道。单元细胞运行时，如果注意观察，可以看到一列由9个轻量级滑翔机（LWSS）组成的小火车呼啸着沿轨道绕行一周。小火车的作用是依次查询8个I/O接口，看每个邻接单元细胞是否存活，并将邻接细胞的计数与控制面板上预先设置的条件相比对，以激活后续指令。OTCA metapixel上边框和右边框内侧，像曲尺形状的结构是用于显示状态的射线枪阵列。一旦接受到激活指令，射线枪阵列就从两个方向连续发射枪弹，将单元细胞铺满。

OTCA metapixel实际上将康威生命游戏原本的单位尺度，从1x1的微观细胞，放大到了2058x2058的宏观单元细胞，同时还支持游戏规则的灵活定义。在二维平面平铺开来的OTCA metapixel单元细胞矩阵，运行起来后，就是一个宏观层面的生命游戏。这的确是生命游戏中的生命游戏！

注：OTCA metapixel之后，康威生命游戏世界又诞生了几种里程碑意义的单元细胞，包括规则表达能力比OTCA metapixel强悍许多的p1 megacell，以及迄今为止尺寸最大的单元细胞0E0P metacell。一个0E0P metacell单元细胞就包含约1865万个存活细胞。0E0P metacell不仅在表达能力上和p1 megacell差不多，而且具有神奇的自我“克隆”能力。我们不需要铺满完整的矩阵，只需要部署存活状态的0E0P metacell单元细胞并将其他位置留白。运行时，0E0P metacell单元细胞有能力在全空的场地上“克隆”出新的自己。参见：

[Unit cell - LifeWikiconwaylife.com][Unit cell - LifeWiki_conwaylife.com]

## 高层级抽象：多规则生命游戏 ##

OTCA metapixel适用于基于邻接计数的生命游戏规则，无法直接转译导线世界游戏里的计算机。极客们需要一种既方便表达电流和电路，又容易被转译为OTCA metapixel的新游戏规则。这一工作的成果就是全新的多规则生命游戏（VarLife）了。

多规则生命游戏的特点是每个细胞遵循的邻接计数规则可以不同。游戏中，我们用不同颜色来区分规则不同的细胞。具体规则如下：

*  背景规则B/S：无论何时背景中都不会诞生新的存活细胞。
 *  蓝/青规则B1/S：蓝色死亡细胞周围有1个任意颜色存活细胞时即诞生为青色存活细胞；任何青色存活细胞总会在下一次迭代时死亡。
 *  绿/黄规则B2/S：绿色死亡细胞周围有2个任意颜色存活细胞时即诞生为黄色存活细胞；任何黄色存活细胞总会在下一次迭代时死亡。
 *  红/橙规则B12/S1：红色死亡细胞周围有1个或2个任意颜色存活细胞时即诞生为橙色存活细胞；橙色存活细胞周围有1个任意颜色存活细胞时即保持存活，否则死亡。

在这几条规则的基础上，蓝色细胞可扮演导线内芯的角色，绿色细胞扮演导线外皮或电流方向控制器的角色（阻止电流反向传播），青、黄两色细胞共同构成一个“V”字型的运动电子。红色和橙色细胞用于表示和存储状态信息。

我们在下图中看一下多规则生命游戏建造的导线长什么样：

![v2-f42f69d90523c896f84318558dc1b7e1_b.gif][]

![v2-f42f69d90523c896f84318558dc1b7e1_b.jpg][]

导线

多规则生命游戏建造的逻辑门如下图所示（左边是“与”门，中间是“异或”门，右边是“或”门）：

![v2-28f31543de82a6c8a9f27cf7a64db956_b.gif][]

![v2-28f31543de82a6c8a9f27cf7a64db956_b.jpg][]

逻辑门

多规则生命游戏中的触发器从左上角标记“SET”的位置接收设置信号，从右上角 “RESET”位置接收重置信号。读取触发器的指令从左下“READ”位置输入，输出信号位于右下“OUT”位置。如下图所示：

![v2-0bf1301066187b5141e3474f97f40505_b.gif][]

![v2-0bf1301066187b5141e3474f97f40505_b.jpg][]

触发器

其他基础元件的搭建原理和我们之前在导线世界游戏中所做的事情大同小异。但极客们基于多规则生命游戏设计的“俄罗斯方块处理器”在软硬件架构上要更加完整、复杂。

“俄罗斯方块处理器”的硬件细节相当丰富，包含约120万个细胞，拥有独立的算术逻辑单元（ALU）、随机存取存储器（RAM）、只读存储器（ROM）、计数器、同步器、指令分离器等：

![v2-ebbdba4a8fbf1b3ad8f4411658de307f_b.jpg][] ![v2-ebbdba4a8fbf1b3ad8f4411658de307f_720w.jpg][] “俄罗斯方块处理器”的硬件构成

设计和实现这个复杂硬件系统的工程量还是相当巨大的。最麻烦的问题在于，这一类用生命游戏建造的电路元件，对信号同步的要求非常高。两条导线长度相差一格，往往就会引起时钟序列上的错误。为此，“俄罗斯方块处理器”使用全异步设计，尽量排除导线长度差异的干扰。系统中有很多看上去复杂、精巧的设计，都是为了同步不同的信号，或者在串行信号和并行信号之间做转换。限于篇幅，这里不详细解释系统的每个细节设计。

架构和软件层面，“俄罗斯方块处理器”是一台真正的通用计算机。它可不是只能运行俄罗斯方块程序。事实上，“俄罗斯方块处理器”拥有一个16位的RISC哈佛架构的指令集，可以运行各类程序。在哈佛架构中，程序指令存储和数据存储分开，指令寻址和数据寻址可相互独立，这与纯冯·诺依曼架构不同。

“俄罗斯方块处理器”指令集的设计特点包括：

*  没有寄存器，指令使用RAM中存储的数值作为操作数。
 *  程序计数器占用RAM地址00，跳转指令直接使用地址00作为操作数。
 *  所有指令预先保存在ROM中，初始数据则保存在RAM中。
 *  数据和地址都是16位的。
 *  支持的最大指令条数是65536。
 *  所有指令的编码大小都相同，都拥有1个操作码（opcode）和3个操作数（operand）。
 *  没有系统主时钟，数据在并行传输时有一个伴行的“时钟信号”，以方便同步。
 *  算术逻辑单元支持条件移动指令、算术运算指令、位逻辑运算指令、位移指令等。

整个指令集包括11条RISC指令：

MNZ [test] [value] [dest] – [test] 非0则设置 [dest] 为 [value]
    MLZ [test] [value] [dest] – [test] 小于0则设置 [dest] 为 [value]
    ADD [val1] [val2] [dest]  – 加法。将 [val1] + [val2] 的结果存入 [dest]
    SUB [val1] [val2] [dest]  – 减法。将 [val1] - [val2] 的结果存入 [dest]
    AND [val1] [val2] [dest]  – 与。将 [val1] & [val2] 的结果存入 [dest]
    OR  [val1] [val2] [dest]  – 或。将 [val1] | [val2] 的结果存入 [dest]
    XOR [val1] [val2] [dest]  – 异或。将 [val1] ^ [val2] 的结果存入 [dest]
    ANT [val1] [val2] [dest]  – 与非。将 [val1] & (![val2]) 的结果存入 [dest]
    SL  [val1] [val2] [dest]  - 左移。将 [val1] << [val2] 的结果存入 [dest]
    SRL [val1] [val2] [dest]  - 无符号右移。将 [val1] >> [val2] 的结果存入 [dest]，不保留符号位
    SRA [val1] [val2] [dest]  - 有符号右移。将 [val1] >> [val2] 的结果存入 [dest]，保留符号位

指令支持4种寻址方式，在汇编语言中用特定前缀区分：

*  立即寻址：无前缀
 *  直接寻址：前缀A
 *  间接寻址：前缀B
 *  双重间接寻址：前缀C

这个指令集使用了延迟（Delay slot）技术，每条指令的写操作是在下一条指令加载后才生效的。下面这段只有5行的汇编语言可以生成斐波那契数列：

0. MLZ -1 1 1;    初始值1存入数据地址01
    1. MLZ -1 A2 3;   将数据地址02中的值存入数据地址03
    2. MLZ -1 A1 2;   将数据地址01中的值存入数据地址02
    3. MLZ -1 0 0;    延迟一个指令周期后，跳转到指令地址01
    4. ADD A2 A3 1;   分支延迟（branch delay slot）指令
                      将数据地址02和03中的值相加后存入数据地址01

极客们甚至还基于这个指令集，创建了一种比汇编语言稍高级的，类似COBOL的编程语言Cogol。

最终，用“俄罗斯方块处理器”指令集编写的俄罗斯方块程序一共有291行。程序运行时，内存地址03到32直接对应于游戏的显示输出。内存地址03显示得分，地址05-08显示下一个方块的预览，地址10到32显示游戏的主场景。内存地址01用于接收用户的操作指令。将1直接写入内存地址01，表示逆时针旋转方块，写入2 表示左移，4表示下移，8表示右移，16表示顺时针旋转方块。

在多规则生命游戏这个抽象层运行俄罗斯方块时，我们可以直接从内存细胞中读出当前的游戏进程。内存中每个二进制位都是拥有4个输入和4个输出的有状态结构（类似一个较复杂的触发器）。可以通过中央的两个红色细胞的状态，读出这个二进制位的值：红色表示0，橙色表示1。如下图：

![v2-21353adb0e19f1af7cf5ae792dd2e3ba_b.jpg][] ![v2-21353adb0e19f1af7cf5ae792dd2e3ba_720w.jpg][] 实时读取内存中的数值

## 编译和运行——大功告成 ##

有了多规则生命游戏中实现的通用计算机，最后一步就相当容易了：自动把多规则生命游戏计算机转换成康威生命游戏。

转换方法非常简单：多规则生命游戏中，组成计算机的每个细胞，都自动被转译成康威生命游戏中的一个OTCA metapixel单元细胞。转译时，多规则生命游戏每个细胞的不同颜色，正好用于配置相应的OTCA metapixel规则。蓝/青配置为 B1/S，绿/黄配置为B2/S，红/橙配置为B12/S1。稍显遗憾的是，多规则生命游戏用不同颜色区分细胞的不同规则，转译成OTCA metapixel语言后，就只能在单色场景中，依靠每个OTCA metapixel单元细胞的控制面板来区分细胞规则了。

因为是一一对应的转译，在多规则生命游戏中实现的计算机，在康威生命游戏中运行时将拥有完全一致的宏观结构和功能。只不过，原本只有120万左右的初始细胞数量，经过转译OTCA metapixel后数量倍增，微观层面的初始细胞数量达到了惊人的292亿！

在“俄罗斯方块处理器”的项目网页上，大家可以下载到两种不同的实现源码。一种是基于多规则生命游戏的高层级实现，一种是转译到康威生命游戏之后的实现。两种源码都可以用Golly工具来运行（第一种需要安装规则文件）。项目网页：

[https://codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-lifecodegolf.stackexchange.com][https_codegolf.stackexchange.com_questions_11880_build-a-working-game-of-tetris-in-conways-game-of-life_codegolf.stackexchange.com]

## 更多思考 ##

先写到这儿吧。要介绍康威生命游戏搭建计算机的所有细节，这篇文章的篇幅至少得扩大10倍。不过，搞清楚技术细节是一回事，从这个搭建计算机的故事里体会出点儿什么是另一回事。

喜欢玩康威生命游戏的人有好多种。理论家擅长从形而上的视角出发，一眼看破生命游戏中内藏的数学抽象，悟出其中的哲学道理。实践家则不然，哲学概念和高层级的数学抽象是否存在并非特别重要，他们看重的是创建具体应用时的工程逻辑和技术细节。

现实中，有很多事情看上去并不存在理论困难，但实施起来超级复杂。在理论家眼里，这类事情属于脏活儿累活儿，最好不要沾身。在实践家眼里，再复杂的工程问题都可以通过建立抽象层次、分而治之、循环迭代、过程优化、使用自动工具等方法来解决。

创造“俄罗斯方块处理器”的这群极客就是典型的实践家。他们的社区讨论中有一个细节：有人问他们为什么选择用OTCA metapixel模拟电流、电路的路线，而不考虑其他类型的图灵机。他们的回答也很简单，当时不知道有其他选项。对工程师来说，只要找到一条合理可行、代价可承受的路径，就撸起袖子加油干——这才是实践家最可爱的一点。

这个世界既需要理论家，也需要实践家。就拿操作系统、数据库、编译器等基础软件来说，我们奋勇攻关几十年，各类资助、补贴、奖励投进去无数，但结果仍不如人意。老实讲，这些软件的基础理论都写在教科书上，理论家肯定不会承认这件事里有什么不能逾越的障碍。但到了实践层面，无论懂多少理论，你还是得静下心来，扎扎实实写代码，勤勤恳恳做测试。这还不算，你还得一个挨一个解决团队管理、产品设计、代码质量保障、系统性能优化、升级迭代、向前向后兼容等一大批实际工程问题。更要命的是，在技术之外，摆在面前的还会有市场开拓、用户留存、商业模式创建等更难搞定的挑战。能把这些脏活儿累活儿干好，才有资格谈突破和创新。

在生命游戏里用几百亿个细胞攒电脑，干这事儿的极客工程师值得尊重。不消说，他们代表的工程师思维和实践家风范，也有值得借鉴的地方。

编辑于 2020-05-29

生命游戏（Game of Life）

计算机原理

数学

赞同 2176

74 条评论

![微信二维码][qrcode_url_https_3A_2F_2Fzhuanlan.zhihu.com_2Fp_2F144162012_23showWechatShareTip] 分享

喜欢 收藏 申请转载

[v2-2883aba223a2affa014515dd9ea928b1_b.jpg]: https://pic2.zhimg.com/v2-2883aba223a2affa014515dd9ea928b1_b.jpg
[v2-2883aba223a2affa014515dd9ea928b1_720w.jpg]: /images/20221021/41b7f23452d94955ad7d8ba5b0c6d75a.png
[v2-627ae588d453836eefa9c2ad734e85fa_b.gif]: /images/20221021/750b16b477024d16bee0f7363677a9f6.png
[v2-627ae588d453836eefa9c2ad734e85fa_b.jpg]: /images/20221021/081f4aada70740a4bbaa674190f51d30.png
[v2-e16894dda70c178ad94fb6bea731a688_b.jpg]: https://pic1.zhimg.com/v2-e16894dda70c178ad94fb6bea731a688_b.jpg
[v2-e16894dda70c178ad94fb6bea731a688_720w.jpg]: /images/20221021/dc4189fce88e49bd8854b4b9e6136ee6.png
[v2-626ff6d7d4af134cc5a62a4af76f2e68_b.jpg]: https://pic1.zhimg.com/v2-626ff6d7d4af134cc5a62a4af76f2e68_b.jpg
[v2-626ff6d7d4af134cc5a62a4af76f2e68_720w.jpg]: /images/20221021/ac982efedbf747b4b812f4b27aa6453d.png
[Universal computer_conwaylife.com]: https://link.zhihu.com/?target=https%3A//conwaylife.com/wiki/Universal_computer
[v2-7841189b94c7109ba52040e874d2b339_b.gif]: /images/20221021/3e5cfccd820c496fb2660191035dd00e.png
[v2-7841189b94c7109ba52040e874d2b339_b.jpg]: /images/20221021/1af634d43a664b849b2ad2319cc11b17.png
[v2-733bbfa37d58a475ead19afe0590f718_b.gif]: /images/20221021/b2e56ba82cec4b0b8a5b678696ce2a94.png
[v2-733bbfa37d58a475ead19afe0590f718_b.jpg]: /images/20221021/3d36f3f669ae4ecead857d57a7dd7b19.png
[v2-7716991c55f21482414e65edb2afc4e0_b.gif]: /images/20221021/e5c95169f29a4ed391bb195f2355a3f6.png
[v2-7716991c55f21482414e65edb2afc4e0_b.jpg]: /images/20221021/4c996fd425f748a0863b9239e0200a3c.png
[v2-716706c5f73026f56c5ae7421d5dcfc7_b.gif]: /images/20221021/f44ca39b7845401387f1140438a6aa0e.png
[v2-716706c5f73026f56c5ae7421d5dcfc7_b.jpg]: /images/20221021/43c21ebeb35b47e4a4838b2d9a160b90.png
[v2-ed42d3f09d71c0aae1472708d34654eb_b.gif]: /images/20221021/9c30571ef7e644508f49ea2cb0484814.png
[v2-ed42d3f09d71c0aae1472708d34654eb_b.jpg]: /images/20221021/61f7c9cd8b9441708d92077647ee7ecf.png
[v2-6d213221ead3bd75326c5ff0c397d8bb_b.gif]: /images/20221021/46d315d6746c4a9ea0fbaaec3500b5fa.png
[v2-6d213221ead3bd75326c5ff0c397d8bb_b.webp]: /images/20221021/aad60f74115740198e9dd00470ac30ca.png
[v2-5e37bf2ffd7767622d03e25336cd3631_b.gif]: /images/20221021/8a31834109fc405bbbfdb92c1430f814.png
[v2-5e37bf2ffd7767622d03e25336cd3631_b.jpg]: /images/20221021/6e3bad1633c142c1bde932bf1e35eba6.png
[v2-a611d2f191bf8cd78846417b8f97fabf_b.gif]: /images/20221021/da21673f89134619b07ed82af39bbe3c.png
[v2-a611d2f191bf8cd78846417b8f97fabf_b.jpg]: /images/20221021/8035bd0cbd6b460999c3695d6448a21a.png
[v2-15fc72ec776d52126fadedc0d94d86dd_b.gif]: /images/20221021/ad126f1c08d04021adc0e735c1f94439.png
[v2-15fc72ec776d52126fadedc0d94d86dd_b.jpg]: /images/20221021/c415b12f42534c979a2d71918de51419.png
[v2-1516e4d4526f8f8b7dc76487b37bd0a4_b.gif]: /images/20221021/31ea179ff3174ed9b71bcda7d90bf7e6.png
[v2-1516e4d4526f8f8b7dc76487b37bd0a4_b.jpg]: /images/20221021/6c4b49f002f640cd9e173782022f2f8a.png
[v2-5e298ebf27e771af8f3c72c1024a5f92_b.jpg]: https://pic3.zhimg.com/v2-5e298ebf27e771af8f3c72c1024a5f92_b.jpg
[v2-5e298ebf27e771af8f3c72c1024a5f92_720w.jpg]: /images/20221021/a9f5cacd954b472391720c5cc531c1cd.png
[v2-196608519c26fd05d41b54d823743cb9_b.jpg]: https://pic2.zhimg.com/v2-196608519c26fd05d41b54d823743cb9_b.jpg
[v2-196608519c26fd05d41b54d823743cb9_720w.jpg]: /images/20221021/0d896ce47d214f17a6ecab9ccea4373a.png
[v2-9f494ebf044ca0b60620128924cd3083_b.jpg]: https://pic4.zhimg.com/v2-9f494ebf044ca0b60620128924cd3083_b.jpg
[v2-9f494ebf044ca0b60620128924cd3083_720w.jpg]: /images/20221021/0fa547a2366b44d3a366de8d2a9fbf42.png
[v2-3017c0aefa08986372fb0f78ccd48513_b.jpg]: https://pic4.zhimg.com/v2-3017c0aefa08986372fb0f78ccd48513_b.jpg
[v2-3017c0aefa08986372fb0f78ccd48513_720w.jpg]: /images/20221021/13ff439bf8f6463fa154ef33e6fe5178.png
[Unit cell - LifeWiki_conwaylife.com]: https://link.zhihu.com/?target=https%3A//conwaylife.com/wiki/Unit_cell
[v2-f42f69d90523c896f84318558dc1b7e1_b.gif]: /images/20221021/522c4ff1f5be44b3a12ad1db8a34552d.png
[v2-f42f69d90523c896f84318558dc1b7e1_b.jpg]: /images/20221021/a608512c2aaf4615a771b0d773aac20e.png
[v2-28f31543de82a6c8a9f27cf7a64db956_b.gif]: /images/20221021/24a2697366da4b169559ad1b331114f0.png
[v2-28f31543de82a6c8a9f27cf7a64db956_b.jpg]: /images/20221021/ed8f88ba19f8475492896307a58b8efb.png
[v2-0bf1301066187b5141e3474f97f40505_b.gif]: /images/20221021/0078f05e59924443882ab5185533f913.png
[v2-0bf1301066187b5141e3474f97f40505_b.jpg]: /images/20221021/529fb408360e42e29e0f381aa8725f64.png
[v2-ebbdba4a8fbf1b3ad8f4411658de307f_b.jpg]: https://pic4.zhimg.com/v2-ebbdba4a8fbf1b3ad8f4411658de307f_b.jpg
[v2-ebbdba4a8fbf1b3ad8f4411658de307f_720w.jpg]: /images/20221021/b23be97a38004213aa801b910d8cb4b4.png
[v2-21353adb0e19f1af7cf5ae792dd2e3ba_b.jpg]: https://pic3.zhimg.com/v2-21353adb0e19f1af7cf5ae792dd2e3ba_b.jpg
[v2-21353adb0e19f1af7cf5ae792dd2e3ba_720w.jpg]: /images/20221021/01fe4d0b09a74ff9a851b70987f36fca.png
[https_codegolf.stackexchange.com_questions_11880_build-a-working-game-of-tetris-in-conways-game-of-life_codegolf.stackexchange.com]: https://link.zhihu.com/?target=https%3A//codegolf.stackexchange.com/questions/11880/build-a-working-game-of-tetris-in-conways-game-of-life
[qrcode_url_https_3A_2F_2Fzhuanlan.zhihu.com_2Fp_2F144162012_23showWechatShareTip]: https://www.zhihu.com/qrcode?url=https%3A%2F%2Fzhuanlan.zhihu.com%2Fp%2F144162012%23showWechatShareTip