0

我不明白为什么按原样使用表条目的标志。例如，考虑带有 alpha-beta 修剪和转置表的 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

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

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

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

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

4

1 回答 1

0

第二个想法，这个问题是微不足道的:)

实际上，如果子节点的值太好而导致 beta 截止（值 ≥ β），这意味着父节点的移动至少与value一样好，但也许还有一些更好的移动。因此，该值是确切节点值的 LOWERBOUND。

value ≤ alphaOrig意味着所有动作都比alphaOrig差。这意味着价值是所有行动结果的上限。

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

于 2020-08-31T20:30:35.017 回答