Анализ слепых алгоритмов. Бэктрекинг
	Если продолжить выполнение алгоритмов перебора вширь и вглубь для рассмотренного начального состояния игры в восемь (для задачи, указанной на рис.1(б)), то на глубине 5 будет найдена целевая конфигурация. При этом алгоритмом поиска вширь будет раскрыто 26 и построено 46 вершин, а алгоритмом поиска вглубь – соответственно 18 и 35 вершин.
Сравнивая в общем алгоритмы поиска вширь и вглубь, можно утверждать, что они примерно сравнимы по эффективности (количеству построенных вершин). Но в ряде случаев второй алгоритм, несмотря на свою неполноту, может оказаться предпочтительнее: если он начат с удачной стороны, то целевая вершина будет обнаружена раньше, чем в алгоритме поиска вширь.
Подчеркнем, что как и в случае перебора вширь, при переборе вглубь формируется именно дерево, а не граф перебора, даже если пространство состояний представлялось графом с циклами. В последнем случае, однако, дерево перебора может содержать дубликаты состояний. Нельзя, к примеру, исключить ситуацию, когда некие две вершины являются друг для друга дочерними, и тогда они будут многократно дублироваться в списке Open, приводя к зацикливанию алгоритма.
Чтобы избежать такого дублирования вершин, и предотвратить тем самым возможное зацикливание алгоритма в случае перебора на графах общего вида, необходимо внести некоторые очевидные изменения в описанные базовые  алгоритмы поиска вширь и вглубь..
 В алгоритме перебора вширь следует дополнительно проверять, не находится ли   каждая вновь построенная  дочерняя вершина (точнее, соответствующее описание состояния) в списках Open и Closed по той причине, что она уже строилась раньше в результате раскрытия какой-то другой вершины. Если это так, то такую вершину не надо снова помещать в список Open (таким образом разрывается цикл графа-пространства, и обрывается соответствующая ветвь дерева перебора). В алгоритме же ограниченного поиска вглубь кроме рассмотренного изменения может оказаться необходимым пересчет глубины порожденной дочерней вершины, уже имеющейся либо в списке Open, либо в списке  Closed. 
Внесенные изменения дают гарантию, что алгоритм поиска вширь всегда завершит работу в случае существования решения, а алгоритм поиска вглубь закончится в любом случае, независимо от существования решения. 
Немаловажно, что алгоритмы слепого перебора описаны нами в форме, пригодной для их программирования с использованием любого языка, не только языка программирования задач искусственного интеллекта. Алгоритм поиска вглубь демонстрирует также  способ решения поисковых задач, называемый бэктрекингом (backtracking), или режимом возвратов. Этот способ предлагает определенную организацию перебора всех возможных вариантов решения задачи, число которых может быть велико.
 Суть бэктрекинга состоит в  том, чтобы в каждой точке процесса решения, где существует несколько равноправных (априори) альтернативных путей дальнейшего продолжения, выбрать один из них и следовать ему, предварительно запомнив другие альтернативные пути – для того, чтобы в случае неуспешности выбранного пути решения вернуться в указанную точку и выбрать для продолжения поиска  следующий  альтернативный вариант-путь. В общем случае в процессе решения возможно возникновение многих подобных точек выбора (называемых развилками) со своими вариантами продолжения решения, и к каждой из точек необходимо совершать возвраты и пробовать другие варианты.
В базовом алгоритме поиска вглубь по существу проводится бэктрекинг: действительно, запоминание всех альтернатив продолжения поиска (нераскрытых вершин) осуществляется в списке Open, на шаге 3 производится выбор варианта-альтернативы, а возврат к этому шагу для выбора следующей альтернативы осуществляется  на шагах 4 и 5. 
 Некоторые языки для задач искусственного интеллекта, как, например, Пролог и Плэнер имеют специальный встроенный механизм для реализации бэктрекинга. Это означает, что запоминание развилок – самих альтернатив и связанной с ними информации, а также реализация возвратов к нужным точкам (с восстановлением всей операционной обстановки этой точки) возложены на интерпретатор языка, т.е. делается автоматически. От программиста требуется лишь определение развилок с нужными альтернативами и инициация в необходимый момент процесса возврата (заметим попутно, что язык Плэнер, в отличие от Пролога предлагает более гибкие средства управления  бэктрекингом).
В целом алгоритмы слепого перебора являются неэффективными методами поиска решения, и в случае нетривиальных задач их невозможно использовать из-за большого числа порождаемых вершин. Действительно, если L – длина решающего пути, а B – количество ветвей (дочерних вершин) у каждой вершины, то для нахождения решения надо исследовать BL  путей, ведущих из начальной вершины. Величина эта растет экспоненциально с ростом длины решающего пути, что приводит к ситуации, называемой комбинаторным взрывом. 
Таким образом, для повышения эффективности поиска необходимо использовать информацию, отражающую специфику решаемой задачи и позволяющую более целенаправленно двигаться к цели. Такая информация обычно называется эвристической, а соответствующие алгоритмы и методы – эвристическими.

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

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

Для раскрытия каждый раз в цикле выбирается наиболее перспективная концевая вершина дерева перебора. Также как и в случае алгоритмов слепого поиска множество порождаемых алгоритмом вершин и указателей образует дерево, в листьях которого находятся нераскрытые вершины.
 Предполагаем, что исследуемое алгоритмом пространство состояний представляет собой дерево. Тогда основные шаги алгоритма эвристического перебора (best_first_search) таковы:
Шаг 1. Поместить начальную вершину в список нераскрытых вершин Open и вычислить ее оценку.
Шаг 2. Если список Open пуст, то окончание алгоритма и выдача сообщения о неудаче поиска, в противном случае перейти к шагу 3.
Шаг 3. Выбрать из списка Open вершину с минимальной оценкой (среди вершин с одинаковой минимальной оценкой выбирается любая); перенести эту вершину (назовем ее Current) в список Closed.
Шаг 4. Если Current – целевая вершина, то окончание алгоритма и выдача решения задачи, получающегося просмотром указателей от нее к начальной вершине, в противном случае перейти к следующему шагу.
Шаг 5. Раскрыть вершину Current, построив все ее дочерние вершины. Если таких вершин нет, то перейти к шагу 2, в ином случае – к шагу 6.
Шаг 6. Для каждой дочерней вершины вычислить оценку (значение оценочной функции), поместить все дочерние вершины в список Open, и построить указатели, ведущие от этих вершин к родительской вершине Current. Перейти к шагу 2.
Конец алгоритма.
	Заметим, что поиск в глубину можно рассматривать как частный случай упорядоченного поиска с оценочной функцией Est(V) = d(V) , а поиск в ширину – с функцией Est(V) = 1/d(V) , где d(V) – глубина вершины V.
Чтобы модифицировать рассмотренный алгоритм для перебора на произвольных графах-пространствах состояний, необходимо предусмотреть в нем реакцию на случай построения дочерних вершин, которые уже имеются либо в списке раскрытых, либо в списке нераскрытых вершин.
	Если оценочная функция учитывает только внутренние   характеристики вершин-состояний, то для предотвращения зацикливания требуется достаточно простая модификация алгоритма – надо просто исключить  дублирование состояний в списках Open и Closed.
