带转置的 Alpha-beta 剪枝 table,迭代加深
Alpha-beta prunning with transposition table, iterative deepening
我正在尝试实施通过转置 tables 增强的 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;
这个算法的三个问题:
我相信我应该在每个保存的转置 table 条目中存储深度(=到叶级的距离),并且仅在 entry.depth>=currentDepth(= 条目离叶层的距离更远或相等)。这在上面的伪代码中没有显示,也没有在那里讨论,我想确保我理解正确。
我想存储每个位置的最佳着手,以便在搜索停止后将其用于着手排序并提取最佳着手。在纯粹的 min-max 中,哪一步最好是显而易见的,但是当使用 alpha-beta 截止值迭代时,哪一步是最好的?我可以假设给定位置的最佳移动是循环结束时找到的最佳移动(有或没有切断)吗?
在迭代加深方案中执行此算法时 - 我是否应该在每次深度增加之前清除转置 table?我不这么认为,我想使用之前迭代的存储位置,但我不确定这些信息是否足以进行更深入的搜索(应该在检查 table 进入深度时使用)?
你是对的。 entry.depth
存储换位 table 条目中的信息所基于的层数。因此,您只能在 entry.depth >= remaining_depth
.
时使用这些信息
逻辑是我们不想使用比 "normal" 搜索弱的结果。
有时,为了调试目的,将条件更改为:
entry.depth == remaining_depth
这避免了一些search instabilities。无论如何,它不能保证没有换位的搜索结果相同 table.
并不总是最好的存储方式。
当搜索失败时,没有"best move"。我们唯一知道的是,没有任何一步可以产生大于 alpha
的分数。无法猜测哪一步是最好的。
所以你应该在散列中存储移动 table 仅用于下限(beta-cutoff 即反驳移动)和精确分数(PV 节点)。
不,你不应该。随着迭代加深,一次又一次到达相同的位置,换位table可以加快搜索速度。
您应该清除移动之间的换位 table(或者,更好的是,使用额外的 entry.age
字段)。
我正在尝试实施通过转置 tables 增强的 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;
这个算法的三个问题:
我相信我应该在每个保存的转置 table 条目中存储深度(=到叶级的距离),并且仅在 entry.depth>=currentDepth(= 条目离叶层的距离更远或相等)。这在上面的伪代码中没有显示,也没有在那里讨论,我想确保我理解正确。
我想存储每个位置的最佳着手,以便在搜索停止后将其用于着手排序并提取最佳着手。在纯粹的 min-max 中,哪一步最好是显而易见的,但是当使用 alpha-beta 截止值迭代时,哪一步是最好的?我可以假设给定位置的最佳移动是循环结束时找到的最佳移动(有或没有切断)吗?
在迭代加深方案中执行此算法时 - 我是否应该在每次深度增加之前清除转置 table?我不这么认为,我想使用之前迭代的存储位置,但我不确定这些信息是否足以进行更深入的搜索(应该在检查 table 进入深度时使用)?
你是对的。
时使用这些信息entry.depth
存储换位 table 条目中的信息所基于的层数。因此,您只能在entry.depth >= remaining_depth
.逻辑是我们不想使用比 "normal" 搜索弱的结果。
有时,为了调试目的,将条件更改为:
entry.depth == remaining_depth
这避免了一些search instabilities。无论如何,它不能保证没有换位的搜索结果相同 table.
并不总是最好的存储方式。
当搜索失败时,没有"best move"。我们唯一知道的是,没有任何一步可以产生大于
alpha
的分数。无法猜测哪一步是最好的。所以你应该在散列中存储移动 table 仅用于下限(beta-cutoff 即反驳移动)和精确分数(PV 节点)。
不,你不应该。随着迭代加深,一次又一次到达相同的位置,换位table可以加快搜索速度。
您应该清除移动之间的换位 table(或者,更好的是,使用额外的
entry.age
字段)。