Негамакс - Википедия - Negamax

Негамакс поиск - это вариантная форма минимакс поиск, опирающийся на с нулевой суммой собственность игра для двух игроков.

Этот алгоритм основан на том, что для упрощения реализации минимакс алгоритм. Точнее, значение позиции для игрока A в такой игре является отрицанием значения для игрока B. Таким образом, игрок на ходу ищет ход, который максимизирует отрицание значения, полученного в результате этого хода: эта последующая позиция должны по определению быть оценены противником. Обоснование предыдущего предложения работает независимо от того, движется ли A или B. Это означает, что для оценки обеих позиций можно использовать одну процедуру. Это упрощение кодирования по сравнению с минимаксом, которое требует, чтобы A выбирал ход с преемником с максимальным значением, а B выбирал ход с преемником с минимальным значением.

Не следует путать с Negascout, алгоритм для быстрого вычисления минимаксного или негамаксного значения за счет умного использования альфа-бета обрезка обнаружен в 1980-х гг. Обратите внимание, что альфа-бета-обрезка сама по себе является способом быстрого вычисления минимаксного или негамаксного значения позиции, избегая поиска определенных неинтересных позиций.

Наиболее состязательный поиск движки кодируются с использованием некоторой формы негамаксного поиска.

Базовый алгоритм Негамакса

Анимированный педагогический пример, показывающий простой алгоритм негамакса (то есть без обрезки альфа-бета). Считается, что человек, выполняющий поиск по дереву игры, должен первым выйти из текущего состояния игры (игрок в этом случае)

NegaMax работает с теми же деревьями игр, что и алгоритмы минимаксного поиска. Каждый узел и корневой узел в дереве - это игровые состояния (например, конфигурация игрового поля) в игре для двух игроков. Переходы к дочерним узлам представляют собой ходы, доступные игроку, который собирается играть из данного узла.

Цель поиска Negamax - найти значение счета узла для игрока, который играет в корневом узле. В псевдокод ниже показан базовый алгоритм негамакса,[1] с настраиваемым пределом максимальной глубины поиска:

функция негамакс (узел, глубина, цвет) является    если глубина = 0 или же узел является конечным узлом тогда        возвращаться цвет × эвристическое значение значения узла: = −∞ для каждого дочерний элемент узла делать        значение: = max (значение, −negamax (дочерний элемент, глубина - 1, −цвет)) возвращаться ценить
(* Первоначальный вызов корневого узла игрока A *)negamax (корневой узел, глубина, 1)
(* Первоначальный вызов корневого узла игрока B *)negamax (корневой узел, глубина, -1)

Корневой узел наследует свой рейтинг от одного из своих непосредственных дочерних узлов. Дочерний узел, который в конечном итоге устанавливает лучший результат для корневого узла, также представляет собой лучший ход для игры. Хотя показанная функция negamax возвращает только лучший результат для узла, практические реализации negamax будут сохранять и возвращать как лучший ход, так и лучший результат для корневого узла. Для некорневых узлов важен только лучший результат узла. И для некорневых узлов не нужно ни сохранять, ни возвращать лучший ход узла.

Что может сбивать с толку, так это то, как вычисляется эвристическое значение текущего узла. В этой реализации это значение всегда рассчитывается с точки зрения игрока A, значение цвета которого равно единице. Другими словами, более высокие эвристические значения всегда представляют ситуации, более благоприятные для игрока А. Это такое же поведение, как и при нормальном минимакс алгоритм. Эвристическое значение не обязательно совпадает с возвращаемым значением узла из-за отрицания значения с помощью negamax и параметра цвета. Возвращаемое значение узла negamax является эвристической оценкой с точки зрения текущего игрока узла.

Показатели Negamax соответствуют минимаксным оценкам для узлов, где игрок A собирается играть, и где игрок A является максимизирующим игроком в минимаксном эквиваленте. Negamax всегда ищет максимальное значение для всех своих узлов. Следовательно, для узлов игрока B минимаксный счет является отрицанием его негамаксного счета. Игрок B - минимизирующий игрок в минимаксном эквиваленте.

Варианты реализации Negamax могут опускать параметр цвета. В этом случае функция эвристической оценки должна возвращать значения с точки зрения текущего игрока узла.

Негамакс с альфа-бета-обрезкой

Анимированный педагогический пример, показывающий алгоритм Negamax с обрезкой альфа-бета. Считается, что человек, выполняющий поиск по дереву игры, должен первым выйти из текущего состояния игры (игрок в этом случае)

Оптимизация алгоритма для минимакс в равной степени применимы и для Negamax. Альфа-бета обрезка может уменьшить количество узлов, оцениваемых алгоритмом Negamax в дереве поиска, аналогично его использованию с алгоритмом минимакса.

Псевдокод для поиска негамакса с ограничением глубины с отсечением альфа-бета следующий:[1]

