Сведение задачи к подзадачам

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

Два типа вершин

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

Поиск решения задачи Цель поиска на И/ИЛИ-графе – показать, что разрешима исходная задача, т.е. начальная вершина. Разрешимость этой вершины зависит от разрешимости других вершин графа.

разрешимость вершины в И/ИЛИ-графе заключительные вершины разрешимы, так как они соответствуют элементарным задачам; ИЛИ-вершина, не являющаяся заключительной, разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин; И-вершина, не являющаяся заключительной, разрешима тогда и только тогда, когда разрешима каждая из ее дочерних вершин. Если в процессе поиска удалось показать, что начальная вершина разрешима, то это значит, что обнаружено решение исходной задачи, которое заключено в так называемом решающем графе. Решающий граф – это подграф И/ИЛИ- графа, состоящий только из разрешимых вершин и доказывающий разрешимость начальной вершины.

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

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

Схема просмотра И/ИЛИ-дерева Процесс просмотра И/ИЛИ-дерева проще всего организовать на основе трех взаимно рекурсивных процедур. Назовем их –AND/OR-процедурой –AND-процедурой –OR-процедурой

AND/OR-процедура AND/OR-процедура, получая на вход некоторую вершину-задачу Goal, вырабатывает либо неудачу, если эта вершина неразрешима, либо возвращает решающее дерево, показывающее ее разрешимость и являющееся решением этой задачи. Шаг 1. Проверить, является ли заданная вершина Goal заключительной. Если да, то закончить процедуру, выдав саму эту вершину в качестве результата, в ином случае перейти к следующему шагу. Шаг 2. Проверить, можно ли раскрыть заданную вершину Goal. Если да, то переход на шаг 3, в противном случае выход из процедуры с сообщением о неудаче. Шаг 3. Раскрыть заданную вершину Goal, сформировав список ее дочерних вершин list, переход на шаг 4. Шаг 4. Если вершина Goal является И-вершиной, то применить к ней и списку list AND-процедуру, после чего закончить текущую процедуру с полученным (AND-процедурой) результатом. Шаг 5. Если вершина Goal является ИЛИ-вершиной, то применить к ней и списку list OR-процедуру, и завершить текущую процедуру с полученным (OR -процедурой) результатом.

AND-процедура Шаг 1. Установить в качестве решающего графа для задачи Goal саму эту вершину и перейти на следующий шаг. Шаг 2. Если список list не пуст, то перейти на шаг 3, в ином случае закончить текущую процедуру, выдав в качестве результата сформированный решающий граф для задачи-цели Goal. Шаг 3. Выбрать из списка list очередную вершину (назовем ее Current) и проверить ее разрешимость, обратившись к AND/OR- процедуре. Шаг 4. Если Current неразрешима, то выход из текущей процедуры с сообщением о неуспехе, иначе перейти на следующий шаг. Шаг 5. Подсоединить полученный AND/OR-процедурой решающий граф для вершины Current к решающему графу вершины Goal и перейти на шаг 2.

OR-процедура Шаг 1. Установить в качестве решающего графа для задачи Goal саму эту вершину и перейти на следующий шаг. Шаг 2. Если список list не пуст, то перейти на шаг 3, в ином случае выход из текущей процедуры с сообщением о неуспехе. Шаг 3. Выбрать из списка list очередную вершину (назовем ее Current) и проверить ее разрешимость, обратившись к AND/OR-процедуре. Шаг 4. Если Current неразрешима, то переход на шаг 2, в противном случае – на следующий шаг. Шаг 5. Включить полученный AND/OR-процедурой решающий граф для вершины Current в решающий граф вершины Goal и закончить текущую процедуру, выдав полученный решающий граф в качестве ее результата.

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

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

Пример: Игра «последний проигрывает». Два игрока поочередно берут по одной или две монеты из кучки, первоначально содержащей семь монет. Игрок, забирающий последнюю монету, проигрывает.

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

В большинстве игр, представляющих интерес, таких как шашки и шахматы, построить полные решающие деревья и найти полные игровые стратегии не представляется возможным. –Например, для шашек число вершин в полном игровом дереве оценивается величиной порядка 10 40, и просмотреть такое дерево практически нереально. –Алгоритмы упорядоченного перебора с применением эвристик не настолько уменьшают просматриваемую часть дерева игры, чтобы дать существенное, на несколько порядков, сокращение времени поиска. Для «неполных» игр в шашки и шахматы (например, для эндшпилей), как и для всех несложных игр, таких как «крестики-нолики» на квадрате небольшого размера, можно успешно применять алгоритмы поиска на И/ИЛИ-графах, позволяющие обнаруживать выигрышные и ничейные игровые стратегии.

Пример: «крестики-нолики» на квадрате 3 3. Игрок 1 ходит первым и ставит крестики, а 2 нолики. –Игра заканчивается, когда составлена либо строка, либо столбец, либо диагональ из крестиков или ноликов. Размер полного дерева игры: –начальная вершина имеет 9 дочерних вершин, каждая из которых в свою очередь имеет 8 дочерних; каждая вершина глубины 2 имеет 7 дочерних и т.д. В таких случаях, как и во всех сложных играх, вместо нереальной задачи поиска полной игровой стратегии решается, как правило, более простая задача поиск для заданной позиции игры достаточно хорошего первого хода.

