ライフゲームのヤバいプロジェクト3選
どうも、ConwayLife.comのフォーラムを眺めるのが日課の108Hassiumです。
ConwayLife.comというのはライフゲームを中心としたセル・オートマトンに関する話題が集められているコミュニティで、フォーラムでは新しいパターンの発見報告などが日々盛んにおこなわれています。
そんなフォーラムでは、時々「そんなことできるの！？」というようなプロジェクトが立ち上げられては偉業が達成されていくので、今回は今回はその中から本当にヤバいプロジェクトを3つ紹介したいと思います。
Spacefillerの合成
ライフゲームにおいて盛んに研究されている内容として、「グライダーの衝突による特定パターンの合成」があります。
この類の研究の集大成のようなプロジェクト(多分)として、Spacefillerの合成が行われていました。
Spacefillerというのは、ひとつながりのパターンを平面全体を埋め尽くすように無限に成長させ続けるパターンの総称です。
今年の2月の終わりごろに合成プロジェクトが動き出し、3月13日にはもう完成したようです。
#ライフゲーム
— 108Hassium (@1Hassium) March 13, 2023
先日紹介した「やばいチャレンジ」が完遂されたようです。https://t.co/tUmvEnwOSt pic.twitter.com/p06ULNXOCA
これで話は終わりかと思いきや、合成方法を改良してグライダーの個数を減らす試みが未だに続いているようです。
合成に必要なグライダーは最初は2373個でしたが、どうやら現在は952個まで減らされているようです。
この手の酔狂な合成プロジェクトは今に始まったことではなく、2021年にはGrayShip(生きたセルの密度が1/2の平面的な繰り返し構造を持つ移動物体)の合成プロジェクトが始動し、最終的には任意サイズのGrayShipの合成に一般化できる合成手順が構築されました。
#ライフゲーム#セル・オートマトン
— 108Hassium (@1Hassium) July 2, 2021
先日紹介した「やばいチャレンジ」が完遂されたようです。https://t.co/s6puNDwyCl pic.twitter.com/SHkzNWX4wP
RCT
Spacefillerの合成に必要なグライダーの数は、何個まで減らせるのでしょうか？
実は、現在使われているような手法とは全く違う(?)手法を用いることで、952個から僅か15個まで減らせるようです。
実はSpacefillerに限らず、グライダーの衝突により合成可能な全ての物体は15個以下のグライダーで合成可能らしいです。
これには、RCT(Reverse Caver-Tosser)というパターンが関係しています。
RCTは自身を構成する特定のパーツの間の距離を読み取ってグライダーの列を生成することにより、各パーツを合成するのに必要な一定の個数のグライダーの個数だけでいくらでも複雑なパターンを合成できるパターンです。
15個のグライダーで作れるRCTは、以下のような構造になっています。
左上と右下に4個、左下に7個のグライダーが配置されています。
しばらく動かしてみると以下のようになります。
各グライダーは4つ(左下が2つ)のGPSE(Glider-Producing Switch Engine)というパターンになり、中央に向かってグライダーを射出しながら中央に移動します。
中央でグライダーが衝突した後はいくつかの固定物体や振動物体が残り、右下に向かってグライダーが1個だけ射出され、GPSEから射出されたグライダー列が中央で相殺しあって何も起こらない状態がしばらく続きます。(左上にもグライダーが射出されるのですが、これは動作原理とはあまり関係ないようです)
右下へ射出されたグライダーが右下のGPSEと衝突すると、GPSEが生成するグライダー列とは別の位置にグライダーが1個生成され、中央へと戻っていきます。
跳ね返ったグライダーが中央の合流地点へ到達すると、右下と右上に向かってグライダーが1個ずつ射出され、右上のグライダーは右上にあった物体群に衝突します。
右下に向かっていたグライダーはGPSEに衝突して中央に向かって跳ね返り、合流地点に到達するとまた右下と右上にグライダーが射出され、という流れをGPSEが中央に到達するまで繰り返す・・・と思いきや実は違います。
グライダーがGPSEに衝突した際に、グライダーが跳ね返るのではなく通常のグライダーの生成を一時的に妨害することがあります。
このグライダー列の欠けた部分が合流地点に到達した場合、右下に再度グライダーが射出されるのは変わらないものの、右上に射出されるグライダーが2個になります。
グライダーとGPSEが衝突した際に「新たなグライダーが打ち返される」か「グライダー列が欠ける」かのどちらが起こるかは衝突のタイミングに依存します。
そして、
衝突結果が合流部に到達する
↓
合流部から右下へグライダーが射出される
↓
グライダーがGPSEに到達する
↓
衝突結果が合流部に到達する
↓
・・・
というサイクルの繰り返しにおいて2つの衝突結果がどの順番で発生するかは、GPSEと合流部の距離によって変わるようです。(距離の2進展開と関係しているらしいです)
距離によって衝突結果の発生順を変えられるということは、右上方向のグライダーの射出パターンも1個のパターンと2個のパターンを好きな順番で発生させることができます。
そして、どうやらグライダーの射出順序をコントロールすることで、グライダーの衝突により合成可能な任意の物体の合成 & GPSEが生成する大量の瓦礫の全消去が可能なんだそうです。
なお、RCTによる合成はあくまでも「理論上可能である」というだけの代物で、実際に面白い物体を合成するパターンは巨大すぎてほぼ構築不可能だそうです。
以下のページには「15グライダーRCTのデモパターン」と称されたファイルが投稿されていますが、実際のデモパターンではRCTの動作を見せつつパターンのサイズを現実的な値(約1兆×1兆)に収めるために代替措置が取られているため、総セル数はグライダー15個分(75セル)より多い59286419セルになっています。
GPSEと中央の距離は1往復ごとにほぼ半分ずつ減っていくので、逆に言うとグライダーの信号がGPSEと中央を往復する回数を1回増やそうとすると初期状態のサイズは2倍になり、結果として本当にグライダー15個だけのパターンは非現実的なサイズになるようです。
余談ですが、「RCT」という名前は以下のような経緯で付けられたようです。
「Caver Tosser」というパターンが作られる。
Caver Tosserの動作を逆にしたものが有限グライダーによる万能合成装置として機能することが発見され、「Reverse Caver-Tosser」と命名され、「RCT」という略称で呼ばれる。
有限グライダーによる万能合成装置全般が、Reverse Caver-Tosserと異なる機構でもRCTと呼ばれるようになる。
最初のReverse Caver-Tosserは329個のグライダーで出来ており、そこから2度の大幅な設計変更により15個まで削減されたようです。
ちなみに、現在ではさらなる改良案としてGPSEの数を4個から3個に減らす案があり、グライダーの個数は12個まで減らせるかもしれない、と言われているようです。
1次元移動物体の構築
ややマイナーではありますが、ライフゲームで研究されているパターンの種類として「幅1セルのパターン」があります。
例えば1998年には幅1セルの無限増殖物体が発見され、2011年にはBreeder(成長速度が2次関数オーダーの無限増殖物体)が発見されています。
そして2016年2月14日、フォーラム上に幅1セルの移動物体に関するスレッドが立てられました。
なお、ここでの「幅1セル」というのは、無限増殖物体やBreederの場合とは微妙に意味合いが異なります。
幅1セルの無限増殖物体というのは幅1セルの初期状態から無限に増殖する、というだけの意味であって、幅が1セルなのは初期状態だけの性質でした。
一方、先程のスレッドでは「移動過程に幅1セルの状態が含まれる移動物体」を作ろうとしており、幅1セルの初期状態から周期的に幅1セルの状態に戻さなければならないので勝手が大きく異なります。
これまで紹介したものとは異なりプロジェクトはまだ完遂されていませんが、どうやらある程度は見通しが立っているようです。
スレッド上での最後の投稿は2022年12月12日で、その時点までの進捗を表すパターンファイルが添付されています。
example.mcを開いてみると一本の長い線状のパターンが表示され、拡大してみると大量のブリンカーで出来ていることがわかります。
ブリンカーを並べただけだと2周期で振動するだけで何も起きませんが、左端から17.6億セル程離れた位置には6つのセルが並んでいる箇所があります。
シミュレーションを開始するとブリンカーが導火線のような働きをして不安定な構造が左に向かって伝達していき、途中でグライダーが射出されます。
そのまましばらくは何も起きませんが、120万世代ほどで導火線が途切れ、LWSS(lightweight spaceship：軽量級宇宙船)が縦方向に射出されます。(以下、ブリンカー列に対して上側の領域だけを観察することにします)
このLWSSは最初の方で射出されたグライダーと衝突し、今度は左下と右下にグライダーが射出されます。
このうち左下に向かったグライダーは左の方に残ったブリンカー列のド真ん中に着弾し、再び導火線の燃焼が始まります。(右下では特に何も起きないようです)
ただし今回の燃え方は最初とは異なり、途中からMWSS(middleweight spaceship：中量級宇宙船)が後ろ向きに射出されるようになります。
この現象は導火線の左右両方で起き、結果として両側から飛来したMWSSの列は点火位置の近くで衝突し、右上に向かってグライダーの列ができます。
グライダーの列はLWSSとグライダーの衝突でできた残骸へと向かい、RCTの右上部分のように衝突を繰り返して何かを合成していきます。
なお、RCTのようにグライダーが衝突する方向は固定されているものの、衝突する位置やタイミングはMWSSの衝突の仕方で調節できる(MWSSの衝突の仕方は導火線の構造で制御できる)ため、RCTよりは効率よく合成作業ができるようです。
合成作業は大体900万世代あたりまで続き、「右上に向かって移動しながら右下に向かってグライダーを射出し続けるPuffer」が8つと「謎の固定物体群」が出来上がります。
Pufferが射出したグライダー群は下半分から射出されたものと合流し、合流地点にブリンカーがあるとそのブリンカーを消去して左上に向かってグライダーを飛ばします。
合流してから最初に出力された2個のグライダーは謎の固定物体群に衝突し、結果として「右上に移動しながら左下にグライダーを射出し続けるPuffer」が２つと「グライダー銃っぽい謎の装置」が組みあがります。
この一連の装置は、どうやら右の方にあるブリンカーの列をデータとして読み取るための装置のようです。
まず、8連pufferが射出するグライダー列がブリンカー列に当たるとブリンカーの有無が左上向きのグライダー列として出力されます。
読み取り結果のグライダー列は後から作られたほうのPufferが生成する左下向きのグライダー列にぶつかり、グライダー列に欠けを作ります。
一方、Pufferが生成したグライダー列が向かう先である左下の方では銃が2304周期でグライダーを射出しており、2個のPufferが生成したグライダー列はそれぞれ衝突して打ち消し合っています。
そこへグライダー列の欠けが到達すると、銃が生成するグライダー列にPufferが生成したグライダー(位置や位相が銃のものとズレている)が混ざります。
銃が生成したグライダー列はブリンカー列の読み取り開始地点の辺りで衝突し、Pufferから生成されたグライダーが到達するまでは斜め方向にハチの巣の列を作っています。
ここにPufferから生成されたグライダー、つまり右側のブリンカー列の読み取り結果が到達することでRCTと同じような原理で再度複雑な合成作業ができるようになります。(最初に行った合成作業とは異なりグライダー列の自由度は低いですが、グライダーの照射間隔が短いのでRCTよりは高効率で動作します)
実際の合成手順としては、まずハチの巣の列を全て消し、代わりにブリンカーの列をはしごのように使って位置を調節しながら左下に向かってグライダーを射出し、左下で合成作業を行うようです。
このようにして、ブリンカー列のデータを基にして合成作業が行われます。
この作業で合成される構造物は非常に大きく、約30億世代かけて1000×1500ほどのサイズの固定物体群を合成します。
この巨大なパターンはどうやら銃らしく、左上に向かって決まった形のグライダー列を射出してブロックをひたすら左上に向かって押していくような動作をします。
残念ながらこの装置が動き始めた辺りで右側のブリンカー列は端まで読み終わってしまい、どうやらexample.mcで実装されているのはここまでのようです。
また、最後に作られた謎の巨大装置は何にも触れずただひたすらブロックを押し続けるだけで、何のために合成されて本来どう働くのかは私にはわかりませんでした。(ブリンカー列を読み取って何かをしそうな配置のパーツはある)
完成版にてこの後実行される動作としては、以下のようなものが予想できます。
Pufferと銃を使ったものとは別のブリンカー列読取装置と、ブリンカー列の再生成機構を合成する。
Pufferと銃の動作を止める。
新たな読み取り装置を起動し、残りのブリンカー列を読み取って初期状態のブリンカー列を再構築する。
読み取り装置やPufferの残骸をすべて消去する。
ブリンカー列にグライダーをぶつけ、最初の発火地点を作る。
技術的に一番難しそうに見えるのは3番で、ライフゲーム版クワインプログラムみたいなことをやることになりそうです。
前述の通り、フォーラムのスレッドにおける最終更新は去年の12月です。
現在プロジェクトが稼働中で続きが作られているかは不明ですが、個人的には完成が非常に楽しみです。