小規模グリッドの周期的境界セルオートマトン

小規模グリッドの周期的境界セルオートマトン

17年前に妻と出会った頃[1]、私はある数学の問題に興味を持っていました。それは次のようなものです。

水平方向と垂直方向の両方で折り返される、非常に小さなセルオートマトン・グリッドにおいて、得られるユニークなパターンの最長シーケンスは何か？

「セルオートマトン」は広範な用語です。私の問題の目的においては、以下の特徴を持つグリッドを指します。

1. チェッカーボードやチェス盤のように、たくさんの正方形があります。これらは「セル」と呼ばれ、各セルは任意の時点で「生きて（オン）」いるか「死んで（オフ）」いるかのどちらかです。各セルには8つの隣接セルがあります。これらは、辺または角で接しているセルです。

   1. グリッドは水平方向と垂直方向で折り返されるため、右端のセルは左端のセルのいくつかを隣接セルとして持ち、下端のセルは上端のセルのいくつかを隣接セルとして持ちます。

2. グリッド全体が一度に更新されます。これは「ステップ」と呼ばれます。各「ステップ」で、セルはすべての隣接セルを見回し、生きているセルの数を数えます。特定の数である場合、そのセルは次の「ステップ」で生きます。それ以外の場合は死にます。どの数がどちらに対応するかは「ルール」と呼ばれます。

   1. 例えば、Conwayのライフゲームとは異なり、セルは自身の状態を追跡しません。つまり、セルはステップ n で生きていても死んでいても、ステップ n + 1 で生きていても死んでいても、その影響はありません。ステップ n + 1 を決定する唯一の要因は、8つの隣接セルのうちいくつがステップ n で生きていたかです。

以下は6x6グリッドの例で、2つのセルが青系の色でハイライトされ、その隣接セルが赤とオレンジでハイライトされています。

[ [画像] ]

濃い色のセルは生きており、薄い色のセルは死んでいます。左端のピンク色のセルが、グリッドが水平方向（および垂直方向）に折り返されるため、濃い青色のセルの隣接セルとしてカウントされていることに注意してください。

このグリッドのルールは次のとおりです。セルが現在3つまたは4つの隣接セルを生きた状態にしている場合、次のターンで生きます。それ以外の数の隣接セルを生きた状態にしている場合、死にます。薄い青色のセルは明らかに3つの隣接セルを生きた状態にしているため、次のターンでオンになります。濃い青色のセルは一見4つの隣接セルを生きた状態にしているように見えるかもしれませんが、実際には5つなので、次のターンでオフになります。ピンク色のセルが隣接セルである理由を理解するには、濃い青色のセルから始めて、右に1つ移動し（これにより左端に到達します）、次に上に1つ移動することを考えてみてください。これは単一の対角線ステップであり、隣接セルとなるため、濃い青色のセルはオフになります。

色分けなしのグリッドは次のようになります（黒いセルは生きています）。

[ [画像] ]

次に、グリッド全体が次のステップでどのようになるかを示します。ランダムな生きているセルをいくつか確認し、それらが事前に正確に3つまたは4つの隣接セルを生きた状態にしていたことを確認してください。

[ [画像] ]

最後に、グリッドが安定して変化しなくなるまでのすべてのステップを示すGIFを示します。

[ [画像] ]

最終的に、これらのグリッドは有限であり、可能な状態の数も限られているため、必ず同じパターンを2回繰り返すことになります。さらに、それらは完全に決定的であるため、一度パターンが繰り返されると、その構成は前回出現したときと同じ「次の」構成を持つことになり、無限ループが作成されます。

理論的には、n 個のセルを持つグリッドは 2^n 通りの異なる構成を持つことができ、すべての可能な構成をヒットするルールは、自身を繰り返す前に最大 2^n ステップ持続する可能性があります。しかし実際には、小さいグリッドではどのルールもこれに到達せず、ましてやそれに近づくことさえありません。

実際、証明できます。3x3から始めましょう。

3x3

まず、くだらない観察ですが、3x3のグリッドでは、すべてのセルがお互いの隣接セルになります。これは「中央」のセルにとって特に明白です。

[ [画像] ]

LとRは左と右、UとDは上と下を表します。ラベルは、薄い青色の中心のセルに対するセルの関係に対応しています。

しかし、グリッドは折り返されるため、他のセルでも同じです。例えば：

[ [画像] ]

ここから、楽しい観察ができます。すべての生きているセルは、他のすべての生きているセルと同じ数の生きている隣接セルを持ち、すべての死んでいるセルも同様です！もし5つのセルが生きているなら、どのセルも自身の隣接セルではないため、すべての生きているセルは4つの生きている隣接セルを持ち、すべての死んでいるセルは5つの生きている隣接セルを持ちます。