Проиллюстрируем работу алгоритма эвристического поиска опять же на примере игры в восемь для той же начальной ситуации. Воспользуемся в качестве оценочной следующей простой функцией:
Est1(V) = d(V) + k(V)   , где
d(V) – глубина вершины V, или число ребер дерева на пути от этой вершины к начальной вершине;
k(V) – число фишек позиции-вершины V, стоящих не на «своем» месте (фишка стоит не на «своем» месте, если ее позиция отлична от позиции в целевом состоянии).
На рис. 6 показано дерево, построенное алгоритмом эвристического перебора с указанной оценочной функцией. Оценка каждой вершины приведена рядом с ней внутри кружка. Отдельно стоящие цифры, как и раньше, показывают порядок, в котором строились вершины. Двойной рамкой обведена найденная целевая вершина, она построена двенадцатой.
Видно, что поскольку каждый раз выбор вершины с минимальной оценкой производится внутри всего построенного к текущему моменту дерева перебора, то раскрываемые друг за другом  вершины могут располагаться в отдаленных друг от друга частях дерева. Применяемая оценочная функция такова, что при прочих равных преимущество имеет менее глубокая вершина.
Решение задачи длиною в пять ходов найдено в результате раскрытия 6  и построения 13 вершин – это существенно меньше, чем при использовании слепого перебора (соответствующие числа были: 26 и 46, 18 и 35). Таким образом, использование эвристической информации приводит к существенному сокращению перебора. 
Существует несколько критериев оценки качества работы алгоритмов перебора. Один из них называется целенаправленностью и вычисляется как P = L / N , где
L – длина найденного пути до цели (она равна глубине целевой вершины), а
N – общее число вершин, построенных в ходе перебора.
P = 1, если  строятся только вершины решающего пути, в остальных случаях P < 1, вообще, эта величина тем меньше, чем больше строится бесполезных вершин. Таким образом, этот критерий показывает, насколько дерево, построенное при переборе, вытянуто, а не кустисто. К сожалению, величина P зависит от длины решающего пути, что затрудняет порой сравнение алгоритмов. Другой критерий оценки, фактор эффективного ветвления, зависит от длины решающего пути гораздо меньше.

Ясно, что алгоритм эвристического поиска с хорошо подобранной оценочной функцией обнаруживает решение задачи быстрее алгоритмов слепого перебора. Однако подбор удачной функции, существенно сокращающей поиск, – наиболее трудный момент при формализации задачи.
 Принято сравнивать различные оценочные функции для одной и той же задачи по их эвристической силе, т.е. по тому, насколько они убыстряют поиск, делают его эффективным. Заметим, что  эвристическая сила функции должна учитывать общий объем вычислительных затрат при поиске, поэтому кроме числа раскрытых и построенных вершин важен и такой фактор, как сложность вычисления самой оценочной функции. 
Для игры в восемь можно предложить еще одну эвристическую функцию:     
                          Est2(V) = d(V) + s(V)  .
Первое слагаемое d(V) этой функции имеет тот же смысл, что и для функции Est1. Второе слагаемое получается, если для каждой из восьми фишек подсчитать сумму  двух  расстояний – по вертикали и горизонтали – между клетками, где находится эта фишка в оцениваемом  и целевом состояниях, а затем подсчитать общую сумму s(V)  таких расстояний для всех восьми фишек (тем самым получим «суммарное расстояние» всех фишек от их целевого положения). 

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

переборную работу (и решение задачи может искаться даже дольше, чем с использованием слепого метода), либо вовсе не может обеспечить обнаружение решающего пути.      
	Математическое исследование алгоритма эвристического поиска – условий, гарантирующих нахождение им решения – было проведено для эвристических оценочных функций специального вида и для более сложной задачи, чем до сих пор рассматриваемая задача поиска любого решающего пути до целевой вершины. 
Предположим, что на множестве дуг пространства состояний определена функция стоимости:
с(VA, VB) – стоимость дуги-перехода от вершины VA к  вершине VB . 
Определим также стоимость любого пути в графе-пространстве как сумму стоимостей входящих в путь дуг. Пусть целью поиска будет не просто нахождение решающего пути, а нахождение оптимального решающего пути – решающего пути с минимальной стоимостью.
	Предположим также, что эвристическая оценочная функция Est(V) построена таким образом, чтобы оценивать стоимость оптимального решающего пути, идущего из начальной вершины к одной из целевой вершин, при условии, что этот путь проходит через вершину V. Тогда значение оценочной функции можно представить в виде суммы двух слагаемых:
	Est(V) = g(V) + h(V)		(*)
где   g(V) – оценка оптимального пути от начальной вершины до вершины V,
а   h(V) – оценка оптимального пути от вершины V до целевой вершины.
Если в процессе поиска уже построена вершина V, то путь до нее найден, и его стоимость может быть вычислена. Найденный путь не обязательно оптимален (возможно, существует более дешевый, еще не найденный путь из начальной вершины в V), однако стоимость найденного пути может быть использована в качестве оценки искомого пути минимальной стоимости из начальной вершины до V, т.е. в качестве первого слагаемого g(V)  эвристической функции. Второе же слагаемое h(V) может быть предложено исходя из эвристических соображений, свойственных конкретной решаемой задаче, как некоторая характеристика-оценка текущей вершины V (близости ее к цели). Таким образом, собственно эвристическая информация будет воплощена только во втором слагаемом оценочной функции.  
Вариант алгоритма эвристического поиска, применяемого для поиска оптимального решающего пути и использующего при этом оценочную функцию указанного выше вида (*), известен в литературе как А-алгоритм. Были доказаны важные свойства этого алгоритма, прежде всего, утверждение о его  допустимости.
Алгоритм перебора называют допустимым (или состоятельным), если для произвольного графа он всегда заканчивает свою работу построением оптимального пути к цели, при условии, что такой путь существует.
Пусть h*(V) – стоимость оптимального пути из произвольной вершины V в целевую вершину. 	Верна следующая теорема о допустимости А-алгоритма:
    А-алгоритм, использующий некоторую эвристическую функцию вида (*), где 
g(V) – стоимость пути от начальной вершины до вершины V в дереве перебора, а
h(V) – эвристическая оценка оптимального пути из вершины V в целевую вершину,
является допустимым, если 	h(V)  h*(V)    для всех вершин V пространства состояний. 
А-алгоритм эвристического поиска, применяющий функцию h(V), удовлетворяющую этому условию, получил название А*-алгоритма.
	Практическое значение этой теоремы в том, что для допустимости А-алгоритма достаточно найти какую-либо нижнюю грань функции h*(V) и использовать ее в качестве h(V) – тогда оптимальность найденного алгоритмом решения будет гарантирована.
Если взять тривиальную нижнюю грань, т.е. установить h(V) = 0 для всех вершин пространства состояний, то допустимость будет обеспечена. Однако этот случай соответствует полному отсутствию какой-нибудь эвристической информации о задаче, и оценочная функция Est не имеет никакой эвристической силы, т.е. не сокращает возникающий перебор. А*-алгоритм ведет себя при этом аналогично поиску вширь. 
Точнее, при 	Est(V) = g(V) (где g(V) – стоимость пути от начальной вершины до вершины V ), мы получаем алгоритм, известный как алгоритм равных цен (или Алгоритм Дейкстры). Алгоритм равных цен представляет собой более общий вариант метода перебора в ширину, при котором вершины раскрываются в порядке возрастания стоимости g(V) , т.е. в первую очередь раскрывается вершина из списка нераскрытых вершин, для которой величина g имеет наименьшее значение.
	Если же, кроме того, положить стоимость с(VA, VB) = 0 для всех дуг пространства состояний, то А*-алгоритм просто превращается в неэффективный слепой поиск вширь.
Обе предложенные для игры в восемь эвристические функции Est1(V) и Est2(V) удовлетворяют условию допустимости А*-алгоритма. Первое их слагаемое d(V) есть стоимость пути к вершине V при 

