Posted by Mr. Thursday
這篇文章的標題翻譯成中文是：「康威：生命遊戲」。康威(John Horton Conway)是一位劍橋的數學家，生命遊戲是他在1970年發明的小遊戲。這個遊戲是一個模擬遊戲，首先有一個長方形棋盤，裡面劃分成許多小格子。每一個可以是活的細胞或死的細胞。每一步棋盤的狀態可以影響下一步的狀態，規則是：
- 如果某一格細胞在時間 t 是活著的話，那麼在時間 t+1 的時候
- 如果這格細胞只有一個鄰居或沒有鄰居活著的話，就死去 (因為孤獨)
- 如果這格細胞有四個或更多鄰居活著的話，就死去 (因為擁擠)
- 如果這格細胞剛好只有兩個或三個鄰居，則繼續活著
- 如果某一格細胞在時間 t 是死的話，那麼在時間 t+1 的時候
- 如果這格細胞剛好有三個鄰居的話，就活起來
上面就是其中一個例子，每一格細胞依照剛才的規則來決定下一步的生死，綠色是活起來的細胞，黑色是還沒有活起來的細胞。這個遊戲之所以稱為「生命遊戲」，是因為他用一些基本的規則，來模擬生命的進行，每一個細胞僅僅依照這幾條規則，就有許多不同的變化。我們甚至可以把大的圖形看成是一個有機體，一堆細胞組成的一個有機體，這個有機體就因為細胞的變化跟著變形，所以「看起來」的確有些生命演化的味道，好像有些有機體會吃掉其他有機體，有時候變大，有時候消失，然而所根據的，是組成有機體的細胞，依照幾條基本規則演化的結果。
除了「看起來」有生命的感覺，裡面其實也有數學在裡頭。因為規則是固定的、可預測的，我們只要知道初始狀態(有哪幾格是活著的細胞)，就可以知道第一步的狀態，知道第一步的狀態，就可以知道第二步的狀態，以此類推，因此如果數學比較有sense的讀者，也許可以嚐試看看，先試試10*10的棋盤，然後把每一格細胞寫成時間 t 的函數，我只要把時間t和初始條件帶入，就可以知道第n步的時候，這個棋盤有哪些細胞會活起來了。
然而這個遊戲其實也是有趣在於可以一步一步看這些有機體演化，因此我也在網路上找到一個JAVA Applet可以讓各位讀者玩玩看：
http://www.bitstorm.org/gameoflife/
上面是screenshot和使用說明。我們除了可以指定初始狀態以外，也可以在中途停下來，變動一些細胞的狀態，再繼續演化。目前我是出一些基本的圖形，像是連續三個細胞形成的直線，連續四個細胞形成的直線，以及四個細胞形成的正方形等等，這些組合方式都可以穩定下來，像是正方形就永遠不會變動，連續三個細胞的直線則會在水平線和垂直線之間不停的交錯變換，連續四個細胞的直線，會在幾個步驟以後穩定下來，變成類似菱形的形狀。
如果我們在菱形旁邊加一個點，會產生甚麼樣子的變化呢？
過了幾步以後，原來的菱形開始向外面擴張。
到最後，穩定下來，居然就變成四個小菱形，排列成一個大菱形狀了。
至於文章一開始提到的圖形，在這個模擬器裡面也有這個圖形需要的初始狀態可以選擇，只要選左邊下拉選單的最後一項“Gosper Glider Gun”然後按開始，就可以看到剛才的動畫了。
然而上面的圖形，假設我們隨便加給個點進去，整個系統就會破壞掉，在這邊還滿有「混沌」(chaos)的味道。因此雖然這個遊戲只有幾個基本規則，演化出來的生命卻是千變萬化，還可以用數學加以分析。Donald E. Knuth在他的一系列演講中的某一次演講，也提到了Game of Life，有興趣的可以在這邊(Dr. Dobb’s Journal Techcast)收看演講錄影。
近代的「系統生物學」(System Biology)應該也是做類似的事情，把生命的機制，歸納出基本的規則，不管是系統層次、器官層次、細胞層次、一直到基因分子層次。雖然這個生命遊戲離真正的生命還有段距離，但是也初步展示了系統生物學的一些原理了！
參考資料
- 生命遊戲Java Applet模擬器
- (Wikipedia) Game of Life
- 美國科學人1970年生命遊戲的文章
- 更多有趣的初始狀態和更多介紹 (中文)
過去的今天：
- Google 推出網路虛擬實境服務 : Lively - 2008
- Randy Pausch: 熱情追求你所愛的事物，勇敢實踐你的夢想 - 2008
- 創意香蕉 - 2007
隨機推薦
 |
 |
