1

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

2 回答 2

2

alpha-beta 能否切断一些实际可行的分支（尤其是在深度有限的情况下）？

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

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

失败软噱头也不会改变这种情况。

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

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

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

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

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

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

    如果您对alpha/使用不同的初始值beta（例如愿望窗口）并且真实分数在初始窗口之外，则需要重新搜索。

  2. 您如何收集/存储/管理/传播主要变体的移动（缺少相关代码）。PV 表等技术与bestValue. 如果这是问题所在，您应该在该位置上获得相同的分数（相对于 Minimax），但最佳着法不同。

于 2016-06-25T13:21:38.943 回答
2

alpha问题是你如何beta在根节点初始化你。我有一个类似的错误，因为我将它们设置为std::numeric_limits<int>::min()并std::numeric_limits<int>::max()相应地在将alpha参数传递给另一个递归调用期间，我通过添加一个减号运算符来negamax(... -a_beta, -a_alpha ... )否定最小值，仍然产生最小值！因为 minimum 的数学否定超出了 'int' 数据类型的范围（完整范围是：-214748364 8 vs 214748364 7）我们不能在类型中表示正...64 8所以它回落到负最小值。intintintint

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

于 2017-12-29T11:24:52.807 回答