ラングトンの自己複製オートマトン

ついにやった！ループが自己複製をしている。
ラングトンの日記（1979/10/26）

ラングトンの自己複製オートマトンは、ラングトン・ループ（Langton's Loops）と呼ばれます。ライフゲームと同じ二次元のセル・オートマトン空間上でループが増殖していきます。下が増殖の様子を撮影した動画です。もっとよくみたいときは後で掲載するPythonスクリプトを実行してみてください。

この自己複製するループは、クリストファー・ラングトン（Christopher Langton）という人が提案しました。ラングトンは、人工生命（Artificial Life）という研究分野の創始者です。

こういう複製はトップダウンでルールを与えれば簡単にできます。たとえば、腕を10ピクセル伸ばしたら左に90度曲げるを繰り返し、ループが完成したら切り離す。でもこれではまったく面白くない！ラングトンのループのすごいところは、局所的なルールから、自己複製という大域的な特性がボトムアップに創発してくるところなのだ！

ラングトン・ループのルール

ラングトン・ループは、ライフゲームと同じ二次元セルオートマトン空間です。ただ、ライフゲームと比べると状態数やルールはだいぶ複雑です。

ラングトン・ループの各セルの取りうる値は8状態あります。アニメーションさせるときは各状態に色をつけるとわかりやすいので下のWikipediaにあった画像と同じ色を使いました。初期状態は、下のようにQみたいな形をしています。

※Wikipediaから引用

次、ラングトン・ループのルールについて。ラングトンが書いた論文にもルール一覧は載っているのですが書き下すのが大変なので、Rule Table Repositoryで公開されているものを使いました。このサイトには、ラングトン・ループ以外にもいろいろなセル・オートマトンのルールがまとまっていて便利です。

今回使うのは、Langtons-Loops.tableです。このルールテーブルは、下のようなテキストフォーマットになっています。

# states: 8
# rules: 219
# format: CNESWC'
n_states:8
neighborhood:vonNeumann
symmetries:rotate4
000000
000012
000020
・・・
012321
012421
・・・

n_states:8は、さっき書いたように状態数が8という意味ですね。

neighborhood:vonNeumannは、フォン・ノイマン近傍の状態から次の状態が決まることを意味しています。フォン・ノイマン近傍は、自分と上下左右の5セルのことを指します。予断ですが、ムーア近傍というのもあって、自分と上下左右斜めの9セルのことを指します。ライフゲームはムーア近傍を使います。名前がすごいので怯みますけど、たいして難しくないですね（笑）

あとにずらずら続く数値は、1行が1つのルールを意味します。現状態の Center, North, East, South, West の状態番号、次の状態の Center の状態番号（format: CNESWC）、この順番で6つの数字が並んでいます。たとえば、ルール012321は、下のようなイメージです。

こういうルールが219個ある（rules: 219）のですが、symmetries:rotate4 というのがクセモノです。これは、各ルールを4回転させたものもルールに追加するという意味です。たとえば、ルール012321から下のように周囲を回転させたルール（021231、032121、023211）も加えます。あらかじめ展開したものを載せといてくれよ・・・

さあ、これで準備は完了！さっそく実装です。

Pythonスクリプト

ラングトン・ループをPythonで書いてみます。PygameというPythonのゲーム作成用ライブラリを使ってます。Pygameについては、Pythonでゲーム作りますが何か？（2008/5/7）に使い方を詳しくまとめたので参考にしてください。ライフゲーム（2008/9/14）と骨格はほとんど同じです。

また、Rule Table Repositoryで公開されているLangtons-Loops.tableというファイルを同じ場所においてください。このルールテーブルを読み込んでいます。実行はけっこう重いです。60FPSでないかも。

#coding: utf-8
import pygame
from pygame.locals import Rect, Color, QUIT
import sys

SCR_RECT = Rect(0, 0, 800, 800)
CS = 5  # セルサイズ
NUM_ROW = SCR_RECT.height / CS
NUM_COL = SCR_RECT.width / CS

# 各状態の色
state2color = ["black", "blue", "red", "green", "yellow", "magenta", "white", "cyan"]

