C ++ Negamax alpha

我一直在使用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;
}

alpha-beta能切断一些实际可行的分支（特别是当深度有限时）吗？

Alpha-Beta算法返回与Minimax相同的结果（ 在根节点和游戏线上评估 ），但是（通常）在更快的时间修剪掉不可能影响最终决定的分支（您可以阅读alpha-beta分析中的证明由Samuel by H.Fuller-1973修剪算法）。

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

此外， 失败软的噱头不会改变这种情况。

当然，浅层搜索可以选择不好的移动，但Minimax也是如此。

所以它必须是一个执行错误。

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

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

问题是你如何在根节点初始化你的alpha和beta。 我有一个类似的错误，因为我相应地将它们设置为std :: numeric_limits :: min（）和std :: numeric_limits :: max（），并将alpha参数传递给另一个递归调用negamax（... -a_beta， - a_alpha ...）我通过添加一个负运算符来否定最小int值，因为最小int值的数学否定在int（-214748364 8 vs 214748364 7 ）的范围之外，所以仍然产生最小int值。

但是，如果您将alpha初始化为不同的值（例如std :: numeric_limits :: min（）+ 1），则情况并非如此。

上一篇: C++ Negamax alpha

下一篇: Minmax algorithm chooses the worst move for some depths