Направленный поиск

Что может представлять собой оценивающая функция? Наиболее типичным примером в шахматах является разница в суммарной силе фигур игрока и противника: присвоив каждой фигуре некоторый вес, можно оценить качество текущей позиции. Эта оценка вполне эвристична: она действительно облегчает выбор хода, но при этом вовсе не гарантирует того, что ход, приводящий к ситуации с наибольшим перевесом по фигурам, будет лучшим. Данная оценка является нестрогой, ее нельзя получить аналитически (дедуктивно). Если бы оценивающая функция позволяла непосредственно выбирать гарантированно оптимальный ход, это означало бы то, что задача не является NP-полной и для нее существует явная выигрышная стратегия без перебора вариантов.

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

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

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

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

Действительно, суть минимаксной оценки в том, что использующая ее компьютерная программа ожидает от противника наиболее сильного (причем по оценке самой программы) хода. Минимаксная оценка, на первый взгляд, может показаться единственно правильной. Однако нужно понимать, что данная оценка не является логически обоснованной и содержит элемент эвристичности. В нее заложено предположение, согласно которому противник «думает» так же, как и компьютерная программа. Это не что иное, как модель противника. При отсутствии дополнительной информации о противнике такая модель может быть принята по умолчанию. Однако она не учитывает ни стиль игры противника, ни его силу. Это наиболее ярко проявляется при игре с форой против как более сильного, так и более слабого противника. В утрированном случае компьютерная программа, давшая фору противнику и способная осуществить полный перебор, должна была бы сразу сдаться, если бы она руководствовалась минимаксной оценкой. Сейчас начинает активно развиваться область «эксплуатирования противника» (opponent exploiting), т. е. использования его уязвимостей. В рамках этой области исследуется вопрос, что нужно делать игроку, когда его противник не придерживается оптимальной (точнее, равновесной) стратегии. В частности, показано, что если сам игрок в этой ситуации будет придерживаться равновесной стратегии, то он не получит наибольшего потенциального выигрыша. Однако такж установлено, что отказ от равновесной стратегии в пользу попытки «эксплойта» не может гарантировать успех, так как сам игрок может стать объектом встречного «эксплойта». Для безопасного отказа от равновесной стратегии необходимо иметь очень надежную модель противника, что выходит далеко за рамки теории игр и эвристического программирования.

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

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

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

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

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

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

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

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

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

Одной из самых известных задач такого рода является задача коммивояжера. В этой задаче дается множество городов и указывается стоимость перемещения между каждой парой городов. Требуется найти маршрут, начинающийся и заканчивающийся в одном и том же городе и проходящий через все имеющиеся города по одному разу. Это типичная NP-полная задача. Для нее несложно построить дерево вариантов: каждый узел соответствует последовательности уже посещенных городов, а каждая из выходящих из него ветвей — перемещению в один из новых, еще не посещенных городов. Строгая оптимистическая оценка для некоторого узла складывается из стоимости уже пройденного маршрута и суммы минимальных расстояний до еще непосещенных городов.

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

Для многих задач (особенно игровых) получить точные оценки сверху и снизу для качества некоторой позиции оказывается затруднительно, в связи с этим в процедуре альфа-бета-отсечения могут использоваться и нестрогие (эвристические) оптимистические и пессимистические оценки. В этом случае нет гарантии того, что лучшее решение не будет пропущено, однако процедура альфа-бета-отсечения позволяет выбирать число отсекаемых ветвей более «интеллектуально», чем процедура n-наилучшего направленного сокращения.

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