стоимости всех дуг с(VA, VB) = 1. Функции отличаются лишь вторым слагаемым, и можно показать, что значение второй функции  всегда (т.е. для всех состояний), больше значения первой функции:	Est1(V)   Est2(V)  , что равнозначно  k (V)  s (V)  .
Действительно, во второй функции вклад каждой фишки в общую оценку-сумму s(V)  либо равен 0 (фишка стоит уже на «своем» месте), либо не меньше 1 (в противном случае), в первой же функции этот вклад в k(V) соответственно либо равен 0, либо  равен 1. 
Из последнего неравенства следует, что условие допустимости достаточно доказать только для второй функции Est2. Справедливость нужного условия  
s(V)  h*(V) следует из следующего соображения. Если бы фишки не мешали друг другу и могли двигаться до «своего» места по кратчайшему пути, как если бы других фишек на квадрате не было, то сумма длин таких путей для всех фишек была бы в точности равна значению s(V) . На самом же деле фишки редко когда могут двигаться по кратчайшей траектории из-за того, что на ней расположены другие фишки, поэтому длина (стоимость) оптимального решения h*(V) будет не меньше s(V).
	Заметим, что s(V) не учитывает должным образом трудность обмена местами двух соседних фишек, а поэтому ее эвристическая сила в принципе может быть повышена. В ряде случаев эвристическая сила некоторой оценочной функции может быть повышена просто путем умножения на положительную константу, большую единицы, однако часто такое повышение осуществимо только за счет отказа от допустимости алгоритма. Например, если для игры в восемь в качестве второй составляющей эвристической функции взять h(V) = 2s(V), то в ряде случаев такая функция будет убыстрять поиск и позволит решать более трудные задачи, но условие допустимости перестанет выполняться (так как для начального состояния на рис. 6:  h*(V)  2s(V) ).
	Вообще в случае, когда верно неравенство h1(V)  h2(V) для всех вершин пространства состояний, не являющихся целевыми, А*-алгоритм, использующий эвристическую составляющую h2(V), называется более информированным, чем А*-алгоритм с функцией h1(V). Показано, что если эти функции статичны (т.е. не изменяются в процессе поиска), то более информированный алгоритм раскрывает всегда меньшее число вершин, прежде чем находит путь минимальной стоимости. Это значит, что более информированный алгоритм осуществляет более направленный, а значит, более эффективный (при прочих равных) поиск целевой вершины. Таким образом, понятие информированности отражает один из аспектов понятия эвристической силы оценочной функции при поиске в пространстве состояний.
	Итак, желательно подобрать такую эвристическую функцию h(V), которая была бы нижней границей h*(V) (чтобы гарантировать допустимость алгоритма) и была бы как можно ближе к h*(V) (чтобы обеспечить эффективность поиска). К сожалению, существуют задачи, для которых нельзя найти оценочную функцию, обеспечивающую во всех случаях как эффективность, так и допустимость эвристического поиска. Поэтому часто приходится останавливаться на эвристических функциях, сокращающих поиск во многих случаях ценой отказа от гарантии найти оптимальный решающий путь.
Заметим, что в идеальном случае, когда известна оценка h*(V), и она используется в качестве h(V), А*-алгоритм находит оптимальный решающий путь сразу, без раскрытия ненужных вершин.

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

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

Деревья игры. Поиск выигрышной стратегии
Будем рассматривать класс игр двух лиц с полной информацией. В таких играх участвуют два игрока, которые поочередно делают свои ходы. В любой момент игры каждому игроку известно все, что произошло в игре к этому моменту и что может быть сделано в настоящий момент. Игра заканчивается либо выигрышем одного игрока (и проигрышем другого), либо ничьей. 
Таким образом, в рассматриваемый класс не попадают игры, исход которых зависит хотя бы частично от случая  большинство карточных игр, игральные кости, «морской бой» и проч. Тем не менее класс достаточно широк: в него входят такие игры, как шахматы, шашки, реверси, калах, крестики-нолики и другие игры. 
Для формализации и изучения игровых стратегий в классе игр с полной информацией может быть использован подход, основанный на редукции задач. Напомним, что при этом должны быть определены следующие составляющие: форма описания задач и подзадач; операторы, сводящие задачи к подзадачам; элементарные задачи; а также задано описание исходной задачи.
Наиболее интересной представляется задача поиска выигрышной стратегии для одного из игроков, отправляясь от некоторой конкретной конфигурации (позиции) игры (не обязательно начальной). При использовании подхода, основанного на редукции задач, выигрышная стратегия ищется  в процессе доказательства того, что игра может быть выиграна. Аналогично, поиск ничейной стратегии, исходя из некоторой конкретной позиции, ведется в процессе доказательства  того, что игра может быть сведена к ничьей.
Ясно, что описание решаемой задачи должно содержать описание конфигурации игры, для которой ищется нужная стратегия. Например, в шашках игровая позиция включает задание  положений на доске всех шашек, в том числе дамок. Обычно описание конфигурации содержит также указание, кому принадлежит следующий ход.
Пусть именами игроков будут ПЛЮС и МИНУС. Будем использовать следующие обозначения:
XS или YS  некоторая конфигурация игры, причем индекс S принимает значения  + или , указывая тем самым, кому принадлежит следующий ход (т.е. в конфигурации X+ следующий ход должен делать игрок ПЛЮС, а в X – игрок МИНУС);
W(XS)  задача доказательства того, что игрок ПЛЮС может выиграть, исходя из конфигурации XS;
V(XS)  задача доказательства того, что игрок МИНУС может выиграть, отправляясь от конфигурации XS.
Рассмотрим сначала игровую задачу W(XS). Операторы сведения  (редукции) этой задачи к подзадачам определяются исходя из ходов, допустимых в проводимой игре:
• Если в некоторой конфигурации X+ очередной ход делает игрок ПЛЮС, и имеется N допустимых ходов, приводящих соответственно к конфигурациям X1, X2, . . . XN , то для решения задачи W(X+) необходимо решить по крайней мере одну из подзадач W(Xi). Действительно, так как ход выбирает игрок ПЛЮС, то он выиграет игру, если хотя бы один из ходов ведет к выигрышу  см. рис. 1(а).
• Если же в некоторой конфигурации Y ход должен сделать игрок МИНУС, и имеется K допустимых ходов, приводящих к конфигурациям Y1+ , Y2+ , . . . YK+, то для решения задачи W(Y) требуется решить каждую из возникающих подзадач W(Yi+). Действительно, поскольку ход выбирает МИНУС, то ПЛЮС выиграет игру, если выигрыш гарантирован ему после любого хода противника  см. рис. 1(б).

Последовательное применение данной схемы редукции к исходной конфигурации игры порождает И/ИЛИ-дерево (И/ИЛИ-граф), которое называют деревом (графом) игры. Дуги игрового дерева соответствуют ходам игроков, вершины  конфигурациям игры, причем листья дерева  это позиции, в которых игра завершается выигрышем, проигрышем или ничьей. Часть листьев являются заключительными вершинами, соответствующими элементарным задачам  позициям, выигрышным для игрока ПЛЮС. Заметим, что для конфигураций, где ход принадлежит ПЛЮСу, в игровом дереве получается ИЛИ-вершина, а для позиций, в которых ходит МИНУС, получается И-вершина.
Цель построения игрового дерева или графа  получение решающего поддерева для задачи W(XS), показывающего, как игрок ПЛЮС может выиграть игру из позиции XS независимо от ответов противника. Для этого могут быть применены разные алгоритмы поиска на И/ИЛИ-графах. Решающее дерево заканчивается на позициях, выигрышных для ПЛЮСа, и содержит полную стратегию достижения им выигрыша: для каждого возможного продолжения игры, выбранного противником, в дереве есть ответный ход, приводящий к победе.
Для задачи V(XS) схема сведения игровых задач к подзадачам аналогична: ходам игрока ПЛЮС будут соответствовать И-вершины, а ходам МИНУСа  ИЛИ-вершины, заключительные же вершины будут соответствовать позициям, выигрышным для игрока МИНУС.
Конечно, подобная редукция задач применима и в случае, когда нужно доказать существование ничейной стратегии в игре. При этом определение  элементарной задачи должно быть соответствующим образом изменено.
Рассмотрим в качестве иллюстрации простую игру, называемую «последний проигрывает». Два игрока поочередно берут по одной или две монеты из кучки, первоначально содержащей семь монет. Игрок, забирающий последнюю монету, проигрывает. 
На рис. 2 показан полный граф игры для задачи V(7+), жирными дугами на нем выделен решающий И/ИЛИ-граф, который доказывает, что второй игрок (т.е. игрок МИНУС, начинающий вторым), всегда может выиграть. Конфигурация игры описана как число оставшихся в текущий момент монет, также указание, кому принадлежит следующий ход. Заключительные вершины, соответствующие элементарной задаче V(1+), т.е. выигрышу игрока МИНУС, в графе подчеркнуты. 
Представленная в решающем графе выигрышная стратегия может быть сформулирована словесно так: если в очередном ходе игрок ПЛЮС берет одну монету, то в следующем ходе МИНУС должен взять две, а если ПЛЮС берет две монеты, то МИНУС должен забрать одну. Отметим, что для аналогичной задачи W(7+) решающий граф построить не удастся (начальная вершина неразрешима); таким образом, у игрока ПЛЮС нет выигрышной стратегии в этой игре.

