Введение
Негамакс-поиск — это вариант алгоритма поиска минимакса, основанный на свойстве нулевой суммы в играх для двух игроков. Этот алгоритм использует тот факт, что 1 = min(a, b) = max(b, a) для упрощения реализации алгоритма минимакса. Более точно, значение позиции для игрока А в такой игре является отрицанием значения для игрока Б. Таким образом, игрок, делающий ход, ищет ход, который максимизирует отрицание значения, полученного в результате этого хода: эта дочерняя позиция по определению должна быть оценена противником. Логика, представленная в предыдущем предложении, работает независимо от того, кто из игроков – А или Б – делает ход. Это означает, что для оценки обеих позиций можно использовать одну и ту же процедуру. Это упрощает кодирование по сравнению с минимаксом, который требует, чтобы игрок А выбирал ход с дочерней позицией с максимальным значением, а игрок Б – ход с дочерней позицией с минимальным значением. Не следует путать его с алгоритмом negascout, который позволяет быстро вычислять значения минимакса или негамакса с помощью эффективного использования альфа-бета отсечения, разработанного в 1980-х годах. Следует отметить, что альфа-бета отсечение само по себе является способом быстрого вычисления значения минимакса или негамакса позиции, избегая поиска определенных неинтересных позиций. Большинство игровых движков, использующих поиск с противником, кодируются с применением той или иной формы негамакс-поиска.
Negamax search is a variant form of minimax search that relies on the zero sum property of a two player game. This algorithm relies on the fact that 1=\min(a, b) = \max( b, a) to simplify the implementation of the minimax algorithm. More precisely, the value of a position to player A in such a game is the negation of the value to player B. Thus, the player on move looks for a move that maximizes the negation of the value resulting from the move: this successor position must by definition have been valued by the opponent. The reasoning of the previous sentence works regardless of whether A or B is on move. This means that a single procedure can be used to value both positions. This is a coding simplification over minimax, which requires that A selects the move with the maximum valued successor while B selects the move with the minimum valued successor. It should not be confused with negascout, an algorithm to compute the minimax or negamax value quickly by clever use of alpha–beta pruning discovered in the 1980s. Note that alpha–beta pruning is itself a way to compute the minimax or negamax value of a position quickly by avoiding the search of certain uninteresting positions. Most adversarial search engines are coded using some form of negamax search.
Негамакс с альфа-бета-орезкой
Оптимизации алгоритма для минимакса также в равной степени применимы и к негамаксу. Альфа-бета-отсечение может уменьшить количество узлов, которые алгоритм негамакс оценивает в дереве поиска, подобно тому, как это делается с алгоритмом минимакса. Далее представлен псевдокод поиска негамаксом в глубину с альфа-бета-отсечением: оптимизация для альфа-бета-отсечения, которая пытается предсказать наиболее вероятные дочерние узлы, определяющие оценку узла. Алгоритм сначала просматривает эти дочерние узлы. Благодаря удачным предсказаниям альфа/бета-отсечения происходят раньше и чаще, что позволяет отсечь дополнительные ветви игрового дерева и оставшиеся дочерние узлы из дерева поиска.