WeakC4：発現するオブジェクトの蒸留

2swap
Connect 4 の解答はここでご覧ください。

WeakC4 は、検索（search）を伴わずに知識量を最小限にした 7x6 サイズの Connect 4 に対する解法です。これは、完全な手応えを示すための言語を特定し、その言語で記述されるノードのみが葉となるような小さなオープニング木を見出すことで構築されました。

本ウェブサイトでは、既存の強力・弱力解法（例：Fhourstones）とは根本的に異なる、最適な初回プレイヤーの Connect 4 手順に対する形式的な戦略を提供します。

• 極めて少ない情報量：圧縮前の対称ペアを重複除去する前であっても、約 150 キロバイト程度の記憶容量で収まる（以下に示す）ほど情報が少ない。
• 実行時検索不使用：移動選択のために O(wh) の時間計算量で動作し、実行時に検索を行う必要がない。
• 可視化とリアルタイムレンダリング：全体の戦略を可視化し、リアルタイムでの描画が可能である。
• 困難な局面の可視的検証：Connect 4 プレイヤーが既に熟知しているような特に困難なオープニング、ライン、およびバリエーションの存在を視覚的に示し、それを確認するものである。

弱解法と強解法

このウェブサイトはゲーム「Connect Four」に対する弱解法（weak solution）を示しています。端的に言えば、これは初回プレイヤーが弱解法の提案に従ってプレイすれば勝利を保証する十分な情報を提供しますが、任意の局面については何のコメントも含みません。（もしそうであればそれは強解法と呼ぶべきです）。

動機付けの例として：プレイヤー 1（以降「赤」と呼ぶ）は、最初の移動で中央列を占め、その後弱解法の提案に従うことで勝利しますが、最初に配置するトークンが別の場所にある場合には必ずしも勝利を保証されません。弱解法には他の列で何が起きるかは一切含まれていません。赤の立場からすれば、そのような分岐の情報は冗長であり、学習する価値がないからです（なぜならそれらは良い手ではないため）。

一方、強解法は各局面に対するゲーム理論的な値を含んでいるのに対し、この弱解法は赤が勝利を保証するために必要な情報のみを含み、他の局面については一切含まない点が異なります。

グラフ理論の用語で言えば、これらの解法タイプをグラフとして考えれば、強解法は「完全なゲーム木」に対応し、弱解法は「一部の重要なノードごとの制約条件（後述）の下で閉じた部分グラフ」に対応します。

Connect 4 はもはや強解されているため、一見すると弱解法の議論は不要そうに見えるかもしれません。しかし実際には、その逆が一般的に真であると考えられます。弱解法には強解法よりも多くの利点があります：

• 少ないデータフットプリント：完璧にプレイするために「暗記」すべき情報は大幅に減ります。
• 根本構造の浮き彫り：弱解法はゲームの構造的な理解に基づいており、その構造を露呈させます。
• 可視化の柔軟性：強解法（圧縮せずに 14TB、圧縮しても 350GB）が可視化できないのに対し、弱解法はある意味で可視化可能です。

強解法とは、構造的な理解を求めない汎用的・素朴なゲーム解決アプローチです。一方、どの勝利分岐を含み、どの分岐を排除するかという選択においてさえ、創造的な余地を残す弱解法は、対象となるゲームの構造的洞察を表現するために用いることができます。

「良い」弱解法

チェス大会に臨み完璧にプレイしたいと仮定しましょう。選択肢 A は何も準備せずに会場に現れ、席についた上であらゆる可能な変化を読んでいくアプローチです。選択肢 B 是会場で検索なしで完璧にプレイできるように、各局面のゲーム理論的値を事前に暗記してきたアプローチです。

ある意味では、この 2 つのアプローチは正反対と言えます。A は知識への依存度を抑えつつ計算に過剰に頼り、B は計算への依存度を抑えつつ知識に過剰に頼っています。

しかし別の意味では、両者は非常に似ています。どちらの場合においても、戦略の「データ産品（data product）」は同一であると考えられます。価値を大会前か大会中に計算しようとも、その瞬間には同じ情報量——つまり同じ木、同じ「データ産品」——に達する必要が生じます。両プレイヤーとも実質的にアルファベットータ（alpha-beta）剪定によって導かれる木を構築することになりますが、それは一人が競争中に、もう一人は事前に行うだけの違いです。

より知性のあるプレイヤーが採用するのは X 戦略であり、これは両方のアプローチをバランスさせます。暗記すべき知識量が一定の深さまで増加するにつれて指数関数的に増え、将棋を解読するために必要な計算量も同様に指数関数的に増加するため、ゲームの半分くらいまでを暗記し、残りの部分は計算に頼ることで両方の量を最小化できます。つまり、このプレイヤーは暗記と計算のバランスを最適化することで、処理すべき全データ量を削減するのです。

優れた弱解法

これまで私たちはゲーム木——あるいは「データ産品」——を無秩序で無限のエントロピーを持つオブジェクトとして扱い、それを形式的に接近するには素朴な検索しかないもののように扱ってきました。しかし実際には、人間の直感やヒューリスティック解析を適用する余地は十分にあります。これはゲーム木が情報上冗長である（構造を持っているため圧縮可能である）という証拠です。驚くべきことではありませんが、一貫した規則系（ゲームのルールそのもの）の下で生成されたものは、ある程度の自己相似性を示すことを期待すべきです。

