Оригинал текста взят с http://www.xs4all.nl/~verhelst/chess/programming.html

Поиск по шахматному дереву

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

Проблема для наиболее интересных игр состоит в том, что размер этого дерева является чрезвычайно огромным, порядка W^D, где W - среднее количество ходов в позиции, а D - количество уровней дерева. Перебор всего дерева невозможен, главным образом из-за недостатка времени, даже на самых быстрых компьютерах. Все практические алгоритмы поиска являются некоторыми приближениями полного перебора.

В этом тексте дан краткий обзор традиционного минимаксного поиска с фиксированной глубиной с различными усовершенствованиями типа выборного расширения и сокращения, которые используются в современных шахматных программах. Имеются и другие, экспериментальные, методы поиска по игровому дереву, которые используют различные подходы, подобно, например, B* и метода "заветных чисел" (conspiracy numbers), которые надеюсь описать несколько позже.

Этот краткий обзор охватывает следующие темы:

Минимакс (MiniMax) и негамакс (NegaMax)
Альфа-бета отсечение (метод Брудно) (Alpha-Beta search)
Стремящийся поиск (Aspiration search)
Таблица перестановок (Transposition table)
Веер перебора (итерационное углубление, каскад) (Iterative Deepening)
Поиск с основным вариантом (Principal Variation Search)
Расширенная проверка памяти (Memory Enhanced Test)
Расширенное отсечение перестановок (Enhanced Transposition Cutoff)
Эвристика убийцы (Killer heuristic)
Эвристика истории (History heuristic)
Эвристика пустого хода (Null move heuristic)
Форсированный вариант (Quiescence search)
Выборочные продления (Selective extensions)

Различные алгоритмы поиска иллюстрированы на компактном псевдо-C. Переменные и используемые функции имеют следующее значение:

pos - позиция в шахматной игре.
depth - число уровней в дереве, которое будет просмотрено.
Evaluate -функция, которая определяет оценку позиции для стороны, которой принадлежит очередь хода. На практике такая функция будет составлена из различи в оценке материала каждой из сторон и большого количества позиционных признаков. Значение функции лежит между минус бесконечностью и плюс бесконечностью.
best - наилучшее значение, обнаруженное при просмотре следующего уровня дерева.
Successors - функция, которая определяет набор позиций, которые могут быть получены из данной в результате одного хода (генератор ходов).
succ - набор позиций, которые могут быть получены из данной в результате одного хода

Минимакс (MiniMax) и негамакс (NegaMax)

Обнаружение лучшего хода для некоторой позиции на шахматной доске заключается в поиске по дереву позиций. В корне дерева мы ищем лучшую последующую позицию для игрока, которому принадлежит очередь хода; на следующем уровне, мы ищем лучшую последующую позицию с точки зрения противника, и так далее. Поиск по шахматному дереву - чередование между максимизированием и минимизированием оценок позиций в дереве, что часто сокращенно называют минимаксингом (minimaxing). Чтобы устранить различие между собственной позицией и позицией противника, значение позиции всегда оценивается с точки зрения игрока, которому принадлежит ход, т.е. беря оценку позиции противником с противоположным знаком, что называется негамаксингом (negamaxing). Этот метод проиллюстрирован следующим C-подобным псевдокодом:

int NegaMax (pos, depth)
{
    if (depth == 0) return Evaluate(pos);
    best = -INFINITY;
    succ = Successors(pos);
    while (not Empty(succ))
    {
        pos = RemoveOne(succ);
        value = -NegaMax(pos, depth-1);
        if (value > best) best = value;
    }
    return best;
}

Число позиций, которое должно быть просмотрено этим алгоритмом - W^D, где W - ширина дерева (среднее количество ходов, возможных в каждой позиции) и D - глубина дерева (^ - означает возведение в степень). Этот метод чрезвычайно неэффективен и не позволяет даже супер-ЭВМ достичь большой глубины.

Альфа-бета отсечение (метод Брудно) (Alpha-Beta search)

