江苏龙网

  1. 首页 > 资讯 > 科技 > >

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

2020年4月 ， 数学家约翰·康威（John H. Conway）因新冠肺炎去世 。 大家回顾康威教授平生贡献时 ， 不可避免要提到伟大、深刻的“康威生命游戏”（Conway’s Game of Life） 。 康威生命游戏规则极简 ， 内涵却无比丰富 ， 可演变出震撼人心的宏大场景 。 其中 ， 程序员最为之着迷的 ， 是由PhiNotPi、El’endia Starman、 K Zhang等人组成的极客团队耗时一年半创建的史诗巨作——他们用康威生命游戏搭建了一台名为“俄罗斯方块处理器”（Tetris Processor）的通用计算机 ， 并成功地在其中运行了俄罗斯方块程序 。
下图是“俄罗斯方块处理器”运行俄罗斯方块程序时的内存快照（每行左侧的数字对应于具体的内存地址；蓝色方块代表1 ， 白色方块代表0；向内存地址01传送数值指令 ， 可操作正在下落的俄罗斯方块）：
游戏康威生命游戏是如何搭建计算机的？
图片

一个最初用于模拟细胞繁衍衰亡的二维数学模型 ， 是如何支撑起建造一台通用计算机的重任的？很多人知道 ， 康威生命游戏是图灵完全的 ， 建造计算机在理论上的确可行 。 但理论和现实之间大概隔了十七八块CPU的复杂度 。 没有强悍的工程能力和扎实的基础知识 ， 是没法完成这种宏大工程的 。
中文世界里介绍这个项目的技术文章不多 ， 有的浅尝辄止 ， 有的语焉不详 。 这里 ， 我试着把那群极客搭建“俄罗斯方块处理器”的技巧梳理一下 ， 争取将其中比较重要的工程原理和技术逻辑讲清楚 。
30万亿个网格上的工程师思维
康威生命游戏在2维网格里模拟细胞的繁衍和衰亡 ， 规则非常简单：死亡细胞周围有3个存活细胞时 ， 该细胞就诞生为新的存活细胞；存活细胞周围有2个或3个存活细胞时 ， 该细胞就保持存活 ， 否则就死去 。 两条简单规则创造了千变万化的新世界 。 人们很快发现 ， 在康威生命游戏里可以创造出特别有趣的图案模式 ， 比如著名的滑翔机（glider）图案：
游戏康威生命游戏是如何搭建计算机的？
图片

滑翔机图案只有5个存活细胞 ， 却非常重要 ， 是构造更复杂图案的核心构件 。 康威生命游戏里 ， 许多经典图案模式都比滑翔机复杂很多倍 。 但 ， 你能想象那群极客搭的“俄罗斯方块处理器”有多少个细胞吗？
“俄罗斯方块处理器”在康威生命游戏中运行时 ， 占用约30万亿个网格的矩形区域 ， 初始状态包含超过292亿个存活细胞！
别惊讶 ， 我没开玩笑！这么复杂的图案在康威生命游戏中长什么样？下图左侧是 “俄罗斯方块处理器”在康威生命游戏中的全貌 ， 蓝色表示存活细胞 ， 白色表示死亡细胞 。 右上是这台计算机的核心部分被放大8倍的结果 ， 右下是这台计算机某个局部被放大2000多倍的样子——即便放大了2000多倍 ， 那个局部还是包含了大约 20万个存活细胞！
游戏康威生命游戏是如何搭建计算机的？
图片

天哪！在30万亿个网格上绘制图案 ， 还要让这个图案可以像通用计算机那样编程或玩游戏……这是人力可以完成的任务吗？
太复杂？计算机工程师并不怕复杂 ， 因为我们有引以为傲的思维法宝：建立抽象层级 。
严格地说 ， “俄罗斯方块处理器”并非直接在康威生命游戏的巨大网格上设计、绘制出来的 。 这么复杂的工程 ， 要先从高得多的抽象层级开始 ， 首先建立高层级的完整模式 ， 然后再用自动化的工具将其转译为低层级的表示——对 ， 没错 ， 这和我们先用高级语言编程 ， 再用编译器将高级语言翻译成机器语言是一个道理 。 每个抽象层级之间 ， 通用的转译或编译工具起到隔离复杂度的作用 。
游戏康威生命游戏是如何搭建计算机的？
图片

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


推荐阅读


上一篇：SpaceX马斯克的星际飞船，爆炸了

下一篇：疗法Nature发文痛批：伪科学抗疫大行其道，政府医院竟为它们背书！