我已经实现了一个带置换表的Alpha-Beta搜索算法。

我关于在表中存储截断值的想法是否正确？

特别是，当表命中时，我返回截断值的方案是否正确？（同样，存储它们的方式是否正确？）我的实现似乎与这个相冲突，但直觉上我觉得我的方式是正确的。

另外，我的算法从未存储带有at_most标志的条目。我应该在什么时候存储这些条目呢？

以下是展示主要思想的简化代码：

int ab(board *b, int alpha, int beta, int ply) {    evaluation *stored = tt_get(b);    if (entryExists(stored) && stored->depth >= ply) {        if (stored->type == at_least) { // 下界            if (stored->score >= beta) return beta;        } else if (stored->type == at_most) { // 上界            if (stored->score <= alpha) return alpha;        } else { // 精确值            if (stored->score >= beta) return beta; // 遵循严格截断            if (stored->score < alpha) return alpha; // Alpha截断            return stored->score;        }    }       if (ply == 0) return quiesce(b, alpha, beta, ply);    int num_children = 0;    move chosen_move = no_move;    move *moves = board_moves(b, &num_children);    int localbest = NEG_INFINITY;    for (int i = 0; i < num_children; i++) {        apply(b, moves[i]);        int score = -ab(b, -beta, -alpha, ply - 1);        unapply(b, moves[i]);        if (score >= beta) {            tt_put(b, (evaluation){moves[i], score, at_least, ply});            return beta; // 严格截断        }        if (score >= localbest) {            localbest = score;            chosen_move = moves[i];            if (score > alpha) alpha = score;        }    }    tt_put(b, (evaluation){chosen_move, alpha, exact, ply});    return alpha;}

回答：

我的实现似乎与这个相冲突

我认为置换表查找的代码是正确的。它大致相当于维基百科上的代码。

// 使用你的符号/变量名重写的维基百科代码if (entryExists(stored) && stored->depth >= ply){  if (stored->type == at_least)    alpha = max(alpha, stored->score);  else if (stored->type == at_most)    beta = min(beta, stored->score);  else if (stored->type == exact)    return stored->score;  if (alpha >= beta)    return stored->score;}

这相当于（检查if (alpha >= beta)已移动到每个节点类型内部）：

if (entryExists(stored) && stored->depth >= ply){  if (stored->type == at_least)  {    alpha = max(alpha, stored->score);    if (alpha >= beta)  return stored->score;  }  else if (stored->type == at_most)  {    beta = min(beta, stored->score);    if (alpha >= beta)  return stored->score;  }  else if (stored->type == exact)    return stored->score;}

并且这可以改为：

if (entryExists(stored) && stored->depth >= ply){  if (stored->type == at_least)  {    // if (max(alpha, stored->score) >= beta) ...    if (stored->score >= beta)  return stored->score;  }  else if (stored->type == at_most)  {    // if (min(beta, stored->score) <= alpha) ...    if (stored->score <= alpha)  return stored->score;  }  else if (stored->type == exact)    return stored->score;}

剩下的区别是维基百科使用了软失败优化，而你的代码是经典的Alpha-Beta剪枝（硬失败）。软失败是一个小的改进，但不会改变算法的关键点。

我的算法从未存储带有at_most标志的条目。我应该在什么时候存储这些条目呢？

你存储exact / at_most节点类型的方式存在一个错误。这里你假设节点总是exact类型：

tt_put(b, (evaluation){chosen_move, alpha, exact, ply});

实际上它可能是at_most节点：

if (alpha <= initial_alpha){  // 这里我们没有最佳移动。  tt_put(b, (evaluation){no_move, initial_alpha, at_most, ply});}else   tt_put(b, (evaluation){chosen_move, alpha, exact, ply});