algorithm - 带转置表的 Alpha-beta 剪枝，迭代加深

Question

我正在尝试实现通过转置表增强的 alpha-beta 最小-最大剪枝。我使用这个伪代码作为引用:

http://people.csail.mit.edu/plaat/mtdf.html#abmem

function AlphaBetaWithMemory(n : node_type; alpha , beta , d : integer) : integer;
    if retrieve(n) == OK then /* Transposition table lookup */
        if n.lowerbound >= beta then return n.lowerbound;
        if n.upperbound <= alpha then return n.upperbound;
        alpha := max(alpha, n.lowerbound);
        beta := min(beta, n.upperbound);
    if d == 0 then g := evaluate(n); /* leaf node */
    else if n == MAXNODE then
        g := -INFINITY; a := alpha; /* save original alpha value */
        c := firstchild(n);
        while (g < beta) and (c != NOCHILD) do
            g := max(g, AlphaBetaWithMemory(c, a, beta, d - 1));
            a := max(a, g);
            c := nextbrother(c);
    else /* n is a MINNODE */
        g := +INFINITY; b := beta; /* save original beta value */
        c := firstchild(n);
        while (g > alpha) and (c != NOCHILD) do
            g := min(g, AlphaBetaWithMemory(c, alpha, b, d - 1));
            b := min(b, g);
            c := nextbrother(c);

    if g <= alpha then 
        n.upperbound := g; 
        store n.upperbound;
    if g >  alpha and g < beta then
        n.lowerbound := g; 
        n.upperbound := g; 
        store n.lowerbound, n.upperbound;
    if g >= beta then 
        n.lowerbound := g; 
        store n.lowerbound;
return g;

这个算法的三个问题:

1. 我相信我应该为每个已保存的换位表条目存储深度(=到叶层的距离)，并且仅当 entry.depth>=currentDepth(=条目与叶层的距离更远或相等)时才使用条目。这在上面的伪代码中没有显示，也没有在那里讨论，我想确保我理解正确。

2. 我想存储每个位置的最佳着法，以便在搜索停止后将其用于着法排序和提取最佳着法。在纯粹的 min-max 中，哪一步最好是显而易见的，但是当使用 alpha-beta 截止值迭代时，哪一步是最好的？我可以假设给定位置的最佳着法是循环结束时找到的最佳着法(有或没有截止)吗？

3. 在迭代加深方案中执行此算法时 - 我是否应该在每次深度增加之前清除转置表？我不这么认为，我想使用上一次迭代的存储位置，但我不确定这些信息是否足以进行更深入的搜索(应该在检查表条目深度时)？

Answer 1

1. 你是对的。 entry.depth 存储换位表条目中的信息所基于的层数。因此，您只能在 entry.depth >= remaining_depth 时使用这些信息。

   逻辑是我们不想使用比“正常”搜索弱的结果。

   有时，出于调试目的，条件会更改为:

   entry.depth == remaining_depth
   

   这避免了一些 search instabilities .无论如何，它不能保证没有换位表的搜索结果相同。

2. 并不总是有最好的存储方式。

   当搜索失败时，就没有“最佳着法”。我们唯一知道的是，没有任何一步可以产生比 alpha 更大的分数。无法猜测哪一步是最好的。

   因此，您应该仅在哈希表中存储下限(beta 截止，即反驳移动)和精确分数(PV 节点)的移动。

3. 不，你不应该。随着迭代的加深，一次又一次到达相同的位置，转置表可以加快搜索速度。

   您应该清除移动之间的换位表(或者，更好的是，使用额外的 entry.age 字段)。