この記事は 本郷学園マイコン部 Advent Calendar 2024 10日目の記事です。
tl;dr
Wolframの3状態総和型セルオートマトンをHSPで実装しました。たのしかったです。
背景
前回に引き続き、NKSを買ってもらってしまった責任を取って、Wolframのいう「シンプルなプログラム」を実装してみることにしました。
3状態セルオートマトンの規則
前回扱った基本セルオートマトン(Elementary Cellular Automata)は空間1次元・近傍は両隣・状態は2種類という考えうるもっとも単純といえるものでしたが、Wolframはもう少し複雑な規則のセルオートマトンについてもその振る舞いを調べています。
ECAではセルの取りうる状態が2種類でしたが、Wolframはこれをまず3種類に増やしました。ECAと同様のかたちで各セルが次に取る状態を定めるようなルールはいくつあるでしょうか？
まずはECAのルールの数を数え上げてみます。セルの3つ組が取りうる状態は$2^3=8$通り、その各々に対して次に取る状態が$2$通りありうるので、ECAのルールは全部で$2^{2^3}=256$種類あります。
同様にして3状態2近傍のセルオートマトンのルールを数え上げてみると、$3^{3^3}=7625597484987$種類あります。2状態2近傍のECAがほんの$256$種類であったことを考えると絶望的な気分になります。
幾何級数的増加は、どんなかたちをとろうとも災いになる。そのせいで肉体人が一掃されかけたのを知っている？
―グレッグ・イーガン, 山岸真訳, 『ディアスポラ』ハヤカワ文庫SF, 2005.
これでは系統的な分析などは到底望めませんが、Wolframは総和型のルールに視野を絞ることで、分析対象の規模を現実的なものにしました。
総和型のルールでは、各セルの両隣と自身が取っている状態が参照され、その総和によって次に取る状態が定まります。例えばECAのルール150は総和型の規則で、各セルはその近傍内に1のセルが奇数個ある、すなわち近傍の総和が奇数のときに状態1を取ります。
3状態総和型CAのルールを数え上げてみます。個々のセルは0から2までの$3$種類の状態を取るので、3つ組みの総和としてありうる値は0から6までの$7$通りがあります。その各々に対して次に取る状態が$3$通りありうるので、3状態総和型CAのルールは$3^7=2187$種類あることになります。ECAと比較すると$8.54$倍もありますが、どうにか現実的に分析できるスケールになりました。
HSPによる実装
プログラムは前回とほぼ同様です。
#include "ca_totalistic.as"
ca_totalistic 777, 1, 0, 0
// cell_automaton/ca_totalistic.as
// by ctes091x (2024)
#module
#deffunc ca_totalistic int rule_code, int cell_size, int is_rand, int boundary_condition
randomize
/*ルールの生成*/
dim rule, 7
repeat 7
rule(cnt) = (rule_code / powf(3, cnt)) \ 3
loop
//状態遷移と表示
size = ginfo_winx / cell_size
height = ginfo_winy / cell_size
dim cells, size
//真ん中に1を置く
cells(int(size/2)) = 1
//ランダム化
if is_rand {
repeat size
cells(cnt) = rnd(3)
loop
}
dim tmp, size
//現在の表示座標
x = 0 : y = 0
repeat height
title "" + cnt + " in " + height
redraw 0
x = 0
//端点の処理
switch boundary_condition
case 0
//周期的境界条件
cells(0) = cells(size-2)
cells(size-1) = cells(1)
swbreak
case 1
//固定的境界条件(0)
cells(0) = 0
cells(size - 1) = 0
swbreak
case 2
//固定的境界条件(1)
cells(0) = 1
cells(size - 1) = 1
swbreak
case 3
//反射的境界条件
cells(0) = cells(1)
cells(size - 1) = cells(size - 2)
swbreak
case 4
//散逸的境界条件
cells(0) = rnd(2)
cells(1) = rnd(2)
swbreak
swend
repeat size - 2, 1
//出力
;mes cells(cnt),1
if cells(cnt) == 2 {
color 0, 0, 0
} else : if cells(cnt) == 1 {
color 127, 127, 127
} else : if cells(cnt) == 0 {
color 255, 255, 255
}
boxf x * cell_size, y * cell_size, x * cell_size + cell_size, y * cell_size + cell_size
// 近傍の総和を求める
tmp(cnt) = rule(cells(cnt - 1) + cells(cnt) + cells(cnt+1))
x += 1
loop
// 次に取る状態を`cells`に代入
repeat size - 2, 1
cells(cnt) = tmp(cnt)
loop
//y座標に1を足す
y += 1
redraw 1
await 1
loop
return
#global
結果
コード777の総和型セルオートマトンはカオス的な振舞いを示し、ルール30ECAを連想させます。
ルール90ECAのようにシェルピンスキーのギャスケットを生成する規則にはコード237などがあります。
ECAで見られるものとは異なった複雑な振舞いを示す規則も複数あります。以下にコード2049の状態遷移を示します。
コード1599のセルオートマトンを1個だけの状態1を取ったセルから開始すると、複雑なパターンがゆっくりと拡大していきますが、第8282世代まで進むとそのパターンは完全に固定された単純なものになります。
コード1599セルオートマトンの状態遷移、第10000世代まで。
感想
たのしかったです。