[ [画像] ]

各セルには、現在生きている隣接セルの数がラベル付けされています。

非常に窮屈なため、3x3グリッドではあまり多くの異なるパターンを得ることはできません。生きている各セルは、一度に生き続けるか、一度に死ぬことができます。死んでいる各セルは、一度に死んだままにするか、一度に生き返ることができます。唯一の現実的な選択肢は、繰り返し反転することです。

[ [画像] ]

または、グリッド全体が生きているか死んでいるかのどちらかになることです。

[ [画像] ]

これらが唯一利用可能な変換であるため、最長の可能なシーケンスは、これら両方を単純に連鎖させるだけです。反転する開始構成を選択し、次にグリッド全体を生きている状態にし、次にグリッド全体を死んだ状態にします。（または、反転してからすべて死んだ状態にし、次にすべて生きた状態にします。どちらでも構いません。4番目の状態の後にグリッドがまったく同じままであるか、永遠にすべて死んだ状態とすべて生きた状態の間で点滅するかどうかも関係ありません。）

例えば、次の開始構成とルールを考えてみましょう。

[ [画像] ]

まず、生きているセルは死にます（それぞれが4つの生きている隣接セルを持っているため）、そして死んでいるセルは生き返ります（それぞれが5つの生きている隣接セルを持っているため）。

[ [画像] ]

今、どのセルも0または5つの生きている隣接セルを持っていません。生きているセルは3つを持ち、死んでいるセルは4つを持ちます。したがって、グリッド全体がオフになります。

[ [画像] ]

今、すべてのセルが0個の生きている隣接セルを持っているので、すべてオンになります。

[ [画像] ]

この時点で、グリッドはすべてオンとすべてオフの間でループするだけですが、それは問題ではありません。私たちの中心的な質問は、ループ自体ではなく、以前に見た状態を再び見る前に、いくつのユニークな構成を得ることができるかということです。この場合、4つを見ました。それらをすべて一緒に示します。

[ [画像] ]

グリッドが自身を繰り返す前に、4つよりも長いシーケンスを持つことは不可能です。4は、今日私たちが扱っている特定の種類の3x3周期的境界CAグリッドにおけるユニークな状態の最大数です。[1]

4x4

4x4は私の心に特別な場所があり、財布にも特別な場所があります。なぜなら、私のキャリアの始まりだからです。私は4x4のケースを解決したかったのですが、鉛筆と紙だけではうまくいきませんでした。そこで、大学でプログラミング入門クラスを取り、コンピューターでそれを解決しました。最初のプログラミングの仕事のためにコールドメールを送ったとき、私は4x4 CAの結果を含めました。それが違いを生んだようです。面接に来たとき、彼らはそれをチェックするために4x4グリッドをホワイトボードに書きました。ですから、次に誰かが4x4周期的境界セルオートマトンは役に立たないと言ったら、ここをリンクしてください！

ええと。グリッドに移りましょう。

[ [画像] ]

数字は、各セルが青いセルをいくつ隣接しているかを示しています。ご覧のとおり、一部のセルは両方に隣接し、一部のセルは1つにのみ隣接し、一部のセルはどちらにも隣接していません。

各セルは8つの隣接セルを持ち、合計16個のセルがあるため、各セルはグリッドのちょうど半分と隣接しています。そのため、3x3の全体主義とは異なり、興味深いパターンが見え始めます。

実際、17歳の私の若い脳で長い間考えていたにもかかわらず、4x4以上については、総当たり攻撃以外のより良いアプローチを見つけることはありませんでした。つまり、すべての可能な開始構成を取り、それらを「ユニークな」ものにフィルタリングし、次に各ユニークな構成を各ルールに対してチェックし、どの組み合わせが最も長く続くかを確認します。

「ユニークな」開始構成で私が意味することを理解するために、次の2つのグリッドを考えてみましょう。

[ [画像] ]

どのようなルールを与えても、これらのグリッドはまったく同じステップ数で持続します。実際、パターン全体が左に2セルシフトされた、まったく同じシーケンスを見ることになります。よく見るとわかります。

[ [画像] ]

これはより一般的に当てはまります。パターン全体を上下、左右、またはその両方に移動させると、結果のシーケンス全体も同様にシフトされ、それ以外は同一になります。

または、次の2つの構成を考えてみましょう。

[ [画像] ]

左側は右側の単なる鏡像です。鏡像されていることを除けば、まったく同じように動作します。

[ [画像] ]

これは見つけにくいですが、2番目のパターンは最初のパターンの右への回転です。同じことです。

[ [画像] ]