Альфа-Бета отсечение - первое и главное усовершенствование для сокращения количества просматриваемых позиций, что, соответственно, позволяет достичь большей глубины за то же самое количество времени. Идея отсечения состоит в том, что в больших частях дерева мы не заинтересованы в получении точной оценки позиции, нам лишь необходимо знать, является ли она лучше или хуже той, что мы нашли прежде. Только оценка позиции основного варианта должно быть определено точно (основной вариант (principal variation) - последовательность собственных лучших ходов и лучших ходов противника от корн до нижнего уровня дерева).

Процедура поиска AlphaBeta получает два дополнительных параметра, которые указывают границы, между которыми мы заинтересованы в точных оценках позиции:

int AlphaBeta (pos, depth, alpha, beta)
{
    if (depth == 0) return Evaluate(pos);
    best = -INFINITY;
    succ = Successors(pos);
    while (not Empty(succ) && best < beta)
    {
        pos = RemoveOne(succ);
        if (best > alpha) alpha = best;
        value = -AlphaBeta(pos, depth-1, -beta, -alpha);
        if (value > best) best = value;
    }
    return best;
}

Выгода от AlphaBeta заключается в более раннем выходе из цикла while; значение best, которое равняется или превышает beta-грань, называется отсечением (cutoff). Эти отсечения полностью безопасны (корректны), потому что они гарантируют, что отсекаема часть дерева хуже чем основной вариант. Самый большой выигрыш будет достигнут, когда на каждом уровне дерева лучшая последующая позиция будет рассмотрена сначала, т.к. эта позиция будет частью основного варианта (который мы хотим обнаружить как можно раньше) или это заставит отсечению произойти как можно раньше.

При оптимальных обстоятельствах перебор с альфа-бета отсечением должен просмотреть W^((D+1)/2) + W^(D/2) - 1 позицию. Это намного меньше чем минимакс, но все еще экспоненциально. Данное отсечение позволяет достигать примерно вдвое большей глубины за то же самое врем. Большее количество позиций будет просмотрено в том случае, если при переборе не совершается упорядочение ходов.

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

Стремящийся поиск (Aspiration search)

Стремящийся поиск - маленькое усовершенствование альфа-бета поиска. Обычно запрос верхнего уровня имеет форму AlphaBeta (pos, depth, -бесконечность, +бесконечность). Стремящийся поиск заменяет ее на AlphaBeta (pos, depth, value-window, value+window), где value - оценка ожидаемого результата, и window - мера предполагаемых отклонений от этого значения.

Стремящийся поиск будет перебирать меньшее количество позиций, потому что использует alpha/beta пределы уже в корне дерева. Опасность состоит в том, что результат поиска будет выходить за пределы окна стремления (aspiration window). В этом случае потребуется повторный перебор. Хороший выбор размера окна будет, тем не менее, в среднем давать выгоду.

Таблица перестановок (Transposition table)

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

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

Таблица перестановок может экономить до фактора 4 на размере дерева и таким образом на времени поиска. Из-за экспоненциальной природы роста дерева, это приводит к тому, что возможно рассмотрение дерева примерно на один уровень глубже за то же самое врем.

Веер перебора (итерационное углубление, каскад) (Iterative Deepening)

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

Поиск с основным вариантом (Principal Variation Search)

Поиск с основным вариантом (Principal Variation Search) - разновидность альфа-бета поиска, где все узлы вне основного варианта просматриваются с минимальным альфа-бета окном, т.е. beta = alpha + 1. Иде состоит в том, что в случае хорошего упорядочения, все ходы вне основного варианта будут хуже чем основной вариант; это может быть доказано поиском с минимальным окном, переходящим нижнюю грань. Если упорядочение несовершенно, то можно столкнуться с переходом верхней грани, и в таком случае перебор должен быть сделан с полным альфа-бета окном. Ожидается, что выгода от окна минимального поиска окна будет выше, чем потер от редких повторных переборов.

Доказано ли это где-нибудь?

