C++ Negamaxα-β错误截止？

Question

我一直在用negamax播放连接四。我注意到的是，如果我添加了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

α-β能切断一些实际可行的分支(尤其是在深度有限的时候)吗？

Alpha-Beta算法返回的结果与Minimax (根节点和播放线上的计算，)相同，但(通常)在较快的时间内，修剪掉不可能影响最终决策的分支(您可以阅读H.Fuller-1973在https://kilthub.cmu.edu/articles/journal_contribution/Analysis_of_the_alpha-beta_pruning_algorithm/6603488中的一个证明)。

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

而且，https://www.chessprogramming.org/Fail-Soft的花招并没有改变这种情况。

当然，在浅层搜索可以挑出不好的移动，但对于Minimax来说也是如此。

所以它必须是一个实现错误。

在我看来，所显示的代码是正确的。你应该检查一下：

1. 在根节点上调用negamax的方式。应该是这样的： 否定(rootState，深度，−极值点，+极值点，颜色) alpha / beta是可能的最低值和最高值。 如果您对alpha / beta使用不同的初始值(例如，https://www.chessprogramming.org/Aspiration_Windows)，并且真正的分数在初始窗口之外，则需要重新搜索。
2. 如何收集/存储/管理/传播主变化的移动(缺少相关代码)。像PV-表这样的技术被链接到bestValue的变化中。如果这是一个问题，你应该得到相同的位置得分(关于Minimax)，但一个不同的最佳移动。

Answer 2

问题是如何在根节点初始化alpha和beta。我也犯了类似的错误，因为我相应地将它们设置为std::numeric_limits<int>::min()和std::numeric_limits<int>::max()，并且在将alpha参数传递给对negamax(... -a_beta, -a_alpha ... )的另一个递归调用时，我通过添加一个减号运算符来否定最小int值，这仍然产生了最小int值！！由于最小值的数学否定超出了“int”数据类型的范围(全范围是：-214748364__8对214748364__7)，我们不能用int表示正的...64__8，所以它回到了负的最小值。

但是，如果将alpha初始化为稍高一点的值(例如std::numeric_limits<int>::min() + 1)，则情况并非如此。