StarWarsという名前のセル・オートマトンがある

どうも、108Hassiumです。

タイトルの通り、StarWarsというセル・オートマトンのルールを紹介します。

定義

StarWarsは4状態2次元ムーア近傍ルールです。(以下、セルの状態を0~3の整数で表します)

具体的には、以下のようなルールです。

• 0番のセルは、周囲にある1番のセルの個数が2個なら1番のセルに変化する。

• 1番のセルは、周囲にある1番のセルの個数が3、4、5のいずれかなら1番のまま変化せず、それ以外なら2番のセルに変化する。

• 2番のセルは、3番のセルに変化する。

• 3番のセルは、0番のセルに変化する。

Gollyではルール欄に"345/2/4"と入力することで利用できます。

※☟Gollyの説明

続いて、このルールに存在する様々な物体を紹介します。

固定物体

ライフゲームと違ってランダムパターンからの自然発生率は低いですが、このルールにも様々な固定物体が存在します。

左上のXペントミノは右端の二つの物体のようにつなぎ合わせることができ、その他にも汎用性のある構造がいくつかあるのでコツをつかむと以下のような大き目の固定物体を手作業でつくることもできます。

移動物体

固定物体が発生しにくい代わりに(?)、このルールではいろいろな移動物体が自然発生します。

基本的には2×3の長方形の移動物体に色々なパーツが付いた形のものが多いですが、最下段にあるもののように違う形のものもあります。

また、以下の斜めの移動物体は2021年(このルールの初出は1999年)になってからやっと発見されたそうです。

振動物体と銃

私がこのルールで一番面白いと思っているのが、振動物体です。

非常にバリエーション豊かでなおかつ非自明な振動物体が、手軽な作業量でザクザク見つかるのがStarWarsの魅力だと思っています。

例えば、私はこのルールを知ってすぐに以下の物体を見つけました。

※以下、この43周期の振動物体を"F43"と呼ぶことにします。他の振動物体には名前は付けませんが、これだけは後で何度も出てくるので覚えておいてください。

さらにその後、いろいろな周期の振動物体を見つける方法を発見し、1年ほど(うろ覚え)で4~100周期の振動物体を自力で発見しました。(生きたセルが死んでから生き返るまで最速でも3世代かかるので、このルールには2周期と3周期の振動物体は存在しません)

というわけで、非自明な振動物体を見つける方法をいくつか紹介します。

焚火法

先程紹介した43周期の振動物体(F43)は、以下のような棒状のパターンから生成されたものです。

Xペントミノをつなげた固定物体に似ていますが、中央に1か所だけ誕生条件を満たしているセルがあり、そこから炎のように生きたセルが噴き出てきます。

このように「安定な棒状の骨格+生存条件を満たす少数のセル」という組み合わせの物体は振動物体になりやすく、似たような物体をつくることで様々な振動物体を見つけることができます。

生成される振動物体が焚火っぽい形をしているので、私はこの方法を「焚火法」と呼んでいます。

なお、骨格の種類によっては炎の中から移動物体が出現し、振動物体ではなく銃ができることもあります。

そういったケースでも、固定物体をうまく配置して移動物体を消すことで振動物体にできることが多いです。

ループ法

こんな振動物体があります。

固定物体であるXペントミノの周りを、最小の移動物体を半分に切ったような形の物体(以下、「電子」と呼ぶことにします)がくるくる回っています。

こんな感じで固定物体の周りを電子が周回する振動物体は、以下のようにいくらでもつくることができます。

また、Xペントミノを1列に$n$個つないで電子を1個付けると$6n+6$周期の振動物体ができますが、電子を複数個にすることで4以上の任意の周期の振動物体をつくることができます。

しかしこんなものを収集しても何も面白くないので、電子ループを応用して非自明な周期の振動物体を見つける方法を考えました。

この物体のように、固定物体の外周に上手く「凹み」を作ると、電子が分裂したりして予測不能な動きをするようになります。

ちなみにこの振動物体は、電子を2個点対称に配置した初期状態から生成されたものです。

この初期状態の電子を1個にしても振動物体が生成されますが、その周期はなんと324になります。

どうやら非自明電子ループを使って対称性の低い振動物体を作ると、周期がかなり長い振動物体ができやすいようです。

余談ですが、ライフゲームにも(面白くないほうの)電子ループと似たような振動物体があります。

この振動物体は、グライダーを反射させることができる固定物体を4つ使ってループにしたものです。

この方法を応用することで、ライフゲームでは43以上の任意の周期の振動物体をつくれるようです。(42以下だと、19周期と41周期のみ未発見らしいです)

StarWarsでも同様に、振動物体を跳ね返すことでループ状の振動物体をつくることができます。

