使用转置表进行Alpha-beta修剪，迭代加深

Question

我正在尝试使用转置表来实现alpha-beta min-max prunning增强功能。我用这个伪代码作为参考：

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字段）。