The Nature of Code閱讀心得與Python實作：7.4 The Game of Life

這一節介紹的是赫赫有名的2D CA：生命遊戲(the Game of Life)。

科普雜誌《科學美國人》(Scientific American)的專欄作家Martin Gardner，在1970年10月那一期的「數學遊戲」(Mathematical Games)專欄中，以〈The fantastic combinations of John Conway's new solitaire game "life".〉一文，深度介紹了由數學家John Conway所設計的「生命遊戲」之後，立刻引起了一股「生命遊戲」的風潮；尤其是電腦玩家，更是為之瘋狂。這股風潮到現在都還沒停歇，在網路上可以找到許多「生命遊戲」的模擬程式，而且「生命遊戲」到現在，都還是許多人在學習程式設計時，會碰到的練習題目。

1. 不應該存在能夠用簡單的方法就能證明它會使細胞族群可以無限制增長的初始樣式(pattern)。
2. 應該存在顯然真的能夠讓細胞族群無限制增長的初始樣式。
3. 應該存在一些簡單的初始樣式，這些樣式可以讓細胞族群在歷經一段長時間的增長和變化之後，以下列三種可能的方式結束增長和變化：
   • 因為過度擁擠或過度稀疏而使族群逐漸消失殆盡。
   • 形成穩定且不再變化的結構。
   • 進入震盪階段，以兩個或多個週期的方式，無限循環地震盪下去。

上述目標所描述的，其實在本質上就是Wolfram的Class 4 CA。怎麼說呢？這類CA雖然有模式存在，但卻沒辦法預測這些模式在什麼時候會出現；除此之外，這類CA最後還會變成只有單一樣式，或者進入在不同模式間震盪的狀態。這也就是說，儘管Conway沒有使用複雜系統這個術語來描述他所設計的「生命遊戲」，但毫無疑問的，「生命遊戲」已具備了複雜系統的所有性質。

The Rules of the Game

在「生命遊戲」的設定中，細胞會有兩種不同的狀態：當細胞的狀態值是1時，代表細胞活著；當狀態值是0時，代表細胞死了。

因為「生命遊戲」是個2D CA，所以每個細胞的鄰域會有9個細胞。

「生命遊戲」的演化規則，是去計算在鄰域中，中央細胞有多少毗鄰的鄰居是活著的，據此來決定中央細胞在下一世代的死活。中央細胞在下一世代是死是活，規則如下：

1. 死亡：如果細胞原本是活著的，當碰到下面任一種情況，它在下一世代就會死亡：
   •過度擁擠：如果有4個或超過4個毗鄰的鄰居活著。
   •孤獨：如果只有1個甚或沒有毗鄰的鄰居是活著的。
2. 出生：如果細胞原本已經死了，當不多不少剛好有3個毗鄰的鄰居是活著的，則在下一世代它會活過來。
3. 靜止不變：如果不屬於前面「死亡」和「出生」兩種情況中的任一種，則細胞在下一世代中會維持原來的狀態不變。這會有兩種狀況：
   •繼續活著：如果細胞原本是活著的，而剛好有2個或3個毗鄰的鄰居是活著的，則它會繼續活著。
   •保持死亡狀態：如果細胞原本是死的，而且沒有3個活著的毗鄰鄰居，則它會繼續保持死亡狀態。

規則有了，那要怎麼展示CA的演化過程呢？跟基礎CA一次展示所有世代的方式有所不同，在展示「生命遊戲」這個2D CA的演化過程時，我們一次只展示一個世代，然後每隔一段時間再展示下一個世代；就像動畫或電影一幀一幀的播放一樣。

設定好初始樣式，然後依據演化規則來讓細胞進行演化，完全不需要人為的介入，就可以看到細胞族群隨著時間一代一代的演變，產生令人驚異的圖案出來。在「生命遊戲」的狂熱之中，玩家們發現了一些可以產生讓人非常著迷結果的初始樣式，並用現實生活中的物品名稱來命名這些特別的樣式。例如，從頭到尾都不動如山，永不改變的方塊(block)、蜂窩(beehive)、麵包(loaf)、小船(boat)

會在兩個不同樣式間來回震盪的信號燈(blinker)、蟾蜍(toad)、信標(beacon)