# ラングトン・ループの初期状態
langtonsLoops = [
    [0,2,2,2,2,2,2,2,2,0,0,0,0,0,0],
    [2,1,7,0,1,4,0,1,4,2,0,0,0,0,0],
    [2,0,2,2,2,2,2,2,0,2,0,0,0,0,0],
    [2,7,2,0,0,0,0,2,1,2,0,0,0,0,0],
    [2,1,2,0,0,0,0,2,1,2,0,0,0,0,0],
    [2,0,2,0,0,0,0,2,1,2,0,0,0,0,0],
    [2,7,2,0,0,0,0,2,1,2,0,0,0,0,0],
    [2,1,2,2,2,2,2,2,1,2,2,2,2,2,0],
    [2,0,7,1,0,7,1,0,7,1,1,1,1,1,2],
    [0,2,2,2,2,2,2,2,2,2,2,2,2,2,0]]

class LangtonsLoops:
    def __init__(self):
        pygame.init()
        self.screen = pygame.display.set_mode(SCR_RECT.size)
        pygame.display.set_caption("Langton's Loops")

        # フィールドを作成
        self.field = [[0 for x in range(NUM_COL)] for y in range(NUM_ROW)]

        # 状態を初期化
        self.init()

        # 規則をロード
        self.loadRule("Langtons-Loops.table")

        # メインループ開始
        self.mainLoop()

    def init(self):
        """Langton's Loopsの初期状態を格納"""
        # 画面の真ん中あたりに初期状態が出てくるように位置を調整
        offset = (NUM_ROW - len(langtonsLoops)) / 2
        for y in range(len(langtonsLoops)):
            for x in range(len(langtonsLoops[y])):
                self.field[y + offset][x + offset - 10] = langtonsLoops[y][x]

    def update(self):
        """状態を更新"""
        nextField = [[0 for x in range(NUM_COL)] for y in range(NUM_ROW)]
        for y in range(NUM_ROW):
            for x in range(NUM_COL):
                try:
                    c = self.field[y][x]
                    n = self.field[y - 1][x]
                    e = self.field[y][x + 1]
                    s = self.field[y + 1][x]
                    w = self.field[y][x - 1]
                    nextField[y][x] = self.rules[(c, n, e, s, w)]
                except IndexError:
                    # 端の処理
                    continue
                except KeyError:
                    # ループが画面外にはみ出した
                    continue
        self.field = nextField

    def draw(self):
        """セルを描画"""
        for y in range(NUM_ROW):
            for x in range(NUM_COL):
                color = Color(state2color[self.field[y][x]])
                pygame.draw.rect(self.screen, color, Rect(x * CS, y * CS, CS, CS))

    def mainLoop(self):
        clock = pygame.time.Clock()
        while True:
            clock.tick(60)
            self.update()
            self.draw()
            pygame.display.update()
            for event in pygame.event.get():
                if event.type == QUIT:
                    pygame.quit()
                    sys.exit()

    def loadRule(self, filename):
        """ルールをロード"""
        self.rules = {}
        fp = open(filename, "r")
        for line in fp:
            line = line.rstrip()
            if line.startswith("#"): continue
            if line.startswith("n_states"): continue
            if line.startswith("neighborhood"): continue
            if line.startswith("symmetries"): continue
            self.rules.update(self.rotate4(line))
        fp.close()

    def rotate4(self, ruleStr):
        """回転させたルールも作成して追加"""
        rules = {}  # フォン・ノイマン近傍の状態 => 次の状態のハッシュ
        c, n, e, s, w, c2 = [int(x) for x in ruleStr]
        rules[(c, n, e, s, w)] = c2
        rules[(c ,w, n, e, s)] = c2
        rules[(c, s, w, n, e)] = c2
        rules[(c, e, s, w, n)] = c2
        return rules

if __name__ == "__main__":
    LangtonsLoops()

実行したのが冒頭の動画です。じっくり観察すると面白いことがわかってきます。赤いセルが壁の役割をしていて、その中を水色のセルが移動していくことで成長していきます。黄色のセルが先端につくと直角に折れ曲がってます。また、成長できなくなると固定化します。

ちょっといじめてやろうと思って、初期状態の一部を書き換えてみました。みるみるうちに壊れていく・・・生命とはこんなにも儚いものなのか？そんな馬鹿な！

参考

• Self-reproduction in cellular automata (PDF) - 1984年に提出されたLangton's loopsの原論文
• Rule Table Repository - さまざまなセルオートマトンのルールがまとめられています。ラングトン・ループのルールはここを参考にしました。
• Langton's Loops - Chris Langtonみずからのデモビデオ（YouTube）
• ラングトンのループ（Wikipedia）
• Langton's loops (Wikipedia)