C++ Negamax alpha-beta 错误截止？

Question

我一直在使用 negamax 玩连连四。我注意到的是，如果我添加 alpha-beta，它有时会给出“错误”的结果，因为在进行失败操作时，我认为它不应该与我正在搜索的深度相匹配。如果我删除 alpha-beta，它会按照预期的方式播放。 alpha-beta 能否切断一些实际可行的分支(尤其是在深度有限的情况下)？以下是以防万一的代码:

int negamax(const GameState& state, int depth, int alpha, int beta, int color)
{
    //depth end reached? or we actually hit a win/lose condition?
    if (depth == 0 || state.points != 0)
    {

        return color*state.points;
    }

    //get successors and optimize the ordering/trim maybe too
    std::vector<GameState> childStates;
    state.generate_successors(childStates);
    state.order_successors(childStates);

    //no possible moves - then it's a terminal state
    if (childStates.empty())
    {
        return color*state.points;
    }
    int bestValue = -extremePoints;
    int v;
    for (GameState& child : childStates)
    {
        v = -negamax(child, depth - 1, -beta, -alpha, -color);
        bestValue = std::max(bestValue, v);
        alpha = std::max(alpha, v);
        if (alpha >= beta)
            break;
    }
    return bestValue;
}

Answer 1

Can the alpha-beta cut off some actually viable branches(especially when the depth is limited)?

Alpha-Beta 算法返回与 Minimax 相同的结果(根节点和游戏线的评估)但(通常)在更快的时间内修剪掉不可能影响最终决策的分支(您可以阅读 H. Fuller - 1973 年在 Analysis of the alpha-beta pruning algorithm by Samuel 中的证明。

您正在使用 Negamax Alpha-Beta 剪枝，但它只是简化算法实现的一种变体。

还有 fail-soft 噱头不会改变情况。

当然，浅层搜索可能会选出错误的着法，但同样适用于 Minimax。

所以一定是实现错误。

显示的代码对我来说似乎是正确的。你应该检查:

1. 在根节点调用 negamax 的方式。它应该是这样的:

    negamax(rootState, depth, −extremePoints, +extremePoints, color)
   

   alpha/beta 是可能的最低值和最高值。

   如果您为 alpha/beta 使用不同的初始值(例如 aspiration windows )并且真实分数在初始窗口之外，您需要重新搜索.

2. 您如何收集/存储/管理/传播主要变化的 Action (缺少相关代码)。像 PV 表这样的技术与 bestValue 的变化有关。如果这是问题所在，您应该获得相同的位置得分(相对于 Minimax)，但最佳移动不同。