一次元セルラーオートマトン/二次元セルラーオートマトン/ライフゲーム

ライフゲーム

ライフゲームとは、イギリスのジョン・コンウェイが提案した二次元セルラーオートマトンのルールセットである。セルラーオートマトンは非線形であり、実行してみないとわからない。

オートマトンになじみない人のために、通常のオートマトンについても記述する

オートマトン

オートマトンとは、計算および処理を行うための抽象的な機械やシステムを指す。オートマントは入力を受けとり、それに基づいて状態を遷移して最終的に出力を生成するモデルである。日本語では「状態機械」という素晴らしい訳がある。

50円の硬貨のみを受け付ける自動販売機
150になると飲み物を出力する

これを考える。
一つ目の状態遷移を考えると、0円に対して50円になるため状態が遷移する。

こういった状態遷移が考えられる。これらを示すのがオートマトン/状態機械である。

セルラーオートマトン

セルラーオートマトンにはルールセットがあると先ほど述べた。そのように、セルラーオートマトンにはいくつかのルールの種類があり、それぞれ細かくルールが違う。下記のルールはすべてのルールで適応できるものである。

空間がある:2次元の場合オセロの盤面のようなセルがある
時間がある:セルの状態が変化するための時間ステップがある
セルに状態がある:簡単な例は死;生などである
セルの状態が変わる条件がある:餓死などが例である。ここでは、左右上下のセルの状態によって判断する

一次元でのセルラーオートマトン

このセルを考える。

これは一次元セルラーオートマトンと呼ばれるもので、ルールは以下のようなものがある。

空間が一次元
時間は一斉更新
状態は2パターン、生か死か
状態遷移条件は256通り

状態更新条件の計算方法
3つのセルがあり、それぞれ2つの通り数を持つことが可能なので、
$$2^3$$
である。また、これらの並び替えを考えると

$$2^8$$
と考えられるよって256通りである。

これらを用いてルールを決定する。上記の並び方ではルールは、22ということになる。

上の3つのセルの配置の時、一つ下のセルは画像の下のように変化するということである。

これらのルールを適応したセルラーオートマトンを動かすと以下のようなクラスに分類できる

クラス1

時間的にパターンが消えたり、固定化するもの

例:ルール40 232

クラス2

周期的な構造を作るようになり、無限にそのパターンを繰り返す

例:ルール94 108

クラス3

非周期でランダムなカオスを作り出す

例:ルール54 90

クラス4

時間的空間的に局在する構造を持つ複雑なパターンを作り出す

例:ルール110 121

コード

import pygame
import numpy as np

# Initialize pygame
pygame.init()

# Constants
SPACE_SIZE = 150
CELL_SIZE = 5
SCREEN_SIZE = SPACE_SIZE * CELL_SIZE
RULE = 110
FPS = 60

# Colors
WHITE = (255, 255, 255)
GRAY = (200, 200, 200)  # Background color for better visibility
BLACK = (0, 0, 0)

# Initialize screen
screen = pygame.display.set_mode((SCREEN_SIZE, SCREEN_SIZE))
pygame.display.set_caption("Cellular Automaton")

# CA state space
state = np.zeros(SPACE_SIZE, dtype=np.int8)
next_state = np.empty(SPACE_SIZE, dtype=np.int8)

