C++ Negamax альфа-бета неправильная отсечка?

Question

Я использую Negamax, чтобы играть соединить четыре. Что я заметил, так это то, что если я добавляю альфа-бета-версию, она иногда дает "неправильные" результаты, так как, делая неудачный ход, я не верю, что он должен делать с той глубиной, на которой я ищу. Если я удаляю альфа-бета, она играет так, как и должна. Может ли альфа-бета отрезать некоторые действительно жизнеспособные ветви (особенно, когда глубина ограничена)? Вот код на всякий случай:

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

Может ли альфа-бета отрезать некоторые действительно жизнеспособные ветви (особенно, когда глубина ограничена)?

Алфа-бета-алгоритм возвращает те же результаты, что и Minimax (оценка в корневом узле и линии воспроизведения), но (часто) в более короткое время, удаляя ветви, которые не могут повлиять на окончательное решение (вы можете прочитать доказательство в разделе Анализ альфа-беты Алгоритм обрезки по Самуэлю Х. Фуллера - 1973).

Вы используете отсечение Negamax Alpha-Beta, но это всего лишь вариант, упрощающий реализацию алгоритма.

Также трюк со сбоем не меняет ситуацию.

Конечно, поиск на малой глубине может выбрать плохие ходы, но то же самое можно сказать и о минимаксе.

Так что это должна быть ошибка реализации.

Показанный код кажется мне правильным. Вы должны проверить:

1. как вы называете Negamax в корневом узле. Это должно быть что-то вроде:

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

   alpha / beta самые низкие и самые высокие возможные значения.

   Если вы используете разные начальные значения для alpha / beta (например, окна аспирации), и истинный счет находится за пределами начальных окон, вам необходимо выполнить повторный поиск.

2. как вы собираете / храните / управляете / распространяете ходы основного варианта (соответствующий код отсутствует). Такие техники, как PV-таблицы, связаны с изменениями bestValue, Если это проблема, вы должны получить тот же счет за позицию (относительно минимакса), но другой лучший ход.

Answer 2

Вопрос в том, как вы инициализируете свои альфа и бета в корневом узле. У меня была похожая ошибка, потому что я установил их в std::numeric_limits::min() и std::numeric_limits::max() соответственно и во время передачи альфа-параметра другому рекурсивному вызову negamax(... -a_beta, -a_alpha ...) Я отрицал минимальное значение int, добавляя оператор минус, который все еще возвращает минимальное значение int, потому что математическое отрицание минимального значения int находится вне диапазона int (-2147483648 против 2147483647).

Однако если вы инициализируете альфа другим значением (например, std::numeric_limits::min() + 1), это не так.