静态搜索 - 处理置换表中的Exact/Alpha/Beta标记

Question

我正在使用alpha-beta剪枝和置换表，在MTD(f)算法内部添加静态搜索到我的国际象棋引擎中。在我的主要搜索中，当达到深度为0（叶节点）时，我会调用Quiescence搜索，这是一个简单的alpha-beta剪枝，没有置换表（因为测试表明仅搜索捕获更快，不需要TT）。我发现在该主题的伪代码中有一些未涵盖的内容：当我在主搜索中递归到深度为0（叶节点）并调用quiescence函数来获得节点评估时，我认为我应该也获取评估类型：精确值、alpha值或beta值：

... beginning of main alpha-beta search, checking node in TT
if (depth == 0)
{
    // calling quiescence search with current alpha beta
    int qresult = QuiescenceAlphaBetaSearch(node, alpha, beta);
    saveInTT(node, qresult.Type, qresult.Value);
} 
else
{
    ... run alpha beta search of node.children
}

在典型的例子中，叶子节点评估在TT中总是以“精确”值存储，但是当节点评估基于alpha-beta搜索通过捕获并且此搜索从不是（-inf，+ inf）的alpha-beta范围开始时，我认为QuiescenceAlphaBetaSearch的结果将不会始终是精确值。如果在TT中存储它，则应使用来自静态搜索返回的标志进行标记，我是正确的吗？

我不确定从主搜索传递当前alpha和beta到Quiescence搜索是否在数学上是正确的，因此我希望在这个问题上得到确认。

- PanJanek

Answer 1

如我所说,静态搜索的置换表项很少使用。由于主存访问代价高昂，不尝试置换表命中并计算位置更快。如果你实现了没有溢出列表且覆盖哈希表项的哈希表，当在“更好”的深度找到新条目时，你肯定只会覆盖现有的条目。因此，当你开始填充哈希表时，很快就没有存储TT条目的选项了，因为有更好的条目，它们的深度与这个静态搜索条目一样。

但是，如果你仍想将静态搜索节点写入TT表中，可以使用“正常”的标志exact、upper-bound和lower-bound。当没有alpha或beta剪枝时，你可以使用“exact”标志，因为在相同的位置开始一个新的静态搜索将返回相同的值。

- TheSlater

Answer 2

已经有一种保护措施来防止错误使用静态TT值。TT条目存储了找到该值的深度，因此只有在搜索深度相同或更深的情况下才会使用它。正如您所说，TT不会在叶子节点处使用，因此无论该值是否来自静态搜索，都不会造成影响。

- TheSlater

---

作为叶节点，我理解为主搜索的末端。在达到一定深度后，会使用当前alpha和beta执行另一个静态搜索。我想将静态搜索的结果存储在置换表中，但我不确定它是否可以被视为精确值。 - PanJanek

@PanJanek，我仍在努力理解你的问题。为什么你不能直接将结果保存到TT中，例如将exact、upper-bound和lower-bound直接保存到TT中？这是所有现代引擎的工作方式。 - ABCD