使用转置表进行 alpha-beta 修剪

Question

我不明白为什么 table 条目的标志会按原样使用。考虑例如Negamax with alpha-beta pruning and transposition tables 的伪代码并专注于 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

没关系。如果条目包含确切值的下限，我们会尝试从左侧缩小 window 等

(* 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)

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

从我的测试以及每个人都使用该版本的事实来看，我的逻辑肯定是错误的。但是我不明白为什么。

Answer 1

转念一想，这个问题微不足道:)

确实，如果子节点值太好导致beta-cutoff（value ≥ β），这意味着父节点至少有移动与 value 一样好，但也许还有一些更好的举措。所以 value 是确切节点值的 LOWERBOUND。

value ≤ alphaOrig 表示所有动作都比 alphaOrig 差。这意味着 value 是所有移动结果的上限。

Lower 和 Upper 是当前节点值的边界，而不是根节点，正如我暗示的那样。

使用转置表进行 alpha-beta 修剪

Alpha-beta pruning with transposition tables

language-agnostic

algorithm

artifactory

alpha-beta-pruning

negamax