带转置表的 Alpha-beta 剪枝，迭代深化 [英] Alpha-beta prunning with transposition table, iterative deepening

问题描述

我正在尝试实现通过转置表增强的 alpha-beta min-max 剪枝.我使用这个伪代码作为参考:

I'm trying to implement alpha-beta min-max prunning enhanced with transposition tables. I use this pseudocode as reference:

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(= 条目与叶级的距离更大或相等时才使用条目).这在上面的伪代码中没有显示，也没有在那里讨论，我想确保我理解正确.

1. I belive that I should store depth (=distance to leaf level) with each saved transposition table entry and use entry only when entry.depth>=currentDepth (= entry is more or equal distant from leaves level). That is not shown in above pseudocode and is not discussed there, I wanted to make sure I understand that correctly.

我想为每个位置存储最佳移动，以便在搜索停止后将其用于移动排序和提取最佳移动.在纯 min-max 中，很明显哪个移动是最好的，但是在使用 alpha-beta 截止值进行迭代时，哪个移动是最好的?我可以假设给定位置的最佳走法是循环结束时找到的最佳走法(有中断或没有中断)?

I would like to store best move for each position to use it for move ordering AND extracting best move after the search stops. In pure min-max it's obvious which move is the best, but which move is the best when iterating with alpha-beta cutoffs? Can I assume that the best move for given position is the best move found when the loop ends (with cut-off or without)?

在迭代深化方案中执行此算法时 - 我应该在每次深度增加之前清除换位表吗?我认为不是，我希望您使用上次迭代中的存储位置，但我不确定这些信息是否足以进行更深入的搜索(应该在检查表条目深度时使用)?

When executing this algorithm in iterative deepening scheme - should I clear transposition table before each depth increase? I think not, I'd like tu use stored position from previous iteration, but I'm not sure if the information is adequate for deeper searches (It should be when checking table entry depth)?

推荐答案

1. 你说得对.entry.depth 存储转置表条目中信息所基于的层数.因此，您只能在 entry.depth >= remaining_depth 时使用这些信息.

1. You're right. entry.depth stores the number of plies the information in the transposition table entry are based on. So you can use those information only when entry.depth >= remaining_depth.

逻辑是我们不想使用比正常"搜索弱的结果.

The logic is that we don't want to use a result weaker than the "normal" search.

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

Sometimes, for debugging purpose, the condition is changed to:

entry.depth == remaining_depth

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

this avoids some search instabilities. Anyway it doesn't guarantee the same result of a search without transposition table.

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

There isn't always a best move to store.

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

When the search fails low, there isn't a "best move". The only thing we know is that no move is good enough to produce a score bigger than alpha. There is no way to guess which move is best.

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

So you should store a move in the hash table only for lower bounds (beta-cutoff i.e. a refutation move) and exact scores (PV node).

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

No, you shouldn't. With iterative deepening the same position is reached again and again and the transposition table can speed up the search.

您应该清除移动之间的换位表(或者，最好使用额外的条目.年龄 字段).

You should clear the transposition table between moves (or, better, use an additional entry.age field).

这篇关于带转置表的 Alpha-beta 剪枝，迭代深化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！