В большинстве игр, представляющих интерес, таких как шашки и шахматы, построить полные решающие деревья и найти полные игровые стратегии не представляется возможным. Например, для шашек число вершин в полном игровом дереве оценивается величиной порядка 1040, и просмотреть такое дерево практически нереально. Алгоритмы же упорядоченного перебора с применением эвристик не настолько уменьшают просматриваемую часть дерева игры, чтобы дать существенное, на несколько порядков, сокращение времени поиска.
Тем не менее для неполных игр в шашки и шахматы (например, для эндшпилей), так же как и для всех несложных игр, таких как  «крестики-нолики» на фиксированном квадрате небольшого размера, можно успешно применять алгоритмы поиска на И/ИЛИ-графах, позволяющие обнаруживать выигрышные и ничейные игровые стратегии.
Рассмотрим, к примеру, игру «крестики-нолики» на квадрате 33. Игрок ПЛЮС ходит первым и ставит крестики, а МИНУС  нолики. Игра заканчивается, когда составлена либо строка, либо столбец, либо диагональ из крестиков (в этом случае выигрывает ПЛЮС) или ноликов (выигрывает МИНУС). Оценим размер полного дерева игры: начальная вершина имеет 9 дочерних вершин, каждая из которых в свою очередь  8 дочерних; каждая вершина глубины 2 имеет 7 дочерних и т.д. Таким образом, число концевых вершин в дереве игры равно 9!=362880, но многие пути в этом дереве обрываются раньше на заключительных вершинах. Значит, в этой игре возможен полный просмотр дерева и нахождение выигрышной стратегии. Однако ситуация изменится при существенном увеличении размеров квадрата или же в случае неограниченного поля игры.
В таких случаях, как и во всех сложных играх вместо нереальной задачи поиска полной игровой стратегии решается, как правило, более простая задача  поиск для заданной позиции игры достаточно хорошего первого хода. 

Минимаксная процедура
С целью поиска достаточно хорошего первого хода просматривается обычно часть игрового дерева, построенного от заданной конфигурации. Для этого применяется один из переборных алгоритмов (в глубину, в ширину или эвристический) и некоторое искусственное окончание перебора вершин в игровом дереве: например, ограничивается время перебора или же глубина поиска.
В построенном таким образом частичном дереве игры оцениваются вершины, и по полученным оценкам определяется наилучший ход от заданной игровой конфигурации. При этом для оценивания концевых вершин (листьев) полученного дерева используется так называемая статическая оценочная функция, а для оценивания остальных вершин – корневой (начальной) и промежуточных между корневой и концевыми вершинами – используется так называемый минимаксный принцип.
Статическая оценочная функция, будучи применена к некоторой вершине-конфигурации игры, дает числовое значение, оценивающее различные достоинства этой игровой позиции. Например, для шашек могут учитываться такие (статические) элементы конфигурации игры, как продвинутость и подвижность шашек, количество дамок, контроль ими центра и проч. По сути, статическая функция вычисляет эвристическую оценку шансов на выигрыш одного из игроков. Для определенности будем рассматривать задачу выигрыша игрока ПЛЮС и соответственно поиска достаточно хорошего его первого хода от заданной конфигурации.
Будем придерживаться общепринятого соглашения, по которому значение статической оценочной функции тем больше, чем больше преимуществ имеет игрок ПЛЮС (над игроком МИНУС) в оцениваемой позиции. Очень часто оценочная функция выбирается следующим образом:
•статическая оценочная функция положительна в игровых конфигурациях, где  игрок ПЛЮС имеет преимущества;
•статическая оценочная функция отрицательна в конфигурациях, где МИНУС имеет преимущества;
•статическая оценочная функция близка к нулю в позициях, не дающих преимущества ни одному из игроков.
Например, для шашек в качестве простейшей статической функции может быть взят перевес в количестве шашек (и дамок) у игрока ПЛЮС. Для игры «крестики-нолики» на фиксированном квадрате возможна такая статическая оценочная функция:
   +		если P есть позиция выигрыша игрока ПЛЮС
E(P) =  	   		если P есть позиция выигрыша МИНУСа
  (NL+ +NC+ +ND+ )(NL +NC +ND) 	в остальных случаях
где 	+  очень большое положительное число;
  очень маленькое отрицательное число;
NL+, NC+, ND+   соответственно число строк, столбцов и диагоналей, «открытых» для игрока ПЛЮС (т.е. где он еще может поставить три выигрышных крестика подряд),
а   NL, NC, ND  аналогичные числа для игрока МИНУС. 
На рис. 3 приведены две игровые позиции (на квадрате 44) и соответствующие значения статической оценочной функции.

Подчеркнем, что с помощью статической оценочной функции оцениваются только концевые вершины дерева игры, для оценок же промежуточных вершин, как и начальной вершины, используется минимаксный принцип, основанный на следующей простой идее. Если бы игроку ПЛЮС пришлось бы выбирать один из нескольких возможных ходов, то он выбрал бы наиболее сильный ход, т.е. ход, приводящий к позиции с наибольшей оценкой. Аналогично, если бы игроку МИНУС пришлось бы выбирать ход, то он выбрал бы ход, приводящий к позиции с наименьшей оценкой. 
Сформулируем теперь сам минимаксный принцип:
• ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин;
• И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин.
Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определения наилучшего (более точно, достаточно хорошего) хода игрока исходя из заданной конфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, что игрок ПЛЮС ходит первым (т.е. начальная вершина есть ИЛИ-вершина). Основные этапы этой процедуры таковы:
4.1 Дерево игры строится (просматривается) одним из известных алгоритмов перебора (как правило, алгоритмом поиска вглубь) от исходной позиции S до глубины N;
4.1.Все концевые вершины полученного дерева, т.е. вершины, находящиеся на глубине N, оцениваются с помощью статической оценочной функции;
4.2.В соответствии с минимаксным принципом вычисляются оценки всех остальных вершин: сначала вычисляются оценки вершин, родительских для концевых, затем родительских для этих родительских вершин и так далее; таким образом оценивание вершин происходит при движении снизу вверх по дереву поиска  до тех пор, пока не будут оценены вершины, дочерние для начальной вершины, т.е. для исходной конфигурации S;
4.3.Среди вершин, дочерних к начальной, выбирается вершина с наибольшей оценкой: ход, который к ней ведет, и есть искомый наилучший ход в игровой конфигурации S.

