生命棋

{{Subst:射影平面上捉生命棋

|0|0|0|0|1|1|0|0|0|0

|0|0|0|1|0|1|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|0|0|0|0|0

|0|0|0|0|0|1|0|0|0|0

}}

生命棋(Game of Life)係架元胞自動機(en:cellular automaton)，英國數學人John Horton Conway響1970年設計。

雖然話「棋」，但其實都唔駛人郁，個遊戲自動由初始態進化。人插得手嘅只係砌好開頭個樣。

規則

生命棋嘅世界係塊（無窮大嘅）兩維四方格板，每格叫一粒「細胞」(cell)；每胞有態：一係生，一係死。 每格同佢嘅上下左右同埋對角嗰八「鄰居」互動。一步棋係以下嘅轉變：

1. 一粒生嘅細胞，若鄰居少過兩就會死（「孤獨」）；
2. 一粒生嘅細胞，若鄰居多過四就會死（「塞死」）；
3. 一粒生嘅細胞，若鄰居兩三，就會繼續生下一代；
4. 一粒死嘅細胞，若鄰居啱啱好有三，就會出世。

成個系統嘅唯一種籽係棋盤開頭個樣。砌好原初狀態， 跟住一次過同時響每格用上面規則，由原初個樣來砌出第一代。有人叫郁呢一下做「的一下(a tick)」。跟住同樣恁由第一代一次過砌出第二代。。。。每代都由上一代完全決定。

源

數學人John von Neumann係1940年代時問過：存唔存在一架理論上可覆製自己嘅機器？渠響四方格上砌出一架嘅數學模型，但要用一套好複雜嘅規則。Conway 試簡化von Neumann 嘅構思，終於成功：夾埋渠之前響羣論中 Leech's problem 嘅念頭同埋渠響自我覆製機器嘅興趣， Conway 設計出生命棋。

Conway 設計呢的規則時好小心，亦試驗過吓。渠要求：

1. 唔要有初始棋形，可以好易證明渠會無限增長。
2. 應有的初始棋形，睇落真會無限增長。
3. 應該有的簡單嘅初始棋形，係一時間內變、增長，直到以下嘅結局：

   • 完全消失（塞死或者太散而孤獨死）；或
   • 成為一舊舊穏定嘅棋形，或唔變，或週期循環。

Conway 曾猜想：無一種棋形可以無限增長 - 換言之，每一種僅有有限子嘅初始棋形都有有限嘅增長上限。 開頭，生命棋響 "Mathematical Games" 出現時， Conway 提議：邊個首先證明道猜想嘅真假，就畀五十蚊渠。一種反證嘅方法係去揾一種唔停加嘢入棋盤嘅棋形：例如一支「鎗」：渠可以重覆咁射出曉得郁嘅棋，如滑翔機同埋噴煙火車 (puffer train，即一隻會郁而且會留低一行唔會散嘅「煙」嘅棋)。

麻省理工學院由Bill Gosper領頭嘅一隊人喺同年十一用攞走咗呢五十蚊。下面支"Gosper 鎗" 喺第十五循環時整好第一架滑翔機，之後每卅循環一架。至今呢支鎗仍然係已知最細嘅。

特别嘅棋形同埋術語

四方 (Block)	艇 （Boat）	蟾蜍 (Toad)	貶眼 (Blinker)	滑翔機 (Glider)	輕太空船 (LWSS)
1 1	1 1 0	1 1 1 0	0 1 0	0 1 0	0 1 0 0 1
1 1	1 0 1	0 1 1 1	0 1 0	0 0 1	1 0 0 0 0
	0 1 0		0 1 0	1 1 1	1 0 0 0 1
					1 1 1 1 0

• Methuselah：要等好耐先至變成穏定週期嘅形。
  • 命硬(diehard)：好耐先至消失嘅棋形
• 滑翔機鎗(Glider Gun)：會週期咁射出一架架滑翔機嘅鎗，第一架喺下面，發現者係MIT嘅 Bill Gosper:

• 噴煙嘅火車(puffer train)：會郁、重會留低一舊舊嘢嘅棋形
• 伊甸園：有出無入嘅棋形

用生命棋砌Turing機

