Поиск по шахматному дереву Поиск по дереву - один из центральных алгоритмов любой игровой программы, построенной по шенноновской схеме. Смысл поиска заключается в рассмотрении всех возможных игровых позиций в виде дерева, ветви которого являются возможными ходами, а листья - всеми заключительными положениями, для которых результат игры известен.
Проблема для наиболее интересных игр состоит в том, что размер этого дерева является чрезвычайно огромным, порядка 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. Идея состоит в том, чтобы обнаружить форсированные варианты за счет того, что одна из позиций-потомков имеет более значимую оценку, чем другие. Реализация весьма хитра, потому что в альфа-бета переборе точные оценки часто недоступны.
Говорят, что коммерческие шахматные программы используют частичные приращения глубины в зависимости от оценки перспективности различных ходов; высокоперспективные ходы, будучи хорошими, получают меньшее приращение глубины чем ходы, которые кажутся плохими. Я не имею никаких прямых ссылок на это; коммерческие шахматные программисты не публикуют свои методы.
Нега-скаут (NegaScout) Подобно AlphaBeta, NegaScout - направленный алгоритм поиска для вычисления минимаксного значения узла.
NegaScout эффективнее AlphaBeta: он никогда не исследует узла, который может быть отсечен AlphaBeta.
Ни NegaScout не превосходит SSS*, ни наоборот: Существуют деревья, в которых NegaScout ищет строго меньшее количество узлов чем SSS* и наоборот. На среднестатистических деревьях, однако, SSS* обычно просматривает меньшее количество узлов чем NegaScout.
Тот же самое относится к DUAL*.
Формальные доказательства могут быть найдены в: A. Reinefeld. Spielbaum-Suchverfahren. Informatik-Fachbericht 200, Springer-Verlag, Берлин (1989), ISBN 3-540-50742-6
C-подобный код:
int NegaScout ( position p; int alpha, beta );
{ /* вычислить минимаксное значение позиции p */
 int a, b, t, i;
 determine successors p_1,...,p_w of p;
 if ( w == 0 )
 return ( Evaluate(p) ); /* лист дерева */
 a = alpha;
 b = beta;
 for ( i = 1; i <= w; i++ ) {
 t = -NegaScout ( p_i, -b, -a );
 if (t > a) && (t < beta) && (i > 1) && (d < maxdepth-1)
 a = -NegaScout ( p_i, -beta, -t ); /* повторный перебор */
 a = max( a, t );
 if ( a == beta )
 return ( a ); /* отсечение */
 b = a + 1; /* установить новое нулевое окно */
}
 return ( a );
}
ДВУХСТУПЕНЧАТЫЙ АЛГОРИТМ ПЕРЕБОРА В ШАХМАТНОЙ ПРОГРАММЕ Одной из важных проблем организации минимаксного перебора позиций в игре является выбор эвристической функции, используемой для оценки позиций в листьях дерева поиска. Сложность заключается в выборе факторов, учитываемых эвристикой. Здесь существует две крайности. С одной стороны, мы можем заложить в оценочную функцию максимальное количество формализуемых свойств позиции. В этом случае позиционная оценка станет достаточно точной, однако, скорость вычисления эвристики будет очень велика. Это приведет к тому, что программа, основанная на подобной функции, не сможет осуществить достаточно глубокий перебор вариантов. Как следствие, такая программа будет неплохо вести стратегическую, позиционную борьбу в относительно спокойных позициях, но не сможет эффективно комбинировать и наносить тактические удары в острые моменты игры.
Другая крайность - построение оценочной функции с минимумом факторов. Очевидно, что программа, основанная на такой оценочной функции, будет обнаруживать прямо противоположную слабость.
Авторами предлагается два различных подхода к разрешению вышеописанной проблемы.
Первый, заключается в отделении тактического перебора от стратегического. Вводится две оценочные функции. Первая - H1 - включает в себя только оценку материала, а также способна обнаруживать матовые или патовые ситуации. Вторая - H2 - включает в себя максимально возможное число параметров позиции.
На первом этапе перебор осуществляется при помощи функции H1. В результате этого перебора отбирается группа ходов, оценка которых не более чем на некоторую грань w отличается от наилучшего. Это значит, что если существуют ходы, ведущие в пределах горизонта перебора к мату или безвозмездному выигрышу материала, то они автоматически окажутся выбранными. Если таких ходов нет, будут отобраны ходы не приводящие к потере материала или к получению мата. Если потеря материала неизбежна, то отобранными окажутся ходы, теряющие наименьшее его количество.
Для отобранных ходов производится перебор, основанный на функции H2. Т.е. из "тактически допустимых" ходов выбирается наилучший с точки зрения стратегической оценочной функции.
Описанный метод реализован в программе SMARTHINK v0.01.
Вторым перспективным методом перебора оказывается разделение в дереве перебора материальной составляющей оценки от позиционной. Причем позиционная оценка производится только до глубины k. Если p1...pn - позиции, возникшие на k-ом уровне дерева перебора, а S(pi) - поддерево, корнем которого является позиция pi, то позиционная оценка позиции a є S(pi) принимается равной позиционной оценке pi.
Данная схема находится в стадии реализации.
ПАРАЛЛЕЛЬНЫЙ ПЕРЕБОР С ИСПОЛЬЗОВАНИЕМ TCP/IP СЕТИ НА ПРИМЕРЕ ЗАДАЧИ КОММИВОЯЖЕРА Использование мощной аппаратной базы при решении переборных задач часто позволяет добиться качественного роста эффективности, не смотря на экспоненциальную сложность большинства переборных схем.
С увеличением глубины минимаксного перебора в шахматах, шашках и других подобных играх происходит стабилизация оценки позиции. Однако разница оценок для достигнутых на сегодняшний день глубин перебора все еще остается значительной. Увеличение глубины просмотра на 2-3 полухода позволяет в большинстве случаев получить решающее преимущество. Именно этот фактор стал одним из немаловажных условий победы шахматного компьютера Deep Blue, аппаратная часть которого позволяла просматривать в одну секунду более 200 млн. позиций.
Однако, следует отметить тот факт, что создание подобной аппаратной базы с последующим ее совершенствованием приводит к значительному росту финансовых и временных затрат.
Альтернативой использованию специализированной аппаратной базы для решения переборных задач является использование распределенных, аппаратно-независимых систем. Одним из примеров такой системы является сетевая реализация алгоритма Литтла для задачи коммивояжера. Объединенные усилия машин сети позволяют обеспечить достижение огромной производительности. Причем подключение новых и модернизация старых узлов сети позволяет добиться роста производительности без внесения изменений в программную часть вычислительного комплекса.
Спецификой алгоритма Литтла для задачи коммивояжера является возможность значительного улучшения результатов за счет увеличения вычислительной мощности. Это связано с тем, что, не смотря на экспоненциальную сложность алгоритма, эффективность отсечения столь высока, что позволяет даже для больших графов (60-70 узлов) находить точные решения за приемлемое время. Для больших графов возможно нахождение приблизительных решений, отличие которых от точных весьма невелико. Для 400-500 вершин перебирая несколько десятков миллионов узлов оказывается возможным нахождение решения, отклонение которого от точного не превышает 10%.
Авторами работы реализован параллельный вариант алгоритма Литтла для вычислений в TCP/IP сети. Система основана на концепции клиент-сервер. Приложение-сервер осуществляет самостоятельный перебор решений на основе алгоритма Литтла, использующего в качестве начальной оценки путь, полученный приближенным полиномиальным алгоритмом, что позволяет достичь большей эффективности отсечения. Приложения-клиенты, подключаясь к серверу, сообщают ему о готовности начать перебор. Сервер выделяет в дереве перебора поддерево достаточной глубины и пересылает его клиенту, а затем получает от клиента результат перебора этого поддерева. Глубина поддерева выбирается с таким расчетом, чтобы:
а) клиент затратил на его обработку не менее нескольких секунд (в противном случае непозволительно возрастет нагрузка на сеть);
б) время отсечения не превысило некоторой величины, определяемой в каждом конкретном случае для конкретного графа (суть этого ограничения заключается в том, чтобы при сбое клиента потерять как можно меньше времени на повторный перебор).
Оценка, полученная клиентом, используется сервером для отсечения в ходе собственного перебора. В случае если оценка, полученная клиентом, меньше наилучшей найденной на данный момент, сервер осуществляет широковещательную рассылку этой оценки, для повышения эффективности отсечения в приложениях-клиентах.
Сервер запоминает задания, выданные клиентам, и в случае сбоя клиентов перебирает эти задания самостоятельно или же рассылает другим клиентам.
Алгоритм построен таким образом, чтобы уменьшить нагрузку на линии связи, т.к. для распределенной TCP/IP системы слабым звеном являются именно каналы связи.
Источник Также большое количество материалов на англ. языке: http://aigroup.narod.ru/texts.htm
- user online
- user offline