ライフゲーム陣取り

# 目的

ライフゲームは生物集団の数理モデルである、と言われています。

生物集団であるならば、例えば、グライダーが固定物体や振動子に衝突して新しいパターンが生じたとき、この新しいパターンは衝突したグライダーの子孫なのかそれとも衝突された側の子孫なのだろうか、と疑問が湧きます。

ライフゲームには「民族」とか「人種」のような概念はないのでこういう疑問には意味がないのですが、無理やり意味をもたせることを考えました。

# 手段

[三すくみルールを取り入れたライフゲーム](https://qiita.com/tadashi9e/items/ba90b369c37eae8cc8d7) では、ライフゲームのルールそのものに手を入れたのですが、今回は「生」「死」の挙動はコンウェイのライフそのままとします。

つまり、「生」「死」２つの状態がセルにさらに色をもたせるイメージです。
冒頭の、グライダーが物体に衝突していく状況を例にとるなら、赤いグライダーが青い物体に衝突していく、という感じです。

ライフゲーム（に限らず大抵のセル・オートマトン）の動きを眺めていてすぐ気がつくのは、セルの値の変化は隣接する別のセルの値の変化によってしか起きない、ということです。
変化を引き起こしたセルの色が、後の世代の変更に引き継がれていく、という形にしようと思いました。

但し、変化した隣接セルが複数それぞれ異なる色だった場合にはどの色を採用するべきか、という問題が生じます。
三すくみライフゲームでは三すくみルールを採用したのですが、ここでは多数決で決定することにします。多数決でも決定できない場合には元のセルの色を変更せず、そのままにします。

（多数決で決定できない場合は色なしにする、というルールも考えられます。
この場合、次回多数決の際に「色なしは色の１つとして含めない」という処理をしないと色なしが強すぎて空間全体が色なしのセルで埋め尽くされていくことになります）

結局、以下のようなルールになりました。

- 各セルは初期状態において、「生」「死」状態と別に色を持っている。
- コンウェイのルールに従って「生」「死」状態を毎ステップ更新していく。
- このとき、「生」あるいは「死」状態のままのセルの色は変化しない。
- あるセルが「死」から「生」へ、あるいは「生」から「死」へと変化した場合、変化の原因となった隣接セルの色にあわせて色を変更する。
- 但し、変化の原因となった隣接セルの色が複数種類あった場合、多数決で決定する。
- また、多数決で色を決定できない場合には元のセルの色そのままにする。

# 実装

上記ルールを Python で実装してみました。
お試し実装なので、curses を使ってセルを色分けしながら表示する形にしてみました。

ソースコードは末尾に添付します。

各セルの「生」「死」および色は、`int` １つで表現しています。

- `int` の最下位ビット 1 が「生」状態、0 が「死」状態を表します。
- それ以外のビットで色を表現します。

# 動作例

## 初期状態

初期状態では画面を左上、左下、右上、右下の４つに分割して、それぞれ

- 左上 - 赤いセルの領域。「生」状態セルは赤色 '&' で、「死」状態セルは赤色 '.' で表示。
- 左下 - 緑色セルの領域。「生」状態セルは緑色 '%' で、「死」状態セルは緑色 '.' で表示。
- 右上 - 青色セルの領域。「生」状態セルは青色 '#' で、「死」状態セルは青色 '.' で表示。
- 右下 - シアン色セルの領域。「生」状態セルはシアン色 '*' で、「死」状態セルはシアン色 '.' で表示。

で、ランダムに「生」「死」セルが分布した状態としました。

![Screenshot from 2024-06-08 08-38-46.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/fcf67b92-c3c9-580e-1c1a-689bcef993ee.png)


## 500 ステップ後

それぞれの色のセルが領域争いを続けた結果、元の色分けとは似つかない形に変化しています。

![Screenshot from 2024-06-08 08-39-14.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/2d06cb8e-215f-6738-30e4-50b257b22c4e.png)

## 1000 ステップ後

かなり固定物体、振動子パターンに落ち着いてきましたが、まだ赤色セルが活動的で、シアン色の領域に攻め込んでいます。

![Screenshot from 2024-06-08 08-39-52.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/cbb0c99d-b9dd-797f-e634-e8a517dcee60.png)

## 1500 ステップ後

赤色セルも固定物体、振動子に落ち着きました。

![Screenshot from 2024-06-08 08-40-19.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/412308/7dbb0bf3-5102-43cc-b1d1-25f5f2c2282f.png)

# まとめ

「生」「死」しかないライフゲームに色分けの概念を持ち込んで陣取り争いさせてみました。

色更新ルールが多数決であるためか、空間上を単一の色が占めてしまうことが多いようです。
繰り返し実行してみると、何度かに一度くらいの割合で複数色が共存して定常状態に落ち着くことがある、という感じでした。

# ソースコード

```python
# -*- mode:python;coding:utf-8 -*-
import curses
import random
import time
from typing import Any

# セル空間サイズ。この値は画面サイズによって初期化し直される
WIDTH = 80
HEIGHT = 40

def empty_space() -> list[int]:
u'''空のセル空間を作る。
'''
return [0 for _ in range(WIDTH * HEIGHT)]

def index(x: int, y: int) -> int:
u'''周期的境界条件。
    empty_space が返すセル空間は一次元配列なので、これをアクセスするにあたって
    座標 (x,y) を一次元配列のインデックスに変換する。
    '''
    if x < 0: x += WIDTH
    if x >= WIDTH: x -= WIDTH
    if y < 0: y += HEIGHT
    if y >= HEIGHT: y -= HEIGHT
    return y * WIDTH + x

def is_alive(cell: int) -> bool:
    u'''セル状態が「生」ならば True を、「死」状態なら False を返す
    '''
    return True if (cell & 1) != 0 else False
def count_alive_neighbours(cells: list[int], x: int, y: int) -> int:
    u'''セル状態が「生」の隣接セルの数の和を返す
    '''
    return sum([(1 if is_alive(cells[index(x + dx, y + dy)]) else 0)
                for dx in range(-1, 2)
                for dy in range(-1, 2)
                if dx != 0 or dy != 0])
def get_promoters(cells: list[int], prev: list[int], x: int, y: int) -> dict[int, int]:
    u'''着目している点 (x,y) の更新について、更新隣接セルの種類ごとのカウント数を
    返す。
    '''
    promoters: dict[int, int] = dict()
    for dy in range(-1, 2):
        for dx in range(-1, 2):
            if dx == 0 and dy == 0:
                continue
            i = index(x + dx, y + dy)
            c = cells[i]
            if is_alive(c) == is_alive(prev[i]):
                continue
            cell_type = c & 0xfe
            if cell_type == 0:  # 色なしの隣接セルは無視する
                continue
            if cell_type in promoters:
                promoters[cell_type] += 1
            else:
                promoters[cell_type] = 1
    return promoters
def get_promoter(cells: list[int], prev: list[int], x: int, y: int) -> int:
    u'''着目している点 (x,y) の更新の原因となったセルの種類を決定する。
    決定は直近に更新があった隣接セルの種類の多数決によって行う。
    多数決での決定が不可能な場合、0 を返す。
    '''
    promoters = get_promoters(cells, prev, x, y)
    i_max = [i for i, count in promoters.items() if count == max(promoters.values())]
    if len(i_max) == 1:
        return i_max[0]
    return 0
    
def next_cells(cells: list[int], prev: list[int]) -> list[int]:
    u'''現在のセル空間(cells)、直前のセル空間(prev) を元に次ステップのセル空間を
    返す。
    '''
    next_cells = empty_space()
    for y in range(0, HEIGHT):
        for x in range(0, WIDTH):
            count = count_alive_neighbours(cells, x, y)
            i = index(x, y)
            is_next_alive = (
                (count == 2 or count == 3) if is_alive(cells[i]) else
                (count == 3))
            if is_next_alive == is_alive(cells[i]):
                next_cells[i] = cells[i]
            else:
                cell_type = get_promoter(cells, prev, x, y)
                if not cell_type:
                    # 更新の原因となった種別が決定不可能な場合には元のまま
                    cell_type = cells[i] & 0xfe
                next_cells[i] = ((1 if is_next_alive else 0) | cell_type)
    return next_cells

def char_of(cell: int) -> str:
    return ('.' if cell == 0 else
            '+' if cell == 1 else
            '.' if cell == 2 else
            '&' if cell == 3 else
            '.' if cell == 4 else
            '%' if cell == 5 else
            '.' if cell == 6 else
            '#' if cell == 7 else
            '.' if cell == 8 else
            '*' if cell == 9 else
            ' ' + str(cell) + ' ')
def color_of(cell: int) -> int:
    cell_type = cell & 0x0e
    return cell_type >> 1

def dump_simple(cells: list[int]) -> None:
    for y in range(0, HEIGHT):
        print(''.join([char_of(cells[index(x, y)]) for x in range(WIDTH)]))

def dump_curses(cells: list[int], screen: Any) -> None:
    for y in range(0, HEIGHT):
        for x in range(0, WIDTH):
            cell = cells[index(x, y)]
            screen.addstr(y + 1, x, char_of(cell),
                          curses.color_pair(color_of(cell)))

def main(screen: Any) -> None:
    global WIDTH, HEIGHT
    # ---- 初期化
    # セル空間サイズを画面サイズに合わせる
    rows, cols = screen.getmaxyx()
    HEIGHT = rows - 1
    WIDTH = cols - 1
    # ランダムな初期状態
    prev = empty_space()
    cells = empty_space()
    for y in range(HEIGHT):
        for x in range(WIDTH):
            i = index(x, y)
            if x < WIDTH / 2:
                if y < HEIGHT / 2:
                    cell_type = 1 << 1
                else:
                    cell_type = 2 << 1
            else:
                if y < HEIGHT / 2:
                    cell_type = 3 << 1
                else:
                    cell_type = 4 << 1
            if random.randrange(0,3) == 0:
                cells[i] = 1 | cell_type
            else:
                cells[i] = 0 | cell_type
    # ---- 色の設定
    curses.start_color()
    curses.use_default_colors()
    #for i in range(0, curses.COLORS):
    #    curses.init_pair(i + 1, i, -1)
    curses.init_pair(1, curses.COLOR_RED, curses.COLOR_BLACK)
    curses.init_pair(2, curses.COLOR_GREEN, curses.COLOR_BLACK)
    curses.init_pair(3, curses.COLOR_BLUE, curses.COLOR_BLACK)
    curses.init_pair(4, curses.COLOR_CYAN, curses.COLOR_BLACK)
    curses.curs_set(0)
    # ---- 初期状態の表示
    screen.clear()
    screen.addstr(0, 0, "genesis")
    dump_curses(cells, screen)
    screen.refresh()
    # screen.getch()  # キー入力を待つ
    time.sleep(1)
    # ---- メインループ
    loop_count = 0
    while True:
        screen.clear()
        screen.addstr(0, 0, str(loop_count))
        loop_count += 1
        dump_curses(cells, screen)
        screen.refresh()
        prev, cells = cells, next_cells(cells, prev)
        time.sleep(0.5)

random.seed(9)
curses.wrapper(main)
```