分岐係数 & ノード数
ゲーム木は、開始位置からのあらゆる可能な手の列をモデル化します。各ノードはボード状態を表します。各エッジは1つの合法的な手を表します。木の構造は、探索が実行可能なままであるかどうかを決定します。
主要パラメータ
分岐係数 b: 典型的な位置で利用可能な合法的な手の数。
深さ d: 先読みするプライ(半手)の数。
深さ d でのノード数: b^d
全深さでの合計ノード: 1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
b & d が大きい場合、合計 ≈ b^d（葉レベルが支配的）。
4×4×4 三目並べ
完全なゲーム木: b ≈ 64（合法的なマス）、d = 64（合計手数）。完全なノード数 ≈ 64^64 ≈ 10^115。観測可能な宇宙には約 10^80 個の原子が含まれます。力ずくの探索は物理的に不可能です。
木のサイズ計算
チェスはより現実的な数値を提供します。平均分岐係数 b ≈ 35。6プライ探索（各側 3 手）には約 35^6 ノードが必要です。
アルファベータ枝狩り: 指数の削減
アルファベータ枝狩りは、ミニマックス結果に影響を与えられない部分木を削除します。重要な洞察: すでに 1 つのブランチが値 V を与えることを知っているなら、兄弟ブランチで値がおそらく V を下回ると証明されるもの（最大化プレイヤーの場合）または V を上回ると証明されるもの（最小化プレイヤーの場合）を枝狩りできます。
最適ケース幾何学
最適な手の順序（最高の手を最初に探索）では、アルファベータは有効分岐係数を b から √b に削減します。探索深さは同じノード予算で効果的に倍になります:
完全な探索: b^d ノード
アルファベータ最適ケース: b^(d/2) ノード
例: b=35、d=6。完全: 35^6 ≈ 1.84 × 10^9。アルファベータ: 35^3 = 42,875。削減係数: ~43,000。
実際には、手の順序は不完全です。典型的な削減: b^(d×0.75) — 有効分岐係数 ≈ b^0.75。
中心-コーナー双対性
ハミングは 4×4×4 キューブの幾何学的双対性を指摘します: 8 つのコーナー位置を 8 つの中心位置（内側の 2×2×2 キューブ）に送り、その逆も同様で、すべての 76 の勝利ラインを保存する反転が存在します。
位置を通過するラインの数
4×4×4 キューブでは、位置は通過する勝利ラインの数が異なります:
コーナー位置: 各 7 ライン（4 つの面対角線、2 つのエッジ線、1 つの空間対角線）
エッジセンター位置: 各 4 ライン
フェイスセンター位置: 各 6 ライン
ボディセンター位置（内側の 2×2×2）: 各 7 ライン
双対性はコーナー（7 ライン）をボディセンター（7 ライン）にマップします。両方のセットは「ホットスポット」を形成します。
ホットスポットが幾何学的に重要な理由
プレイヤーが高いライン数の位置をより多く制御すると、より多くの潜在的な勝利ラインを制御します。これは直接的な幾何学的議論です: ラインカバレッジの最大化は探索なしで手の選択をガイドします。
評価関数
すべてのゲームプレイングプログラムには評価関数が必要です: ボード状態を数値にマップする関数（正 = 最大化プレイヤーに良い、負 = 最小化プレイヤーに良い）。評価関数は探索木の葉での境界条件を提供します。
線形評価関数
線形評価関数は、位置の各特徴 f_i に重み w_i を割り当てます:
E(位置) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
4×4×4 三目並べの場合: 特徴には、制御されたオープンラインの数、高いライン数の四角形での位置、脅かされたフォークが含まれる可能性があります。チェスの場合: 材料カウント、中央制御、キング安全、ポーン構造。
これは機能空間の線形関数です — ℝ^n の超平面。同じ機能値を持つ 2 つの位置は、他のすべての違いに関係なく、同じ評価を取得します。評価関数の幾何学は、プログラムが「見る」ものを決定します。
サミュエルのチェッカープログラムは重みベクトル w を調整することにより改善されました — 線形評価関数の空間での勾配降下。
幾何学 & 形式化の境界
ゲーム木は、クリーンな幾何構造を持っています: 深さ d での指数成長、アルファベータによる b^(d/2) への削減、高値位置 (ホットスポット削減有効 b) への制限によるさらなる削減。評価関数は機能空間の超平面を定義します。
これはすべてクリーン、正確、形式的に完全です。ゲームプレイングの問題の 中央 — 数学的構造が明確なガイダンスを提供する領域を説明します。
境界 — ルール適用から探索への切り替えの時期、位置利点を戦術的な機会のために取引する時期、評価関数を超えて浮上パターンを認識する方法 — この形式化に抵抗します。ハミングの暗黙的な知識がその境界に住んでいます。
幾何学により、あなたが負担できる検索量を計算できます。あなたが何を探すべきかは教えていません。