跳去內容

生命棋

出自維基百科，自由嘅百科全書
一盤簡單嘅生命棋；紅色嘅係生，白色嘅係死。

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

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

基本規則

[編輯]

生命棋係格仔自動機一種，當中格仔自動機又有元胞自動機等嘅名。

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

系統一開始嗰陣嘅狀態，即係邊啲格係生邊啲格係死，係由玩家決定嘅。成個系統嘅唯一種籽係棋盤初頭個樣。原初狀態砌好咗，遊戲就會開始，每一格都會同佢嘅上下左右同埋對角嗰八格鄰里互動。遊戲會一步步恁演進，每步謂之一個剔tik1[註 3]，每一格都係按照以下嘅法則嚟改變：

  1. 生嘅細胞，若果佢鄰里數量少過 2 就會死，是謂「孤獨死」；
  2. 生嘅細胞，若果佢鄰里數量多過 3 就會死，是謂「擠逼死」；
  3. 生嘅細胞，若果鄰里數量係 2 或者 3，就會繼續生存落去；
  4. 死嘅細胞，若果鄰里數量啱啱好係 3 咁多，就會「誕生」，變成新嘅生細胞。

要留意嘅係，演進嗰陣，啲格嘅變化係同時發生嘅，所以若果某格要孤獨死，佢冇得話因為佢隔籬有格死格喺同一步中要誕生而唔洗孤獨死。如是者，場遊戲會一剔一剔恁行，而事實表明，生命棋往往會形成好多獨特嘅變化形態。呢種變化引起咗唔少數學愛好者嘅注意，而且趣味數學上亦成日會討論[5]。

下圖係用生命棋製作嘅「賽道」，定時會有個黃色嘅人型喺藍色嘅賽道上「奔跑」。



特別棋形

[編輯]

生命棋雖然話難以預測，但係有某啲規律，硬係成日會喺生命值中出現。呢啲棋形可以分做幾類：

  • Still life，意即靜物：呢啲棋形唔會隨時間而演變。
  • Oscillator，意即振盪子：呢啲棋形，經過若干代之後就會返去原先個樣。
  • Spaceship，意即太空船：呢啲棋形，識得「移動」。

砌圖靈機

[編輯]

喺生命值當中，放幾架 glider（暫譯滑翔機）撞埋啲嘢道，可以產生到各種效果。例如校啱兩架滑翔機，用某種方式射向一嚿四方形，恁嚿四方形就會移向支滑翔機嘅來源。若校啱三架滑翔機，用某種方式射向個四方，恁個四方就會郁開。即係話個四方最後喺邊個位，就可用來記嘢或者表示資訊。研究者甚至可用滑翔機嚟砌出邏輯門，例如AND、OR 同埋 NOT 等，亦可用生命棋模擬出一架連住兩部計算機嘅有限狀態機－呢部機同通用圖靈機等價，同一 架有無限記憶嘅計算機等價：換言之，生命棋係圖靈完整嘅[6]。

呢篇文度作者提出一架生命棋圖靈機：[7]

歷史起源

[編輯]
喺〇五年影到嘅約翰·何頓·康威（英文：John Horton Conway ）
睇埋：自我複製

生命棋嘅諗頭，源自二十世紀中。美國數學家馮紐曼喺一九四〇年代嗰時問過噉嘅問題：識得覆製自己嘅機器，理論上有冇可能存在？渠響四方格上砌出咗一個數學模型，但係要用一套好複雜嘅規則。及後康威試圖簡化馮紐曼嘅構思，終於成功設計出生命棋[2]。

康威設計呢的規則時好小心，亦試驗過吓。渠要求[未記出處或冇根據]：

  1. 唔要有初始棋形，可以好易證明渠會無限增長。
  2. 應有的初始棋形，睇落真會無限增長。
  3. 應該有的簡單嘅初始棋形，係一時間內變、增長，直到以下嘅結局：
    • 完全消失（塞死或者太散而孤獨死）；或
    • 成為一舊舊穏定嘅棋形，或唔變，或週期循環。

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

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

相關算法

[編輯]

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

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

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

理論上生命棋盤應無限大，但計算機記憶始終有限，而且通常一開始就要設定的 array幾大。咁當盤棋嘅近邊開始郁時就會出問題。有幾種方法處理：最簡單嘅解決就係當外圍嘅格咸辦闌永遠都係死嘅。（少少似Template:生命棋開頭嘅設計[8]咁）。咁樣雖然方便編程，但如果陣列嘅邊活躍起上來，結果會唔準。好少少嘅做法係黏埋上下、左右，做成個錨環 (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:生命棋

再睇埋

[編輯]

攷、註

[編輯]

引用咗嘅來源：

  1. ↑ Gardner, Martin (October 1970). "The fantastic combinations of John Conway's new solitaire game 'life'" (PDF). Mathematical Games. Scientific American.第223卷第4號. pp. 120–123. doi:10.1038/scientificamerican1070-120. JSTOR 24927642. 原先內容歸檔 (PDF)喺2022-10-09.
  2. 1 2 Izhikevich, Eugene M.; Conway, John H.; Seth, Anil (2015-06-21). "Game of Life". Scholarpedia (英文). 10 (6): 1816. Bibcode:2015SchpJ..10.1816I. doi:10.4249/scholarpedia.1816. ISSN 1941-6016.
  3. ↑ The Game of Life - Emergence in Generative Art
  4. ↑ MATHEMATICAL GAMES: The fantastic combinations of John Conway's new solitaire game "life" by Martin Gardner (1970).
  5. ↑ The Game of Life.
  6. ↑ It is a model and simulation that is interesting to watch and can show that simple things can become complicated problems.Paul Chapman (11 November 2002). "Life Universal Computer". 原著喺6 September 2009歸檔. 喺12 July 2009搵到.
  7. ↑ 〈存档副本〉 (PDF)。原著 (PDF)喺2007年5月11號歸檔。喺2007年3月28號搵到。
  8. ↑ 〈存档副本〉。原著喺2020年3月28號歸檔。喺2007年4月4號搵到。

註釋：

  1. ↑ 參見英文：cell
  2. ↑ 參見英文：live or dead
  3. ↑ 參見英文：tick
由「https://zh-yue.wikipedia.org/w/index.php?title=生命棋&oldid=2396703」收