Я путаюсь с этими двумя. Negamax — это просто оптимизация для минимакса? или Negamax - это другой алгоритм дерева поиска? Если negamax — это еще один алгоритм дерева поиска, то какой из них лучше?
В чем разница между Минимакс и Негамакс?
Ответы (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
Это правильно. Просто чтобы уточнить первоначальный вопрос, Negamax и Minimax - это один и тот же алгоритм и имеют одинаковую эффективность/производительность.
- person eligolf; 18.01.2021