Conway を探せ: Part 1，あるいは rust で プロット

じぶん advent calendar 22日目の記事です．

色々遅刻するわけがあり，基本的には書こうとしたネタが消滅したり爆発したという感じなのですが，まあともかく． 実はまずはこの Rust 実装を webassembly でコンパイルしてブラウザで試せるように…と思って，ほぼうまく行き， 最終的に npm run start でサーバを起動してゆんゆん動くところまでは行ったのですが， そこから static なページとしてホストする方法にかなり長い間かけてたどり着けず…． もう npm 一生触りたくない

Conway を探せ

日本語で「ライフゲーム」と呼ばれるセルラ・オートマトンは英語圏では Conway's game of life というかたちで多くは提唱者の名を冠して呼ばれ， 要するに次のようなものです．

• まず升目をイメージ
• 各升目には Cell がいるつもりで，それが生きている Alive か死んでいる Dead かのどちらか
• 各升目は，そのときの周囲3x3マスの様子によって次のターンでの生死を決める（ルール，という）
  • 具体的には，Conway's では
  • 今生きてる細胞→ 周囲の細胞が2か3個ある時に生存，それ以外は死亡
  • 今死んでるマス→周囲にちょうど3個の生きてるマスがあれば生まれる
  • 多すぎると人口過多で，少なすぎると環境が整わずに死ぬイメージ

拡張が色々ある…話は今度するとして，この「2-3」に妙味を感じませんか． ここの「ちょうどいい」感じに彼はどうやってたどり着いたのでしょう． 同様にルールを設定しても多分殆どの場合は全然おもしろくない時間発展しかしないのに…

我々もこれを見つけてみたい．他に面白いルールはないでしょうか．

すべてのルール，では 2¹⁸ 通りあります． すなわち，今このマスが生きてるとき死んでるときそれぞれについて，周りのマスのうち生きてる数(0-8) 各々で直後の生死を決めるというわけです． もうちょっとシンプルな， a₀ ≤ neighbour ≤ a₁ の形ならもっと減りそうです． ともかく，ある程度機械的に「面白そうなルール」を抽出したい．色々やり方を感じますが， まずいちばんシンプルな方法として全体の生存数がどう時間発展するかを見てみましょう． おそらく全部死に絶えたりほとんど全体を生存者が埋めるようなルールは面白くない． またある程度時間が経って，生存数が定数になったり，2値の間を振動したりするのも面白くなさそうです．

というわけで本日の課題:

• Life を実装
• まず知ってるルールである Conway's game of life で，世代を追って個体数がどうなるかを調べる
  • そのために，rust から plot をしてみよう

この時点でのコードは github にあります．

Life の実装

概ね続きを書こうとしたら爆発した以前の記事の通り． pupulation というフィールドを作って現在の人口を覚えておき， 次のステップでの状態を計算する際にこれ一緒にアップデートすることにします． （Vec<(u32, Cell)> を返しているのは，直前から変化のあったマスだけを返すことで描画する際の省力化を図るためです）

#[derive(Clone, Debug)]
pub struct Model {
    world: Vec<Cell>,
    pub width: u32,
    pub height: u32,
    pub population: u32,
    rule: Rule,
}

impl Model{
    pub fn tick_and_report(&mut self) -> Vec<(u32, Cell)> {
        // update itself, and reports the change in population
        let current = self.clone();
        let mut updates = Vec::new();
        for (i, &cell) in current.world.iter().enumerate() {
            let neighbours = current.neighbours_of(i as u32);
            if cell.is_alive() {
                if neighbours < self.rule.alive_min || self.rule.alive_max < neighbours {
                    self.world[i] = Cell::Dead;
                    self.population -= 1;
                    updates.push((i as u32, Cell::Dead));
                }
            } else {
                // for dead cells
                if self.rule.birth_min <= neighbours && neighbours <= self.rule.birth_max {
                    self.world[i] = Cell::Alive;
                    self.population += 1;
                    updates.push((i as u32, Cell::Alive));
                }
            }
        }
        updates
    }

    fn neighbours_of(&self, loc: u32) -> u8 {
        let mut ns = 0;
        let (x, y) = (loc % self.width, loc / self.width);
        for &dx in &[self.width - 1, 0, 1] {
            for &dy in &[self.height - 1, 0, 1] {
                ns += self
                    .at((x + dx) % self.width, (y + dy) % self.height)
                    .as_num();
            }
        }
        ns -= self.world[loc as usize].as_num();
        ns
    }
}

