生命棋
出自維基百科,自由嘅百科全書
你可以參與嘅一盤生命棋 (而家有兩架「滑翔機」(glider)): {{Subst:生命棋
|1|0|0|0|0|0|0|0|0|0
|1|0|0|0|0|0|0|0|1|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|1|0|1
|0|0|0|0|0|0|0|0|1|1
|0|0|0|0|0|0|0|0|1|0
|0|0|0|0|0|0|0|0|0|0
|0|0|0|0|0|0|0|0|0|1
}}
生命棋(Game of Life)係架元胞自動機(en:cellular automaton),英國數學人John Horton Conway響1970年設計。
雖然話「棋」,但其實都唔駛人郁,個遊戲自動由初始態進化。人插得手嘅只係砌好開頭個樣。
目錄 |
[編輯] 規則
生命棋嘅世界係塊(無窮大嘅)兩維四方格板,每格叫一粒「細胞」(cell);每胞有態:一係生,一係死。 每格同渠嘅上下左右同埋對角嗰八「鄰居」互動。一步棋係以下嘅轉變:
- 一粒生嘅細胞,若鄰居少過兩就會死(「孤獨」);
- 一粒生嘅細胞,若鄰居多過四就會死(「塞死」);
- 一粒生嘅細胞,若鄰居兩三,就會繼續生下一代;
- 一粒死嘅細胞,若鄰居啱啱好有三,就會出世。
成個系統嘅唯一種籽係棋盤開頭個樣。砌好原初狀態, 跟住一次過同時響每格用上面規則,由原初個樣來砌出第一代。有人叫郁呢一下做「的一下(a tick)」。跟住同樣恁由第一代一次過砌出第二代。。。。每代都由上一代完全決定。
[編輯] 源
數學人John von Neumann係1940年代時問過:存唔存在一架理論上可覆製自己嘅機器?渠響四方格上砌出一架嘅數學模型,但要用一套好複雜嘅規則。Conway 試簡化von Neumann 嘅構思,終於成功:夾埋渠之前響羣論中 Leech's problem 嘅念頭同埋渠響自我覆製機器嘅興趣, Conway 設計出生命棋。
Conway 曾猜想:無一種棋形可以無限增長 - 換言之,每一種僅有有限子嘅初始棋形都有有限嘅增長上限。 開頭,生命棋響 "Mathematical Games" 出現時, Conway 提議:邊個首先證明道猜想嘅真假,就畀五十蚊渠。一種反證嘅方法係去揾一種唔停加嘢入棋盤嘅棋形:例如一支「鎗」:渠可以重覆咁射出曉得郁嘅棋,如滑翔機同埋噴煙火車 (puffer train,即一隻會郁而且會留低一行唔會散嘅「煙」嘅棋)。
The prize was won in November of the same year by a team from the 麻省理工學院, led by Bill Gosper; the "Gosper 鎗" shown below produces its first glider on the 15th generation, and another glider every 30th generation from then on. This first glider gun is still the smallest one known:
[編輯] 特别嘅棋形同埋術語
四方 (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機:[1]
[編輯] 算法
最早期嘅發現,例如靜物、搖擺形,都來自紙筆、黑板同埋圍棋盤之類。嗰陣 Conway 發現咗 F-pentomino (which Conway 叫渠做 "R-pentomino") 好耐先至演變到穏定嘅循環。
呢的發現觸發咗世界各地嘅人寫程式去跟踪生命棋嘅進化。多數早期算法都差唔多:用兩維陣列來代表棋盤;多數人用兩塊陣列,一塊代表而家,一塊代表下一代;用 0 1 代表死生格;用雙循環來計每一格嘅下一代;輸出下一代嘅陣列;跟住再塊陣列嘅作用對掉。。。。
有好幾種細修改可以慳番的計算。例如:若一格上次無變,而渠嘅隔蘺亦無變,咁今次都唔會變。所以唔使改無活動嘅區。
理論上生命棋盤應無限大,但計算機記憶始終有限,而且通常一開始就要設定的 array幾大 。咁當盤棋嘅近邊開始郁時就會出問題。有幾種方法處理: 最簡單嘅解決就係當外圍嘅格咸辦闌永遠都係死嘅。 (少少似template:生命棋開頭嘅設計[2]咁)。咁樣雖然方便編程,但如果陣列嘅邊活躍起上來,結果會唔準。好少少嘅做法係黏埋上下、左右,做成個錨環 (torus)。咁,過界嘅棋型亦可借用棋盤對面,就可消除咗的病態嘅邊界效果;當然,若舊棋變到太大,終會唔準。另外,我地亦可用「動態儲存配置 」來變大個棋盤。
我地可以唔用兩維陣列來表示棋盤,改用其他結構,例如用座標對向量(?vector of coordinate pairs)來表示生嘅格仔。咁樣塊棋可以自由無阻咁郁,除非渠嘅「人口」增長到大過架生嘅座標陣列(? live-coordinate array);但缺點就係要揾(search)一輪先知道有一格有幾多鄰居,慢。 我地可用更仔細嘅資料結構大致解決呢個問題。
如要深入探索大規模嘅棋形,有精細嘅算法用,例如Hashlife。
[編輯] 參閱
[編輯] 生命棋嘅程式
生命棋程式有好多,下面啲有多人玩同有特別功能:
- Conway's Game of Life by Alan Hensel. A pop-up Java web applet with fast simulation algorithms and a big library of interesting Life patterns.
- Golly. A cross-platform (Windows, Macintosh, and Linux) open-source Life simulation system by Andrew Trevorrow and Tomas Rokicki including the hashlife algorithm for 極之快 generation and Python scriptability for both editing and simulation.
- Life32. Freeware for Windows machines includes powerful and scriptable pattern editing features.
- Mirek's Cellebration. Free 1-D and 2-D Cellular Automata viewer, explorer and editor for Windows. Includes powerful facilities for simulating and viewing a wide variety of CA rules including Life, and a scriptable editor.
- Xlife A cellular-automaton laboratory by Jon Bennett. For a long time the standard Linux Life simulation application, and has also been ported to Windows. Can handle cellular automaton rules with the same neighborhood as Life and up to eight possible states per cell. See here for many alternative versions.