В чем разница между Минимакс и Негамакс?

Я путаюсь с этими двумя. Negamax — это просто оптимизация для минимакса? или Negamax - это другой алгоритм дерева поиска? Если negamax — это еще один алгоритм дерева поиска, то какой из них лучше?


person James Urian    schedule 16.01.2021    source источник


Ответы (1)


Информация извлечена из здесь

Negamax — это упрощение MinMax за счет использования следующего свойства:

макс(а,б) = -мин(-а,-б)

Итак, вместо вычисления условного значения в minmax, которое выглядит следующим образом:

if maximizingPlayer then
    value := −∞
    for each child of node do
        value := max(value, minimax(child, depth − 1, FALSE))
    return value
else (* minimizing player *)
    value := +∞
    for each child of node do
        value := min(value, minimax(child, depth − 1, TRUE))

у вас есть одна строка, которая делает то же самое в Negamax:

value := max(value, −negamax(child, depth − 1, −color))

и логическое значение заменено понятием (в статье) цвета, которое представляет собой просто значение 1 или -1 для переключения между ходами игрока (если мы должны минимизировать или максимизировать следующий ход)

person Sami Tahri    schedule 16.01.2021
comment
Это правильно. Просто чтобы уточнить первоначальный вопрос, Negamax и Minimax - это один и тот же алгоритм и имеют одинаковую эффективность/производительность. - person eligolf; 18.01.2021