人工生命を実装して世界大戦、人類滅亡への一歩を踏み出す

1999年から20年も経とうとしている今日このごろ、みなさんはいかがお過ごしでしょうか。

MMR 8巻89ページ〜の、「忍び寄る魔のテクノロジーとは？」を昔読んで、そこにあったrock-paper-scissorライフゲームを実装したいと以前から思っておりました。
最近変なやる気が出たので、やってみようと思います。

ちょっと漫画中の絵を引用するのは
面倒くさい
気が引けるので、
http://www.nicovideo.jp/watch/sm31413234
5:25〜を参照いただけたら幸いです。（ネタバレ注意）

ライフゲームの箇所は6:47〜6:56あたりです。

# 盤面づくり

まず、六角形グリッドを設計します。

Hexマップはデータ量的には普通の２次元配列で管理できます。
それで、下から`N`行目は`0.5*N`文字分後ろにずらすとすると、なんか六角形の格子っぽく並びます。しかし２次元配列をすべて使うと菱型の盤面になります。

```
    1 1 1 1 1
   1 1 1 1 1
  1 1 1 1 1
 1 1 1 1 1
1 1 1 1 1
```
そこで右上、左下の部分を使わないようにして、盤面全体も六角形にします。

この盤面の六角形の１辺に$N$個のセルが並ぶと、配列の１辺は$2N - 1$次元必要です。

盤面の情報とメソッドを持つクラスを準備します。

```python
class RockPaperScissorAuto(object):
    def __init__(self, N):
        self.N = N
        self.L = N*2 - 1
        self.mask = np.eye(self.L, dtype=int)
        for i in range(1, N):
            self.mask += np.eye(self.L, k=i, dtype=int)
            self.mask += np.eye(self.L, k=-i, dtype=int)
```

この時、`self.mask`は以下のようになっています。

```plain:self.mask
[[1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0]
 [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1]
 [0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1]]
```

あとは盤面のデータを保持します。

```
        self.F = np.zeros((self.L, self.L), dtype=int)
```
この `self.F` には`0`から`3`までの値が入ります。

* 0: 空セル
* 1: Rock
* 2: Paper
* 3: Scissors

# 可視化

盤面情報を画像にします。漫画であるように、頑張って円を六角形に並べていきます。

六角形の高さは$2\sqrt{3}$ですので、あらかじめ定数を準備します。

```python
import math
root3 = math.sqrt(3.0)
```

Rock、Paper、Scissorをそれぞれ赤、青、黄に対応させます。
赤、青、黄色をWikipediaで調べて出てきたカラーコードで決めます。

```python
cell_color = [(200, 0, 0), (61, 26, 237), (192, 103, 0), (0, 212, 255)]
```
(BGR)タプルをリストに並べます。先頭から空きセル、Rock、Paper、Scissorsに対応します。OpenCVを使う予定ですので、タプル内の数字はB,G,Rの順です。

画像をフィールドの情報から生成するメソッドを定義します。

```python
import cv2
# （中略）
    def make_image(self, cell_rad=15):
        width = int(self.L*cell_rad*2)
        height = int(self.L*cell_rad * root3)
        img = np.zeros((height, width, 3), dtype=np.uint8)
        for iy, ix in self.draw_index:
            dx = -abs(iy - self.W) if iy > self.W else abs(iy - self.W)
            x = int((2*ix + dx)*cell_rad + 0.5)
            y = int((2*iy + 1) * root3 * 0.5 * cell_rad + 0.5)
            color = cell_color[self.F[iy, ix]]
            lw = 2 if self.F[iy, ix] == 0 else -1
            cv2.circle(img, (x, y), cell_rad - 1, color, lw)
        return img
```

`dx`が六角形に並べるための横方向のズレです。中心の行を境にルールが変わります。

これで一辺が１５のもので描写してみます。とりあえずすべてのセルが空セルです。

```python
F = RockPaperScissorAuto(15)
img = F.make_image(cell_rad=15)
cv2.imshow("test", img)
cv2.waitKey(0)
cv2.destroyAllWindows()
```