На рис. 4 показано применение минимаксной процедуры для дерева игры, построенного до глубины N=3. Концевые вершины не имеют имен, они обозначены своими оценками  значениями статической оценочной функции. Числовые индексы имен остальных вершин показывают порядок, в котором эти вершины строились алгоритмом перебора вглубь. Рядом с этими вершинами находятся их минимаксные оценки, полученные при движении в обратном (по отношению к построению дерева) направлении. Таким образом, наилучший ход – первый из двух возможных.
На рассматриваемом игровом дереве выделена ветвь (последовательность ходов игроков), представляющая так называемую минимаксно-оптимальную игру, при которой каждый из игроков всегда выбирает наилучший для себя ход. Заметим, что оценки всех вершин этой ветви дерева совпадают, и оценка начальной вершины равна оценке концевой вершины этой ветви.
В принципе статическую оценочную функцию можно было бы применить и к промежуточным вершинам, и на основе этих оценок осуществить выбор наилучшего первого хода, например, сразу выбрать ход, максимизирующий значение статической оценочной функции среди вершин, дочерних к исходной. Однако считается, что оценки, полученные с помощью минимаксной процедуры, есть более надежные меры относительного достоинства промежуточных вершин, чем оценки, полученные прямым применением статической оценочной функции. Действительно, минимаксные оценки основаны на просмотре игры вперед и учитывают разные особенности, которые могут возникнуть в последующем, в то время как простое применение оценочной функции учитывает лишь свойства позиции как таковой. Это отличие статических и минимаксных оценок существенно для «активных», динамичных позиций игры (например, в шашках и шахматах к ним относятся конфигурации, в которых возникает угроза взятия одной или нескольких фигур). В случае же так называемых «пассивных», спокойных позиций статическая оценка может мало отличаться от оценки по минимаксному принципу.

Альфа-бета процедура
Минимаксная процедура организована таким образом, что процесс построения частичного дерева игры отделен от процесса оценивания вершин. Такое разделение приводит к тому, что в целом минимаксная процедура  неэффективная стратегия поиска хорошего первого хода. Чтобы сделать процедуру более экономной, необходимо вычислять статические оценки концевых вершин и минимаксные оценки промежуточных вершин одновременно с построением игрового дерева. Этот путь приводит к так называемой альфа-бета процедуре поиска наилучшего первого хода от заданной позиции, при этом можно добиться существенного сокращения вычислительных затрат, прежде всего, времени вычисления статических оценок. В основе сокращения поиска лежит достаточно очевидное соображение: если есть два варианта хода одного игрока, то худший в ряде случаев можно сразу отбросить, не выясняя, насколько в точности он хуже.
Рассмотрим сначала идею работы альфа-бета процедуры на примере игрового дерева, приведенного на рис. 4. Дерево игры строится до глубины N=3 алгоритмом перебора вглубь. Причем сразу, как это становится возможным, вычисляются не только статические оценки концевых вершин, но и предварительные минимаксные оценки промежуточных вершин. Предварительная оценка определяется соответственно как минимум или максимум уже известных к настоящему моменту оценок дочерних вершин. В общем случае, эта оценка может быть получена при наличии оценки хотя бы одной дочерней вершины. В ходе дальнейшего построения дерева игры и получения новых оценок вершин предварительные оценки постепенно уточняются, опять же по минимаксному принципу.
Пусть таким образом построены вершины W1,  W2+ и первые три конечные вершины (листья)  см. рис. 5. Эти листья оценены статической функцией, и вершина W2+ получила точную минимаксную оценку 3, а вершина W1  предварительную оценку 3. Далее при построении и раскрытии вершины W3+ статическая оценка первой ее дочерней вершины дает величину 4, которая становится предварительной оценкой самой вершины W3+. Эта предварительная оценка будет потом, после построения второй ее дочерней вершины, пересчитана. Причем согласно минимаксному принципу оценка может только увеличиться (поскольку подсчитывается как максимум оценок дочерних вершин), но даже если она увеличится, это не повлияет на оценку вершины W1, поскольку последняя при уточнении по минимаксному принципу может только уменьшаться (так как равна минимуму оценок дочерних вершин). Следовательно, можно пренебречь второй дочерней вершиной для W3+, не строить и не оценивать ее, поскольку уточнение оценки вершины W3+ не повлияет на оценку вершины W1. Такое сокращение поиска в игровом дереве называется отсечением ветвей.

Продолжим для нашего примера процесс поиска в глубину с одновременным вычислением предварительных (и точных, где это возможно) оценок вершин вплоть до момента, когда построены уже вершины W4 , W5+ и две дочерних последней, которые оцениваются статической функцией. Исходя из оценки первой дочерней вершины начальная вершина W0+, соответствующая исходной позиции игры, к этому моменту уже предварительно оценена величиной 3. Вершина W5+ получила точную минимаксную оценку 3, а ее родительская W4 получила пока только предварительную оценку 3. Эта предварительная оценка вершины W4может быть уточнена в дальнейшем, и в соответствии с минимаксным принципом возможно только ее уменьшение, но это уменьшение не повлияет на оценку вершины W0+, поскольку последняя, опять же согласно минимаксному принципу, может только увеличиваться. Таким образом, построение дерева можно прервать ниже вершины W4, отсекая целиком выходящие из нее вторую и третью ветви (и оставляя ее оценку предварительной).
На этом построение игрового дерева заканчивается, полученный результат  лучший первый ход  тот же самый, что и при минимаксной процедуре. У некоторых вершин дерева осталась неуточненная, предварительная оценка, однако этих приближенных оценок оказалось достаточно для того, чтобы определить точную минимаксную оценку начальной вершины и наилучший первый ход. В то же время произошло существенное сокращение поиска: вместо 17 вершин построено только 11, и вместо 10 обращений к статической оценочной функции понадобилось всего 6.
Обобщим рассмотренную идею сокращения перебора. Сформулируем сначала правила вычисления оценок вершин дерева игры, в том числе предварительных оценок промежуточных вершин, которые для удобства будем называть альфа- и бета-величинами:
4.2 концевая вершина игрового дерева оценивается статической оценочной функцией сразу, как только она построена;
4.3 промежуточная вершина предварительно оценивается по минимаксному принципу, как только стала известна оценка хотя бы одной из ее дочерних вершин; каждая предварительная оценка пересчитывается (уточняется) всякий раз, когда получена оценка еще одной дочерней вершины;
4.4 предварительная оценка ИЛИ-вершины (альфа-величина) полагается равной наибольшей из вычисленных к текущему моменту оценок ее дочерних вершин;
4.5 предварительная оценка И-вершины (бета-величина) полагается равной наименьшей из вычисленных к текущему моменту оценок ее дочерних вершин.
	Укажем очевидное следствие этих правил вычисления: альфа-величины не могут уменьшаться, а бета-величины не могут увеличиваться.
	Сформулируем теперь правила прерывания перебора, или отсечения ветвей игрового дерева:.
4.6   Перебор можно прервать ниже любой И-вершины, бета-величина которой не больше, чем альфа-величина одной из предшествующих ей ИЛИ-вершин (включая корневую вершину дерева);
4.7  Перебор можно прервать ниже любой ИЛИ-вершины, альфа-величина которой не меньше, чем бета-величина одной из предшествующих ей И-вершин.
При этом в случае А говорят, что имеет место альфа-отсечение, поскольку отсекаются ветви дерева, начиная с ИЛИ-вершин, которым приписана альфа-величина, а в случае В  бета-отсечение, поскольку отсекаются ветви, начинающиеся с бета-величин). 
	Важно, что рассмотренные правила работают в ходе построения игрового дерева вглубь; это означает, что предварительные оценки промежуточных вершин появляются лишь по мере продвижения от концевых вершин дерева вверх к корню и реально отсечения могут начаться только после того, как получена хотя бы одна точная минимаксная оценка промежуточной вершины.
	В рассмотренном примере на рис. 5 первое прерывание перебора было бета-отсечением, а второе  альфа-отсечением. Причем в обоих случаях отсечение было неглубоким, поскольку необходимая для соблюдения соответствующего правила отсечения альфа- или бета-величина находилась в непосредственно предшествующей к точке отсечения вершине. В общем же случае она может находиться существенно выше отсекаемой ветви – где-то на пути от вершины, ниже которой производится отсечение, к начальной вершине дерева, включая последнюю.
	После прерывания перебора предварительные оценки вершин в точках отсечения остаются неуточненными, но, как уже отмечалось, это не препятствует правильному нахождению предварительных оценок всех предшествующих вершин, как и точной оценки корневой вершины и ее дочерних вершин, а значит, и искомого наилучшего первого хода.
