How to fix minimax algorithm

Question

Required to write a minimax algorithm that returns a value from a array of random numbers, the length of which is 2 ^ depth(the algorithm works on a binary tree).

my code:

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;

But sometimes the program outputs the wrong value:

random values:

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

result: 1
move: 0

move is the direction of the subsequent action of the AI. 0 - left, 1 - right

Answer 1

You have at least 2 bugs:

1. Inside if (search_max_score) block you call minmax with false as the 5th argument, which is equivalent to making the search for max element becoming a search for min element, and then max again, etc.

2. If you have an interval [left, right] and you want to halve it, the midpoint is NOT right/2 (unless left == 0), but rather (left + right)/2 or left + (right-left + 1)/2. You need to work on the exact form of this formula that will fit your needs, taking into account the integer rounding when dividing an odd integer by 2. Or you can calculate the offset from depth, as the interval length will always be a power of two.

3. The third point is not a bug, but an error it is: please use a debugger.