PDF-лекции (1156613), страница 19

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 19)

У некоторых вершин дерева осталась неуточненная,предварительная оценка, однако этих приближенных оценок оказалось достаточно для того, чтобыопределить точную минимаксную оценку начальной вершины и наилучший первый ход. В то же времяпроизошло существенное сокращение поиска: вместо 17 вершин построено только 11, и вместо 10обращений к статической оценочной функции понадобилось всего 6.Обобщим рассмотренную идею сокращения перебора. Сформулируем сначала правилавычисления оценок вершин дерева игры, в том числе предварительных оценок промежуточных вершин,которые для удобства будем называть альфа- и бета-величинами: концевая вершина игрового дерева оценивается статической оценочной функцией сразу, как толькоона построена; промежуточная вершина предварительно оценивается по минимаксному принципу, как только сталаизвестна оценка хотя бы одной из ее дочерних вершин; каждая предварительная оценкапересчитывается (уточняется) всякий раз, когда получена оценка еще одной дочерней вершины; предварительная оценка ИЛИ-вершины (альфа-величина) полагается равной наибольшей извычисленных к текущему моменту оценок ее дочерних вершин; предварительная оценка И-вершины (бета-величина) полагается равной наименьшей извычисленных к текущему моменту оценок ее дочерних вершин.Укажем очевидное следствие этих правил вычисления: альфа-величины не могут уменьшаться, абета-величины не могут увеличиваться.Сформулируем теперь правила прерывания перебора, или отсечения ветвей игрового дерева:.A) Перебор можно прервать ниже любой И-вершины, бета-величина которой не больше, чем альфавеличина одной из предшествующих ей ИЛИ-вершин (включая корневую вершину дерева);B) Перебор можно прервать ниже любой ИЛИ-вершины, альфа-величина которой не меньше, чем бетавеличина одной из предшествующих ей И-вершин.При этом в случае А говорят, что имеет место альфа-отсечение, поскольку отсекаются ветви дерева,начиная с ИЛИ-вершин, которым приписана альфа-величина, а в случае В  бета-отсечение, посколькуотсекаются ветви, начинающиеся с бета-величин).Важно, что рассмотренные правила работают в ходе построения игрового дерева вглубь; этоозначает, что предварительные оценки промежуточных вершин появляются лишь по мере продвиженияот концевых вершин дерева вверх к корню и реально отсечения могут начаться только после того, какполучена хотя бы одна точная минимаксная оценка промежуточной вершины.В рассмотренном примере на рис.

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

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

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

Таким образом, при фиксированномвремени и памяти альфа-бета процедура сможет пройти при поиске вдвое глубже по сравнению собычной минимаксной процедурой.В заключение отметим, что статическая оценочная функция и альфа-бета процедура  двенепременные составляющие почти всех компьютерных игровых программ (в том числе коммерческих).Часто используются также дополнительные эвристические приемы в самой альфа-бета процедуре: направленное (эвристическое) отсечение неперспективных ветвей: например, построение дерева игрыобрывается на «пассивных» позициях, к которым применяется оценочная функция, для «активных»же позиций поиск продолжается дальше, до нужной глубины или даже глубже, поскольку на этоможно использовать время, сэкономленное вследствие отсечения ветвей; последовательное углубление, при котором альфа-бета процедура применяется неоднократно:сначала до некоторой небольшой глубины (например, 2), а затем глубина увеличивается с каждойитерацией, причем после каждой итерации выполняется переупорядочение всех дочерних вершин – стем, чтобы увеличить число отсечений в последующих итерациях; фиксированное упорядочение вершин при спуске-построении дерева вглубь, при котором в первуюочередь строится и раскрывается дочерняя вершина, оцениваемая как более перспективная (этаоценка может быть проведена как с помощью статической оценочной функции, так и более простой,хотя и менее надежной эвристической функции); динамическое упорядочение вершин, при котором каждый раз после уточнения минимаксных оценоки проведения отсечений производится переупорядочивание вершин во всем построенном к текущемумоменту дереве (с помощью некоторой эвристической функции) и для дальнейшего раскрытиявыбирается наиболее перспективная вершина (заметим, что по существу это означает переход отклассического перебора вглубь к алгоритму упорядоченного перебора на И/ИЛИ-графах).Для усиления игры могут быть также использованы библиотеки типовых игровых ситуаций.Редукция задачКроме уже рассмотренного подхода – представления задач в пространстве состояний – длярешения ряда задач возможен и другой, более сложный подход.

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

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

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

Характеристики

Список файлов лекций