Alpha-beta prunning with transposition table,迭代加深

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
   

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

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

   当搜索失败率很低时，就没有“最佳举措”。我们唯一知道的是，没有任何移动足以产生大于 的分数alpha。没有办法猜测哪个动作是最好的。

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

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

   您应该清除移动之间的换位表（或者，最好使用附加entry.age字段）。