8128

Альфа-бета отсечение

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-02-04

392 KB

37 чел.

Альфа-бета отсечение

(конспект)

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

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

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

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

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

Второй лист, расположенный ниже узла B, имеет значение 12 (б). Игрок MIN должен избегать этого хода, поэтому значение В, все еще самое большее, равно 3.

Третий лист, расположенный ниже узла В, имеет значение 8; мы проверили всех преемников узла В, поэтому значение В в точности равно 3 (в).

Рис. 7.1 – Этапы вычисления оптимального решения для дерева игры

Теперь можно сделать вывод, что значение корня, самое меньшее, равно 3, поскольку игрок МАХ в корне делает выбор со значением 3.

Первый лист, находящийся ниже С, имеет значение 2. Поэтому С, который представляет собой узел MIN, имеет, самое большее, значение 2. Но известно, что узел В позволяет достичь значения 3, поэтому игрок МАХ ни в коем случае не должен выбирать узел С. Это означает, что нет смысла проверять остальных преемников узла С. Это — пример применения альфа-бета-отсечения (г). Первый лист, находящийся ниже D, имеет значение 14, поэтому D имеет, самое большее, значение 14. Оно все еще выше, чем наилучшая альтернатива для игрока МАХ (т.е. 3), поэтому необходимо продолжить исследование преемников узла D. Следует также отметить, что теперь определены предельные значения всех преемников корневого узла, поэтому значение корня также равно, самое большее, 14 (д); второй преемник D имеет значение 5, поэтому снова приходится продолжать исследование. Значение третьего преемника ровно 2, поэтому теперь значение D точно равно 2. В корневом узле игрок MAX  принимает решение сделать ход, ведущий к узлу B, что позволяет ему получить значение 3 (e).

Этот подход может также рассматриваться под другим углом - как упрощение формулы для получения минимаксного значения Minimax-Value. Допустим, что два преемника узла С на рисунке, еще не обработанные в процессе вычисления, имеют значения  х и у, и предположим, что z — минимальное значение среди x и y. В таком случае значение корневого узла можно найти следующим образом:

Minimax-Value(root) = max(min(3, 12, 8), min(2, x, y), min(14, 5, 2))

   = max(3, min(2, x, y), 2)

   = max(3, z, 2)

= 3, где z<=2

Иными словами, значение корневого узла, а следовательно, и минимаксное решение не зависит от значений отсеченных листовых узлов х и у.

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

Рис. 7.2 – Альфа-бета-отсечение: общий случай. Если для Игрока узел m лучше чем n, то узел n никогда не встретится в игре

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

•  α =  значение наилучшего варианта (т.е. варианта с самым высоким значением), который был сих пор найден в любой точке выбора вдоль пути для игрока MAX;

•  β = значение наилучшего варианта (т.е. варианта с самым низким значением), который был до сих пор найден в любой точке выбора вдоль пути для игрока MIN.

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

function Alpha-Beta-Search(state) returns действие action

inputs: state, текущее состояние в игре

v <— Max-Value (state, -∞, +∞)

return действие action из множества Successors(state) со значением v

function Max-Value(state, α, β) returns значение полезности 

inputs: state, текущее состояние в игре

α, значение наилучшей альтернативы для игрока МАХ вдоль

пути к состоянию state

β, значение наилучшей альтернативы для игрока MIN вдоль пути к состоянию state

if Terminal-Test(state) then return Utility(state)

v <— - ∞

for a, s in Successors(state) do

v <— Max(v, Min-Value(s, α, β))

if v >= β then return v

α <— Max (α, v)

return v

function Min-Value(state, α, β) returns значение полезности 

inputs: state, текущее состояние в игре

α, значение наилучшей альтернативы для игрока МАХ вдоль

пути к состоянию state

β, значение наилучшей альтернативы для игрока MIN рдоль. пути к состоянию state

if Terminal-Test(state) then return Utility(state)

v <— + ∞

for α, s in Successors(state) do

v Min(v, Max-Value(s, α, β) )