これら2つは「反転」しています。左側の生きているセルは右側では死んでおり、その逆です。反転したパターンは、特定のルールでは同じではありません。しかし、ユニークな状態の最長の連鎖（そして私たちはそれに関心があります）のみを気にする場合、それらはより微妙な方法で同じです。具体的には、開始構成とルールの両方を完全に反転させると、同じパターンが得られます。例えば、元のパターンとルール{3オン、4オン}、および反転したパターンとルール{0オン、1オン、2オン、3オン、6オン、7オン、8オン}を示します[2]。

[ [画像] ]

つまり、手短に言うと、開始構成またはチェックするルールの数を半分にすることができます。なぜなら、反転したルールは、「オフ」と「オン」を切り替えるだけで、まったく同じパターンを示しているからです。

すべてのアイデンティティをまとめると、アルゴリズムを実行できます。

1. まだ除外していない開始構成を取る。
2. それを左に1つ移動し、すべてのネストされたステップを実行します。完了したら、合計3回実行されるまでこのステップを繰り返します。
   1. それを下に1つ移動し、すべてのネストされたステップを実行します。完了したら、合計3回実行されるまでこのステップを繰り返します。
      1. それを右に90度回転させ、次に...

そして続きます[3]。

移動、反射、回転でフィルタリングすることにより、ユニークな開始構成の数を65,536から、はるかに扱いやすい805に減らすことができます。そして反転でフィルタリングすることにより、512のルールを256に減らすことができるため、試行する{ルール、構成}の組み合わせの総数は206,080になります。

私は2009年に、新鮮なコンピューターのスキルを使って、その数字を crunch しました。そして、答えは…14であると判断しました。

[ [画像] ]

タダ！

5x5

カフェテリアのテーブルで私の目に浮かんだ遠い数学的な表情（そしてその周りの非常に長いまつげ）は、現在の妻の初期の注意を引き続けるのに役立ちました。そして私の「14」という答えは、私のキャリアをジャンプスタートさせるのに役立ったので、私は10年半の間、自分の業績に満足していました。私は完全に諦めたわけではなく、時折その問題に戻っていましたが、私の計算では5x5はコンピューターが連続して実行するのに1ヶ月以上かかるだろうと示唆していました。したがって、私の選択肢は次のとおりでした。

1. コンピューターに5x5をバックグラウンドで実行させ、進行状況を保存させる。
2. より洗練されたフィルタリング体制を考案し、より少ないユニークな構成をテストできるようにする[4]。
3. どうにかして「スーパーコンピューター」の時間を借りる（私は文字通り「スーパーコンピューター」という言葉を考えました）、そして当時それはさらに困難でした。

これらすべてがクールで楽しそうに聞こえたにもかかわらず、2025年まで本格的に試さなかったことを恥じています。その時点で、「コンピューターは今や強力になり、私は楽しいセルオートマトン部分に集中しながら、AIを使って厄介なコンピュータサイエンスの最適化を行うことができる」と気づきました。

本格的に試した結果、うまくいきました。さらなるブレークスルーもなく、Cursor（まだClaude Codeにはいませんでした）を liberal に使用して、私は何度も4x4のケースを確認し、5x5の答えを得ました。それは…916です。

[ [画像] ]

はい！この数字はまったく驚きではありませんでした。CAの本来のポイントは、小さなグリッドに限定されない場合、単純なルールが巨大な複雑性を生み出すことです。したがって、グリッドがそれほど混雑しなくなるにつれて、爆発的な成長を期待すべきです。

6x6？

この記事は、6x6を試す前にここまで書いてきました。私が5x5に使用した実装は遅すぎることを知っていたので、5x5のGIFを眺めて「916」とつぶやくことに満足していました。

しかし、新しい時代です。AIはミレニアム賞問題を解決しています。ですから、私の気まぐれな人間のプライドを飲み込み、目に涙をこらえ、純粋で意欲的な機械的な数学的進歩の雪崩の導管になることを自分に誓い…

コンピューター！お願い！6x6の答えは何ですか？[5]

[ [画像] ]

それは1,717です。5x5のケースの2倍にも満たない。奇妙です！[6]

もっと早く爆発して、数十万になると思っていました。しかし実際には、最長の6x6チェーンと最長の5x5チェーンの比率は、4x4と3x3の比率ほど大きくありません。生きて、学ぶものです。

なぜ6x6はそれほど控えめなのでしょうか？よくわかりませんが、一つの理論は、6は非常に割り切れる数であり、5は素数であるということです。6x6を解いている間にClaudeがふと指摘した興味深い結果は、4つの3x3グリッドをタイリングして単一の6x6グリッドを作成すると、4つの3x3グリッドは3x3ケースとまったく同じように動作し、最大4ターンしか到達できないということです。最初は直感的ではありませんでした。しかし、それはチェックアウトします。

[ [画像] ]

