2次元のセルラー・オートマトン（ライフゲーム）をPythonで試す

# TL;DR

- 2次元環境でのセルラー・オートマトンを復習しつつPythonで動かします。
- 以下のようなアニメーションのものを作ります。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/d921e6d6-3879-bc7b-ede0-0e0cc2180250.gif">　<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/8558243e-b506-f038-d0bd-f611369822e0.gif">

# 主な参考文献

- [作って動かすALife ―実装を通した人工生命モデル理論入門](https://www.amazon.co.jp/dp/4873118476/)

また、上記書籍の[githubのリポジトリ](https://github.com/alifelab/alife_book_src)のコードもMITライセンスなので参照・利用させていただきますmm

※本記事では割愛した説明なども山ほどあるので、ALife関係の詳細は書籍をお買い求めください。

# 前提

[以前書いた1次元のセルラー・オートマトンの記事](https://qiita.com/simonritchie/items/f41ed3448ad4c43e7621)をベースとしています（用語の説明なども含め、重複している箇所の説明は省きます）。

# ライフゲームとは

> ライフゲーム (Conway's Game of Life[1]) は1970年にイギリスの数学者ジョン・ホートン・コンウェイ (John Horton Conway) が考案した生命の誕生、進化、淘汰などのプロセスを簡易的なモデルで再現したシミュレーションゲームである。単純なルールでその模様の変化を楽しめるため、パズルの要素を持っている。
>
> 生物集団においては、過疎でも過密でも個体の生存に適さないという個体群生態学的な側面を背景に持つ。セル・オートマトンのもっともよく知られた例でもある。
> [ライフゲーム - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0)より。

3x3のグリッドで、中央のグリッドが次の時間で0になるのか1になるのかを、周囲のグリッドの現在の条件に応じて決められたルールに応じて変化させる計算となります。
1次元のときは左右の2つのセルに応じて次の時間の中央のセルの状態が決定する、というものでしたが、今度は上下と斜めのセルが増えるので、8個のセルに依存します。
それぞれ1が生きている、0が死んでいると表現され、結果として生まれるアニメーションがまるで生命のように振舞ったりすることから名前にライフと付いています。

![20190818_1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/10e2a5dc-b537-a2ed-7bb1-1dbeb3613cab.png)

1次元のときは、例えばウルフラムさんのルール0～ルール255のように、様々なルールが存在しました。
2次元のライフゲームでは、固定で以下のようなルールが存在するようです（それぞれ**誕生**・**生存**・**過疎**・**過密**と呼ばれます）。

# ライフゲームのルール

## 誕生・もしくは再生

中央のセルが死んでいる（0）状態で、且つ周りのセルで生きているセル（1）が3つある場合に、次の時間で中央のセルは誕生（もしくは再生と呼ばれます）します（1になります）。

![20190818_3.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/d58d089b-276f-021b-3683-d290a57a160f.png)

## 生存・もしくは均衡状態

中央のセルが生きている（1）状態で、且つ周りに生きている（1）セルが2つもしくは3つある場合は、そのセルはそのまま次の時間も生存（1のまま）します（均衡状態とも呼ばれます）。

![20190818_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/c0b03dc6-b767-8c65-6ec7-0b9b6c6eb899.png)

## 過疎・もしくは人口過疎

中央のセルが生きている（1）状態で、且つ周りに生きている（1）セルが1つ以下の場合、次の時間に死にます（0になります）。

![20190818_5.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/568ffdfe-86a4-087d-4436-5d305636dcf4.png)

## 過剰・もしくは人口過剰

中央のセルが生きている（1）状態で、且つ周りに生きている（1）セルが3つ以上ある場合、次の時間に死にます（0になります）。

![20190818_6.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/7e42e0ec-65b9-464b-a0ce-751dd51f3c5f.png)

生きている状態が多くても少なくても死んでしまい、死んでいる状態で周りに生きている状態が増えたら生き返り、バランスが良い状態の場合はそのまま生き続けるといった感じです。

人口が多すぎると快適に生活ができなかったり、食料が足りなくて死んでしまい、人口が少なすぎても生活で困ってしまう。何も無い状況から突然生物が生まれたりはせず、親が居てはじめて次の世代が誕生する、といったように現実と照らし合わせると面白いルールですね。

# Pythonでの実装

## 使う環境

- Windows
- Python 3.6.8
- NumPy==1.14.5
- Vispy==0.5.3
- Jupyter notebook
- [前述の書籍のgithubのコード](https://github.com/alifelab/alife_book_src)
    - ※事前にcloneしてimportできるようにしておきます。可視化でalifebook_lib以下のモジュールを利用します。

## 初期化処理

まずは必要なモジュールのimportや可視化用のウインドウなど含め初期化処理を進めていきます。

```py
import numpy as np
from alifebook_lib.visualizers import MatrixVisualizer

visualizer = MatrixVisualizer()
```

縦横でいくつずつセルを設けるかを`WIDTH`と`HEIGHT`という名前で定義します。今回は50個ずつ扱います。

```py
WIDTH = 50
HEIGHT = 50
```

続いて行列を初期化します。1次元のセルラー・オートマトンの時と同様、次の時間を扱うために、`state`の他にも`next_state`という名前で行列を用意します。

stateの方の行列は、ランダムに0もしくは1の値が設定されるように設定しておきます。

```py
state = np.random.randint(low=0, high=2, size=(HEIGHT, WIDTH))
next_state = np.zeros(shape=(HEIGHT, WIDTH), dtype=np.int8)

state
```

```
array([[1, 1, 1, ..., 1, 0, 1],
       [0, 0, 0, ..., 0, 1, 1],
       [1, 1, 1, ..., 1, 0, 1],
       ...,
       [0, 0, 0, ..., 0, 1, 0],
       [1, 0, 0, ..., 1, 1, 0],
       [0, 0, 0, ..., 1, 0, 1]])
```

続いて、状態を更新するためのループを実装します。
行列全体に処理をする必要があるので、ネストしたfor文で対応します。

```py
while True:
    for row in range(HEIGHT):
        for column in range(WIDTH):
            # ...
```

今回は、更新対象のセル（row, columnの位置のセル）の周囲を含めて、9個のセルの現在の値を参照する必要があります。
それぞれ、以下の図のように東西南北で変数名を設定します。

![20190818_7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/6274e417-a29a-3370-4309-6a490d1807e7.png)

行もしくはカラムのインデックスを加算する箇所（`north_east`, `east`, `south_west`, `south`, `south_east`の位置）に関しては、インデックスが行列範囲外にならないように、剰余で計算しています（範囲を超えた場合に0に戻るように）。

```py
            upper_row_idx = row - 1
            lower_row_idx = (row + 1) % HEIGHT
            left_column_idx = column - 1
            right_column_idx = (column + 1) % WIDTH
            
            north_west = state[upper_row_idx, left_column_idx]
            north = state[upper_row_idx, column]
            north_east = state[upper_row_idx, right_column_idx]
            
            west = state[row, left_column_idx]
            center = state[row, column]
            east = state[row, right_column_idx]
            
            south_west = state[lower_row_idx, left_column_idx]
            south = state[lower_row_idx, column]
            south_east = state[lower_row_idx, right_column_idx]
```

周りのセルがいくつ生きているか（1なのか）をカウントします。
0か1かの値なので、そのままcenter以外を加算していけば実現できます。

```py
            neighbor_cell_sum = (north_west + north + north_east,
                                 + west + east
                                 + south_west + south + south_east)
```

続いて、誕生（もしくは再生）の条件を書きます。中央が生きていて（1）、且つ回りに生きているセルが3つ存在する、という条件になります。

```py
            if center == 0 and neighbor_cell_sum == 3:
                next_state[row, column] = 1
```

生存（もしくは均衡状態）の条件を書きます。中央が生きている（1）で且つ周りに生きているセルが2つもしくは3つの場合はそのまま生きたままになります。

```py
            elif center == 1 and neighbor_cell_sum in (2, 3):
                next_state[row, column] = 1
```

そのほかの過剰や過疎の条件は死ぬように条件を設定しておきます。

```py
            else:
                next_state[row, column] = 0
```

最後に、for文の外で次の時間の状態の行列（`next_state`）の値を現在の状態の行列に反映し、可視化のオブジェクトに行列を渡して完成です。

```py
    state[:] = next_state[:]
    
    visualizer.update(1 - state)
```

ループのコードは最終的に以下のようになりました。

```py
while True:
    for row in range(HEIGHT):
        for column in range(WIDTH):
            upper_row_idx = row - 1
            lower_row_idx = (row + 1) % HEIGHT
            left_column_idx = column - 1
            right_column_idx = (column + 1) % WIDTH
            
            north_west = state[upper_row_idx, left_column_idx]
            north = state[upper_row_idx, column]
            north_east = state[upper_row_idx, right_column_idx]
            
            west = state[row, left_column_idx]
            center = state[row, column]
            east = state[row, right_column_idx]
            
            south_west = state[lower_row_idx, left_column_idx]
            south = state[lower_row_idx, column]
            south_east = state[lower_row_idx, right_column_idx]
            
            neighbor_cell_sum = (north_west + north + north_east
                                 + west + east
                                 + south_west + south + south_east)
            
            if center == 0 and neighbor_cell_sum == 3:
                next_state[row, column] = 1
            elif center == 1 and neighbor_cell_sum in (2, 3):
                next_state[row, column] = 1
            else:
                next_state[row, column] = 0
    
    state[:] = next_state[:]
    
    visualizer.update(1 - state)
```

動かしてみると、以下のようなアニメーションをします。

![20190819_1.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/66ed7b51-94ce-ae2b-9e0d-f9a6e2cf4ef7.gif)

ランダムな行列（実質ノイズ的な値）から、なんだかセル同士で近寄ったり、その結果消えて無くなったり・・・と、まるで生きているように、顕微鏡で微生物を見ている時みたく、意志を持っているかのような独特な動きになりました。

## 他のパターンを試す

1次元のセルラー・オートマトンでは各ルールを変えることで生成される模様が変わります。
今回の2次元のライフゲームでは、最初に与える状態の行列を調整することで色々なパターンに切り替わります。

サンプルとして本記事では、**グライダー**と**グライダーガン**と呼ばれるパターンを動かしてみます。

### グライダーパターン

まず、ランダムな初期状態を設定している箇所をコメントアウトします。

```py
# state = np.random.randint(low=0, high=2, size=(HEIGHT, WIDTH))
```

続いて、状態の行列を0で初期化し、グライダーパターンを生成するパターンを行列に与えます（行列の一部だけを更新します）。

```py
pattern = np.array(
    [[0, 0, 0, 0],
     [0, 0, 1, 0],
     [0, 0, 0, 1],
     [0, 1, 1, 1]])
state[2:2 + pattern.shape[0], 2:2 + pattern.shape[1]] = pattern
```

他のコードはそのままです。この時点で可視化してみると以下のようになります。

```py
visualizer.update(1 - state)
```

![20190819_4.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/7eca5439-59e9-a9e4-3940-62ea6c8cb0b2.png)

左上にのみ、黒い領域が設定されています。この形がなんとなくレトロゲームのグライダーっぽい・・・感じがします。
また、実際に動かしてみると、グライダーのように形をある程度保ったまま移動していくさまを確認できます。

![20190819_6.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/dccc39a5-a775-a094-813b-69313a1619db.gif)

興味を惹かれる点として、行列計算のコードはまったく変わっておらず、与える行列の初期値を変えるだけでアニメーションの傾向が変わることです。

### グライダー銃（グライダーガン）パターン

グライダーパターンをさらに発展させたものとして、グライダー銃という、周期的にグライダーを生成するようなパターンも存在します。まるでレトロゲームで攻撃のエフェクトを打ち出しているような挙動になります。

> コンウェイは「生きたセルの数が無限に増えつづけるパターンはありうるか」という問題に50ドルの懸賞金をかけた。コンウェイ自身は、そのようなパターンとして「周期的だが次々にグライダーを打ち出すもの」や「移動しながら通過した後に破片を残すもの」の存在を予想し、前者を「グライダー銃」、後者を「シュシュポッポ列車」と呼んだ。1970年11月、ビル・ゴスパー（英語版）らは、初めてグライダー銃の具体例を挙げて賞金を獲得した。
> [ライフゲーム - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0)

グライダーパターンと同様に最初に特定の行列の初期値を与えるだけで実現できます。ただし、グライダーパターンと比べて与える行列は大きく複雑です。グライダーパターンが結構発生しやすい（パターンが多い）のに対して、こちらは大分パターンが限られ、しっかり初期値を調整しないと発生してくれないそうです。

以下のように大きな行列の初期値を与えます。

```py
pattern = np.array(
    [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
      1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1],
     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0,
      1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0,
      0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
     [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
      0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
```

可視化してみると、以下のようになっています。

![20190819_7.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/bc83bc11-6679-c9c4-99be-ab7a19558e9d.png)

動かしてみると以下のようなアニメーションになります。

![20190819_7.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/228778/8558243e-b506-f038-d0bd-f611369822e0.gif)

確かに、グライダーパターンが定期的に生成されています。行列の設定だけでこういったアニメーションが生まれるというのはなんだか不思議ですね・・・。

# 参考文献まとめ

- [作って動かすALife ―実装を通した人工生命モデル理論入門](https://www.amazon.co.jp/dp/4873118476/)
- [ライフゲーム - Wikipedia](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%82%A4%E3%83%95%E3%82%B2%E3%83%BC%E3%83%A0)
- [セル・オートマトン - Wikipedia](https://ja.wikipedia.org/wiki/%E3%82%BB%E3%83%AB%E3%83%BB%E3%82%AA%E3%83%BC%E3%83%88%E3%83%9E%E3%83%88%E3%83%B3)