相信大家對蝴蝶效應(butterfly effect)耳熟能詳,最簡單的譬喻大概是:台灣美濃的一隻蝴蝶輕拍一下翅膀,可能造成影響美國佛羅里達州的颶風。由於氣候系統是動態的,初始條件微不足道的變化,可能造成影響整個系統的巨大連鎖反應。可是這個蝴蝶變颶風的「實例」說得簡單,實際上卻很難想像和驗證啊!不打緊,只要我們打開電腦或平板,玩一玩生命遊戲(Game of Life),就能在螢幕上看到蝴蝶效應了!
遊戲規則
生命遊戲是由英國數學家約翰.何頓.康威(John Horton Conway)發明,刊登在《科學人》雜誌的數學遊戲專欄。生命遊戲的名稱,來自遊戲模擬的就是真實世界當中的生物。首先假設一個方形的棋盤格,每一格都是一個細胞的空間;遊戲開始時,我們可以扮演「上帝」的角色,任意決定棋盤上哪些細胞是活的。之後細胞就遵循下列規則,與周圍相鄰的8個細胞互動:
- 假如一個活細胞周圍有 2~3 個活細胞,這個活細胞就能繼續存活到下一世代。
- 假如一個活細胞周圍 <2 個或 >3 個活細胞,這個活細胞就會因為「資源不足」或「過度擁擠」,在下一世代死亡。
- 假如一個死細胞周圍恰好有 3 個活細胞,這個死細胞就會在下一世代復活,象徵「細胞繁殖」。
同一個世代的每個細胞同時依照以上三個規則運算後,就產生下一世代的細胞圖,如此周而復始。大家有沒有注意到了:生命遊戲開始之後,不需要玩家插手,就可以一直繼續玩下去了!所以這是一個零玩家遊戲,只要初始條件設定好,我們就可以泡杯咖啡,靜靜觀察這些細胞自我繁殖的過程。
生命遊戲的多變圖案
康威當初在設計生命遊戲時,經過許多實驗精心考慮規則,使細胞不會爆炸性繁殖,又能從相對簡單的初始條件,產生難以預測的結果。生命遊戲更具有「不可決定性」的特點:給定任意起始條件 A 和最終條件 B,判斷 A 的後續世代中是否會造成 B 的演算法是不存在的。因此上述的規則看似簡單,卻能衍生出非常複雜又引人入勝的圖案。一個穩定繁殖中的圖案,往往只要稍微改變幾個細胞,就會產生骨牌效應,把整個系統搞砸,或者產生出令人意想不到的結果!數學家與電腦科學家們往往會用現實生活中的物品,為他們發現的圖案命名。
首先最單調的就是靜物(still lifes),也就是世世代代都不動如山的圖案,最簡單的圖案有下面幾種,其中白色圓點代表活細胞,藍色空白處為死細胞:
我們可以用上面的規則檢查看看,上面每個圖案中,是不是所有的細胞都會維持原本狀態呢?
稍微有趣一點的是振盪器(oscillators),顧名思義,就是在世代發展的過程中,會在幾個不同圖案之間循環。振盪器可以有不同週期,數學家已經發現了很多週期的振盪器,但卻還找不到週期為 19、23、34、38、41 的,這是個非常有趣而具有挑戰性的問題。
太空船(spaceships)就更有意思了,這些圖案會隨著世代發展在棋盤格上移動或「飛行」。太空船中最有名的大概就是滑翔翼(glider,下圖左)了,只要路線上沒有東西阻礙,就會沿著對角線永無止境地滑翔。由於許多程式設計師喜歡玩生命遊戲,結構簡單的滑翔翼被許多駭客們當作標誌。各種太空船的速度不盡相同(下圖右),但就像現實生活中所有物體移動和資訊傳播都沒辦法超越光速,生命遊戲中也有「光速」(一樣用 c 表示):由於一個細胞每世代只能影響到相鄰的細胞,所以生命遊戲中的光速就是每世代一格,所有太空船都沒辦法超過這個速度。
康威曾經懷疑,生命遊戲中是否有圖案能夠永無止盡繁殖下去(穩定產生越來越多的活細胞),還懸賞了50英鎊給第一個發現可無限繁殖圖案的人。這樣的圖案很快就被美國數學家比爾.高斯帕(Bill Gosper)發現了,他設計了一種可以不斷產生滑翔翼的裝置,稱為滑翔翼機關槍(glider gun),之後數學家又發現更多可以不斷發射出太空船的構造,仿照高斯帕原本取的名字統稱為「槍」(guns)。另外一般的太空船,船過水無痕,但有些特殊的太空船會邊走邊「慶煙」,在軌跡上留下「廢氣」,被數學家暱稱為「蒸汽火車」(puffer train)。
除了以上的「生物」之外,還有可把其他生物吃掉的大胃王(eaters)、可以反射太空船的反射板(reflectors)、甚至可以邊走邊產生無數「二級結構」,這些二級結構又可以不斷產生「三級結構」,使活細胞數量成二次方生長的繁殖器(breeder)等等多采多姿的不同結構。數學家與電腦科學家利用這些結構的組合,可以在生命遊戲中製造相當於現實生活中的許多機械。
生命遊戲的應用
讀到這邊,大家可能會出現一些疑惑:這種純粹欣賞的零玩家遊戲,除了當螢幕保護程式之外,有什麼具體用途嗎?首先由於生命遊戲規則簡單,卻能產生非常複雜的結果,因此不論是初學者或高階程式設計者都經常接觸它。假如記憶體和運算時間沒有限制,生命遊戲可以用來模擬所有的運算過程;換句話說生命遊戲本身就等於一台電腦。筆者也是在大學的基礎 MATLAB 程式設計課程中,首次認識生命遊戲的,最近重新讀到,頓時興致大發,就在生命遊戲中建立一個泛科學跑馬燈:
生命遊戲屬於一個更大範疇的模型──細胞自動機(cellular automaton),泛指所有規律格狀的系統,每格處於有限種類的狀態,而這些狀態是由上一世代的相鄰格子狀態來定義出來的。細胞自動機依照演化方式可粗略分成 4 大類,其中最複雜的第 4 類中,幾乎所有初始狀態都會演化成複雜、渾沌和接近隨機的狀態,生命遊戲也屬於第 4 類。由於以上的特性,細胞自動機可以模擬生物過程、物理粒子的交互作用,甚至地理學、經濟學和社會學;甚至有不少科學家提出了一個問題:整個宇宙是否也是個細胞自動機呢?
1986 年法國藝術家奧利維爾.奧柏(Olivier Auber)更提出了「真人版」生命遊戲──Poietic Generator:在傳統生命遊戲中,每個細胞下一回合的命運,純粹由鄰近的細胞決定;而在 Poietic Generator 中,每位玩家一次可以更改點陣圖中其中一格的顏色,由不同玩家透過網路連線共同創作。在這個遊戲中,沒有所謂的輸贏,主要的目標在欣賞和參與大家的創作過程,共同創造出動態的藝術品。
想玩玩看生命遊戲嗎?網路上有許多利用 JavaScript 寫成的模擬器,另外假如想要深入了解生命遊戲和更多規則各異的細胞自動機,筆者建議下載 Golly 這個免費模擬器,在電腦、iPad與Android多平台上都可以使用喔!
參考文獻
- 維基百科
- LifeWiki
- Conway’s Game of Life, Binary Digits