このパターンは自力で発見したものですが、ConwayLife.comというサイトのフォーラムで調べてみたところ4周期で動作させられるものが見つかりました。

よって、移動物体のループでも電子ループと同様に4以上の任意の周期の振動物体をつくれるようです。

鳥籠法

続いて、こんな振動物体があります。

閉環状の骨格の内側に焚火のような発火点をつくることで、こんな形の振動物体をつくることができます。

ちなみに「鳥籠型」という形容に合わないので別物として紹介しますが、以下の振動物体もほぼ同じ発想で作られています。

焚火干渉法

焚火法で発見したF43を使うことで、さらに以下のような振動物体を発見することができます。

焚火を2つ向い合せ、炎が干渉しあうことで元の振動物体とは異なる周期の振動物体が出来上がります。

この手法のバリエーションは非常に豊富で、

• 使用する焚火の種類を変える

• 焚火の位相をずらす

• 異なる2種類の焚火を使う

• 単体では振動物体にも銃にもならずに崩壊する焚火を使う

• 2つの焚火の向きを平行ではなく垂直にする

• 焚火2個ではなく焚火+固定物体にする

・・・等が考えられます。

ちなみに、F43を位相をずらさずに向かい合わせてできる43周期でない振動物体を数えてみたところ、全部で93個ありました。

そして周期ごとの振動物体の個数をグラフにすると、こうなります。

ご覧の通り、なぜか25周期の振動物体の個数だけやたら多いです。(32個)

他の焚火を使った時でも、「元の焚火の周期と全く関係なさそうな特定の周期の振動物体だけがたくさん見つかる」という現象は時々見られます。

ライター法

焚火干渉法は焚火の炎の部分に細工をする手法でしたが、骨組みの方を弄る方法もあります。

これらの振動物体は、左端のF43の骨格に対して下方向にXペントミノを付け足していった形の骨格を持っています。

一部の焚火はこのように骨格を下に伸ばすことによって周期が変化し、それを利用した振動物体探しの手法を「ライター法」と呼ぶことにします。

ちなみに、F43にライター法を適用することで得られる振動物体の周期は、以下のように続きます。(0は崩壊して振動物体にならないパターン)

このあとは必ず骨格が崩壊するようになり、0が無限に続くようです。

以下、ライター法により得られる振動物体の周期を順番に並べた数列を「ライター数列」と呼ぶことにします。

F43から生成されるライター数列は途中から0しか出てこなくなってしまいますが、そうでないパターンもあります。

このパターンから生成されるライター数列は以下の通りです。

観察の結果、どうやらこの数列は以下の式で表せるっぽいです。

$a_n=\begin{cases}6n+44&\text{if}　n\equiv 0\pmod{2}\\6n+42&\text{if}　n\equiv 1\pmod{2}\end{cases}$

※初項は$a_0$。

百数十個程のライター数列を調べてみたところ、大体の数列が剰余で場合分けされた等差数列で表せそうでした。(数列自体も最初の数十～数百項を手作業で調べただけなので、信頼性は低いです)

ただし、上の例とは以下のような違いがありました。

• 等差数列で表せるのは途中の項からで、最初の方だけ不規則になっているような数列が多い。

• 場合分けの数($\mod N$の$N$の値)は2より大きくなることがある。

• 公差は一定ではない。

• 一般項が不明な数列もあった。(場合分けの数が非常に多いか、規則性が現れるのが遅いか、もしくはその両方？)

一般項が不明なパターンには、非自明ループ法で使ったような凹みのあるものが多いです。

また、一般項がわかっている(といっても厳密に証明したわけではないですが)パターンには以下のような共通点が見られました。

• 場合分けの個数は偶数。

• 公差は6の倍数。

場合分けの個数として現れたことのある数値は2,4,6,8,10,14,16,22,28,34,40,104で、公差は6,12,18,24,30でした。

このような性質が本当に成り立っているかどうかははっきりしませんが、成り立つとしてもその原理は私には見当もつきません。

ところで、ライター法は単なる振動物体探しの手法の一つではなく、「焚火から新しい焚火を作る方法」と考えることもできます。

ということは、ライター法の結果を利用すればこういうこともできます。

また、逆にこういうこともできます。

最後に

以上、StarWarsの紹介でした。

個人的に好きであるというだけの振動物体の話がメインになってしまいましたが、他にも

• breeder(2次関数オーダーの速度で成長する物体)探し

• 回路・計算機作り

等のテーマがあり、なおかつ面白いパターンを自力で見つける難易度がライフゲームよりは低いというのもこのルールの魅力だと思います。

というわけで、皆さんもぜひSarWarsの世界を楽しんでください。

それではさようなら。