3

我正在使用 alpha-beta 修剪和在 MTD(f) 算法内部调用的转置表向我的国际象棋引擎添加静止搜索。在我的主要搜索中，在达到 depth=0（叶节点）后，我调用 Quiescence 搜索，它被实现为没有转置表的简单 alpha beta 修剪（因为测试表明，没有 TT，搜索只捕获工作得更快）

我注意到有关此主题的伪代码中未涵盖的内容：当我在主搜索中处于 depth=0（叶）并且我调用静止搜索函数来获得节点评估时，我认为我也应该获得评估类型：精确，阿尔法或贝塔：

... 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 搜索是否在数学上是正确的，所以我也希望能确认这个主题。

4

2 回答 2

1

正如我所说，很少使用静止搜索的 TT 条目。由于访问主存的成本很高，因此不尝试 TT 命中并计算位置会更快。如果您在没有溢出列表的情况下实现哈希表并覆盖哈希条目，那么当在“更好”深度中找到新条目时，您肯定只会覆盖现有条目。因此，当您开始填充哈希表时，没有快速存储 TT 条目的选项，因为有更好的条目没有“超过”最大深度，比如这个静止条目。

但是，如果您想将静止节点写入 TT 表，您可以使用“正常”标志精确、上限和下限。当没有 alpha-或 beta-cut 时，您可以使用标志“exact”，因为在相同位置开始的新静止搜索将返回相同的值。

于 2015-07-22T14:35:15.453 回答
0

已经存在防止以错误方式使用静止 TT 值的保护措施。TT 条目存储找到该值的深度，因此仅当搜索处于相同或更深的搜索深度时才会使用它。正如您所说，TT 不会在离开节点上使用，因此无论该值是否来自静默搜索，它都不会造成伤害。

于 2015-05-13T13:56:13.287 回答