int PrincipalVariation (pos, depth, alpha, beta)
{
    if (depth == 0) return Evaluate(pos);
    succ = Successors(pos);
    pos = RemoveOne(succ);
    best = -PrincipalVariation(pos, depth-1, -beta, -alpha);
    while (not Empty(succ) && best < beta)
    {
        pos = RemoveOne(succ);
        if (best > alpha) alpha = best;
        value = -PrincipalVariation(pos, depth-1, -alpha-1, -alpha);
        if (value > alpha && value < beta)
            best = -PrincipalVariation(pos, depth-1, -beta, -value);
        else if (value > best)
            best = value;
    }
    return best;
}

Дальнейшая обработка этого алгоритма известна под названием нега-скаут (NegaScout, Nega-Scout). См. описание Александра Рейнфельда.

Расширенная проверка памяти (Memory Enhanced Test)

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

Расширенное отсечение перестановок (Enhanced Transposition Cutoff)

Упорядочение ходов важно в поиске по дереву, т.к. увеличивает шанс получения отсечения на первой просмотренной позиции. Это не всегда является оптимальным; могут иметься несколько позиций-сыновей, создающих отсечение, и мы хотим использовать ту, которая имеет меньшее дерево поиска. Один из испытанных способов заключается в том, чтобы просматривать все позиции-сыновья, и проверять, находятся ли они в таблице перестановок и приводят ли к отсечению. Если одна такая позиция найдена, то более не требуется никакого дальнейшего перебора. Это может экономить приблизительно 20-25% от размера дерева перебора.

Эвристика убийцы (Killer Heuristic)

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

Эвристика истории (History Heuristic)

Эвристика истории - другой метод усовершенствования для упорядочения ходов. В таблице, индексированной по статистике полей с которых совершаются ходы и полей, на которые совершаются ходы, хранится статистика хороших ходов отсечения. Эта таблица используется при упорядочивании ходов (вместе с другой информацией типа выигрыша/потерь при взятии).

Эвристика пустого хода (Null move heuristic)

Эвристика пустого хода - метод пропуска перебора в частях дерева, где позиция хороша. Последнее проверяется совершением пустого хода (т.е. отказа от всякого хода) и затем поиском с уменьшенной глубиной. Если результат этого поиска выше чем beta, то никакой дальнейший поиск не производится; если результат более низкий чем бета, то мы осуществляем нормальный поиск.
Эвристика пустого хода несет в себе большие опасности, т.к. она может быть не в состоянии обнаружить глубокую комбинацию. С другой стороны, она может сберегать много времени, пропуска большие части дерева поиска.

Форсированный вариант (Quiescence search)

Вместо вызова функции Evaluate при depth=0, обычно вызывают функцию форсированного перебора (Quiescence). Ее цель состоит в том, чтобы предотвратить эффект горизонта, когда плохой ход скрывает еще худшую угрозу из-за того, что эта угроза находится вне горизонта поиска. Это достигается тем, что окончательна оценка позиции функцией evaluate производится только в устойчивых модельно-заключительных позициях, то есть позициях, где не имеется никаких прямых угроз (например зависающих фигур, мата, превращения). Форсированный вариант не рассматривает все возможные ходы, а ограничивает себя, например, взятиями, шахами, уклонениями от шаха, и угрозами превращения. Искусство заключается в том, чтобы ограничить поиск в режиме форсированного варианта, чтобы это не привело к значительному возрастанию времени поиска. Главные дебаты возможны относительно того, лучше ли иметь еще один уровень в полном дереве перебора при риске пропустить более глубокие угрозы в форсированном варианте.

Выборочные продления (Selective Deepening)

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

Специальный случай выборочных продлений - сингулярная эвристика продления, примененная в программе Deep Thought. Идея состоит в том, чтобы обнаружить форсированные варианты за счет того, что одна из позиций-потомков имеет более значимую оценку, чем другие. Реализация весьма хитра, потому что в альфа-бета переборе точные оценки часто недоступны.

Говорят, что коммерческие шахматные программы используют частичные приращения глубины в зависимости от оценки перспективности различных ходов; высокоперспективные ходы, будучи хорошими, получают меньшее приращение глубины чем ходы, которые кажутся плохими. Я не имею никаких прямых ссылок на это; коммерческие шахматные программисты не публикуют свои методы.

© Пол Верхельст (Paul Verhelst), 1997
© Перевод с английского - С. Марков, 2000