На приведенных выше правилах вычисления оценок вершин и выполнения отсечений (всюду, где это возможно) основана альфа-бета процедура, являющаяся более эффективной реализацией минимаксного принципа. В принципе, используя математическую индукцию и рассуждая аналогично рассмотренному примеру, несложно доказать следующее
Утверждение:
Альфа-бета процедура всегда приводит к тому же результату (наилучшему первому ходу), что и простая минимаксная процедура той же глубины.
	Важным является вопрос, насколько в среднем альфа-бета процедура эффективнее обычной минимаксной процедуры. Нетрудно заметить, что количество отсечений в альфа-бета процедуре зависит от степени, в которой предварительные оценки (альфа- и бета-величины), полученные первыми, аппроксимируют окончательные минимаксные оценки: чем ближе эти оценки, тем больше отсечений и меньше перебор. Это положение иллюстрирует пример на рис. 5, в котором ветвь дерева с минимаксно-оптимальной игрой строится практически в самом начале поиска.
Таким образом, эффективность альфа-бета процедуры зависит от порядка построения и раскрытия вершин в дереве игры. Возможен и неудачный порядок просмотра, при котором придется пройти без отсечений через все вершины дерева, и в этом, худшем случае, альфа-бета процедура не будет иметь никаких преимуществ против минимаксной процедуры.
Наилучший случай, т.е. наибольшее число отсечений, достигается, когда при переборе в глубину первой обнаруживается конечная вершина, статическая оценка которой станет в последствии минимаксной оценкой начальной вершины. При максимальном числе отсечений строится и оценивается минимальное число концевых вершин. Показано, что в случае, когда самые сильные ходы всегда рассматриваются первыми, количество концевых вершин глубины N, которые будут построены и оценены альфа-бета процедурой, примерно равно числу концевых вершин, которые были бы построены и оценены на глубине  N/2 обычной минимаксной процедурой. Таким образом, при фиксированном времени и памяти альфа-бета процедура сможет пройти при поиске вдвое глубже по сравнению с обычной минимаксной процедурой.
	В заключение отметим, что статическая оценочная функция и альфа-бета процедура  две непременные составляющие почти всех компьютерных игровых программ (в том числе коммерческих). Часто используются также дополнительные эвристические приемы в самой альфа-бета процедуре:
•направленное (эвристическое) отсечение неперспективных ветвей: например, построение дерева игры обрывается на «пассивных» позициях, к которым применяется оценочная функция, для «активных» же позиций поиск продолжается дальше, до нужной глубины или даже глубже, поскольку на это можно использовать время, сэкономленное вследствие отсечения ветвей;
•последовательное углубление, при котором альфа-бета процедура применяется неоднократно: сначала до некоторой небольшой глубины (например, 2), а затем глубина увеличивается с каждой итерацией, причем после каждой итерации выполняется переупорядочение всех дочерних вершин – с тем, чтобы увеличить число отсечений в последующих итерациях;
•фиксированное упорядочение вершин при спуске-построении дерева вглубь, при котором в первую очередь строится и раскрывается дочерняя вершина, оцениваемая как более перспективная (эта оценка может быть проведена как с помощью статической оценочной функции, так и более простой, хотя и менее надежной эвристической функции);
•динамическое упорядочение вершин, при котором каждый раз после уточнения минимаксных оценок и проведения отсечений производится переупорядочивание вершин во всем построенном к текущему моменту дереве (с помощью некоторой эвристической функции) и для дальнейшего раскрытия выбирается наиболее перспективная вершина (заметим, что по существу это означает переход от классического перебора вглубь к алгоритму упорядоченного перебора на И/ИЛИ-графах).
Для усиления игры могут быть также использованы библиотеки типовых игровых ситуаций.

Редукция задач

Кроме уже рассмотренного подхода – представления задач в пространстве состояний – для решения ряда задач возможен и другой, более сложный подход. При этом подходе производится анализ исходной задачи с целью выделения такого набора подзадач, решение которых означает решение исходной задачи. Каждая из выделенных подзадач в общем случае является более простой, чем исходная, и может быть решена каким-либо методом, в том числе – с использованием пространства состояний. Но можно продолжить процесс, выделяя последовательно из возникающих задач подзадачи – до тех пор, пока не получим элементарные задачи, решение которых уже известно. Такой путь называется подходом, основанным на сведении задач к подзадачам, или на редукции задач.
Для иллюстрации этого подхода рассмотрим один из вариантов известной головоломки – задачи о пирамидке, или ханойской башне. В ней используются 3 колышка (обозначим их буквами A, B, C) и 3 диска разного диаметра, которые можно нанизывать на колышки через отверстия в центре. В начале все диски расположены на колышке А, причем диски меньшего диаметра лежат на дисках большего диаметра – см. рис. 6 (диски занумерованы в порядке возрастания диаметра). Требуется переместить все диски на колышек С, двигая их по очереди и соблюдая следующие правила. Перемещать можно только самый верхний диск, и нельзя никакой диск класть на диск меньшего размера. На рис.6 показаны начальное и целевое состояния задачи о пирамидке.
Эта задача легко может быть формализована в пространстве состояний: состояние задачи задается списком из трех элементов, каждый из которых указывает местоположение соответствующего диска (первый элемент – первого диска, второй – второго, третий – третьего). Начальное состояние описывается списком (ААА), а целевое – (ССС). При этом предполагается, что если на одном колышке находится более одного диска, то любой больший диск расположен ниже любого меньшего.

Посмотрим, как можно решить эту задачу методом редукции задач. Ключевая идея редукции состоит в том, что для перемещения всей пирамидки необходимо переложить самый нижний диск 3, а это возможно, только если располагающаяся над ним пирамидка из двух меньших дисков 1 и 2 перенесена на колышек В – см. рис. 7(а). Таким образом, исходную задачу можно свести к следующим подзадачам:
4.8 переместить диски 1 и 2 с колышка А на колышек В ( 1, 2 : А  В);
4.9 переместить диск 3 с колышка А на колышек С ( 3 : А  С);
4.10 переместить диски 1 и 2 с колышка В на колышек С ( 1, 2 : В  С).

На рис. 7(б) показано исходное состояние для третьей задачи. 

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

