带换位表的α-β剪枝，迭代深化

Question

我正在尝试用换位表实现增强的α-β-最小-最大修剪。我使用这个伪代码作为参考：

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;

这个算法有三个问题:

>

我相信我应该在每个保存的换位表条目中存储深度（=到叶级的距离），并且仅在 entry.depth 时才使用条目

我想存储每个位置的最佳移动，以便在搜索停止后使用它进行移动排序和提取最佳移动。在纯最小值-最大值中，哪一步是最好的是显而易见的，但是当迭代α-β截止点时，哪一步是最好的呢？我可以假设给定位置的最佳移动是循环结束时找到的最佳移动(有或没有截止)吗？

当在迭代深化方案中执行此算法时，我应该在每次深度增加之前清除换位表吗？我想不是，我想使用上一次迭代中的存储位置，但我不确定信息是否足以进行更深入的搜索（应该是在检查表条目深度时）？

Answer 1

>

你是对的。entry.depth存储了换位表条目中信息所基于的层数。因此，您只能在entry.depth

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

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

entry.depth == remaining_depth

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

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

当搜索失败时，没有“最佳移动”。我们唯一知道的是，没有一个动作足够好，可以产生比alpha更大的分数。没有办法猜测哪一步是最好的。

因此，您应该将移动存储在哈希表中，仅用于较低的边界（β截止值，即反驳移动）和精确的分数（PV节点）。

不，你不应该。通过迭代深化，一次又一次地到达相同的位置，换位表可以加快搜索速度。

您应该在移动之间清除转置表（或者，更好的是使用额外的 entry.age 字段）。