訂閱 所有文章 (含專欄文章 + 產業新聞 + 其他文章)
[...] http://mmdays.wordpress.com/2007/07/12/game_of_life/ [...]
很有趣的模型
不過在我隨意測試的結果
好像無論任何一種起始狀態
在經過一定長度的時間後
整個系統就會進入收斂
維持某一個狀態
或是某幾種狀態不停的循環
在數學上
是真的有這樣的proposition嗎?
哈，真是勾起回憶，生命遊戲是我當初學 BASICA 的作業之一啊！
Willy: Game of Life 的計算能力, 跟 Turing Machine 全等. 所以所有 Turing Machine 能產生的行為, 理論上都能在 Game of Life 上得到. Game of Life 的行為已經分析得非常清楚了, 除了 Conway 寫的 The Wining Ways 有深入討論外, 還有專門的雜誌 Life Line.
想猜測是否最後一定會循環
有些像是猜測一個數字是否為循環小數一樣
有的數字是循環小數(0.333….)
有的是從不循環的小數(3.141596…)
————-
不過我自己想了一個證法
就是先令所有可能的狀態為A, B, C, …等等
譬如說一個10*10的棋盤,每一個都可以是活或死(2種狀態)
所以總共有2的100次方種狀態
為了討論方便,先假設總共只有A,B,C,D,E五種狀態
————-
因為規則是固定的,所以只要知道目前的狀態
下一步的狀態是固定不變 可以預測的
我們再假設,初始狀態A開始變成B再變成C,D,一直到E
到目前為止都沒有重複之前的狀態
但是到第六步,因為總共只有5種狀態
一定會重複到之前其中一個狀態
假設重覆之前的狀態C,則又因為規則是固定的
所以C以後一定是D然後E
所以就出現C,D,E循環了
————-
這個證法可能沒辦法考慮到棋盤上某塊子區域的重複
(狀態是設定成整個棋盤的狀態)
另外也沒有考慮有些狀態可能沒辦法達到的情形(是否可能?)
不過至少可以證明只要步驟夠多次
總是會出現循環
只不過如果剛才2的100次方種狀態(1024的10次方)
如果初始條件剛好…造成那麼大的循環
可能在重覆之前我們都看不出來有循環…
就會以為是隨機產生的了…
————-
也謝謝pyridine的補充!
改天我再來談談Turing Machine
Mr. Thursday: 當然, Game of Life 跟 Turing Machine 全等的證明, 是假設遊戲板無限大, 因此可能的 state 也有無限多個. 在這種假設下, Game of Life 的行為有所有 Turing Machine 的複雜性, 因此可以有非周其行為. 其實這類的研究在 70 年代就作得很詳細了, 有些人甚至造出能產生值數的 glider gun (!). 此外, Game of Life 沒有達不到的 state.
我曾經想寫一個在 klein bottle 上玩的 game of life, 不過一值沒有機會. 大部分模擬 game of life 的軟體, 都是讓邊界 wrap 到另外一邊, 也就是使用甜甜圈的拓僕. 改用 Klien bottle 的拓僕, 不會影響到遊戲的性質, 不過我覺得劃成 3D 的圖形會滿好看的, 可以做 screen saver.
謝謝pyridine的說明!
也許以後可以向您請教一下拓樸的問題?
因為我現在manifolds看書還看不大懂…
主要是neighbor的概念不大了解
也許有機會再向您問問啦! 謝謝囉!
———————
Game of Life的行為我就沒有再詳細研究下去
也許等日後有遇到類似問題的時候才會繼續研究了…
希望我沒有錯過那些精采的研究成果才好…