たのしい1次元セル・オートマトンの世界

はじめに

Happy hacking!
初投稿記事です。

突然ですが、こんな図形を描画するプログラム、カワイイと思いませんか？

カワイイですよね、ありがとうございます。
今回は皆様に摩訶不思議なセル・オートマトンの世界をご紹介したいと思います。

それでは、いってみましょ～！🐕

セル・オートマトンとは

セル・オートマトン（英: cellular automaton、略称：CA）とは、格子状のセルと単純な規則による、離散的計算モデルである。

Wikipediaより引用

なるほど、わからん

まず、無限に広がる方眼紙を想定します。Excelでもいいです。 無限……？
その方眼紙におけるマス目がセルにあたります。
各セルは2つの状態(0, 1)のうちいずれかに決定されます。
各セルは単純なルールに従って、離散的な――つまり分断された非連続的な時間経過とともに変化していきます。
その変化の様を観察していくと、冒頭のような幾何学模様を描き出す 単純なルール が存在することに気が付きます。
気が付いたんです、昔のすごいヒトが。
すごいですよね。

今回は 1次元 のセル・オートマトンにフォーカスしていきます。
高次のセル・オートマトンについてはまたの機会に！

1次元セル・オートマトンにおけるルール

さて、先程から話しているこの魔法のような単純なルールって一体何なんでしょうね。
まず、用語として 近傍 (neighbourhood, neighborhood)という言葉が出てきます。
ここでは、隣接するセル群のことだと理解してください。

1次元というくらいですから、セルは線状に並んでいます。こんな感じに。

(0)	1	0	1	0	1	(0)

🐕 < 有限の計算をする際、両端には常に0の状態を持つセルを想定するワン🐾

両端の亜空間を除いた5マスの方眼紙に、0の状態を持つセルが2つと、1の状態を持つセルが3つ並んでいます。
例えば、真ん中の1の状態を持つセルを中心に考えると、近傍は両隣の0の状態を持つセルです。
全てのセルについてそれぞれの近傍を見ていくと、次のようになります。

(0)	1	0

1	0	1

0	1	0

1	0	1

0	1	(0)

5マスの方眼紙なので、中心とその近傍のグループは当然5つ存在します。
このグループの状態をもとに、次の世代におけるセルの状態を決定していきます。
具体的なルールを例に、その状態変化の過程を見てみましょう。

ルール90

フラクタル図形のひとつであるシェルピンスキーのギャスケットと呼ばれる図形を生成する、ルール90を例にして1次元セル・オートマトンにおけるルールを理解してみます。

現在の状態	次世代における中央セルの状態
0 | 0 | 0	| 0 |
0 | 0 | 1	| 1 |
0 | 1 | 0	| 0 |
0 | 1 | 1	| 1 |
1 | 0 | 0	| 1 |
1 | 0 | 1	| 0 |
1 | 1 | 0	| 1 |
1 | 1 | 1	| 0 |

これは、中心とその近傍の状態をもとに、その中心セルが次世代においてどのような状態に決定されるかを表したものです。

次のようなセルの初期状態を想定します。
(記載していませんが、両端は0です。)

0	0	0	0	1	0	0	0	0

先程の状態遷移表に従って次世代のセルの状態を表してみると、こんな感じになります。

0	0	0	1	0	1	0	0	0

さらに次の世代を見てみましょう。

0	0	1	0	0	0	1	0	0

このような変化を無限に繰り返すわけです。
この変化を下方向に積み上げるかたちで描画すると、こんな興味深い図形が生成されるんですね～！

はい、記事冒頭の図形はルール90によって生成されたものでした。

ルールの命名

ところで、ルール90における 90 って何なんでしょう。
先程の、ルール90についての状態遷移表における 次世代における中央セルの状態 を下から順に並べてみます。

01011010

これを2進数として捉え、10進数に変換したものをルールの名称として使っているのです！

01011010(2) = 90(10)

つまり、逆算するとルールの番号から状態遷移表が導き出せます。
ルール30の状態遷移表をつくってみましょう。

30(10) = 00011110(2)

現在の状態	次世代における中央セルの状態
0 | 0 | 0	| 0 |
0 | 0 | 1	| 1 |
0 | 1 | 0	| 1 |
0 | 1 | 1	| 1 |
1 | 0 | 0	| 1 |
1 | 0 | 1	| 0 |
1 | 1 | 0	| 0 |
1 | 1 | 1	| 0 |