# Initialize first state
state[len(state)//2] = 1

def update_state(state, next_state, rule):
    for i in range(SPACE_SIZE):
        l = state[i-1]
        c = state[i]
        r = state[(i+1)%SPACE_SIZE]
        neighbor_cell_code = 2**2 * l + 2**1 * c + 2**0 * r
        next_state[i] = (rule >> neighbor_cell_code) & 1
    return next_state

def draw_state(screen, state, row):
    for i in range(SPACE_SIZE):
        color = BLACK if state[i] == 1 else GRAY  # Use GRAY as the background color
        pygame.draw.rect(screen, color, (i * CELL_SIZE, row * CELL_SIZE, CELL_SIZE, CELL_SIZE))

def main():
    clock = pygame.time.Clock()
    row = 0

    running = True
    while running:
        # Event handling
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False

        # Update state
        draw_state(screen, state, row)
        global next_state
        next_state = update_state(state, next_state, RULE)
        state[:] = next_state

        # Update display
        pygame.display.flip()

        # Control the frame rate
        clock.tick(FPS)

        # Move to next row
        row += 1
        if row >= SCREEN_SIZE // CELL_SIZE:
            row = 0
            screen.fill(GRAY)  # Fill the screen with GRAY color

    pygame.quit()

if __name__ == "__main__":
    main()

二次元セルラーオートマトン

先ほどの一次元では、両隣のみからの影響を受けたが、2次元では上下左右斜めからも影響を受ける。

ルールは以下である。

人口過剰:生きているセルが、囲まれているセル3つより多くのセルが生きていればそのセルは死ぬ

均衡状態:生きているセルの囲んでいるセルのうち2つor3つが生きていればそのセルは生き残る

人口過疎:生きているセルの囲んでいるセルのうち、2つ未満のセルしか生きていない場合、そのセルは死ぬ

再生:死んでいるセルが、囲まれているセルのちょうど3つが生きていればそのセルは生き返る。

これらには以下のパターンが存在する

1.ランダムパターン:ランダムなパターン
2.静的パターン:静的なパターン
3.オシレーター:いくつかのステップ後に初期状態に戻るもの
4.グライダー:あるパターンが壊れることなくセルを移動するもの
5.グライダーガン:グライダーがグライダーを作り出し、周囲に送るもの

ランダムパターン

ランダムパターンは以下のようにランダムな状態変化を起こす

ランダムパターンではそれぞれのセルがランダムに生きているか死んでいるかを決定します。

例:細菌のコロニーの形成など、カオスに存在するものが時間をかけて一定の状態に落ち着くようなもの

静的パターン

上記のように状態が全く変化しない状態を静的パターンといいます。

安定した構造です。

オシレーター

オシレーターは複数のステップののち初期状態に戻るものです。先ほどのランダムパターンにも、こういった構造が見られたと思います。これはオシレーターの状態です。周期的に動いています。

例:クロックなどに応用されています。また、経済の景気の拡大と縮小にも類似していると考えることができます。

グライダー

私は個人的にこれが一番好きです。

グライダーは自律的なシステムであり、一度グライダーが形成されるとこのパターンから変わることはないです。

例:台風のように一度形成されるとほとんど形を変えることなく海上を移動するので見ていて面白いです

グライダーガン

グライダーガンとは、先ほどのグライダーを作り出すものをグライダーガンといいます。

自然に作られることはめったにないそうです。

生物の分裂と繁殖に似ています。

2次元セルラーオートマトンのコード

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import numpy as np
import pygame

# Pygameの初期化
pygame.init()

# ウィンドウサイズとセルサイズの設定
WIDTH, HEIGHT = 500, 500
CELL_SIZE = 10
GRID_WIDTH = WIDTH // CELL_SIZE
GRID_HEIGHT = HEIGHT // CELL_SIZE

# 色の定義
BLACK = (0, 0, 0)
WHITE = (255, 255, 255)

# スクリーンの初期化
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption('Game of Life')

# パターンの定義
STATIC = np.array([
    [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
    [1,1,0,0,0,1,1,0,0,0,0,1,1,0,0,0,1,1,0],
    [1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1],
    [0,0,0,0,0,1,1,0,0,0,0,1,0,1,0,0,0,1,0],
    [0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0],
])

OSCILLATOR = np.array([
    [1,0,0,0,0,1,0,0],
    [1,0,0,0,1,0,0,1],
    [1,0,0,0,1,0,0,1],
    [0,0,0,0,0,0,1,0]
])

GLIDER = np.array([
    [0,0,0,0],
    [0,0,1,0],
    [0,0,0,1],
    [0,1,1,1]
])

GLIDER_GUN = 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]
])

# 初期状態の設定
state = np.zeros((GRID_HEIGHT, GRID_WIDTH), dtype=np.int8)
next_state = np.empty((GRID_HEIGHT, GRID_WIDTH), dtype=np.int8)

# パターンの選択
def select_pattern():
    print("Select a pattern:")
    print("1: Random")
    print("2: STATIC")
    print("3: OSCILLATOR")
    print("4: GLIDER")
    print("5: GLIDER_GUN")
    choice = input("Enter the number of your choice: ")
    if choice == "1":
        return np.random.randint(2, size=(GRID_HEIGHT, GRID_WIDTH), dtype=np.int8)
    elif choice == "2":
        state[2:2+STATIC.shape[0], 2:2+STATIC.shape[1]] = STATIC
        return state
    elif choice == "3":
        state[2:2+OSCILLATOR.shape[0], 2:2+OSCILLATOR.shape[1]] = OSCILLATOR
        return state
    elif choice == "4":
        state[2:2+GLIDER.shape[0], 2:2+GLIDER.shape[1]] = GLIDER
        return state
    elif choice == "5":
        state[2:2+GLIDER_GUN.shape[0], 2:2+GLIDER_GUN.shape[1]] = GLIDER_GUN
        return state
    else:
        print("Invalid choice, defaulting to random.")
        return np.random.randint(2, size=(GRID_HEIGHT, GRID_WIDTH), dtype=np.int8)

state = select_pattern()

# ゲームループ
running = True
while running:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            running = False

    for i in range(GRID_HEIGHT):
        for j in range(GRID_WIDTH):
            nw = state[i-1,j-1]
            n  = state[i-1,j]
            ne = state[i-1,(j+1)%GRID_WIDTH]
            w  = state[i,j-1]
            c  = state[i,j]
            e  = state[i,(j+1)%GRID_WIDTH]
            sw = state[(i+1)%GRID_HEIGHT,j-1]
            s  = state[(i+1)%GRID_HEIGHT,j]
            se = state[(i+1)%GRID_HEIGHT,(j+1)%GRID_WIDTH]
            neighbor_cell_sum = nw + n + ne + w + e + sw + s + se
            if c == 0 and neighbor_cell_sum == 3:
                next_state[i,j] = 1
            elif c == 1 and neighbor_cell_sum in (2,3):
                next_state[i,j] = 1
            else:
                next_state[i,j] = 0

    state, next_state = next_state, state

    # スクリーンの更新
    screen.fill(WHITE)
    for i in range(GRID_HEIGHT):
        for j in range(GRID_WIDTH):
            if state[i, j] == 1:
                pygame.draw.rect(screen, BLACK, (j*CELL_SIZE, i*CELL_SIZE, CELL_SIZE, CELL_SIZE))

    pygame.display.flip()
    pygame.time.delay(100)

pygame.quit()