可放幾架滑翔機撞埋啲嘢道，產生各種效果。例如，若校啱兩架滑翔機，用某種方式射向一舊四方形，咁舊四方形就會郁向支滑翔機嘅來源。若校啱三架滑翔機，用某種方式射向舊四方，恁舊四方就會郁開的。咁樣舊四方嘅位置就可用來記嘢。我地甚至可用滑翔機來砌出邏輯閘，例如AND、OR同埋NOT。我地亦可用生命棋模擬出一架連住兩個計數器嘅有限態機 (finite state machine) － 呢架機等價於通用Turing機( universal Turing machine)，等價於一架有無限記憶嘅計算機：換言之，生命棋係Turing完全(en:Turing complete)嘅。

重有，一舊棋可以包括一集可以夾埋砌出新棋形嘅鎗。，甚至可以重新砌出原本個棋形。我地可以砌出一架「普適砌棋者」("universal constructor")－渠包括成架Turing 完全嘅計算機，可以用來砌出好多種複雜嘅嘢，砌番渠自己嘅 copies 都得。Conway、Elwyn Berlekamp 同埋Richard Guy寫嘅Winning Ways有介紹。

呢篇文度作者提出一架生命棋Turing機：

算法

最早期嘅發現，例如靜物、搖擺形，都來自紙筆、黑板同埋圍棋盤之類。嗰陣 Conway 發現咗 F-pentomino (which Conway 叫渠做 "R-pentomino") 好耐先至演變到穏定嘅循環。

呢的發現觸發咗世界各地嘅人寫程式去跟踪生命棋嘅進化。多數早期算法都差唔多：用兩維陣列來代表棋盤；多數人用兩塊陣列，一塊代表而家，一塊代表下一代；用 0 1 代表死生格；用雙循環來計每一格嘅下一代；輸出下一代嘅陣列；跟住再塊陣列嘅作用對掉。。。。

有好幾種細修改可以慳番的計算。例如：若一格上次無變，而渠嘅隔蘺亦無變，咁今次都唔會變。所以唔使改無活動嘅區。

理論上生命棋盤應無限大，但計算機記憶始終有限，而且通常一開始就要設定的 array幾大 。咁當盤棋嘅近邊開始郁時就會出問題。有幾種方法處理： 最簡單嘅解決就係當外圍嘅格咸辦闌永遠都係死嘅。 （少少似Template:生命棋開頭嘅設計咁）。咁樣雖然方便編程，但如果陣列嘅邊活躍起上來，結果會唔準。好少少嘅做法係黏埋上下、左右，做成個錨環 (torus)。咁，過界嘅棋型亦可借用棋盤對面，就可消除咗的病態嘅邊界效果；當然，若舊棋變到太大，終會唔準。另外，我地亦可用「動態儲存配置 」來變大個棋盤。

我地可以唔用兩維陣列來表示棋盤，改用其他結構，例如用座標對向量（？vector of coordinate pairs）來表示生嘅格仔。咁樣塊棋可以自由無阻咁郁，除非渠嘅「人口」增長到大過架生嘅座標陣列（？ live-coordinate array)；但缺點就係要揾(search)一輪先知道有一格有幾多鄰居，慢。 我地可用更仔細嘅資料結構大致解決呢個問題。

如要深入探索大規模嘅棋形，有精細嘅算法用，例如Hashlife。

生命棋嘅程式

生命棋程式有好多，下面啲有多人玩同有特別功能：

• Conway's Game of Life ， Alan Hensel 寫嘅。係種彈出來嘅 Java web applet。算法快。有間有好多好玩生命棋形嘅圖書館。

• Golly. Andrew Trevorrow 同埋 Tomas Rokicki 寫嘅誇平臺 (Windows, Macintosh, and Linux) 開源嘅生命棋模擬系統，用hashlife算法，極之快，編輯同模擬上有Python scriptability。

• Life32 －－ Windows 機上行嘅自由程式，有強勁、可編碼(scriptable)嘅圖形編緝功能。

• Mirek's Cellebration－行Windows 嘅自由１維埋２維元胞自動機 編輯器。有強勁嘅模擬一大系列自動機規則嘅工具，同埋 scriptable 嘅編輯器 editor.

• Xlife Jon Bennett 寫嘅元胞自動機實驗室。長期係 Linux 嘅標準生命棋模擬程式，亦都搬咗過 Windows 用。可以搞掂有同生命棋一樣嘅鄰域而每格有多至釞種態嘅元胞自動規律。呢度 有好多第啲版本。

• Conway's game of life implementation. (Silverlight)

• Game of Life on JavaScript

• Template:生命棋