タイリングされた開始構成は多くないので、それ自体は大きな問題ではありません。しかし、素数グリッドは、うまく割り切れるグリッドよりも奇妙である可能性を示唆しています。あるいは、そうでないかもしれません！この時点で、私は推測しています。

せっかくなので、4x4と5x5の解は、重複を除外すると、ほぼユニークであると remark します。6x6は実際にユニークです。重複を除外すると、単一の開始構成と単一のルールに対してのみ1,717に到達します。

ここまで読んだなら、コードを見てみたいかもしれません。ですから、ワイルドな推測に入る前に、ここにあります。その多くは2025年の私の努力によるもので、最初に5x5を解決しました。この投稿を開始してから作成された6x6のコードは、「fast」の下で見つけることができます。

7x7？？

まだです。7x7でルールごとに20,000個のランダムな開始構成をサンプリングしたところ、最長シーケンスは545,752ステップになりました。したがって、答えは少なくともそのくらい高くなくてはなりません。大まかな推測では、私のCPUは答えを見つけるのに270年かかり、私のコンピューター全体（GPUを最大限に活用しても）は連続して5年かかります。並列でテストを実行するために、より高価なGPU時間をオンラインで購入することもできますが、おそらく約10,000ドルかかるでしょう。私の息子は数日中に出産予定で、娘は数日後に2歳になるので、この白鯨を追いかけるために10,000ドルを費やすべきではないでしょう。

7x7を手の届く範囲にするために、おそらく派手なエンジニアリングトリックが必要になるでしょう。おそらくコストを数百ドルに抑えたり、私のコンピューターでバックグラウンドで数ヶ月実行したりできるかもしれませんが、かなりの作業が必要になるでしょう。

セルオートマトンは、単純なルールが非常に複雑な創発的振る舞いを作成できるため、特別です。私の小さなグリッドでの奇妙ないじくり回しは、その稲妻をボトル詰めし、ほぼ完全な制約下でどれだけ混沌とすることができるかを見る方法です。しかし、制約が緩和されグリッドが大きくなるにつれて、還元不可能な複雑さが忍び寄ります。巧妙なアルゴリズムを考案し、インテリジェントにサンプリングすることはできますが、結局のところ、最大値を知る唯一の方法はすべてをチェックすることです。

この中に、私をnerdsnapして先に到達する人がいなければ、いつか7x7を解決するかもしれません[7]。しかし、今日はしません。

8x8？！

忘れてください。ルールごとに2,000個の開始構成をサンプリングしたところ、5,064,397ステップのシーケンスが見つかりました。数百万ドルのコンピューティング能力があっても、できることは教育的な推測だけです。そして、9x9、10x10、11x11に近づくにつれて、人類がその問題を解決するためにすべてのリソースを捧げたとしても、失敗する可能性のある領域に忍び寄ります。16x16になると、おそらく物理的に不可能であり、多くの銀河のサイズを持つコンピューターが必要になります。そして、そのように続きます。

[ [画像] ]

未知の顔を崇拝せよ

それでも、このプロジェクト全体は小さなグリッドに関するものです。現時点では、6x6で線を引くことができ、シーケンスは完了したと呼べます。4、14、916、1,717。これらは、最も小さい正方形グリッドの周期的境界CAの最大終端数です。これでわかりました。

それ以降は、サンプリングと狂気だけが待っています。あなたが、親愛なる読者、より良い方法を見ない限り。

1

真のCA愛好家にとって、私たちは「誕生」と「生存」のルールが同一である2状態CAを見ています。これが何を意味するかわからない場合は、心配しないでください。

2

これらの2つのルールが両方とも「3オン」を持っているのに、なぜ反転しているのか不思議に思うかもしれません。基本的に、ルールを反転するには、そのルール内のすべての「オン」を取り、その数から8（隣接セルの総数）を引いて、それらだけを「オフ」にします。奇妙ですが、うまくいきます。

3

実際のいくつかの実装については、gitリポジトリを確認してください。

4

ここでもいくつかのアイデアがありましたが、主に各構成の後に残りのステップ数を事前計算することでしたが、それは計算とメモリの間の厄介なコンピュータサイエンスのトレードオフになり、グリッドの対称性ほど楽しくはありませんでした。

5

このブログ記事と昨年使用した5x5のローカルコードを考慮すると、Claude Opus 5.5は確かに一度で6x6を解決しました。

6

興味があるなら、ClaudeはC++でソルバーを書き、私が知っている言語よりもはるかに効率的なプログラミング言語で、私が5x5で詰まっていたときに夢見ていたような事前計算を行いました。6x6の実装は、3x3、4x4、5x5で正しい答えを得るので、それが機能すると信頼しています（偶然にすべてを得るのは非常に驚くべきことです）。それでも興味があるなら、gitリポジトリを確認してください。

7

もしそれがあなたなら、知らせてください！