Минимаксный принцип ИЛИ-вершине дерева игры приписывается оценка, равная максимуму оценок ее дочерних вершин; И-вершине игрового дерева приписывается оценка, равная минимуму оценок ее дочерних вершин. Минимаксный принцип положен в основу минимаксной процедуры, предназначенной для определения наилучшего (более точно, достаточно хоро­шего) хода игрока исходя из заданной конфигурации игры при фиксированной глубине поиска N в игровом дереве.

Минимаксная процедура Предназначена для определения наилучшего (более точно, достаточно хорошего) хода игрока исходя из заданной конфигурации игры S при фиксированной глубине поиска N в игровом дереве. Предполагается, что игрок ПЛЮС ходит первым (т.е. начальная вершина есть ИЛИ-вершина).

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

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

Принципы построения оценочной функции статическая оценочная функция положительна в игровых конфигурациях, где игрок ПЛЮС имеет преимущества; статическая оценочная функция отрицательна в конфигурациях, где МИНУС имеет преимущества; статическая оценочная функция близка к нулю в позициях, не дающих преимущества ни одному из игроков.

Например, для шашек в качестве простейшей статической функции может быть взят перевес в количестве шашек (и дамок) у игрока ПЛЮС.

Для игры «крестики-нолики» на фиксированном квадрате возможна такая статиче­ская оценочная функция: +,если P есть позиция выигрыша игрока ПЛЮС E(P) =,если P есть позиция выигрыша игрока МИНУС (N L + +N C + ­ +N D + ) (N L +N C +N D ) в остальных случаях где:+ очень большое положительное число; очень маленькое отрицательное число; N L +, N C +, N D + соответственно число строк, столбцов и диагоналей, «открытых» для игрока ПЛЮС (т.е. где он еще может поставить три выигрышных крестика подряд); N L, N C, N D аналогичные числа для игрока МИНУС.

Примеры

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

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

Пример

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

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

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

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

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

Правила вычисления и β в процессе поиска рекомендуются следующие правила вычисления и β : –у MAX вершины значение равно наибольшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин; –у MIN вершины значение β равно наименьшему в данный момент значению среди окончательных возвращенных значений для ее дочерних вершин.

Правила прекращения поиска –можно не проводить поиска на поддереве, растущем из всякой MIN вершины, у которой значение β не превышает значения всех ее родительских MAX вершин; –можно не проводить поиска на поддереве, растущем из всякой MAX вершины, у которой значение не меньше значения β всех ее родительских MIN вершин.

При построении и раскрытии вершины W 3 + статическая оценка первой ее дочерней вершины дает величину 4. Это – предварительная оценка самой вершины W 3 +. Предварительная оценка после построения второй ее дочерней вершины будет пересчитана. Причем согласно минимаксному принципу оценка может только увеличиться (поскольку подсчитывается как максимум оценок дочерних вершин). Если она увеличится, это не повлияет на оценку вершины W 1, т.к. последняя при уточнении по минимаксному принци­пу может только уменьшаться ( - равна минимуму оценок дочерних вершин). Следовательно, можно пренебречь второй дочерней вершиной для W 3 +, не строить и не оценивать ее, поскольку уточнение оценки вершины W 3 + не повлияет на оценку вершины W 1. Такое сокращение поиска в игровом дереве называется отсечением ветвей. Пусть построены вершины W 1, W 2 + и первые три конечные вершины (листья). Эти листья оценены статической функцией, и вершина W 2 + получила точную минимаксную оценку 3, а вершина W 1 предварительную оценку 3.

Исходя из оценки первой дочерней вершины начальная вершина W 0 +, соответствующая исходной позиции игры, к этому моменту уже предварительно оценена величиной 3. Вершина W 5 + получила точную минимаксную оценку 3, а ее родительская W 4 получила пока только предварительную оценку 3. Эта предварительная оценка вершины W 4 может быть уточнена в дальнейшем, но в соответствии с минимаксным принципом возможно только ее уменьшение, и это уменьшение не повлияет на оценку вершины W 0 +, поскольку последняя, согласно минимаксному принципу, может только увеличиваться. Таким образом, построение дерева можно прервать ниже вершины W 4, отсекая целиком выходящие из нее вторую и третью ветви (и оставляя ее оценку предварительной). Продолжим для поиска в глубину с одновременным вычислением предварительных (и точных, где это возможно) оценок вершин вплоть до момента, когда построены уже вершины W 4, W 5 + и две дочерних последней, которые оцениваются статической функцией. На этом построение игрового дерева заканчивается, полученный результат лучший первый ход. У некоторых вершин дерева осталась неуточненная, предварительная оценка, однако приближенных оценок оказалось достаточно для того, чтобы определить точную минимаксную оценку начальной вершины и наилучший первый ход.

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

Многие из рассмотренных выше идей были использованы А. Ньюэллом, Дж. Шоу и Г. Саймоном в их программе GPS. Процесс работы GPS в общем воспроизводит методы решения задач, применяемые человеком: выдвигаются подцели, приближающие к решению; применяется эвристический метод (один, другой и т. д.), пока не будет получено решение. Попытки прекращаются, если получить решение не удается.