生命棋

**生命棋**（；參見 ）係由英倫數學家康威響一九七〇年設計嘅格仔自動機。生命棋係零玩家遊戲，佢嘅狀態會點變化，完全取決於佢初頭嘅狀態：雖然叫做**棋**，但其實都唔使人郁，個遊戲會自動由初始態進化，人插到手嘅，只係砌開頭個狀態，跟住玩者唔洗畀咩輸入，生命棋都可以一路行。

喺電腦科學以至趣味數學當中，生命棋都廣受關注：事實表明，生命棋雖然規則簡單，而且係決定型嘅，但長遠嚟講無法預測，引起咗關於複雜系統同自我組織嘅討論；此外，生命棋嘅愛好者仲時常會用生命棋嚟整出各種嘅圖案，甚至有人因而主張，話生命值係有藝術價值嘅。

## 基本規則

生命棋係零玩家遊戲，一撳咗開始，玩家就完全唔洗再畀任何 input 。遊戲嘅起始，係一塊無止盡咁大嘅二維平面，塊平面分做一格格噉嘅四方格，每格謂之一個**細胞**或者**格仔**，當中每個格仔都有一個狀態，狀態一係**生**一係**死**。

系統一開始嗰陣嘅狀態，即係邊啲格係生邊啲格係死，係由玩家決定嘅。成個系統嘅唯一種籽係棋盤初頭個樣。原初狀態砌好咗，遊戲就會開始，每一格都會同佢嘅上下左右同埋對角嗰八格鄰里互動。遊戲會一步步噉演進，每步謂之一個，每一格都係按照以下嘅法則嚟改變：
#生嘅細胞，若果佢鄰里數量少過 2 就會死，是謂「孤獨死」；
#生嘅細胞，若果佢鄰里數量多過 3 就會死，是謂「擠逼死」；
#生嘅細胞，若果鄰里數量係 2 或者 3，就會繼續生存落去；
#死嘅細胞，若果鄰里數量啱啱好係 3 咁多，就會「誕生」，變成新嘅生細胞。
要留意嘅係，演進嗰陣，啲格嘅變化係同時發生嘅，所以若果某格要孤獨死，佢冇得話因為佢隔籬有格死格喺同一步中要誕生而唔洗孤獨死。如是者，場遊戲會一剔一剔噉行，而事實表明，生命棋往往會形成好多獨特嘅變化形態。呢種變化引起咗唔少數學愛好者嘅注意，而且趣味數學上亦成日會討論。

生命棋嘅例子：

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

Conway 設計呢的規則時好小心，亦試驗過吓。渠要求：
#唔要有初始棋形，可以好易證明渠會無限增長。
#應有的初始棋形，睇落真會無限增長。
#應該有的簡單嘅初始棋形，係一時間內變、增長，直到以下嘅結局：
#:*完全消失（塞死或者太散而孤獨死）；或
#:*成為一舊舊穏定嘅棋形，或唔變，或週期循環。

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

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

## 特别嘅棋形同埋術語

*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 for your Mathematical Plays|Winning Ways]]*有介紹。

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

## 算法
最早期嘅發現，例如靜物、搖擺形，都來自紙筆、黑板同埋圍棋盤之類。嗰陣 Conway 發現咗 F-pentomino（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
*

## 睇埋
*複雜系統

## 攷、註
引用咗嘅來源：


註釋：