本プロジェクトの設計目標の一つは、リアルタイムの計算 whatsoever に頼らないことにありました。私は完全な解法を可視化したいと考えていたからです。計算ステップが存在することは、実質的に私たちが持解决方案内部に存在する情報を隠してしまうことを意味し、したがって私たちはゲーム木の全体を忠実に可視化することになります。

もし賢く行動すれば、計算ステップを完全に排除できます。

人生において全てには代償があります。簡単な言葉で言えば、それは「非常に深い事前の計算が必要になる」こと——つまり、この膨大なゲーム木内の分岐をどのように提示すべきかを知的に選択するためです。実際、この巨大なゲーム木の疎な（sparse）いくつかの分岐は、完全に規則的でパターンのある継続を持つことがあり、その継続には「簡単なトリック」が存在し、計算も暗記も必要としません。

この事前計算の技術的課題を説明するための動機付けとなるパズルをご覧ください：

これは赤と黄色による指向性ゲーム木で、赤の手順は赤色、黄色の手順は黄色で示されています。「単純なトリック」があるノードには緑色の十字があり、葉ノードとして描かれています。与えられたゲームにおける赤の弱解法となる最小の部分木を見出してみてください。つまり、ご任務は赤の辺を除去し、残りの「赤が移動するべき」ノードのすべてにちょうど一つの outgoing 赤の辺を保つようにすること——黄色の辺は一切切り落とさないという条件付きです。（画像をクリックすると答えが示されます）。

本プロジェクトの根本的課題は以下の二点でした：

• ゲーム木の十分に大きな臨界質量（critical mass）のノードに対して「単純なトリック」を表現する言語を見出すこと、および
• 暗記のための「オープニングブック」木を見出すこと——その葉ノードはすべて上述のような「単純なトリック」を持つもの。

私はこのアプローチが単なる Connect 4 完璧プレイの「戦略」に過ぎず、より重要なのは、Connect 4 ルールから発現する複雑なパターンの構造を持つゲーム木の形を理解するための演習であると考えています。ゲームの本質的な形式を理解していないと、巧妙なトリックを見出したり、それらを記述する言語を発見したり、すべての葉がそのような巧妙なトリックを含む小さな木を見つけることはどう可能でしょうか。「 Reflections（考察）」セクションでさらに触れます。

最小の弱解法

ここには注意すべき微細な点があります。上記のパズルは「最小の弱解法」を求めますが、本プロジェクトはグラフ理論的な最小サイズのグラフを検索するのではなく、「表現するのに必要な情報がより少ない」グラフを探しています。繰り返しのテキストファイルを圧縮するのと似て、ゲーム木が情報冗長性を持っているという事実を利用してグラフのサイズを削減し、グラフ理論的には小さくないまでも情報理論的には小さな解法を導き出します。

Claimeven

これらの「単純なトリック」を表現するための言語全体を定義する前に、動機付けとなる Connect 4 の局面をご覧ください。黄色の番手ですが、赤は既に簡単なトリックを企んでいます。見つけられますか？

このトリックは、赤が黄色とコール・アンド・レスポンス（call-and-response）を行うだけであり、黃色の直前の移動と同じ列に移動します。赤がこのようにすれば、幾何学的なターン後、中央列で勝利できます。黄色の次の動きは何であっても最終的な盤面を可視化できます：

パズルの局面には奇数個の空きスペースを持つ列が単一のみあり、それが赤が勝利に必要な行であったことに注意してください。他のすべての列は偶数個の空きスペースを持っていました。これは重要で、もし複数の列が奇数の空きスペースを持っていたなら、黄色は意図的にその一つを埋め、赤はその移動に追いつけずコール・アンド・レスポンスのパターンを破らされます。

この戦略では赤が 2, 4, 6 の行を埋めるため、Victor Allis は論文「A Knowledge-based Approach of Connect-Four」においてこれを Claimeven と呼称しました。残念ながら、純粋な Claimeven で解決できる局面は Connect 4 には不足しており、さらに一般化する必要があります。

Steady-State Language（定常状態言語）

私がこれらの「単純なトリック」を表現するために採用した言語は「Steady State Diagram（定常状態図）」を使用しており、以下のように見えます：

これは赤が描かれた盤面で示された局面から勝利するまで、どのように続いてプレイすべきかを示す「チートシート」として考えられます。図には、赤の次に何をすべきかを決定するために使用されるグリッド上の注釈が含まれています。赤がプレイしながら図は変化しません。

赤が何をするべきかを決定するには、現在赤が行うことができるすべての合法な移動を検討します。「浮遊する」注釈はすべて無視します。

赤が選択する移動はこの優先順位リストに従って選ばれます：

• 勝利をもたらす移動があればそれを実行する。
• 相手の勝利をもたらす移動をブロックできるならそれを blocks する。
• 「！'(urgent、緊急）」があればそれを行う。
• 「@'(miai)」はちょうど一つしかない場合にのみ行う。
• 「｜'(claimodd)」は奇数の行にある場合のみ（それ以外は無視）、または「・'(claimeven) は偶数の行にある場合のみ。claimeven は空白セルとして表現されており、非常に多く出現するため、claimeven をある種の「デフォルト動作」と考えるのが良い。
• 「+」があればそれを行う。
• 「=」があればそれを行う。
• 「-」を行