分支因子与节点计数
游戏树模拟从起始位置出发的所有可能移动序列。每个节点表示一个棋盘状态。每条边表示一个合法移动。树的结构决定了搜索是否可行。
关键参数
分支因子 b：典型位置可用合法移动的数量。
深度 d：要向前搜索的半步（half-moves）数量。
深度 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(位置) = 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 的隐性知识位于该边界。
几何让你计算你能承受多少搜索。它不告诉你要寻找什么。