Поиск Negamax - это вариантная форма минимаксного поиска, основанная на свойстве игры с нулевой суммой в игре для двух игроков .
Этот алгоритм основан на том, что для упрощения реализации минимаксного алгоритма. Точнее, значение позиции для игрока A в такой игре является отрицанием значения для игрока B. Таким образом, игрок на ходу ищет ход, который максимизирует отрицание значения, полученного в результате этого хода: эта позиция-преемник должны по определению быть оценены противником. Обоснование предыдущего предложения работает независимо от того, движется ли A или B. Это означает, что для оценки обеих позиций можно использовать одну процедуру. Это упрощение кодирования по сравнению с минимаксом, которое требует, чтобы A выбирал ход с преемником с максимальным значением, а B выбирал ход с преемником с минимальным значением.
Его не следует путать с negascout , алгоритмом для быстрого вычисления минимаксного или негамаксного значения за счет умного использования альфа-бета-отсечения, открытого в 1980-х годах. Обратите внимание, что альфа-бета-обрезка сама по себе является способом быстрого вычисления минимаксного или негамаксного значения позиции, избегая поиска определенных неинтересных позиций.
Большинство состязательных поисковых систем кодируются с использованием некоторой формы негамаксного поиска.
Базовый алгоритм Негамакса
NegaMax работает с теми же деревьями игр, что и алгоритмы минимаксного поиска. Каждый узел и корневой узел в дереве - это игровые состояния (например, конфигурация игровой доски) в игре для двух игроков. Переходы к дочерним узлам представляют собой ходы, доступные игроку, который собирается играть из данного узла.
Цель поиска Negamax состоит в том, чтобы найти значение счета узла для игрока, который играет в корневом узле. Псевдокод ниже показывает алгоритм negamax основания, [1] с настраиваемым пределом для глубины максимального поиска:
функция negamax (узел, глубина, цвет) - если глубина = 0 или узел является конечным узлом, то возвращает цвет × эвристическое значение узла значение: = −∞ для каждого дочернего элемента узла сделать value: = max (value, negamax (child, depth - 1, −color)) return −value
(* Первоначальный вызов корневого узла игрока A *)negamax (корневой узел, глубина, 1)
(* Первоначальный вызов корневого узла игрока B *)negamax (корневой узел, глубина, -1)
Корневой узел наследует свою оценку от одного из своих непосредственных дочерних узлов. Дочерний узел, который в конечном итоге устанавливает лучший результат для корневого узла, также представляет собой лучший ход для игры. Хотя показанная функция negamax возвращает только лучший результат узла, практические реализации negamax будут сохранять и возвращать как лучший ход, так и лучший результат для корневого узла. Для некорневых узлов важен только лучший результат узла. И для некорневых узлов нет необходимости сохранять или возвращать лучший ход узла.
Что может сбить с толку, так это то, как вычисляется эвристическое значение текущего узла. В этой реализации это значение всегда вычисляется с точки зрения игрока A, значение цвета которого равно единице. Другими словами, более высокие эвристические значения всегда представляют ситуации, более благоприятные для игрока A. Это то же поведение, что и нормальный алгоритм минимакса . Эвристическое значение не обязательно совпадает с возвращаемым значением узла из-за отрицания значения негамаксом и параметром цвета. Возвращаемое значение узла negamax является эвристической оценкой с точки зрения текущего игрока узла.
Показатели Negamax соответствуют минимаксным оценкам для узлов, где игрок A собирается играть, и где игрок A является максимизирующим игроком в минимаксном эквиваленте. Negamax всегда ищет максимальное значение для всех своих узлов. Следовательно, для узлов игрока B минимаксный счет является отрицанием его негамаксного счета. Игрок B - минимизирующий игрок в минимаксном эквиваленте.
Варианты реализации Negamax могут опускать параметр цвета. В этом случае функция эвристической оценки должна возвращать значения с точки зрения текущего игрока узла.
Негамакс с альфа-бета-обрезкой
Оптимизация алгоритмов для минимакса также применима и для Negamax. Отсечение альфа-бета может уменьшить количество узлов, оцениваемых алгоритмом Negamax в дереве поиска, аналогично его использованию с алгоритмом минимакса.
Псевдокод для поиска негамакса с ограничением глубины с отсечением альфа-бета следующий: [1]
функция negamax (узел, глубина, α, β, цвет) - если глубина = 0 или узел является конечным узлом, то возвращает цвет × эвристическое значение узла childNodes: = generateMoves (узел) childNodes: = orderMoves (childNodes) значение: = −∞ foreach дочерний элемент в childNodes do value: = max (value, −negamax (child, depth - 1, −β, −α, −color)) α: = max (α, значение) если α ≥ β, то возвратное значение break (* cut-off *)
(* Первоначальный вызов корневого узла игрока A *)negamax (корневой узел, глубина, −∞, + ∞, 1)
Альфа (α) и бета (β) представляют нижнюю и верхнюю границы значений дочерних узлов на заданной глубине дерева. Negamax устанавливает аргументы α и β для корневого узла на наименьшее и наибольшее возможные значения. Другие алгоритмы поиска, такие как negascout и MTD-f , могут инициализировать α и β с альтернативными значениями для дальнейшего повышения производительности поиска по дереву.
Когда Negamax встречает значение дочернего узла вне диапазона альфа / бета, поиск Negamax прерывается, тем самым отсекая части игрового дерева от исследования. Отсечки неявны на основе возвращаемого значения узла. Значение узла, найденное в диапазоне его начальных значений α и β, является точным (или истинным) значением узла. Это значение идентично результату, который вернет базовый алгоритм негамакса, без отсечений и без каких-либо границ α и β. Если возвращаемое значение узла выходит за пределы допустимого диапазона, то значение представляет собой верхнюю (если значение ≤ α) или нижнюю (если значение ≥ β) границу точного значения узла. Отсечение альфа-бета в конечном итоге отбрасывает любые результаты с привязкой к значению. Такие значения не влияют и не влияют на значение негамакса в его корневом узле.
Этот псевдокод показывает безупречный вариант обрезки альфа-бета. Fail-soft никогда не возвращает α или β непосредственно как значение узла. Таким образом, значение узла может выходить за пределы начальных границ диапазона α и β, установленных с помощью вызова функции Negamax. Напротив, безотказная альфа-бета-обрезка всегда ограничивает значение узла в диапазоне от α до β.
Эта реализация также показывает необязательный порядок перемещения до цикла foreach, который оценивает дочерние узлы. Упорядочение перемещений [2] - это оптимизация для альфа-бета-отсечения, которая пытается угадать наиболее вероятные дочерние узлы, которые дают оценку узла. Алгоритм сначала ищет эти дочерние узлы. Результатом правильных предположений является более раннее и более частое отсечение альфа / бета, тем самым удаляя дополнительные ветви дерева игры и оставшиеся дочерние узлы из дерева поиска.
Negamax с альфа-бета-таблицами обрезки и транспонирования
Таблицы транспонирования выборочно запоминают значения узлов в дереве игры. Перенос - это термин, обозначающий, что данная позиция на игровом поле может быть достигнута более чем одним способом с различными последовательностями ходов игры.
Когда negamax ищет в дереве игры и встречает один и тот же узел несколько раз, таблица транспонирования может возвращать ранее вычисленное значение узла, пропуская потенциально длинные и повторяющиеся повторные вычисления значения узла. Производительность Negamax улучшается особенно для игровых деревьев с множеством общих путей, ведущих к данному узлу.
Псевдокод, который добавляет функции таблицы транспонирования к negamax с отсечением альфа / бета, имеет следующий вид: [1]
функция negamax (узел, глубина, α, β, цвет) есть alphaOrig: = α (* Поиск в таблице транспонирования; узел - это ключ поиска для ttEntry *) ttEntry: = transpositionTableLookup (узел) если ttEntry действителен и ttEntry.depth ≥ depth, тогда, если ttEntry.flag = EXACT, тогда вернуть ttEntry.value, иначе, если ttEntry.flag = LOWERBOUND, тогда α: = max (α, ttEntry.value) иначе, если ttEntry.flag = UPPERBOUND, то β: = min (β, ttEntry.value) если α ≥ β затем возвращают ttEntry.value если глубина = 0 или узел является конечным узлом затем возвращают цвет × эвристическое значение узла childNodes: = generateMoves (узел) childNodes: = orderMoves (childNodes) значение: = −∞ для каждого ребенка в childNodes делаем value: = max (value, −negamax (child, depth - 1, −β, −α, −color)) α: = max (α, значение) если α ≥ β, то ломаем (* Хранилище таблиц транспозиции; узел - это ключ поиска для ttEntry *) ttEntry.value: = значение если значение ≤ alphaOrig, то ttEntry.flag: = ВЕРХНЯЯ ЧАСТЬ иначе, если значение ≥ β, то ttEntry.flag: = LOWERBOUND еще ttEntry.flag: = ТОЧНЫЙ ttEntry.depth: = глубина transpositionTableStore (узел, ttEntry) возвращаемое значение
(* Первоначальный вызов корневого узла игрока A *)negamax (корневой узел, глубина, −∞, + ∞, 1)
Отсечение альфа / бета и ограничения максимальной глубины поиска в negamax могут привести к частичной, неточной или полностью пропущенной оценке узлов в дереве игры. Это усложняет добавление оптимизаций таблицы транспонирования для Negamax. Это недостаточно , чтобы отслеживать только этот узел значения в таблице, поскольку значение не может быть истинное значением этого узла. Следовательно, код должен сохранять и восстанавливать взаимосвязь значения с параметрами альфа / бета и глубиной поиска для каждой записи таблицы транспонирования.
Таблицы транспонирования обычно с потерями и будут пропускать или перезаписывать предыдущие значения определенных узлов игрового дерева в своих таблицах. Это необходимо, поскольку количество посещений негамакс узлов часто намного превышает размер таблицы транспонирования. Потерянные или пропущенные записи таблицы некритичны и не повлияют на результат негамакса. Однако потерянные записи могут потребовать от Negamax более частого повторного вычисления определенных значений узлов игрового дерева, что влияет на производительность.
Рекомендации
- Джордж Т. Хейнеман; Гэри Поллис и Стэнли Селкоу (2008). «Глава 7: Поиск пути в AI». Об алгоритмах в двух словах . Oreilly Media . С. 213–217. ISBN 978-0-596-51624-6.
- Джон П. Фишберн (1984). «Приложение A: Некоторые оптимизации поиска α-β». Анализ ускорения в распределенных алгоритмах (редакция кандидатской диссертации 1981 г.) . UMI Research Press . С. 107–111. ISBN 0-8357-1527-2.
- ^ a b c Брейкер, Деннис М. Память против поиска в играх , Маастрихтский университет, 16 октября 1998 г.
- ^ Шеффер, Джонатан.Улучшения исторической эвристики и альфа-бета-поиска на практике , транзакции IEEE по анализу шаблонов и машинному анализу, 1989.