次のような初期状態を与えて、3世代分の変化を見てみます。

0	0	0	0	1	0	0	0	0

0	0	0	1	1	1	0	0	0

0	0	1	1	0	0	1	0	0

ルール30は次のような図形を生成します。
これまたカワイイ……。

ルールの種類

前述したように、各セルは2つの状態(0, 1)のうちいずれかに決定されます。
先程の状態遷移表を見ても分かるように、1次元セル・オートマトンにおける中心と近傍は3つのセルによって構成されるので、8つのパターン(2³ = 8)をとります。
中心と近傍によって決定される 次世代における中央セルの状態 もまた2つの状態をとるので、ルールは全部で 256種類 (2⁸ = 256)存在することが分かります。

ルールに与えられた0から255までの番号を ウルフラム・コード と呼びます。
これは、イギリスの理論物理学者スティーブン・ウルフラムが考案したことに由来します。

C#で実装してみる

すきな言語でつくってみよう！

🐕 < イヌはC#がすき！

以下は抜粋したソースです。
ソースのフルバージョンはイヌの GitHub にありますので、是非遊んでみてください！

入力したウルフラム・コードからルールを生成する

/// <summary>
/// ルールを取得する
/// </summary>
/// <param name="ruleDec">ウルフラム・コード</param>
/// <returns>ルール</returns>
private static string[,] GetRule(int ruleDec)
{
    // ウルフラム・コードを2進数に変換し8桁0埋め
    var ruleBinArray = int.Parse(Convert.ToString(ruleDec, 2)).ToString("D8").ToCharArray();
    // 近傍の状態を表す10進数
    var n = 7;

    var rule = new string[8, 2];
    var count = 0;

    // ルールを生成
    foreach (var bin in ruleBinArray)
    {
        rule[count, 0] = int.Parse(Convert.ToString(n, 2)).ToString("D3");
        rule[count, 1] = bin.ToString();

        count++;
        n--;
    }

    return rule;
}

第1世代のセル・オートマトンを生成し初期状態を与える

// 第1世代のセル・オートマトンを生成し初期状態を与える
var firstGene = "0".PadLeft(automatonSize + 2, '0').ToCharArray();
firstGene[firstGene.Count() / 2] = '1';

セルの状態に応じて描画する

for (var t = 0; t < stepCount; t++)
{
    foreach (var cell in currentGene.ToCharArray())
    {
        // セルの状態に応じて描画
        var view = cell == '0' ? " " : "*";
        Console.Write(view);
    }
    Console.Write("\r\n");

ルールに従って次世代のセル・オートマトンを生成する

/// <summary>
/// 次世代のセル・オートマトンを取得する
/// </summary>
/// <param name="rule">ルール</param>
/// <param name="currentGene">現世代のセル・オートマトン</param>
/// <returns>次世代のセル・オートマトン</returns>
private static string GetNextGene(string[,] rule, string currentGene)
{
    // 左端は常に0
    var nextGene = "0";

    // ルールに従って次世代のセル・オートマトンを生成
    for (var i = 1; i < automatonSize + 1; i++)
    {
        for (var j = 0; j < rule.GetLength(0); j++)
        {
            if (rule[j, 0] == currentGene.Substring(i - 1, 1) + currentGene.Substring(i, 1) + currentGene.Substring(i + 1, 1))
            {
                nextGene += rule[j, 1];
                break;
            }
        }
    }

    // 右端は常に0
    return nextGene + "0";
}

カワイイけど、これって何に使うの？

セル・オートマトンは様々な研究に用いられています。
今回のテーマである1次元セル・オートマトンにおける最も有名であろう利用方法として、一車線の高速道路における交通流シミュレーションが挙げられます。
ルール184 がこのシミュレーションをするためのモデルとして利用できます。

実際に適当な初期状態を与えてルール184を動かしてみると、交通渋滞の様子を再現できます。
この素晴らしいインターネッツで検索してみるとたくさんの論文を読むことができるので、興味のある方は是非！

自然界におけるセル・オートマトン

イモガイの一種であるタガヤサンミナシという貝は、ルール30が生成する模様によく似た貝殻を持つことで知られています。

何故キミはその模様を選んだのだ……？
何に対して都合が良かったのだ……？

おわりに

生命 という現象の謎を解き明かすために考案され、発展してきたセル・オートマトン。
この深淵の先に見えるものとは？
たとえそれが、呪いだったとしても……。