以及圖案會移動的滑翔機(glider)、輕型太空船(lightweight spaceship)等。

在網路上有不少網站可以玩「生命遊戲」；原書提供了兩個：

• Exploring Emergence by Mitchel Resnick and Brian Silverman, Lifelong Kindergarten Group, MIT Media Laboratory
• Conway's Game of Life in p5.js by Steven Klise

另外這個也不錯：

• Play John Conway's Game of Life

The Implementation

先前在寫基礎CA的程式時，因為細胞的排列方式是1D長條狀的，所以使用1D的list來存放細胞的狀態值。與基礎CA不同，「生命遊戲」的細胞排列方式是2D棋盤狀的，所以必須改用2D的list來存放細胞的狀態值。

從1D的list改用2D的list，這看起來沒什麼大不了的，不過python的2D list在使用上有許多要注意的地方，稍有不慎或觀念不清，就有可能犯錯而不自知；在〈跌跌撞撞製造二維list〉這篇文章中所提到的，就是一例。

要使用2D list，第一步當然就是要先造出來。假設「生命遊戲」的細胞排列成一個有rows橫列及columns直行的棋盤狀2D平面，要造一個填滿0，可以存放這些細胞狀態的2D list，程式可以這樣寫：

board = [[0]*columns for _ in range(rows)]

除了board這個2D list之外，我們還需要再造一個用來存放下一世代細胞狀態的2D list：

next_generation = [[0]*columns for _ in range(rows)]

造好可以存放細胞狀態的2D list之後，接下來就是要設定每個細胞的初始狀態。不過，在進行設定前，必須先決定那些位於邊緣的細胞，它們的狀態要怎麼處理；因為那些細胞的鄰域並不完整，其內並沒有正常應該有的細胞數量。

跟在處理基礎CA時的方式一樣，我們讓邊緣細胞的狀態都維持不變，不會因世代的變化而有所不同。因為在造board這個2D的list時，我們直接就把所有的元素值都設定為0，所以在設定「生命遊戲」的初始樣態時，就只需要設定非邊緣細胞的初始狀態就可以了。假設我們要讓初始樣態是隨機的，程式可以這樣寫：

for i in range(1, rows-1):
    for j in range(1, columns-1):
        board[i][j] = random.randint(0, 1)

這裡因為要排除位於邊緣的細胞，所以巢狀迴圈的內、外圈索引值，必須分別落在range(1, columns-1)及range(1, row-1)之中。

有了初始樣態之後，就可以進行迭代了。在迭代時，必須針對每個非邊緣細胞，計算其8個毗鄰的鄰居中，有幾個是活著的。對於board[i][j]這個細胞而言，它會有如下圖所示的8個毗鄰的鄰居

所以，要計算board[i][j]這個細胞有幾個活著的毗鄰鄰居，做法很簡單，就利用迴圈把九宮格中的所有細胞狀態值加總，並扣除board[i][j]這個細胞的狀態值就可以了。寫成程式就長這樣：

neighbor_sum = -board[i][j]
for m in range(-1, 2):
    row = i + m
    for n in range(-1, 2):
        col = j + n    
        neighbor_sum += board[row][col]

另一種可以讓程式比較精簡的寫法，是利用sum()函數搭配list這個資料結構的slicing功能，寫成這樣：

neighbor_sum = sum(board[i-1][j-1:j+2]) +  \
               sum(board[i][j-1:j+2:2]) +  \
               sum(board[i+1][j-1:j+2])

知道細胞周圍有多少活著的毗鄰鄰居之後，就可以根據規則來決定細胞在下一世代的狀態了；程式如下：

if board[i][j] == 1 and (neighbor_sum >= 4 or neighbor_sum <= 1):
    # 規則 1
    next_generation[i][j] = 0
elif board[i][j] == 0 and neighbor_sum == 3:
    # 規則 2
    next_generation[i][j] = 1
else:
    # 規則 3
    next_generation[i][j] = board[i][j]

當所有細胞在下一世代的狀態都已經算出來之後，必須把放在next_generation中的狀態值複製到board中。這個複製的動作可以這樣寫：

for i in range(rows):
    for j in range(columns):
        board[i][j] = next_generation[i][j]

另一個比較簡潔的寫法是利用deep copy的方式：

board = [element[:] for element in next_generation]

