分支因子與節點計數
遊戲樹對從起始位置開始的所有可能動作序列進行建模。每個節點表示一個棋盤狀態。每條邊表示一個合法動作。樹的結構決定了搜尋是否仍然可行。
關鍵參數
分支因子 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 個節點。
Alpha-Beta 剪枝：縮減指數
Alpha-beta 剪枝消除了不會影響 minimax 結果的子樹。關鍵洞察：如果你已經知道一個分支給出值 V，你可以剪枝任何值明確低於 V（對於最大化玩家）或高於 V（對於最小化玩家）的兄弟分支。
最佳情況幾何
在最優動作排序下（最好的動作首先搜尋），alpha-beta 將有效分支因子從 b 縮減到 √b。對於相同的節點預算，搜尋深度有效翻倍：
完整搜尋：b^d 個節點
Alpha-beta 最佳情況：b^(d/2) 個節點
例子：b=35，d=6。完整：35^6 ≈ 1.84 × 10^9。Alpha-beta：35^3 = 42,875。縮減因子：~43,000。
實際上，動作排序不完美。典型縮減：b^(d×0.75) — 等效分支因子 ≈ b^0.75。
中心-角落對偶性
Hamming 指出 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(position) = w_1 × f_1 + w_2 × f_2 + ... + w_n × f_n
對於 4×4×4 井字遊戲：特徵可能包括控制的開放線、高線計數方格中的位置、威脅的叉。對於國際象棋：物質計數、中心控制、王的安全、兵的結構。
這是特徵空間中的線性函數 — ℝ^n 中的超平面。兩個具有相同特徵值的位置無論所有其他差異如何都得到相同的評估。評估函數的幾何確定程式「看到」什麼。
Samuel 的跳棋程式通過調整權重向量 w 而改進 — 線性評估函數空間中的梯度下降。
幾何與形式化的邊界
遊戲樹有清晰的幾何結構：深度 d 時的指數增長，通過 alpha-beta 縮減為 b^(d/2)，通過限制在高價值位置（熱點將有效 b 縮減）進一步縮減。評估函數在特徵空間中定義一個超平面。
所有這一切都是清晰、精確、形式上完整的。它描述了遊戲程式問題的中心 — 數學結構提供清晰指導的區域。
邊界 — 何時從規則應用切換到探索，何時用戰術機會交換位置優勢，如何識別超越評估函數的新興模式 — 抵抗這種形式化。Hamming 的隱知識生活在那條邊界。
幾何讓你計算你能承受多少搜尋。它不告訴你要看什麼。