Негамакс
Негамаксный поиск — это вариант минимаксного поиска, основанный на свойстве нулевой суммы в игре для двух игроков .
Этот алгоритм основан на том, что упростить реализацию минимаксного алгоритма. Точнее, ценность позиции для игрока А в такой игре — это отрицание ценности для игрока Б. Таким образом, игрок на ходу ищет ход, который максимизирует отрицание ценности, полученной в результате хода: эта последующая позиция по определению должно быть оценено противником. Рассуждения предыдущего предложения работают независимо от того, ходит ли A или B. Это означает, что для оценки обеих позиций можно использовать одну процедуру. Это упрощение кодирования по сравнению с минимаксом, которое требует, чтобы A выбирал ход с преемником с максимальным значением, а B выбирал ход с преемником с минимальным значением.
Его не следует путать с negascout — алгоритмом быстрого вычисления минимаксного или негамаксного значения с помощью умного использования альфа-бета-отсечения, открытого в 1980-х годах. Обратите внимание, что альфа-бета-отсечение само по себе является способом быстрого вычисления минимаксного или негамаксного значения позиции, избегая поиска определенных неинтересных позиций.
Большинство состязательных поисковых систем используют ту или иную форму негамаксного поиска.
Базовый алгоритм Negamax [ править ]
NegaMax работает с теми же деревьями игры , что и алгоритм минимаксного поиска. Каждый узел и корневой узел в дереве представляют собой игровые состояния (например, конфигурацию игрового поля) игры для двух игроков. Переходы к дочерним узлам представляют собой ходы, доступные игроку, который собирается играть из данного узла.
Цель поиска negamax — найти значение счета узла для игрока, который играет в корневом узле. Псевдокод ниже показывает базовый алгоритм negamax: [1] с настраиваемым ограничением максимальной глубины поиска:
function negamax(node, depth, color) is
if depth = 0 or node is a terminal node then
return color × the heuristic value of node
value := −∞
for each child of node do
value := max(value, −negamax(child, depth − 1, −color))
return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, 1)
(* Initial call for Player B's root node *) negamax(rootNode, depth, −1)
Корневой узел наследует свой рейтинг от одного из своих непосредственных дочерних узлов. Дочерний узел, который в конечном итоге устанавливает лучший результат для корневого узла, также представляет собой лучший ход для игры. Хотя показанная функция negamax возвращает только лучший результат узла, практические реализации negamax сохранят и вернут как лучший ход, так и лучший результат для корневого узла. Для некорневых узлов важен только лучший результат узла. И лучший ход узла не является обязательным для сохранения или возврата для некорневых узлов.
Что может сбить с толку, так это то, как рассчитывается эвристическое значение текущего узла. В этой реализации это значение всегда рассчитывается с точки зрения игрока А, значение цвета которого равно единице. Другими словами, более высокие значения эвристики всегда представляют ситуации, более благоприятные для игрока А. Это то же самое поведение, что и обычный минимаксный алгоритм. Эвристическое значение не обязательно совпадает с возвращаемым значением узла из-за отрицания значения с помощью negamax и параметра цвета. Возвращаемое значение узла negamax — это эвристическая оценка с точки зрения текущего игрока узла.
Очки Negamax соответствуют минимаксным оценкам для узлов, в которых собирается играть игрок A, и где игрок A является максимизирующим игроком в минимаксном эквиваленте. Negamax всегда ищет максимальное значение для всех своих узлов. Следовательно, для узлов игрока B минимаксная оценка является отрицанием его негамаксной оценки. Игрок B — минимизирующий игрок в минимаксном эквиваленте.
Вариант Negamax без параметра цвета [ править ]
Negamax может быть реализован без параметра цвета. В этом случае эвристическая функция оценки должна возвращать значения с точки зрения текущего игрока узла (Пример: в шахматной игре, если сейчас ход белых и белые выигрывают, она должна возвращать положительное значение. Однако, если это ход черных, он должен вернуть отрицательное значение).
function negamax(node, depth) is
if depth = 0 or node is a terminal node then
return evaluatePosition() // From current player's perspective
value := −∞
for each child of node do
value := max(value, −negamax(child, depth − 1))
return value
// Example picking best move in a chess game using negamax function above
function think(boardState) is
allMoves := generateLegalMoves(boardState)
bestMove := null
bestEvaluation := -∞
for each move in allMoves
board.apply(move)
evaluateMove := -negamax(boardState, depth=3)
board.undo(move)
if evaluateMove > bestEvaluation
bestMove := move
bestEvaluation := evaluateMove
return bestMove
Negamax с обрезкой - альфа бета
Оптимизация алгоритма для минимакса также в равной степени применима и для Negamax. Альфа-бета-обрезка может уменьшить количество узлов, которые алгоритм негамакс оценивает в дереве поиска, аналогично его использованию с алгоритмом минимакс.
Ниже приведен псевдокод для поиска негамакса с ограниченной глубиной и альфа-бета-отсечением: [1]
function negamax(node, depth, α, β, color) is
if depth = 0 or node is a terminal node then
return color × the heuristic value of node
childNodes := generateMoves(node)
childNodes := orderMoves(childNodes)
value := −∞
foreach child in childNodes do
value := max(value, −negamax(child, depth − 1, −β, −α, −color))
α := max(α, value)
if α ≥ β then
break (* cut-off *)
return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, −∞, +∞, 1)
Альфа (α) и бета (β) представляют нижнюю и верхнюю границы значений дочерних узлов на заданной глубине дерева. Negamax устанавливает аргументы α и β для корневого узла в минимально возможное и максимальное значения. Другие алгоритмы поиска, такие как negascout и MTD(f) , могут инициализировать α и β альтернативными значениями для дальнейшего улучшения производительности поиска по дереву.
Когда negamax встречает значение дочернего узла за пределами альфа/бета-диапазона, поиск negamax отсекает, тем самым отсекая части игрового дерева от исследования. Отсечения являются неявными и основаны на возвращаемом значении узла. Значение узла, найденное в диапазоне его начальных α и β, является точным (или истинным) значением узла. Это значение идентично результату, который вернул бы базовый алгоритм negamax, без обрезков и без каких-либо границ α и β. Если возвращаемое значение узла выходит за пределы диапазона, то это значение представляет собой верхнюю (если значение ≤ α) или нижнюю (если значение ≥ β) границу точного значения узла. Альфа-бета-обрезка в конечном итоге отбрасывает любые результаты, связанные со значениями. Такие значения не вносят вклад и не влияют на значение negamax в его корневом узле.
Этот псевдокод показывает отказоустойчивый вариант обрезки альфа-бета. Fail-soft никогда не возвращает α или β напрямую в качестве значения узла. Таким образом, значение узла может находиться за пределами начальных границ диапазона α и β, установленных с помощью вызова функции negamax. Напротив, отказоустойчивое сокращение альфа-бета всегда ограничивает значение узла в диапазоне α и β.
Эта реализация также показывает необязательный порядок перемещения перед циклом foreach , который оценивает дочерние узлы. Переместить порядок [2] — это оптимизация альфа-бета-отсечения, которая пытается угадать наиболее вероятные дочерние узлы, которые дают оценку узлу. Алгоритм сначала ищет эти дочерние узлы. Результатом хороших догадок является более раннее и более частое отсечение альфа/беты, тем самым отсекая дополнительные ветки игрового дерева и оставшиеся дочерние узлы из дерева поиска.
с таблицами альфа-бета-обрезки транспонирования и Negamax
Таблицы транспозиции выборочно запоминают значения узлов в дереве игры. Транспозиция — это термин, обозначающий, что данная позиция на игровом поле может быть достигнута более чем одним способом с разными последовательностями игровых ходов.
Когда negamax выполняет поиск в дереве игры и несколько раз встречает один и тот же узел, таблица транспонирования может возвращать ранее вычисленное значение узла, пропуская потенциально длительные и повторяющиеся повторные вычисления значения узла. Производительность Negamax особенно повышается для игровых деревьев со многими путями, ведущими к данному узлу.
Псевдокод, который добавляет функции таблицы транспонирования в negamax с сокращением альфа/бета, выглядит следующим образом: [1]
function negamax(node, depth, α, β, color) is
alphaOrig := α
(* Transposition Table Lookup; node is the lookup key for ttEntry *)
ttEntry := transpositionTableLookup(node)
if ttEntry is valid and ttEntry.depth ≥ depth then
if ttEntry.flag = EXACT then
return ttEntry.value
else if ttEntry.flag = LOWERBOUND then
α := max(α, ttEntry.value)
else if ttEntry.flag = UPPERBOUND then
β := min(β, ttEntry.value)
if α ≥ β then
return ttEntry.value
if depth = 0 or node is a terminal node then
return color × the heuristic value of node
childNodes := generateMoves(node)
childNodes := orderMoves(childNodes)
value := −∞
for each child in childNodes do
value := max(value, −negamax(child, depth − 1, −β, −α, −color))
α := max(α, value)
if α ≥ β then
break
(* Transposition Table Store; node is the lookup key for ttEntry *)
ttEntry.value := value
if value ≤ alphaOrig then
ttEntry.flag := UPPERBOUND
else if value ≥ β then
ttEntry.flag := LOWERBOUND
else
ttEntry.flag := EXACT
ttEntry.depth := depth
ttEntry.is_valid := true
transpositionTableStore(node, ttEntry)
return value
(* Initial call for Player A's root node *) negamax(rootNode, depth, −∞, +∞, 1)
Ограничения альфа-/бета-обрезки и максимальной глубины поиска в negamax могут привести к частичной, неточной или полной пропущенной оценке узлов в дереве игры. Это усложняет добавление оптимизации таблицы транспонирования для negamax. Недостаточно отслеживать только значение узла в таблице, поскольку значение может не совпадать с истинным значением узла. Поэтому код должен сохранять и восстанавливать взаимосвязь значений с параметрами альфа/бета и глубиной поиска для каждой записи таблицы транспонирования.
Таблицы транспозиции обычно содержат потери и пропускают или перезаписывают предыдущие значения определенных узлов игрового дерева в своих таблицах. Это необходимо, поскольку количество посещений negamax узлов часто намного превышает размер таблицы транспозиции. Потерянные или пропущенные записи таблицы некритичны и не повлияют на результат negamax. Однако потерянные записи могут потребовать от negamax более частого повторного вычисления определенных значений узлов игрового дерева, что влияет на производительность.
Ссылки [ править ]
- Джордж Т. Хайнеман; Гэри Поллис и Стэнли Селкоу (2008). «Глава 7: Поиск пути в ИИ». Коротко об алгоритмах . Орейли Медиа . стр. 213–217. ISBN 978-0-596-51624-6 .
- Джон П. Фишберн (1984). «Приложение A: Некоторые оптимизации поиска α-β». Анализ ускорения распределенных алгоритмов (переработка кандидатской диссертации 1981 г.) . UMI Research Press . стр. 107–111. ISBN 0-8357-1527-2 .
- ^ Jump up to: Перейти обратно: а б с Брейкер, Деннис М. Память против поиска в играх , Маастрихтский университет, 16 октября 1998 г.
- ^ Шеффер, Джонатан (1989). «Усовершенствования исторической эвристики и альфа-бета-поиска на практике». Транзакции IEEE по анализу шаблонов и машинному интеллекту . 11 (11): 1203–12. дои : 10.1109/34.42858 .