![test_screenshot_29.05.2018.png](https://qiita-image-store.s3.amazonaws.com/0/258019/4620da30-be56-a5bd-2161-6fdff57f57cd.png)

できました。

# 時間発展

では、本題の時間発展メソッドです。
隣接セルの定義をします。

```python
neighbor = np.array([
    [1, 1, 0],
    [1, 0, 1],
    [0, 1, 1]
], dtype=int)
```

続いて、`RockPaperScissorAuto`クラスに時間発展メソッドを追加します。

```python
from scipy import signal
（中略）
    def step(self):
        empty = self.F == 0
        rock = self.F == 1
        paper = self.F == 2
        scissor = self.F == 3
        nxp = signal.correlate2d(paper, neighbor, mode="same")*(rock + empty)
        nxs = signal.correlate2d(scissor, neighbor, mode="same")*(paper + empty)
        nxr = signal.correlate2d(rock, neighbor, mode="same")*(scissor + empty)
        self.F[(nxp > 0)] = 2 
        self.F[(nxs > 0)] = 3 
        self.F[(nxr > 0)] = 1 
        self.F = self.F * self.mask
```
まずそれぞれの種類のマップを作ります（最初の４行）。
ここでpaperを例に取ります。

* あるセルに隣接するpaperセルの数：`signal.correlate2d(paper, neighbor, mode="same")`
* paperが侵略する可能性のあるセルは現在rockもしくは空のセルなので、それらとの積を取る：`correlate2d()*(rock + empty)`
* これを`nxp`に代入。これはpaperが侵略しようとしているセルについて、その周りにいるpaperセルの数を示しています。
* `nxp`が１以上のセルは次はpaperになるセルです。`self.F[(nxp > 0)] = 2`

これをrock, scissorsに対しても行います。
ここである空セルに複数種類のセルが隣接した場合、`nxp`、`nxs`、`nxr`の複数が１以上になります。このときは、paper, scissors, rockの順で上書きされます。

最後に、はみ出たものをトリミングします。`self.F = self.F*self.mask`

# ミューテーション

初期がすべて空セルなので、このままだと何も起きません。また漫画中でも突然変異と表現しているので、これを導入します。

```python
    def mutation(self, rate=0.001):
        mut = (np.random.rand(self.L, self.L) < rate)*self.mask
        self.F[mut == 1] += 1
        self.F[self.F == 4] = 1
```

すべてのセルで0.1%の確率で変異するようにします。
それぞれに一様乱数を発生させ、これが`rate`より小さいものを`True`としつつ、`mask`と積をとって系が注目する範囲にトリミングします。
それで`mut`が1のところが変異するセルということになります。
ここで変異の内容を考えると、空セル(0)がRock(1)、Rock(1)がPaper(2)、Paper(2)がScissors(3)と基本セルの値が1増えるようになっています。
一方でScissors(3)が変異するとRock(1)になりますが、そのまま１を足すと`4`になってしまうので、これを`1`に持って行って、循環させます。
これで変異が実装できました。

# 実験その１

メインルーチンです。

```python
def main():
    F = RockPaperScissorAuto(15)
    waiting = 10
    while True:
        F.step()
        F.mutation()
        img = F.make_image(cell_rad=15)
        cv2.imshow("test", img)
        r = cv2.waitKey(waiting)
        if r == ord("+"):
            waiting = max(10, waiting//2)
        if r == ord("-"):
            waiting = min(1000, waiting*2)
        if r == ord("q"):
            break
    cv2.destroyAllWindows()

if __name__ == '__main__':
    main()

```
+キーを押して加速、-キーを押して減速、qキーで終了。
これで適当に１６０ステップまでを録画してみました。

![test.gif](https://qiita-image-store.s3.amazonaws.com/0/258019/9f72f59b-e768-b594-309e-2a64c29f15f3.gif)

これではあまりに整いすぎて、漫画（8巻166頁あたり）であったような、迷彩柄のような３色入り乱れた様子にはなっていません。

# 実験その２

すこしランダム性を足してみます。周りに侵食するとき、ランダムで侵食したりしなかったりするとどうなるかやってみます。

```python
    def step(self):
        empty = self.F == 0
        rock = self.F == 1
        paper = self.F == 2
        scissor = self.F == 3
        nxp = signal.correlate2d(paper, neighbor, mode="same")*(rock + empty)
        nxs = signal.correlate2d(scissor, neighbor, mode="same")*(paper + empty)
        nxr = signal.correlate2d(rock, neighbor, mode="same")*(scissor + empty)
        pickup_mask = np.random.rand(self.L, self.L) < 1.0/6
        self.F[(nxp > 0)*pickup_mask] = 2 
        self.F[(nxs > 0)*pickup_mask] = 3 
        self.F[(nxr > 0)*pickup_mask] = 1 
        self.F = self.F * self.mask
```
適当に間引くために`pickup_mask`を導入します。確率的に6分の1になるようにします。
６つの隣接セルに対してランダムで１方向だけに進むイメージでパラメータを決めましたが、多少少なすぎたかもしれません。

変異率のパラメータなどを調整して、漫画であるような見た目に近づけます。
一辺20セル、変異率を0.00001程度にしてみました。

QiitaにGIFアニメを上げるにあたって、ファイル容量削減のため、かなり途中経過を削りました。

![test.gif](https://qiita-image-store.s3.amazonaws.com/0/258019/9db07874-0e38-75b3-88b8-2eab11953026.gif)

漫画の例に比べてまだ島が小さい気がするのですが、この程度で満足しておきます。

# 他のパターン

https://www.youtube.com/watch?v=M4cV0nCIZoc
こちらの動画では同じくRock-Paper-Scissor Automatonですが、一定の配置になると渦巻きが発生します。こちらを再現したいと思います。

いろいろ試した結果、セルにHPを定義するとうまく行きました。

HP制のルールは以下のようにしました。

* 空セルは初期HP１、Rock/Paper/Scissorsは初期HPに`MAX_HP`を持つ。
* 時間発展の１ステップ中で：
  - Rock/Paper/Scissorsは周囲の空セルもしくは自分が勝てる相手に１のダメージを与える。
  - HPを０以下にできたマスに、自分と同じ色のセルを置く。新しく生まれたセルのHPは`MAX_HP`。

例えばPaperに周りを囲まれたRockは１ターンで６のダメージを受けます。
Paperに囲まれたScissorsは周りのPaper全てにそれぞれ１のダメージを与えます。

この時、`step`と`mutation`をはじめ、`RockPaperScissorAuto`クラスを以下のように定義します。

```python
MAX_HP = 8

class RockPaperScissorAuto(object):
    def __init__(self, W):
        self.W = W
        self.L = W*2 - 1
        self.F = np.zeros((self.L, self.L), dtype=int)
        self.HP = np.ones_like(self.F)
        ...
（中略）

    def step(self):
        empty = self.F == 0
        rock = self.F == 1
        paper = self.F == 2
        scissor = self.F == 3
        nxp = signal.correlate2d(paper, neighbor, mode="same")*(rock + empty)
        nxs = signal.correlate2d(scissor, neighbor, mode="same")*(paper + empty)
        nxr = signal.correlate2d(rock, neighbor, mode="same")*(scissor + empty)
        self.HP -= (nxp + nxs + nxr)
        self.F[(nxp > 0)*(self.HP < 1)] = 2 
        self.F[(nxs > 0)*(self.HP < 1)] = 3 
        self.F[(nxr > 0)*(self.HP < 1)] = 1 
        self.HP[((nxp + nxs + nxr) > 0)*self.HP < 1] = MAX_HP 
        self.F = self.F * self.mask
    
    def mutation(self, rate=0.0025):
        mut = (np.random.rand(self.L, self.L) < rate)*self.mask
        self.F[mut == 1] += 1
        self.F[self.F == 4] = 1
        self.HP[mut == 1] = MAX_HP
```

これで時間発展させるとこんな感じになりました。

上段：左は開始直後、右は初期の変異が起こって広い範囲を占領する段階。
中段：左は中程に渦の種ができています。右はそこから渦が広がっています。
下段：左は大体渦が全体に広がり、変異でところどころ縞が途切れています。右は渦が広がってだいぶ経った段階で、形が崩れています。

![test_tile.png](https://qiita-image-store.s3.amazonaws.com/0/258019/abf6d98f-d4f8-f5a3-55bc-8c6e89e6f7c4.png)

動画作ってみたらGIFアニメで数十MBあったので、スナップショットにしておきました。

これのpythonコードは
https://gist.github.com/sage-git/27633820a95325d067765c1adbab8446
にあげておきます。

6/1 追記
https://www.youtube.com/watch?v=LcquTQOcPGc
に動画を上げました。
あとソースコード、こちらで引用する関数を間違えていたので修正しました。

8/9 追記
正方格子ですが、6/7にChainerを使ってＧＰＵ化した記事を書きました。
https://qiita.com/sage-git/items/b4c01dc1c7ebec59c0d2

# ちなみに （ネタバレ注意）

このあと本格的に漫画の通りに実装しようとしたら、系の発展がある程度進んだあと、
謎の荒いポリゴンのキャラクターを出してFPSだかTPSゲームに切り替わるのですが、
そこまで実装する元気はありませんでいた。

そして、漫画でのオチはオートマトン、人工生命から人工知能、そして人類への反逆というようなSFではなく、ゲーム脳あるいは脳内麻薬により理性を消してゲーム脳兵士にするといういつもの軍産複合体の陰謀論でした。

この記事がAK-クラスシナリオ回避の一助になれば幸いです。