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

Question

我一直在使用 negamax 玩连四。我注意到的是，如果我添加 alpha-beta，它有时会给出 "wrong" 结果，因为在进行失败操作时，我认为它不应该符合我正在搜索的深度。如果我删除 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 算法 returns 与 Minimax 相同的结果（在根节点和游戏线处的评估）但是（通常）在更快的时间内修剪掉那些分支不可能影响最终决定（您可以阅读 H. Fuller - 1973 的 Analysis of the alpha-beta pruning algorithm by Samuel 中的证明）。

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

此外 fail-soft 噱头并没有改变这种情况。

当然，浅层搜索可能会选出错误的着法，但对于 Minimax 也是如此。

所以一定是执行错误。

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

你在根节点调用 negamax 的方式。它应该是这样的：
```
 negamax(rootState, depth, −extremePoints, +extremePoints, color)
```
alpha / beta 是可能的最低值和最高值。

如果您为 alpha / beta 使用不同的初始值（例如 aspiration windows）并且真实分数在初始 windows 之外，您需要重新-搜索。
你如何收集/存储/管理/传播主要变化的动作（相关代码缺失）。 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 的数学否定超出了 'int' 数据类型的范围（完整范围是：-2147483648 vs 2147483647) 我们不能在 [=16 中表示正数 ...648 =] 类型，使其回落到负最小值。

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

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

C++ Negamax alpha-beta wrong cutoff?

c++

artificial-intelligence

alpha-beta-pruning

negamax