функция negamax (узел, глубина, α, β, цвет) является    если глубина = 0 или же узел является конечным узлом тогда        возвращаться цвет × эвристическое значение узла childNodes: = generateMoves (node) childNodes: = orderMoves (childNodes) value: = −∞ для каждого ребенок в childNodes делать        value: = max (value, −negamax (child, depth - 1, −β, −α, −color)) α: = max (α, value) если α ≥ β тогда            перемена (* отрезать *)    возвращаться ценить
(* Первоначальный вызов корневого узла игрока A *)negamax (корневой узел, глубина, −∞, + ∞, 1)

Альфа (α) и бета (β) представляют нижнюю и верхнюю границы значений дочерних узлов на заданной глубине дерева. Negamax устанавливает аргументы α и β для корневого узла на наименьшее и наибольшее возможные значения. Другие алгоритмы поиска, например Negascout и МПД-ф, может инициализировать α и β альтернативными значениями для дальнейшего повышения производительности поиска по дереву.

Когда Negamax встречает значение дочернего узла вне диапазона альфа / бета, поиск Negamax прерывается, тем самым отсекая части игрового дерева от исследования. Отсечки неявны на основе возвращаемого значения узла. Значение узла, найденное в диапазоне его начальных значений α и β, является точным (или истинным) значением узла. Это значение идентично результату, который вернет базовый алгоритм негамакса, без отсечений и без каких-либо границ α и β. Если возвращаемое значение узла выходит за пределы допустимого диапазона, то значение представляет собой верхнюю (если значение ≤ α) или нижнюю (если значение ≥ β) границу точного значения узла. Отсечение альфа-бета в конечном итоге отбрасывает любые результаты с привязкой к значению. Такие значения не влияют и не влияют на значение негамакса в его корневом узле.

Этот псевдокод показывает безупречный вариант обрезки альфа-бета. Отказоустойчивый никогда не возвращает α или β непосредственно как значение узла. Таким образом, значение узла может выходить за пределы начальных границ диапазона α и β, установленных с помощью вызова функции Negamax. Напротив, отказоустойчивое отсечение альфа-бета всегда ограничивает значение узла в диапазоне от α до β.

Эта реализация также показывает необязательный порядок ходов до цикл foreach который оценивает дочерние узлы. Заказ переезда[2] - оптимизация для альфа-бета-отсечения, которая пытается угадать наиболее вероятные дочерние узлы, которые дают оценку узла. Алгоритм сначала ищет эти дочерние узлы. Результатом правильных предположений является более раннее и более частое отсечение альфа / бета, что приводит к отсечению дополнительных ветвей дерева игры и оставшихся дочерних узлов из дерева поиска.

Negamax с альфа-бета-таблицами обрезки и транспонирования

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

Когда negamax выполняет поиск в дереве игры и встречает один и тот же узел несколько раз, таблица транспонирования может возвращать ранее вычисленное значение узла, пропуская потенциально длинные и повторяющиеся повторные вычисления значения узла. Производительность Negamax улучшается особенно для игровых деревьев с множеством общих путей, ведущих к данному узлу.

Псевдокод, который добавляет функции таблицы транспонирования к negamax с отсечением альфа / бета, выглядит следующим образом:[1]

функция negamax (узел, глубина, α, β, цвет) является    alphaOrig: = α (* Поиск в таблице транспонирования; узел - это ключ поиска для ttEntry *)    ttEntry: = transpositionTableLookup (узел) если ttEntry действителен и ttEntry.depth ≥ глубина тогда        если ttEntry.flag = ТОЧНЫЙ тогда            возвращаться ttEntry.value иначе если ttEntry.flag = НИЖНЯЯ ОСНОВА тогда            α: = max (α, ttEntry.value) иначе если ttEntry.flag = ВЕРХНИЙ тогда            β: = min (β, ttEntry.value) если α ≥ β тогда            возвращаться ttEntry.value если глубина = 0 или же узел является конечным узлом тогда        возвращаться цвет × эвристическое значение узла childNodes: = generateMoves (node) childNodes: = orderMoves (childNodes) value: = −∞ для каждого ребенок в childNodes делать        value: = max (value, −negamax (child, depth - 1, −β, −α, −color)) α: = max (α, value) если α ≥ β тогда            перемена    (* Хранилище таблиц транспозиции; узел - это ключ поиска для ttEntry *)    ttEntry.value: = значение если значение ≤ alphaOrig тогда        ttEntry.flag: = ВЕРХНЯЯ ЧАСТЬ иначе если значение ≥ β тогда        ttEntry.flag: = LOWERBOUND еще        ttEntry.flag: = ТОЧНЫЙ ttEntry.depth: = глубина transpositionTableStore (node, ttEntry) возвращаться ценить
(* Первоначальный вызов корневого узла игрока A *)negamax (корневой узел, глубина, −∞, + ∞, 1)

Отсечение альфа / бета и ограничения максимальной глубины поиска в 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.
  1. ^ а б c Брейкер, Деннис М. Память против поиска в играх, Маастрихтский университет, 16 октября 1998 г.
  2. ^ Шеффер, Джонатан Улучшения исторической эвристики и альфа-бета-поиска на практике, IEEE Transactions по анализу шаблонов и машинному интеллекту, 1989 г.

внешняя ссылка