分支因子与节点数
一个游戏树模型了从起始位置的所有可能的移动序列。每个节点表示一个棋盘状态。每个边表示一个合法的移动。树的结构决定了搜索是否可行。
关键参数
分支因子 b：在一个典型位置可用的合法移动数量。
深度 d：向前搜索的半移动数（半棋局）。
深度为 d 的节点数：b^d
在所有深度的总节点数：1 + b + b² + ... + b^d = (b^(d+1) − 1) / (b − 1)
对于大 b 和 d，总数约为 b^d（由叶层主导）。
4×4×4 Tic-Tac-Toe
整个游戏树：b ≈ 64（合法的方块），d = 64（总的移动）。全节点数约为 64^64 ≈ 10^115。可观察到的宇宙包含大约 10^80 个原子。盲目搜索是物理上不可能的。
计算树大小
国际象棋提供了更实际的数字。平均分支因子 b ≈ 35。一个 6-ply 搜索（每边三次移动）需要大约 35^6 个节点。
Alpha-Beta 剪枝：减少指数
Alpha-beta 剪枝消除了不能影响最小最大结果的子树。关键见解：如果你已经知道一个分支的值为 V，你可以剪掉任何一个同级分支，whose value provably falls below V (for the maximizing player) or above V (for the minimizing player).
最佳情况几何
在最佳移动排序（搜索最先的最佳移动）下，alpha-beta 将有效分支因子从 b 减少到 √b。搜索深度实际上是 doubled for the same node budget:
全搜索：b^d nodes
Alpha-beta 最佳情况：b^(d/2) nodes
例子：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。
中心-角落对偶性
汉明注意到4×4×4立方体存在几何对偶性：存在一个将8个角位置映射到8个中心位置（内层2×2×2立方体）并且 vice versa 的逆变换，同时保留所有76条获胜线。
计算通过某个位置的线数
在4×4×4立方体中，位置的差异在于通过它们有多少条获胜线:
角位置：每个有7条线（4条面对角线，2条边线，1条空间对角线）
边-中心位置：每个有4条线
面-中心位置：每个有6条线
体-中心位置（内层2×2×2）：每个有7条线
对偶性将角位置（7条线）映射到体-中心位置（7条线）。这两个集合都形成了‘热点’。
为什么热点在几何上重要
控制更多高线数位置的玩家控制更多潜在获胜线。这个是直接的几何论证：线覆盖最大化指导移动选择，没有任何搜索。
评估函数
每个游戏AI程序都需要一个评估函数：一个将棋盘状态映射到数字值的函数（正值表示好于最大化玩家，负值表示好于最小化玩家）。评估函数提供了搜索树叶节点的边界条件。
线性评估函数
线性评估函数为每个特征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）。评估函数在特征空间中定义了一个超平面。
所有这些都非常清晰、精确、形式上完整。它描述了游戏玩法问题的中心——数学结构提供的明确指南所在的区域。
在边界处，switch from rule-application to exploration（从规则应用转向探索），when to trade positional advantage for tactical opportunity（何时进行战术机会与战位优势的交换），how to recognize emergent patterns beyond the evaluation function（如何识别评估函数之外的新兴模式）——这些问题难以用这种形式化来解决。Hamming 的潜在知识生活在边界上。
几何让你计算出可以承受的搜索量。它并不能告诉你应该寻找什么。