if v <= (α then return v

β  Min(β, v)

return v

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

Если принять допущение, что это может быть сделано (очевидно, что при этом невозможно достичь идеальных результатов, поскольку в противном случае функцию упорядочения можно было бы использовать для ведения идеальной игры!), то окажется, что в алгоритме альфа-бета-отсечения для определения наилучшего хода достаточно исследовать только 0(bm/2) узлов, а не 0(bm) узлов, как при использовании минимаксного алгоритма. Это означает, что эффективный коэффициент ветвления становится равным , а не b; например, для шахмат он равен 6, а не 35. Иными словами, за такое же время альфа-бета-поиск позволяет заглянуть в дерево игры примерно в два раза дальше по сравнению с минимаксным поиском. А если исследование преемников происходит в случайном порядке, а не по принципу первоочередного выбора наилучших вариантов, то при умеренных значениях b общее количество исследованных узлов будет составлять примерно О(b3m/4). В случае шахмат применение довольно простой функции упорядочения (например, такой, в которой в первую очередь рассматриваются взятия фигур, затем угрозы, затем ходы вперед, а после этого ходы назад) позволяет оставаться в пределах, не превышающих удвоенное значение результата 0(bm/2), который может быть получен в наилучшем случае. Добавление динамических схем упорядочения ходов, в частности, таких, в которых в первую очередь проверяются ходы, обозначенные как наилучшие на предыдущем этапе, позволяют подойти совсем близко к этому теоретическому пределу.

Наличие повторяющихся состояний в дереве поиска может вызвать экспоненциальное увеличение стоимости поиска. В играх повторяющиеся состояния встречаются часто из-за возникновения транспозиций — различных перестановок последовательностей ходов, которые оканчиваются в одной и той же позиции. Например, если белые имеют в своем распоряжении ход а1 на который черные могут ответить ходом b1 а также еще один не связанный с ним ход а2 на другой стороне доски, на который может быть дан ответ b2, то обе последовательности, [a1,b1,a2,b2] и [a1,b2,a2,b1] оканчиваются в одной и той же позиции (как и перестановки, начинающиеся с а2). Поэтому целесообразно сохранять оценку каждой конкретной позиции в хэш-таблице при первом ее возникновении, чтобы не приходилось вычислять ее повторно при последующих возникновениях. По традиции хэш-таблица с ранее встретившимися позициями называется таблицей транспозиций; она по сути идентична списку closed в алгоритме Graph-Search. Использование таблицы транспозиций может оказать чрезвычайно эффективное воздействие, которое иногда выражается в удваивании достижимой глубины поиска в шахматах. С другой стороны, если существует возможность вычислять оценки со скоростью в несколько миллионов узлов в секунду, то практически нет смысла хранить данные обо всех этих узлах в таблице транспозиций.

PAGE   \* MERGEFORMAT 1


 

А также другие работы, которые могут Вас заинтересовать

49624. Розрахунки ділянки тепловозною тягою за одним варіантом ведення поїзда 1.57 MB
  Тяга поїздів – це галузева наука яка вивчає керований рух поїздів тобто такий рух що дозволяє досягти поставленої перед залізничним транспортом мети – повного та своєчасного забезпечення народного господарства у перевезеннях при безпеці цих перевезень та надійній роботі локомотивів. Таблиця 51 № елемента Довжина елемента Крутість Початкова швидкість Питома рівнодійна сила Відрізок шляху Швидкість кінцев...
49625. ДИСКРЕТНАЯ ОБРАБОТКА СИГНАЛОВ И ЦИФРОВАЯ ФИЛЬТРАЦИЯ 913.5 KB
  Дискретная обработка аналогового сигнала.1 Сравнить форму спектра дискретизированной последовательности со спектром исходного аналогового сигнала. Установить связь между: результатом Z – преобразования и спектральной плотностью дискретной последовательности; спектром исходного периодического аналогового сигнала и дискретными отсчетами его спектральной плотности.1 Методом билинейного Zпреобразования синтезировать цифровой фильтр нижних частот ФНЧ с частотой среза равной ширине основного лепестка в области положительных частот спектра...
49626. Разработка микропроцессорной системы с заданой частоты сигнала Fmax=200 Гц 806 KB
  Метки Оператор команды Операнд команды Комментарий MVI 36H Запись слова управления в регистр управления таймера OUT 7H MVI E8H Запись числа N в 0й канал OUT 4H MVI 3H OUT 4H MVI 72H Запись слова управления в регистр управления таймера OUT 7H CYCLE: MVI 8H Запись числа N в 1й канал OUT 5H MVI 52H OUT 5H MVI 1H Запуск таймера OUT 8H CC: IN 10H Опрос логического состояния счетного триггера JNZ CC MVI 0H Остановка таймера OUT 8H IN 5H Считывание частоты MOV C IN 5H MOV B MVI 8H Подсчет частоты SUB C MOV E MVI 52H...
49627. АНАЛИЗ ДЕНЕЖНЫХ ПОТОКОВ БАНКА (на материалах ПАО «ПриватБанк») 493.5 KB
  Осуществление практически всех видов финансовых операций коммерческого банка генерирует определенное движение денежных средств в форме их поступления или расходования. Это движение денежных средств функционирующего предприятия во времени представляет собой непрерывный процесс и определяется понятием “денежный поток”.
49628. ПРОЕКТ КОМПЬЮТЕРНОГО КЛАССА КОЛЛЕДЖА НА ОСНОВЕ БЕСПРОВОДНОЙ СЕТИ 143 KB
  Тема КР Организация локально-вычислительной сети учебного центра. Обеспечить выход в Интернет электронную почту а также: предусмотреть возможность развития сети за счет увеличения количества компьютеров в классах 1 и 2; обеспечить возможность обмена информацией между преподавателями; организовать резервирование данных; обеспечить возможность вывода на принтер D всем преподавателям а на принтер А и В только из кабинетов А и В соответственно. Перечень графического материала – схема сети.
49630. Привод к ленточному конвейеру с графиком нагрузки 2.63 MB
  Схема привода ленточного конвейера Окружное усилие на барабане Ft = 3 кН окружная скорость барабана V = 01 м с и диаметр барабана D = 350 мм. Коэффициент диаметра червяка: принимаем q = 125. Истинное межосевое расстояние Размеры червяка и колеса: Червяк: Делительный диаметр d1 = q ∙ m = 125 ∙ 5 = 625 мм. Диаметр вершин витков dа1 = d1 2 ∙ m = 625 2 ∙ 5 = 725 мм.
49631. Разработка комплекта технологической документации обработки детали на металлорежущих станках 142.6 KB
  В данной работе произведен анализ конструкции детали на технологичность выбор заготовки определен тип производства последовательность технологических операций рассчитаны оптимальные припуски на механическую обработку выбрано оборудование режущий и измерительный инструмент выбраны приспособления. Содержание Введение 4 1 Назначение и конструкция детали 5 2 Анализ конструкции детали на технологичность 7 3 Определение типа производства 8 4 Выбор заготовки 9 5 Техникоэкономическое обоснование выбора заготовки 10 5. 4 Выбор...