Таким образом, в случае подхода, основанного на редукции задач, мы получаем также пространство, но состоящее не из состояний, а из задач/подзадач (точнее, их описаний). При этом роль, аналогичную операторам в пространстве состояний, играют операторы, сводящие задачи в подзадачи. Точнее, каждый оператор редукции преобразует описание задачи в описание множества результирующих подзадач, причем это множество таково, что решение всех подзадач обеспечивает решение редуцированной задачи.
При решении задач методом редукции, как и при решении в пространстве состояний, может возникнуть необходимость перебора. Действительно, на каждом этапе редукции может оказаться несколько применимых операторов (т.е. способов сведения задачи к  подзадачам) и, соответственно, несколько альтернативных множеств подзадач. Некоторые способы, возможно, не приведут к решению исходной задачи, поскольку обнаружатся неразрешимые подзадачи, другие же способы могут дать окончательное решение. В общем случае для полной редукции исходной задачи необходимо перепробовать несколько операторов. Процесс редукции продолжается, пока исходная задача не будет сведена к набору элементарных задач, решение которых известно.
Аналогично представлению в пространстве состояний, формализация задачи в рамках подхода, основанного на редукции задач, включает определение следующих составляющих:
4.11 формы описания задач/подзадач и описание исходной задачи;
4.12 множества операторов и их воздействий на описания задач;
4.13 множества элементарных задач.
Эти составляющие задают неявно пространство задач, в котором требуется провести поиск решения задачи.
Что касается формы описания задач/подзадач, то часто их удобно описывать в терминах пространства состояний, т.е. задавая начальное состояние и множество операторов, а также целевое состояние или его свойства. В этом случае элементарными задачами могут быть, к примеру, задачи, решающиеся за один шаг перебора в пространстве состояний. 
В дополнение отметим, что подход с использованием пространства состояний можно рассматривать как вырожденный случай подхода, основанного на редукции задач, так как применение оператора в пространстве состояний сводит обычно исходную задачу к несколько более простой задаче, т.е. редуцирует ее. При этом результирующее множество подзадач состоит только из одного элемента, т.е. имеем простейший случай замены редуцируемой задачи на ей эквивалентную.

И/ИЛИ графы. Решающий граф
Для изображения процесса редукции задач и получающихся при этом альтернативных множеств подзадач используются обычно графоподобные структуры, вершины которых представляют описания задач/подзадач, а дуги связывают любую пару вершин, соответствующих редуцируемой задаче и одной из результирующих подзадач, причем стрелки на дугах указывают направление редукции. Пример такой структуры приведен на рис. 9 (а): задача G может быть решена путем решения либо задач D1 и D2, либо E1, E2 и E3  либо задачи F. При этом ребра, относящиеся к одному и тому же множеству подзадач, связываются специальной дугой. Чтобы сделать такую структуру более наглядной, вводятся дополнительные промежуточные вершины, и каждое множество результирующих задач группируется под своей родительской вершиной. При этом структура на рис. 9(а) преобразуется в структуру, изображенную на рис. 9(б): для двух из трех альтернативных множеств подзадач добавлены соответственно вершины D и E.

Если считать, что вершины D и E соответствуют описаниям альтернативных путей решения исходной задачи, то вершину G можно назвать ИЛИ-вершиной, так как задача G разрешима или способом D, или способом E, или способом F. Аналогично вершины D и E можно назвать И-вершинами, поскольку каждый из соответствующих им способов требует решения всех подчиненных задач, что и обозначается специальной дугой. По этой причине структуры, подобные структурам, изображенным на рис. 9(б), называются И/ИЛИ-графами. 
Если некоторая вершина такого графа имеет непосредственно следующие за ней (дочерние) вершины, то либо все они являются И-вершинами, либо все они – ИЛИ-вершины. Заметим, что если у некоторой вершины И/ИЛИ-графа имеется ровно одна дочерняя вершина, то ее можно считать как И-вершиной, так и ИЛИ-вершиной   как, например, вершину F на рис. 9(б) .
На языке И/ИЛИ-графов применение некоторого оператора редукции задачи  будет означать, что сначала будет построена промежуточная И-вершина, а затем непосредственно следующие за ней ИЛИ-вершины подзадач. Исключение составляет случай, когда множество задач состоит только из одного элемента, в этом случае будет образована ровно одна вершина, будем для определенности считать ее ИЛИ-вершиной. 
Вершину И/ИЛИ-графа, соответствующую описанию исходной задачи, будем называть начальной вершиной. Вершины же, которые соответствуют описаниям элементарных задач, будем называть заключительными вершинами. Поиск, осуществляемый путем перебора вершин графа, применим и в подходе, основанном на редукции задач. Цель поиска на И/ИЛИ-графе – показать, что разрешима исходная задача, т.е. начальная вершина. Разрешимость этой вершины зависит от разрешимости других вершин графа. 
Сформулируем общее рекурсивное определение разрешимости вершины в И/ИЛИ-графе:
•заключительные вершины разрешимы, так как они соответствуют элементарным задачам;
•вершина, не являющаяся заключительной и имеющая дочерние И-вершины,  разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин;
•вершина, не являющаяся заключительной и имеющая дочерние ИЛИ-вершины, разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин.
Если в процессе поиска удалось показать, что начальная вершина разрешима, то это значит, что обнаружено решение исходной задачи, которое заключено в так называемом решающем графе. Решающий граф – это подграф И/ИЛИ-графа, состоящий только из разрешимых вершин и доказывающий разрешимость начальной вершины.

Пример: задача символьного интегрирования
В качестве примера применения метода редукции рассмотрим решение задачи символьного интегрирования, т.е. нахождения неопределенного интеграла F(x)dx. Обычно эта задача решается путем последовательного преобразования интеграла к выражению, содержащему известные табличные интегралы. Для этого используется несколько правил интегрирования, в том числе: правило интегрирования суммы функций, правило интегрирования по частям, правило вынесения постоянного множителя за знак интегрирования, а также применение алгебраических и тригонометрических подстановок и использование различных алгебраических и тригонометрических тождеств. 
Для формализации этой задачи в рамках подхода, основанного на редукции задач, необходимо определить форму описания задач/подзадач, операторы редукции и элементарные задачи. В качестве возможной формы описания задач может быть взята символьная строка, содержащая запись подынтегральной функции и переменной интегрирования (если последняя не фиксирована заранее). Операторы редукции будут основаны, очевидно, на упомянутых правилах интегрирования. Например, правило интегрирования по частям udv = udv  - vdu сводит исходную задачу (неопределенный интеграл в левой части равенства) к двум подзадачам интегрирования (два соответствующих интеграла в правой части равенства).
Заметим, что часть получаемых таким образом операторов редукции (как, например, операторы, соответствующие правилу интегрирования по частям и правилу интегрирования суммы функций), действительно редуцируют исходную задачу и порождают И-вершину в И/ИЛИ-графе, в то время как алгебраические и тригонометрические подстановки и тождества (как, например, деление числителя на знаменатель или дополнение до полного  квадрата) лишь заменяют одно подынтегральное выражение на  другое, порождая, таким образом, ИЛИ-вершины.
Элементарные задачи интегрирования соответствуют табличным интегралам, к примеру,  sin(x)dx =  - cos(x) + C. Отметим, что поскольку каждая из таких табличных формул содержит переменные, на самом деле она является схемой, задающей бесконечное множество элементарных задач.
На рис.10 показан решающий граф для одной задачи интегрирования. В вершинах графа указаны соответствующие задачи/подзадачи, заключительные вершины заключены в двойные рамки. Решение задачи может быть собрано из содержащейся в графе информации. Оно состоит из следующих шагов:
4.14 применения подстановки z=tg(x); 
4.15 эквивалентного преобразования подынтегрального выражения;
4.16 применения правила интегрирования суммы функций.
При этом одна из трех результирующих подзадач оказывается элементарной, а две остальные решаются за один шаг (первая –  путем вынесения постоянного множителя за знак интеграла, вторая –  применением подстановки z=tg(w) ).
Подход, основанный на редукции задач, применим и имеет преимущества по сравнению с подходом, использующем представление в пространстве состояний, когда получающиеся при редукции подзадачи можно решать независимо друг от друга, как в примере с интегрированием. Впрочем, это условие взаимной независимости результирующих задач можно несколько ослабить. Метод редукции применим также, если решения получающих подзадач зависят друг от друга, но при этом существует такой порядок их редукции, при котором найденные решения одних, более ранних  подзадач не разрушаются при решении других, более поздних – как в головоломке о ханойской башне, в которой важен лишь порядок решения выделяемых подзадач.

