Intel_Nils (526801), страница 32
Текст из файла (страница 32)
Пусть дерево имеет глубину 0 и у каждой вершины (за исключением концевой) в точности В дочерних вершин. У такого дерева будет ровно Вп концевых вершин. Предположим, что в альфа-бета процедуре дочерние вершины строятся в порядке, соответствующем их истинным обращенным величинам для «ИЛИ» вершин строятся дочерние ~вершины с наибольшими значениями; а для вершин «И» — с наименьшими. (Конечно, эти обращенные величины в момент построения дочерних вершин, как правило, не известны, так что в действительности этот порядок никогда не достигается„ разве что случайно.) Оказывается, что такой порядок максимизирует число отсечений и минимизирует число построенных концевых вершин. Обозначим это минимальное число концевых вершин через 1чо.
Можно показать, что ~ 2Во!з 1 для четного В, Ф 1 В'о+н" + В'о щ' — 1 для нечетного О. Иными словами, число концевых вершин глубины О, которые будут построены при оптимальном альфа-бета переборе, примерно равно числу концевых вершин, которые были бы построены на глубине сз/2 без альфа-бета процедуры. Таким образом, при тех же требованиях к памяти альфа-бета процедура с совершенным упорядочением дочерних вершин позволяет удвоить глубину перебора.
Конечно, в задачах перебора невозможно добиться совершенного упорядочения (если бы это было возможно, то мы не нуждались бы ни в каком процессе перебора!), однако важно использовать наилучшую из имеющихся в нашем распоряжении функций упорядочения, поскольку это приносит большую потенциальную выгоду. 5.14. КОМБИНИРОВАННЫЕ АЛЪФА-БЕТА ПРОИЕДУРЫ И ПРОНЕДУРЫ УПОРЯДОЧЕНИЯ Сразу приходят на ум две процедуры построения дочерних вершин в той последовательности, которая оценивается как наилучшая. о.е4. Комбинироеанные процедуры Фиксированное упорядочение Можно использовать процедуру йеребора в глубину, в которой в первую очередь строится. дочерняя вершина, оцениваемая как лучший ход (для любого игрока).
Мы будем говорить, что в такой процедуре используется фиксированное упорядочение. Так, если, скажем, вершина 1 оценивается как наилучшая из дочерних вершин начальной вершины (с точки зрения игрока ПЛЮС), то следующей строится она, и она же выбирается для очередного раскрытия. Тогда если, скажем, вершина 11 оценивается как наилучшая из дочерних вершин вершины 1 (с точки зрения игрока МИНУС), то она строится следующей и выбирается для раскрытия.
Этот процесс продолжается до тех пор, пока не будет достигнута концевая вершина, после чего становятся возможными отсечения. Перебор в глубину (с использованием альфа-бета процедуры) продолжается обычным образом, причем построение вершин по-прежнему производится в порядке их оцениваемого достоинства. Оценку достоинства вершины можно производить различными способами. Для ранжирования дочерних вершин можно взять саму статическую оценочную функцию нли, быть может, какую-нибудь более простую (и менее надежную) оценочную функцию. С другой стороны, под каждой из дочерних вершин можно произвести менее глубокий перебор, а потом упорядочить дочерние вершиньь исходя из их обращенных величин, полученных в результате такого неглубокого перебора.
Конечно, в каждом из этих методов следует сопоставить дополнительные затраты на перебор, связанные с упорядочением, с той экономией, которая вызывается возрастающим при этом числом отсечений ветвей в дереве перебора. Обычно для того, чтобы выбрать правильное соотношение между этими'факторами, нужно произвести эксперимент. Динамическое упорядочение Достоинство описанной альфа-бета процедуры с фиксированным упорядочением заключается в том, чтоонадовольнопроста, Но может случиться, что в ходе перебора, идущего по определенному пути в дереве перебора, становится очевидно, что этот перебор следовало бы продолжить, отправляясь от некоторой более высокой вершины, которая теперь более эффективна.
Осуществлять перебор в той части дерева, которая представляется наиболее перспективной, до тех пор пока не будет достигнута максимальная глубина, можно будет, слегка изменив алгоритм упорядоченного перебора на деревьях «И/ИЛИ». Мы будем говорить, что модифицированный алгоритм упорядочен-' ного перебора использует в этом случае динамическое упорядочение. 166 Гд 6.
Методы поиска при сведении задач к подзадачам Изменения весьма просты. На каждом этапе в процессе перебора в дереве перебора будут концевые вершины. Вместо того чтобы подсчитывать для этих вершин значения б (измеряющие оцениваемую стоимость), можно для измерения достоинства соответствующих позиций игры привлечь некоторую оценочную функцию е.
Тогда, по аналогии с подсчетом значений б, для не- концевых вершин дерева перебора будут вычисляться обращенные величины, или е-значения. (Заметим, что стоимости дуг в дереве игры обычно не задаются; поэтому обращенные величины будут вычисляться точно так же, как в минимаксной про* цедуре.) На основе обращенных е-значений в дереве выделяется цепочка наилучших ходов, ведущая к одной из его концевых вершин. Эта вершина и раскрывается в следующую очередь. (Наилучшим ходом под вершиной и будет выбор дочерней «ИЛИ» вершины, имеющей наибольшее обращенное е-значеиие; наилучшим ходом под «ИЛИ» вершиной будет выбор дочерней «И» вершины, имеющей наименьшее обращенное е-значение.) Когда в конечном итоге достигается максимальная глубина, у нас появляется, возможность подсчитать предварительные обращенные величины, и тогда можно начать искать возможные отсечения. (Выполнение отсечений аналогично удалению вершин из списка ОТКРЫТ на шагах (7) и (12) алгоритма упоря.
доченного перебора (стр. 144, !45).) Здесь снова можно оценить' достоинства позиции, соответствующей этой концевой вершине дерева перебора, с помощью статической оценочной функции или посредством неглубокого перебора. Можно допустить также, чтобы до того, как будут производиться вычисления, связанные с получением нового дерева то, под вершиной, выбранной для раскрытия, вырастал целый кусок дерева. В ряде экспериментов (Слейджл и Диксон, 1959) на примере игры калах ') было показано, что метод альфа-бета, использующий определенный внд динамического упорядочения, более эффективен по- сравнению с альфа-бета процедурой с фиксированным упорядочением или же (естественно) по сравнению с простой минимаксной процедурой без альфа-бета.
6.16. ВОЗМОЖНОЕ УЛУЧШЕНИЕ МЕТОДОВ, ОСНОВАННЫХ НА МИНИМАКСЕ Основная философия методов, основанных на минимаксе (включая методы, использующие альфа-бета), состоят в том, что наилучший ход игрока МИНУС определяется перебором, произведенным игроком ПЛЮС. Если предположить, что по- ') Игра калах подробно описана а журнале «Наука» н жизнь», № !2, 106 — !!4, 1971.
Там же прнпедено (популярное) описание нескольких программ этой игры для ЭВМ. — Прим. перев, бпб. Библиографические и исторические замечания 167 исковые возможности игрока МИНУС те же, что и у игрока ПЛЮС; то в действительности его перебор будет произведен на один уровень глубже перебора, произведенного в дереве перебора игроком ПЛЮС. Таким образом, после того как игрок МИНУС осушествит перебор, он может выбрать свой ответный ход на основе обращенных величин, более надежных, чем те, что были вычислены игроком ПЛЮС. Следовательно, наилучший ход игрока МИНУС не будет совпадать с наилучшим ходом, полученным райее игроком ПЛЮС. Можно исправить это положение, слегка изменив минимаксный метод построения обрашенных величин.
Вместо того чтобы в качестве обращенной величины брать наибольшее (или наименьшее) из значений для дочерних вершин, можно взять некоторую более сложную функцию этих значений. Например, к обращенной величине для «И» вершины предлагалось добавлять еще некоторую фиксированную величину, если наибольшее значение имеет более чем одна из дочерних вершин «ИЛИ». Аналогично эту фиксированную величину предлагалось вычитать из величин «ИЛИ» вершин, если «И» вершина имеет более чем одну «хорошую» (для игрока МИНУС) дочернюю вершину. Эта стратегия добавления или вычитания определенной суммы позволяет выделить дополнительные достоинства позиции, из которой можно сделать несколько хороших ходов.
Эксперименты, проведенные с этой стратегией (Слейджл и диксон, 1970), показывают, что ее использование действительно приводит к лучшей игре, по крайней мере в случае игры калах. зда. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ Развитие методов перебора на «И/ИЛИ» графах В стратегиях поиска большинства из ранних программ, в которых строились деревья подзадач, применялись лишь простые методы упорядочения.
В первых вариантах универсального решателя задач применялась стратегия перебора в глубину и привлекались средства оценки трудности задач; возвращение назад производилось в тех случаях, когда дочерняя задача представлялась более сложной по сравнению с одной из предшествующих ей задач. В программе ЬА!ХТ Слейджла в качестве меры трудности задачи вводится «глубнна подинтегрального выражения» и обычно в первую очередь расматривается самая легкая иэ задач. В 60-х годах Слейджл и его сотрудники провели много экспериментов с различными стратегиями перебора для игровых деревьев и «И/ИЛИ» деревьев. Обзор стратегий для игровых деревьев содержится в статье Слейджла и Диксона (1969). В самой сложной из этих стратегий используется динамическое упорядочение раскрытия вершин. Программа Слейджла и 168 Гл. б, Метода поиска при сведении задач к подзадачам Бурского (1968), названная М(Л.Т!Р!.Е (М!)!.Т!рпгрозе Ргойгаш 1Ьа! ЕЕагпз), включает некоторую универсальную стратегию для перебора на «И/ИЛИ» графах.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
