0%

约翰康威的生命游戏

发表于
from Peter Norvig's pytudes project

规则

生命游戏的世界是一个无限的二维正交(orthogonal)网格，每个网格都处于两种可能的状态中的一种。空(empty)的或者活(live)的。每个单元格有八个相邻单元格，即水平，垂直或对角(diagonally)相邻的单元格。在每一步中，应用一下规则创造下一代：

  • 任何有两个或三个邻居的活格子会存活到下一代
  • 任何空各自周围刚好有三个邻居的时候会在下一代变成活格子
  • 其他格子在下一代会变成空的

开发生命程序

为了创造玩生命游戏的程序，我们先厘清以下词汇所代表的概念：

  • 世界
  • 格子(cell)
  • 活/空
  • 邻居
  • 下一代
  • 展示(display)
  • 活邻居数(Live Neighbor Counts)

然后考虑如何实现它们:

  • 世界：世界的需要表现格子的状态，空或者活。难办的是各自数是无限的，我们不能在电脑里存一个无限大的数组。为此，我想了三个办法来解决这个：

    ​ 1.改变规则：变无限为有限(世界边缘的格子邻居少，或者让他们环绕到世界另一边)

    ​ 2.在无限的网格中用一个有限的矩形窗口来盖住所有活的格子，比如说：

    [[0, 0, 0, 0, 0],

    [0, 0, 0, 1, 0],

    [0, 1, 0, 0, 0],

    [0, 0, 0, 0, 0]]

    ​ 3.用活着的格子的集合(set of live cells)来表示世界，这个集合会随着代际变化缩小或者扩大，但是不用担心溢出。例如：world = {(3, 1), (1, 2), (1, 3), (2, 3)}

    我选择这个解决办法。

  • 格子：每个格子用(x, y)表示

  • 活/空：格子是活的，表明它在活着的格子的集合中

  • 邻居：一个细胞有8个邻居，例如：

    neighbors((8, 8)) == [(7, 7), (8, 7), (9, 7), (7, 8), (9, 8), (7, 9), (8, 9), (9, 9)]

  • 展示：我们需要展示这个世界的状态，让我们先推迟(defer)一下。

  • 下一代：我们定义一个函数next_generation(word), 把世界作为输入，根据这个规则，返回一个新的世界，其中有新的活着的格子的集合，例如：

    next_generation({(3, 1), (1, 2), (1, 3), (2, 3)}) == {(1, 2), (1, 3), (2, 3)}

  • 活邻居数：我要知道每个格子有多少活邻居。一个好办法是用字典：{(x, y):count}.但是哪些格子应该作为键呢？我们可以从活格子开始，然后把所有活格子的邻居加入。一个生成该字典的简单方法是创建一个Counter，并传递给所有活格子的邻居。这个有点像在做“反向”计数(counting “backwards”)，我们不是对每个格子询问：你有多少邻居，而是对每个活格子问，并对每个邻居计数。

以下是实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from collections import Counter

def next_generation(world):
    "The set of live cells in the next generation."
    possible_cells = counts = neighbor_counts(world)
    return {cell for cell in possible_cells
           if(counts[cell] == 3)
           or (counts[cell] == 2 and cell in world)}

def neighbor_counts(worlds):
    "A {cell: int} counter of the number of live neighbors for each cell that has neighbors."
    return Counter(nb for cell in world
                  for nb in neighbors(cell))

def neighbors(cell):
    "All 8 adjacent neighbors of cell."
    x, y = cell
    return [(x-1, y-1), (x, y-1), (x+1, y-1), 
            (x-1, y),             (x+1, y), 
            (x-1, y+1), (x, y+1), (x+1, y+1)]

run函数可以生成N代

1
2
3
4
def run(world, n):
    for g in range(n):
        world = next_generation(world)
    return world

展示（display）

现在我们看下如何展示世界。

1
2
3
4
5
6
7
8
9
10
11
import time
from IPython.display import clear_output, display_html

LIVE = '@'
EMPTY = '.'
PAD = ' '

def picture(world, Xs, Ys):
    "return a picture: agrid of characters representing the cells in this window."
    def row(y): return PAD.join(LIVE if (x, y) in world else EMPTY for x in Xs)
    return '\n'.join(row(y) for y in Ys)
1
print(picture(world, range(5), range(5)))
1
2
3
4
5
. . . . .
. . . @ .
. @ . . .
. @ @ . .
. . . . .

下面这个函数在每一步展示出图片

1
2
3
4
5
6
7
8
9
10
11
def display_run(world, n=10, Xs=range(10), Ys=range(10), pause=0.2):
    "Step and display the world for the given number of generations."
    for g in range(n + 1):
        html = ('Generation {}, Population {}\n{}'
               .format(g, len(world), pre(picture(world, Xs, Ys))))
        clear_output()
        display_html(html, raw=True)
        time.sleep(pause)
        world = next_generation(world)
        
def pre(text): return '<pre>' + text +'</pre>'
1
display_run(world, 5, range(5), range(5))
1
2
3
4
5
6
Generation 5, Population 4 
. . . . .
. . . . .
. @ @ . .
. @ @ . .
. . . . .

有趣的世界

现在让我们来看看生命游戏爱好者们发现的一些最初的世界。用一组明确的（x，y）坐标来枚举这些是很乏味的，因此我们将定义函数shape，它将图片作为输入并返回一个世界；shape和picture或多或少是相反的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shape(picture, offset=(3, 3)):
    "Convert a graphical picture into a world(set of cells)"
    cells = {(x, y)
            for (y, row) in enumerate(picture.splitlines())
            for (x, c) in enumerate(row.replace(PAD, '')) if c == LIVE}
    return move(cells, offset)

def move(cells, offset):
    "Move/Translate/slide a set of cells by a (dx, dy) displacement/offset."
    (dx, dy) = offset
    return {(x + dx, y + dy) for (x, y) in cells}
    
blinker = shape("@@@")
block = shape("@@\n@@")
beacon = block | move(block, (2, 2))
toad = shape(".@@@\n@@@.")
glider = shape(".@.\n..@\n@@@")
rpentomino = shape(".@@\n@@.\n.@.", (36, 20))
line = shape(".@@@@@@@@.@@@@@...@@@......@@@@@@@.@@@@@", (10, 10))
growth = shape("@@@.@\n@\n...@@\n.@@.@\n@.@.@", (10, 10))

不用IPython

如果要在Ipython/Jupyter notebook之外的终端中运行此代码，可以删除:

1
2

from IPython.display import clear_output, display_html

加上

1
2
3
4
5
def clear_output(): print("\033[;H\033[2J") # ANSI terminal home and clear

def display_html(text, raw=False): print(text)

def pre(text): return text

Coding Kata

代码kata是一种编程练习，它帮助程序员通过练习和重复来磨练他们的技能。

其中一个练习是在不使用任何条件（如if）语句的情况下编写生命游戏。我使用了大致如下所示的程序，但在next_generation中将单独的 if改为filter：

1
2
3
4
def next_generation(world):
    possible_cells = counts = neighbor_counts(world)
    def good(cell): return counts[cell] == 3 or (counts[cell] == 2 and cell in world)
    return set(filter(good, possible_cells))