我在使用负极大值算法（Negamax）玩四子棋游戏时发现，如果我加入alpha-beta剪枝，有时会得到“错误”的结果，即做出我认为在当前搜索深度下不应该做出的输棋走法。如果我去掉alpha-beta剪枝，它就会按预期进行游戏。alpha-beta剪枝会不会剪掉一些实际上可行的分支（特别是在搜索深度有限的情况下）？以防万一，这里是代码：

int negamax(const GameState& state, int depth, int alpha, int beta, int color){    //是否达到深度终点？或者我们实际上达到了胜/负条件？
    if (depth == 0 || state.points != 0)
    {
        return color*state.points;
    }
    //获取后继状态并优化排序/可能需要修剪
    std::vector<GameState> childStates;
    state.generate_successors(childStates);
    state.order_successors(childStates);
    //没有可能的移动 - 那么它是一个终止状态
    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;
}

回答：

alpha-beta剪枝会不会剪掉一些实际上可行的分支（特别是在搜索深度有限的情况下）？

Alpha-Beta算法返回的结果与Minimax算法相同（根节点的评估和游戏路线），但通常能更快地剪掉那些不可能影响最终决策的分支（你可以在H. Fuller的《Analysis of the alpha-beta pruning algorithm by Samuel》 – 1973年中阅读相关证明）。

你使用的是Negamax Alpha-Beta剪枝，但这只是为了简化算法实现的一种变体。

此外，fail-soft技巧并不会改变这种情况。

当然，在浅层深度进行搜索可能会选择不好的走法，但这同样适用于Minimax算法。

所以这应该是实现上的错误。

我认为展示的代码看起来是正确的。你应该检查以下几点：

1. 你在根节点调用negamax的方式。它应该类似于：

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

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

   如果你对alpha / beta使用了不同的初始值（例如aspiration windows），并且真实分数超出了初始窗口，你需要重新搜索。

2. 你如何收集/存储/管理/传播主要变体的走法（相关代码缺失）。像PV表这样的技术与bestValue的变化有关。如果这是问题所在，你应该会得到与Minimax算法相同的位置分数，但最佳走法不同。