C++ Negamax alpha-beta неправильное обрезание?

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

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

альфа-бета алгоритм возвращает те же результаты, как Минимакс (оценки в корневом узле и линии игры), но (часто) в более быстрое время обрезки далеко ветвей, которые никак не могут повлиять на окончательное решение (вы можете прочитать доказательство в Analysis of the alpha-beta pruning algorithm by Samuel H. Fuller - 1973).

Вы используете Обрезка альфа-бета Negamax, но это просто вариант, упрощающий реализацию алгоритма.

Также fail-soft трюк не меняет ситуацию.

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

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

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

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

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

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

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

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

Answer 2

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

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