まずは200回，1000世代ほど走らせてみましょうか．世界は 200x200=40000px とします． 単純に1試行1行，横に1000列の tsv の形式にすることにします．

fn main() {
    let file_name = format!(
        "./results/conways_{}.tsv",
        time::SystemTime::now()
            .duration_since(time::UNIX_EPOCH)
            .unwrap()
            .as_secs()
    );
    let f = File::create(file_name).expect("unable to create");
    let mut writer = BufWriter::new(f);
    for trial in 0..1000 {
        println!("START {}", trial);
        let w = random_world(SIZE);
        let mut m = Model::from_world(w, 200, 200, CONWAY);
        for _ in 0..200 {
            writer
                .write_all(format!("{}\t", m.population).as_bytes())
                .expect("write_err");
            let _ = m.tick_and_report();
        }
        writer.write_all(b"\n").expect("write_err");
    }
}

Plotting

Rust の plotting library といって決定打がまだない状態みたいですが，とりあえず使いやすいものとして gnuplot というクレートがあります． Gnuplot のラッパみたいな形で，素直で使いやすく，また gnuplot 知ってたら雰囲気をつかみやすいというのがあり， 今回これを使って書いてみることにしました．おおよそこんな感じでプロットできます．

fn plot_tsv(fname: &str) -> gnuplot::Figure {
    // gnuplot:Figure を返すので，
    // そこから画像に保存したり描き足したりできる
    let f = File::open(fname).expect("unable to open file");
    let reader = BufReader::new(f);
    let mut fg = gnuplot::Figure::new();
    let axes = fg.axes2d();
    // マジでそのまま
    for line in reader.lines().take(MAX_PLOT_SEQS as usize) {
        let ys: Vec<u32> = line
            .expect("unable to read line")
            .split_whitespace()
            .map(|n| n.parse::<u32>().unwrap())
            .collect();
        axes.lines(0..ys.len() as u32, &ys, &[]);
    }
    fg.show().unwrap();
    fg
}

axes.lines() みたいな描画を足して自分を返す系の関数が揃っているので，これでどんどん描き足していきます． 滅茶苦茶素直な使い心地で確かによいです．

ちなみにこれ，単に gnuplot を内部的に呼び出してるだけなので色々ちょっとしたハマりどころがあります． はじめ save_to_png(filename, w,h) に与える filename に ./ とか " が混じった状態になってて， これはそのまま set output "filename" の filename を置換する形になるので余裕でエラーが起き， 更にそのエラーは検知されずに次の命令に進むためにターミナルに png のバイナリ列がそのまま溢れたりもしました．

眺める

というわけで結果はこちら．

ランダムな状態から 1000 世代での個体数の変化

最初は単純にランダムに振ってるのでめっちゃ鋭い正規分布で population=20000 くらい． その後ストンと落ちるのは経験と合致しますが，なんか曲線があまりに綺麗で何か fit する函数がありそう． （案外 cellular automaton は応用については報告が多いけど自身の性質についての言及はまだうまく調べられていない．）

最終的には2000前後, ざっくり生存率 5% 程度で安定してるっぽいですね． もうすこし最後の方に寄ってみましょう

800世代以降を拡大

こうしてみると結構細かい上下を繰り返してるのがわかります．これも我々が直観的に思う「面白さ」の必須要素ですね． 前後20世代くらいをみるとドラマチックな変化があるところが検出できるので， ハイライト映像みたいなのを作るようなのを考えても面白そう．10000世代のなかでブワッと上下するところ， 見てみたくないですか．

あとやっぱりこの曲線の性質気になりますね．なにかしら知られてるんだろうけど，cellular automata は単に実装してみました系の露出が多すぎてそういうしっかりした考察に当たりづらい．

まとめ

• Conway's game of life ではランダムな分布から始めるとストンと落ちて，ゆっくり生存率5%弱で安定するようにみえる
• 細かく見ると，あとの方の世代でも（もちろん）ちゃんと変動が見られる
  • 変動のないパターンというのがいくつか知られてるので，それのカウントとか調べても面白そう
• Rust の細々した（タイムスタンプとか）触りどころにちょっとなれた
• RustGnuplot は，単なるラッパなのでエラーとかに問題を抱えつつも，素直で使いやすい
• ルールの捜索，したいですね
• npm はクソ

ちなみに，これで面白いルールを見つけるところまでで一つの記事にしようとするから長くなりがちだし遅刻も直ぐするのだとおもいました．まる．