如何修复极小极大算法

Question

需要编写一个 minimax 算法，returns 随机数数组中的一个值，其长度为 2 ^ 深度（该算法适用于二叉树）。

我的代码：

int minimax(int* scores, unsigned int left, unsigned int right, int depth, bool search_max_score, bool& move)
{
    if (search_max_score)
    {
        if (depth == 1)
        {
            int result = std::max(scores[left], scores[right]);
            move = (result == scores[right]);
            return result;
        }

        int left_value = minimax(scores, left, right / 2, depth - 1, false, move);
        int right_value = minimax(scores, right / 2 + 1, right, depth - 1, false, move);
        int result = std::max(left_value, right_value);

        move = (result == right_value);

        return result;
    }
    else
    {
        if (depth == 1)
        {
            int result = std::min(scores[left], scores[right]);
            move = (result == scores[right]);
            return result;
        }

        int left_value = minimax(scores, left, right / 2, depth - 1, true, move);
        int right_value = minimax(scores, right / 2 + 1, right, depth - 1, true, move);
        int result = std::min(left_value, right_value);

        move = (result == right_value);

        return result;
    }
}

    //score_num - array length
    //search_max_score - which element to search for (false - minimum, true - maximum)
    bool move;
    int result = minimax(scores, 0, score_num - 1, depth, search_max_score, move);

    std::cout << "result: " << result << '\n';
    std::cout << "move: " << move;

但有时程序会输出错误的值：


random values:

     ___/___         __\____
   _/_     _\_     _/_     _\_
  /   \   /   \   /   \   /   \
 -1   3  -5   1  -8   6   4  -7

result: 1
move: 0

move是AI后续动作的方向。 0 - 左，1 - 右

Answer 1

您至少有 2 个错误：

在 if (search_max_score) 块中调用 minmax 并将 false 作为第 5 个参数，这相当于使搜索 max 元素成为搜索 min元素，然后再次最大，依此类推
如果你有一个间隔 [left, right] 并且你想将它减半，则中点不是 right/2（除非 left == 0），而是 (left + right)/2 或 left + (right-left + 1)/2。您需要使用适合您需要的公式的确切形式，同时考虑将奇数除以 2 时的整数舍入。或者您可以从 depth 计算偏移量，因为间隔长度始终是二的幂。
第三点不是bug，而是报错：请使用调试器

如何修复极小极大算法

How to fix minimax algorithm

c++

algorithm

minimax