Различия и ключевые операторы
		В заключение целесообразно обсудить ряд общих идей, на которых может быть основана редукция задач. К их числу  прежде всего относится идея выделения так называемых ключевых операторов и различий состояний. Будем далее предполагать, что задачи и подзадачи формулируются в пространстве состояний, т.е. как тройки вида ( SI , O, SG ), где SI   и SG  – соответственно начальное и целевое состояния, или же  как двойки (SI , SG ), если предполагать неизменным при поиске множество O операторов преобразования состояний. 
	Часто при поиске в пространстве состояний нетрудно обнаружить один оператор, который обязательно должен входить в решение задачи (по сути, применение этого оператора есть необходимый шаг решения этой задачи). В графе-пространстве состояний этому оператору обычно соответствует дуга, связывающая две практически отдельные части графа. Такой оператор и называется ключевым оператором в пространстве состояний. К примеру, в задаче о пирамидке ключевым оператором был оператор переноса на нужный колышек самого большого диска 3.
	Ключевой оператор может быть использован для следующего способа сведения исходной задачи к подзадачам. Пусть:
Op –  найденный в пространстве состояний задачи ключевой оператор (OpO) ;
SOp  – множество состояний, к которым применим ключевой оператор Op;
Op(s) – состояние, полученное в результате применения  ключевого оператора Op к состоянию s (s  SOp).
Тогда исходную задачу можно свести к трем подзадачам:
4.17 первая задача (SI , SOp)  состоит в поиске пути от начального состояния исходной задачи к одному из состояний, к которому применим ключевой оператор Op;
4.18 вторая задача является элементарной, она заключается в применении этого ключевого оператора;
4.19 третья задача (Op(s) , SG)  состоит в поиске пути от состояния, полученного применением ключевого оператора,  к целевому состоянию исходной задачи.
Порядок решения перечисленных задач существен (третья задача не может быть решена раньше первой и второй, также как вторая – раньше первой). Для решения первой и третьей задач может быть применен опять метод редукции с помощью ключевого оператора, или же их решение может быть найдено непосредственным поиском в пространстве состояний.
	 Для большинства задач не удается всегда однозначно выделить ключевой оператор, гораздо чаще удается найти множество операторов-кандидатов в ключевые (т.е. операторов, с большой вероятностью могущих стать ключевыми). Таким образом, в общем случае необходим процесс перебора операторов-кандидатов, каждый из которых образует свое множество результирующих задач (этот перебор и означает поиск на И/ИЛИ-графе задачи). 
    Самый важный вопрос при таком способе редукции задач состоит в том, как найти кандидаты в ключевые операторы. Один из способов, предложенных и опробованных впервые в одной из наиболее известных систем искусственного интеллекта GPS, заключается в выявлении различий для начального и целевого состояний задачи.	Различие легче всего формализовать как несоответствие различных элементов описаний начального и целевого состояний. Если начальное состояние является целевым, то различий между ними нет, и задача решена.
	К примеру, в задаче об обезьяне и банане различием можно считать неравенство соответствующих элементов списков, описывающих два состояния. Тогда при сравнении состояний (ТО,П,ТЯ,0)  и (ТЯ,П, ТО,1)  выявляются  три различия – соответственно в первых, третьих и четвертых элементах списков.
	С каждым различием в системе GPS был связан один или несколько операторов, призванных  устранять или уменьшать это различие. Эти операторы и являлись по сути кандидатами в ключевые. На каждом этапе работы система определяла различие между текущим состоянием (объектом) задачи и целевым состоянием (объектом), а затем выбирала и пыталась применить оператор для уменьшения найденного различия. В общем случае операторы включали в себя предусловия (условия применимости), выполнение которых было необходимо для их применения, в этом случае GPS сводила исходную задачу к задаче достижения нужного условия.
 В задаче об обезьяне естественно связать различия и операторы-кандидаты в ключевые следующим образом:
4.20 Различие в первом элементе списка-описания состояния (положение обезьяны в плоскости пола) – операторы  Перейти и Передвинуть.
4.21 Различие во втором элементе (положение обезьяны по вертикали) – оператор  Взобраться.
4.22 Различие в третьем элементе (положение ящика) – оператор Передвинуть.
4.23 Различие в четвертом элементе (содержимое руки обезьяны) – оператор Схватить.
Ясно, что для реализации рассмотренных идей в виде алгоритма или программы должна быть, во-первых, специальная процедура сравнения описаний состояний и вычисления различий. Во-вторых, необходима процедура, связывающая ключевые операторы с возможными различиями (в GPS использовалась таблица связей различие-оператор). Последняя процедура должна также устанавливать порядок устранения различий в случаях, когда выявлено несколько различий и возможно применение нескольких ключевых операторов. Различия должны быть упорядочены по степени их существенности, значимости для конечного решения исходной задачи. Система GPS начинала с попытки обработки более серьезных и трудно устранимых различий, переходя затем к более легким.
 В задаче об обезьяне и банане приоритет (существенность) различий можно установить, например, следующим образом: различие в четвертом, затем во втором, затем в третьем и первом элементе описания состояния задачи. Такой же приоритет может быть и у  операторов, уменьшающих эти различия.
Важно, что воплощаемая в указанных процедурах информация является специфической, зависящей от конкретной задачи, т.е.  эвристической проблемно-ориентированной информацией. Одной из слабостей применяемого в системе GPS подхода было то, что процедуры определения различий и уменьшающих их операторов должны были быть отдельно реализованы для каждой конкретной задачи (или для очень узкой предметной области, включающей несколько видов задач), в противном случае снижалась эффективность решения задач. 
	Подчеркнем, что основной механизм системы GPS не был проблемно-ориентированным: он представлял собой реализацию универсального эвристического метода решения задач, часто применяемого человеком, и известного как анализ целей и средств (means-ends analysis). Ключевая идея этой эвристики такова:
4.24 поиск различий между тем, что дано в поставленной задаче, и тем, что надо получить;
4.25 последовательное устранение найденных различий с помощью подходящих средств–операций.
Работая в соответствии с этой эвристикой, GPS применяла несколько схем редукции задач, и на основе выявления различий между объектами задачи и применения уменьшающих эти различия операторов рекурсивно формировала  систему (дерево) задач-целей (подзадач).

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

	В последние годы понятие интеллектуальный робот в известной степени вытеснено близким понятием интеллектуальный агент.

Интеллектуальные Агенты

Термин Интеллектуальный Агент, ставший популярным лет 5 назад, понимается различными исследователями по-разному.
 
Общим для различных подходов (точек зрения) является следующая трактовка: 
Интеллектуальный Агент – некоторая программно-аппаратная сущность, способная действовать в интересах достижения целей, поставленных перед ним владельцем и/или пользователем (или даже от лица владельца и/или пользователя).

Обычно предполагается, что Интеллектуальный Агент:
- действует автономно или совместно с другими компьютерными/интеллектуальными системами;
- выполняет шаблонные предписанные действия и/или действия, требующие активности и учета состояния окружающей среды (reactivity);
- может генерировать цели и действовать рациональным образом для их достижения (activity / pro-activity);
- в той или иной степени способен к обучению, корпоративным действиям; мобилен.

В работах, посвященных Интеллектуальным Агентам, указываются, в частности, следующие сферы их применения (и соответствующие технологии):
агенты, поддерживающие интеллектуальный пользовательский интерфейс;
мульти-агентные системы (и технологии «распределенного искусственного интеллекта»);
мобильные агенты (в том числе реализованные программно), которые могут общаться между собой и перемещаться в своем специфическом окружении (в частности, в компьютерных сетях; они могут покидать клиентский компьютер и перемещаться на удаленный сервер для выполнения некоторых действий, после чего возвращаются обратно).