Введение
Улучшение поиска в дереве игры AlphaBeta Основной поиск вариаций (иногда приравнивается к практически идентичному NegaScout) - это алгоритм negamax, который может быть быстрее, чем alphabeta обрезка. Как и alphabeta обрезка, NegaScout - это алгоритм направленного поиска для вычисления минимакса значения узла в дереве. Он доминирует над alphabeta-обрезкой в том смысле, что он никогда не будет изучать узел, который может быть обрезан alphabeta; однако, он полагается на точное упорядочение узлов, чтобы извлечь выгоду из этого преимущества. NegaScout работает лучше всего, когда есть хороший заказ на переезд. На практике порядок перемещения часто определяется предыдущими более мелкими поисками. Он производит больше отсеков, чем альфа-бета, предполагая, что первый исследованный узел является лучшим. Другими словами, предполагается, что первый узел находится в основной вариации. Затем он может проверить, верно ли это, просматривая оставшиеся узлы с помощью нулевого окна (также известного как окно разведки; когда альфа и бета равны), что быстрее, чем поиск с помощью обычного окна alphabeta. Если доказательство не удается, то первый узел не был в основной вариации, и поиск продолжается как нормальный альфабета. Поэтому NegaScout работает лучше всего, когда заказ переезда хорош. При случайном распоряжении движений NegaScout займет больше времени, чем обычная alphabeta; хотя он не будет исследовать какие-либо узлы, которые не были исследованы alphabeta, ему придется повторно искать многие узлы. Александр Райнефельд изобрёл NegaScout через несколько десятилетий после изобретения alphabeta обрезки. Он дает доказательство правильности NegaScout в своей книге. Другой алгоритм поиска, называемый SSS*, теоретически может привести к меньшему количеству поисковых узлов. Однако его первоначальная формулировка имеет практические проблемы (в частности, он в значительной степени полагается на открытый список для хранения), и в настоящее время большинство шахматных движков все еще используют форму NegaScout в своих поисках. Большинство шахматных систем используют таблицу транспонирования, в которой хранится соответствующая часть дерева поиска. Эта часть дерева имеет тот же размер, что и список OPEN SSS*. Переформулировка под названием MT SSS* позволила реализовать его как серию нулевых вызовов окна в AlphaBeta (или NegaScout), которые используют таблицу транспозиции, и можно было провести прямые сравнения с использованием игровых программ. На практике он не превзошел NegaScout. Еще один алгоритм поиска, который на практике имеет тенденцию работать лучше, чем NegaScout, - это лучший первый алгоритм, называемый MTD ((f), хотя ни один алгоритм не доминирует над другим. Есть деревья, в которых NegaScout ищет меньше узлов, чем SSS* или MTD{f}, и наоборот. NegaScout берет за основу SCOUT, изобретенный Джудией Перл в 1980 году, который был первым алгоритмом, который превосходил alphabeta и был асимптотически оптимальным. Нулевые окна с β=α+1 в негамаксной настройке были изобретены независимо J. P. Fishburn и использованы в алгоритме, похожем на SCOUT в приложении к его Ph. D. тезис, в параллельном алгоритме alphabeta, и на последнем поддереве корневого узла дерева поиска.
Principal variation search (sometimes equated with the practically identical NegaScout) is a negamax algorithm that can be faster than alpha–beta pruning. Like alpha–beta pruning, NegaScout is a directional search algorithm for computing the minimax value of a node in a tree. It dominates alpha–beta pruning in the sense that it will never examine a node that can be pruned by alpha–beta; however, it relies on accurate node ordering to capitalize on this advantage. NegaScout works best when there is a good move ordering. In practice, the move ordering is often determined by previous shallower searches. It produces more cutoffs than alpha–beta by assuming that the first explored node is the best. In other words, it supposes the first node is in the principal variation. Then, it can check whether that is true by searching the remaining nodes with a null window (also known as a scout window; when alpha and beta are equal), which is faster than searching with the regular alpha–beta window. If the proof fails, then the first node was not in the principal variation, and the search continues as normal alpha–beta. Hence, NegaScout works best when the move ordering is good. With a random move ordering, NegaScout will take more time than regular alpha–beta; although it will not explore any nodes alpha–beta did not, it will have to re search many nodes. Alexander Reinefeld invented NegaScout several decades after the invention of alpha–beta pruning. He gives a proof of correctness of NegaScout in his book. Another search algorithm called SSS* can theoretically result in fewer nodes searched. However, its original formulation has practical issues (in particular, it relies heavily on an OPEN list for storage) and nowadays most chess engines still use a form of NegaScout in their search. Most chess engines use a transposition table in which the relevant part of the search tree is stored. This part of the tree has the same size as SSS*'s OPEN list would have. A reformulation called MT SSS* allowed it to be implemented as a series of null window calls to Alpha–Beta (or NegaScout) that use a transposition table, and direct comparisons using game playing programs could be made. It did not outperform NegaScout in practice. Yet another search algorithm, which does tend to do better than NegaScout in practice, is the best first algorithm called MTD(f), although neither algorithm dominates the other. There are trees in which NegaScout searches fewer nodes than SSS* or MTD(f) and vice versa. NegaScout takes after SCOUT, invented by Judea Pearl in 1980, which was the first algorithm to outperform alpha–beta and to be proven asymptotically optimal. Null windows, with β=α+1 in a negamax setting, were invented independently by J. P. Fishburn and used in an algorithm similar to SCOUT in an appendix to his Ph. D. thesis, in a parallel alpha–beta algorithm, and on the last subtree of a search tree root node.
Идея
Большинство ходов неприемлемы для обоих игроков, поэтому нам не нужно полностью искать каждый узел, чтобы получить точный результат. Точный счет нужен только для узлов в основной вариации (оптимальная последовательность ходов для обоих игроков), где он будет распространяться до корня. В итеративном углубленном поиске предыдущая итерация уже установила кандидата для такой последовательности, которая также обычно называется основным вариантом. Для любого нелиста в этой основной вариации его дети перенастраиваются таким образом, что следующий узел из этой основной вариации является первым ребенком. Предполагается, что все остальные дети приводят к худшему или равному результату для текущего игрока (это предположение следует из предположения, что текущий кандидат в ПВ является фактическим ПВ). Чтобы проверить это, мы ищем первый ход с полным окном, чтобы установить верхнюю границу на балле других детей, для которых мы проводим поиск нулевого окна, чтобы проверить, может ли ход быть лучше. Поскольку поиск в нулевом окне намного дешевле из-за более высокой частоты бета-отрезок, это может сэкономить много усилий. Если мы обнаружим, что ход может повысить альфа, наше предположение было опровергнуто для этого хода, и мы выполняем поиск с полным окном, чтобы получить точный результат.