我正在尝试实现使用置换表增强的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;关于这个算法有三个问题：
-
我认为应该在每个保存的置换表条目中存储深度（=到叶子节点的距离），并且只有当条目深度大于或等于当前深度（=条目距离叶子节点的距离更多或相等）时才使用该条目。这在上面的伪代码中没有显示，也没有讨论，我想确认我是否理解正确。
-
我想为每个位置存储最佳移动，以便用于移动排序和在搜索停止后提取最佳移动。在纯极小极大算法中，很明显哪个移动是最佳的，但在使用Alpha-beta剪枝迭代时，哪个移动是最佳的？我可以假设给定位置的最佳移动是循环结束时找到的最佳移动（无论是否有剪枝）吗？
-
在迭代加深方案中执行此算法时，是否应该在每次深度增加前清除置换表？我认为不应该，我想使用前一次迭代存储的位置，但我不确定这些信息是否适合更深的搜索（如果检查表条目深度，应该是合适的）？
回答：
-
你是对的。
entry.depth存储了置换表条目中信息所基于的层数。因此，只有当entry.depth >= remaining_depth时，你才能使用这些信息。逻辑是我们不想使用比“正常”搜索更弱的结果。
有时，为了调试目的，条件会改为：
entry.depth == remaining_depth这可以避免一些搜索不稳定性。无论如何，这并不能保证与没有置换表的搜索结果相同。
-
并不总是有最佳移动可以存储。
当搜索失败低时，没有“最佳移动”。我们唯一知道的是，没有移动能产生大于
alpha的分数。我们无法猜测哪个移动是最佳的。因此，你应该只在下界（beta-cutoff，即反驳移动）和精确分数（PV节点）时在哈希表中存储移动。
-
不，你不应该这样做。在迭代加深中，同一个位置会被反复达到，置换表可以加速搜索。
你应该在移动之间清除置换表（或者更好，使用额外的
entry.age字段）。