當然，利用copy這個module的deepcopy()函數，也可以達到目的。之所以必須用deep copy的方式，是為了避免board和next_generation這兩個list在更動元素的值時互相影響；這是使用2D list時必需要特別小心注意的。

最後，來看看在把細胞畫出來顯示在畫面上時，可以用到的小技巧。

因為細胞的排列方式是棋盤狀的，所以用方塊來呈現細胞的樣子是最直接了當的。要畫方塊，可以用pygame的draw.rect()方法。假設我們希望用填滿的方塊來代表活著的細胞，而用空心的方塊來代表死了的細胞，這時候程式可以這樣寫：

for i in range(rows):
    for j in range(columns):
        x, y = j*cell_size, i*cell_size
        rect = pygame.Rect(x, y, cell_size, cell_size)
        pygame.draw.rect(screen, (0, 0, 0), rect, 1-board[i][j])

這裡的cell_size是細胞的尺寸，也就是方塊的邊長；screen則是要顯示的畫面。

在上面那段程式中，要不要把方塊填滿，是由在draw.rect()裡頭的1-board[i][j]這個引數來控制的；這個引數對應的是width這個非必要、可給可不給的參數。參數width，可以用來設定要用多粗的線來畫矩形，也可以用來設定要不要把矩形填滿；用法如下：

width = 0：預設值；填滿矩形
width > 0：用來畫矩形的線的寬度
width < 0：不畫任何東西

所以，如果設定

width = 1 - board[i][j]

則當細胞的狀態值是1時，width會等於0；而當細胞的狀態值是0時，width會等於1。這也就是說，碰到活的細胞，draw.rect()會畫出填滿的方塊；而碰到死的細胞，則會畫出空心的方塊。利用這樣子的寫法，可以在不預先檢查細胞狀態值的情況下，正確地畫出對應於細胞狀態的方塊，而讓程式看起來簡潔一點。

Example 7.2: Game of Life

# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0

    
pygame.init()

pygame.display.set_caption("Example 7.2: Game of Life")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 640, 240
screen = pygame.display.set_mode(screen_size)

FPS = 10
frame_rate = pygame.time.Clock()

# 細胞方塊邊長
cell_size = 10

columns, rows = WIDTH//cell_size, HEIGHT//cell_size

board = [[0]*columns for _ in range(rows)]

# 設定初始樣式；排除位於邊緣的細胞
for i in range(1, rows-1):
    for j in range(1, columns-1):
        board[i][j] = random.randint(0, 1)
        
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()    

    screen.fill(WHITE)

    next_generation = [[0]*columns for _ in range(rows)]
    # 計算下一代細胞的狀態；排除位於邊緣的細胞
    for i in range(1, rows-1):
        for j in range(1, columns-1):
            # 計算活著的鄰居數量
            neighbor_sum = sum(board[i-1][j-1:j+2]) +  \
                           sum(board[i][j-1:j+2:2]) +  \
                           sum(board[i+1][j-1:j+2])
            
            # 依據規則決定下一代細胞的狀態
            if board[i][j] == 1 and (neighbor_sum >= 4 or neighbor_sum <= 1):
                # 規則 1
                next_generation[i][j] = 0
            elif board[i][j] == 0 and neighbor_sum == 3:
                # 規則 2
                next_generation[i][j] = 1
            else:
                # 規則 3
                next_generation[i][j] = board[i][j]

    # 畫出細胞；活著的細胞為黑色方塊
    for i in range(rows):
        for j in range(columns):
            x, y = j*cell_size, i*cell_size
            rect = pygame.Rect(x, y, cell_size, cell_size)
            pygame.draw.rect(screen, (0, 0, 0), rect, 1-board[i][j])
    
    board = [element[:] for element in next_generation]
  
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 7.5

點擊細胞可切換細胞狀態。

# python version 3.10.9
import random
import sys

import pygame  # version 2.3.0


pygame.init()

pygame.display.set_caption("Exercise 7.5")

WHITE = (255, 255, 255)

screen_size = WIDTH, HEIGHT = 750, 360 # 640, 240
screen = pygame.display.set_mode(screen_size)

FPS = 10
frame_rate = pygame.time.Clock()

# 細胞方塊邊長
cell_size = 20

# 側邊欄寬度
sidebar = 150

