A positional $\mathbf{\Pi}^0_3$-complete objective

イヴとアダムという二人のプレイヤーが、巨大で無限のマップ上で繰り広げる終わりのない追いかけっこ（タグ）のゲームを想像してみてください。彼らはこのマップの経路に沿ってトークンを動かし、その軌跡に色の付いたステッカーを残していきます。目的はただ永遠に走り続けることではありません。特定のルールを満たす、無限のステッカーのパターンを作り出すことです。もしパターンがルールに合致すれば、イヴの勝ちです。そうでなければ、アダムの勝ちです。これは単なる遊びではありません。コンピュータ科学者が、ソフトウェアが将来どのように振る舞うか（プログラムが最終的にクラッシュするか、行き詰まるか、あるいは完璧に動き続けるか）を検証するために用いる、極めて基本的な手法なのです。

ここでの大きな疑問は、「記憶」についてです。プレイヤーは、今まさに自分がどこにいるかを見るだけで決定を下して勝つことができるのでしょうか？ それとも、ゲームが始まって以来のすべてのステップを記憶しておく必要があるのでしょうか？ 現在の場所だけを見て判断する戦略は「位置的（positional）」または「メモリレス（memoryless）」と呼ばれます。これは最も単純でエレガントな方法です。長い間、多くの複雑なルールにおいては、このような位置的な戦略で勝てるということが知られていました。しかし、知識の地図には奇妙な空白がありました。単純な戦略が可能とされる既知のルールはすべて、特定の「容易な」複雑性のカテゴリーに属していました。しかし、$\Pi^0_3$として知られる、もっとはるかに難しいカテゴリーが存在しました。そこでは、誰もが膨大な記憶が必要だと考えていたのです。果たして、この超難解なカテゴリーの中に、メモリレスで勝つことができるルールは存在するのでしょうか？

この論文は、「はい、存在します」と述べています。著者であるアントニオ・カサレス、ピエール・オルマン、そしてピエール・ヴァンデンホーフェは、SumToInfinityと呼ばれる、数学的に非常に複雑（$\Pi^0_3$-完全）でありながら、驚くほどシンプルにプレイできる特定のゲームルールを発見しました。彼らは、たとえルールがどれほど複雑であっても、プレイヤーは現在の場所を見るだけで常に勝つことができることを証明しました。彼らは単に推測したのではなく、それが真実であることを示すための厳密な数学的証明を構築したのです。

無限和のゲーム

彼らの発見を理解するために、彼らが考案したゲームを見てみましょう。マップは、都市が道路で結ばれた構造をしていると想像してください。すべての道路には、スコアのような数字が付いています。例えば $+5$、$-2$、$+100$ などです。トークンが移動するにつれて、これらの数字を加算していきます。SumToInfinityのルールは単純です。ゲームが永遠に続く中で、合計値がどんどん大きくなり続け、正の無限大へと向かっていく場合、イヴの勝ちとなります。もし合計値が停滞したり、減少したり、あるいは増えも減りもしないまま彷徨ったりする場合、アダムの勝ちとなります。

この論文が出る前、マップが小さく有限であれば、このゲームに単純な戦略で勝てることは分かっていました。しかし、もしマップが（理論的なゲームにおいて許容されるように）無限であった場合、どちらの道に進むべきかを知るために、ゲームの履歴を記憶するスーパーコンピュータのような脳が必要になると誰もが考えていました。著者たちは、これは間違いであることを示しました。無限のマップであっても、イヴは「自分は今どこにいるのか？」と問いかけ、適切な道を選ぶだけで勝つことができるのです。

魔法のマップ（普遍グラフ）

彼らはどのようにしてこれを証明したのでしょうか？ 彼らは単に戦略を探したのではなく、それが存在することを証明するための「魔法のマップ」を構築しました。次のように考えてみてください。ある特定のタイプの迷路が解けることを証明したいとします。あらゆる迷路を一つずつ解こうとする代わりに、そのタイプのあらゆる小さな迷路を内包する、一つの巨大で完璧な「マスター迷路」を構築します。もし、あらゆる小さな迷路がルールを壊すことなくこのマスター迷路の中に折り畳み込めることを示せれば、マスター迷衛はそれらすべてを攻略する秘密を保持していることになります。

著者たちは、このマスターマップ（これを「グラフ」と呼びます）を構築しました。これは少し抽象的です。このマップの「都市」は単なる点ではなく、どんどん長くなっていく数字のリスト（タプル）です。都市間の移動ルールは厳格です。ある都市から別の都市へ移動するには、以下の特定のパターンに従わなければなりません：

1. 数字のリストの長さが、通った道のスコアに応じて変化しなければならない。
2. もし道のスコアが長さの変化と正確に一致する場合、新しいリストの数字は、非常に厳格な順序（辞書式順序のようなもの）において、古いリストよりも「小さく」なければならない。

この構造こそが鍵となります。これは、合計スコアが上がることなしにループ（循環）しようとすると、マップのルールによってそのループを強制的に破らせるように設計されています。スコアが上昇しない限り、同じ場所に留まり続けることはできません。このように構築されているため、このマップは普遍的なガイドとして機能します。もしゲームマップが「SumToInfinity」のルールを満たしていれば、それはこのマスターマップへと写像（マッピング）することができます。そして、このマスターマップは非常に整理されているため、単純なメモリレス戦略が完璧に機能することが分かります。あらゆる勝利可能なゲームは、このマスターマップに写像できるため、そこで機能する単純な戦略もまた有効なのです。

なぜこれが重要なのか

この発見は、複雑性の理解における空白を埋める重要なものです。長年、もしゲームのルールが「難しい」$\Pi^0_3$カテゴリーにあるならば、プレイ自体も複雑にならざるを得ないと私たちは考えてきました。しかし、著者たちは、ルールの複雑さが必ずしも戦略の複雑さを意味するわけではないことを示しました。彼らは、定義するのは数学的に「難しい」が、プレイするのは「簡単」なルールを見つけたのです。

それは、何千ものツメバコや奇妙な形状を持つ、恐ろしく複雑に見える錠前を見つけたのに、実はいつでも使えるたった一つのシンプルな鍵を持っているようなものです。これは、問題の記述がいかに難しいかと、それを解くのがいかに難しいかという関係についての私たちの考え方を変えるものです。この論文は、これが特定のゲームに対する単なる幸運な推測ではなく、どのような規模のゲームマップであっても通用する、論理に基づいた数学的事実であることを証明しています。彼らはコンピュータでシミュレーションを行ったわけでも、単にそうかもしれないと示唆したわけでもありません。どんなに巨大で奇妙なゲームマップであっても、その論理が成立することを証明したのです。

ですから、次にスコアを永遠に上昇させ続けることを目標とするゲームをしているときは、覚えておいてください。たとえルールが不可能に思えるほど複雑に見えても、そこには、目の前に隠された、単純でメモリレスな勝利への道があるかもしれないということを。著者たちはその道を見つけ出し、それがどのように機能するかを私たちに示したのです。