使用转置表进行α-β修剪

Question

我不明白为什么表条目的标志被原样使用。例如，考虑具有α-β修剪和转置表的Negamax的伪代码，并集中于TT部分。

(* Transposition Table Lookup; node is the lookup key for ttEntry *)
ttEntry := transpositionTableLookup(node)
if ttEntry is valid and ttEntry.depth ≥ depth then
    if ttEntry.flag = EXACT then
        return ttEntry.value
    else if ttEntry.flag = LOWERBOUND then
        α := max(α, ttEntry.value)
    else if ttEntry.flag = UPPERBOUND then
        β := min(β, ttEntry.value)

    if α ≥ β then
        return ttEntry.value

没关系。如果条目包含确切值的下限，我们尝试从左侧缩小窗口，依此类推。

(* Transposition Table Store; node is the lookup key for ttEntry *)
ttEntry.value := value
if value ≤ alphaOrig then
    ttEntry.flag := UPPERBOUND
else if value ≥ β then
    ttEntry.flag := LOWERBOUND
else
    ttEntry.flag := EXACT
ttEntry.depth := depth  
transpositionTableStore(node, ttEntry)

而这部分我不明白。如果值太小，为什么我们设置上限标志？值位于搜索窗口的左侧 - 它小于已知的下限 - alpha。所以看起来值应该是一个下限。

从我的测试和每个人都使用那个版本的事实来看，我肯定是错的。但我不明白为什么。

Answer 1

再一想，这个问题很琐碎:)

事实上，如果子节点值太好而导致β截止(值≥ β)，这意味着父节点具有至少与值一样好的移动，但是可能有一些甚至更好的移动。所以这个值是精确节点值的下界。

value≤alphaOrig表示所有移动都比alphaOrig差。这意味着值是所有移动后果的上界。

下限和上限是当前节点值的边界，而不是根节点，正如我以某种方式暗示的那样。