board_width, board_height = WIDTH-sidebar, HEIGHT

columns, rows = board_width//cell_size, HEIGHT//cell_size

board = [[0]*columns for _ in range(rows)]
next_generation = [[0]*columns for _ in range(rows)]

# 狀態欄及按鈕文字
font = pygame.font.SysFont(None, 32)
text_status = font.render('', True, (0, 0, 0))
text_start = font.render('Start', True, (255, 255, 255), (0, 0, 0))
text_pause = font.render('Pause', True, (255, 255, 255), (0, 0, 0))
text_reset = font.render('Reset', True, (255, 255, 255), (0, 0, 0))

# 狀態欄及按鈕位置
status_block = text_status.get_rect()
status_block.topleft = (board_width+15, 50)

button_start = text_start.get_rect()
button_start.topleft = (board_width+35, 100)

button_pause = text_pause.get_rect()
button_pause.topleft = (board_width+35, 130)

button_reset = text_reset.get_rect()
button_reset.topleft = (board_width+35, 160)

evolving = False
        
while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            sys.exit()    
        elif event.type == pygame.MOUSEBUTTONDOWN:
            if event.button == 1:
                x, y = event.pos
                if cell_size < x <= board_width and cell_size < y <= board_height:
                    # 不在邊緣的細胞才能點擊設定狀態
                    row, column = y//cell_size, x//cell_size
                    board[row][column] = 1 - board[row][column]
                elif button_start.collidepoint(x, y):
                    evolving = True
                    text_status = font.render('Evolving...', True, (0, 0, 0))
                elif button_pause.collidepoint(x, y):
                    evolving = False
                    text_status = font.render('Pausing...', True, (0, 0, 0))
                elif button_reset.collidepoint(x, y):
                    evolving = False
                    text_status = font.render('', True, (0, 0, 0))
                    board = [[0]*columns for _ in range(rows)]

    screen.fill(WHITE)
   
    if evolving:
        # 計算下一代細胞的狀態；排除位於邊緣的細胞
        for i in range(1, rows-1):
            for j in range(1, columns-1):
                # 計算活著的鄰居數量
                neighbor_sum = sum(board[i-1][j-1:j+2]) +  \
                               sum(board[i][j-1:j+2:2]) +  \
                               sum(board[i+1][j-1:j+2])
                
                # 依據規則決定下一代細胞的狀態
                if board[i][j] == 1 and (neighbor_sum >= 4 or neighbor_sum <= 1):
                    # 規則 1
                    next_generation[i][j] = 0
                elif board[i][j] == 0 and neighbor_sum == 3:
                    # 規則 2
                    next_generation[i][j] = 1
                else:
                    # 規則 3
                    next_generation[i][j] = board[i][j]
                    
        board = [element[:] for element in next_generation]

    # 畫出細胞；活著的細胞為黑色方塊
    for i in range(rows):
        for j in range(columns):
            x, y = j*cell_size, i*cell_size
            rect = pygame.Rect(x, y, cell_size, cell_size)
            pygame.draw.rect(screen, (0, 0, 0), rect, 1-board[i][j])
    
    # 放置狀態欄及按鈕
    screen.blit(text_status, status_block.topleft)
    screen.blit(text_start, button_start.topleft)
    screen.blit(text_pause, button_pause.topleft)
    screen.blit(text_reset, button_reset.topleft)
    
    pygame.display.update()
    frame_rate.tick(FPS)

Exercise 7.6

使用modulo運算子「%」就可以了。把計算細胞有多少活著的鄰居那段程式改成

# 計算活著的鄰居數量
neighbor_sum = -board[i][j]
for m in range(-1, 2):
    row = (i+m) % rows
    for n in range(-1, 2):
        col = (j+n) % columns    
        
        neighbor_sum += board[row][col]

要注意的是，使用modulo運算子來寫的話，就只能用迴圈的寫法，而沒辦法用list的slicing功能來寫。

Exercise 7.7

以Example 7.2為例，在while迴圈外新增一行

next_generation = [[0]*columns for _ in range(rows)]

然後把迴圈內的

board = [element[:] for element in next_generation]

這一行改成

for i in range(1, rows-1):
    for j in range(1, columns-1):
        board[i][j] = next_generation[i][j]

這樣就可以了。