带transposition tables的Negamax算法相关问题咨询

前置概念：置换表条目的三类标记含义 #

我们先统一negamax搜索框架下的变量定义：

• 当前节点的真实最优估值为v，代表当前玩家在该局面下能拿到的最好分数
• alpha为当前搜索窗口的下限：当前玩家已经能保证拿到的最低分数
• beta为当前搜索窗口的上限：当前玩家最多可能拿到的最高分数

三类标记对应的含义是：

• EXACT：完整搜索完该节点所有分支后，确认alpha < v < beta，存储的score就是v的精确值
• LOWERBOUND（下界）：搜索过程中发现至少一个走法的得分≥beta，直接触发剪枝，此时可确认v ≥ score，不需要搜索剩余分支
• UPPERBOUND（上界）：搜索完该节点所有分支后，最好的得分仍然≤alpha，此时可确认v ≤ score

问题1：为什么UPPERBOUND节点不存最佳走法，LOWERBOUND反而可以？ #

置换表存储走法的核心目的是后续搜索到相同局面时，优先尝试该走法提升剪枝效率，本质是存储「高质量候选走法」。

• LOWERBOUND触发时，我们已经找到了至少一个走法，它的得分足够高直接触发了剪枝。哪怕还有更好的走法没搜索，这个走法已经被证明是「足够好」的候选，后续优先尝试它能大幅提升剪枝概率，所以完全可以存储。
• UPPERBOUND触发时，我们遍历完所有走法得到的最高得分仍然低于当前搜索窗口的下限，也就是说所有走法都是「不符合要求的差走法」。哪怕你能选出其中相对最好的那个，它本质还是个低效的候选走法，存下来对走法排序、提升剪枝效率没有任何帮助，所以不需要存储。

问题2：为什么相同局面不能直接返回之前存储的取值？ #

核心原因有两个：

2.1 存储的边界值不一定匹配当前搜索窗口 #

置换表存储的大多是边界值而非精确值，只有当边界值能直接满足当前搜索的剪枝判断逻辑时，才能直接返回：

• 如果存储的是EXACT精确值，且搜索深度满足要求，不管当前搜索窗口是什么，都可以直接返回。
• 如果存储的是边界值，只有满足以下两个条件之一才能直接用：
  • 存储的UPPERBOUND值 ≤ 当前搜索的alpha，说明当前节点的真实值肯定低于窗口下限，可以直接返回触发剪枝
  • 存储的LOWERBOUND值 ≥ 当前搜索的beta，说明当前节点的真实值肯定高于窗口上限，可以直接返回触发剪枝
    其余情况都需要重新搜索计算。

举个实际例子：

之前搜索该局面时，搜索窗口是[3, 10]，遍历完所有分支后最高得分为2，因此存储为UPPERBOUND，值为2，确认v ≤ 2。
后续再次搜索到同一局面时，搜索窗口变成了[1, 10]：此时存储的2>当前alpha=1，不满足直接返回的条件，你只知道v ≤ 2，但不知道v到底是小于1还是介于1~2之间。如果v < 1，则可以直接返回剪枝；如果v介于1~2之间，就属于当前搜索窗口的范围内，需要重新搜索得到精确值。因此这种场景下不能直接返回之前存储的2。

2.2 存储值的搜索深度可能不足 #

你存储的是之前某一次搜索深度下的估值，如果当前需要搜索的深度比之前存储的更深，旧的估值精度不足，自然不能直接使用。

内容的提问来源于stack exchange，提问作者NightShade