Программирование на языке Пролог для искусственного интеллекта

дост_хор( [], _, _, Поз, Оц, Поз, Оц) :- !.
 % Больше нет кандидатов
дост_хор( _, Альфа, Бета, Поз, Оц, Поз, Оц) :-
 ход_мина( Поз), Оц > Бета, !;
  % Переход через верхнюю границу
 ход_макса( Поз), Оц < Альфа, !.
  % Переход через нижнюю границу
дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-
 нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета),
  % Уточнить границы
 прибл_лучш( СписПоз, НовАльфа, НовБета, Поз1, Оц1),
 выбор( Поз, Оц, Поз1, Оц1, ХорПоз, ХорОц).
нов_границы( Альфа, Бета, Поз, Оц, Оц, Бета) :-
 ход_мина( Поз), Оц > Альфа, !.
  % Увеличение нижней границы
нов_границы( Альфа, Бета, Поз, Оц, Альфа, Оц) :-
 ход_макса( Поз), Оц < Бета, !.
  % Уменьшение верхней границы
нов_границы( Альфа, Бета, _, _, Альфа, Бета).
выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-
 ход_мина( Поз), Оц > Оц1, !;
 ход_макса( Поз), Оц < Оц1, !.
выбор( _, _, Поз1, Оц1, Поз1, Оц1).

Рис. 15.5. Реализация альфа-бета алгоритма.

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

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

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

Проект

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

15.4. Минимаксные игровые программы: усовершенствования и ограничения

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

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

Многое зависит от оценочной функции. Если бы мы располагали абсолютно точной оценочной функцией, мы могли бы ограничить поиск рассмотрением только непосредственных преемников текущей позиции, фактически исключив перебор. Но для таких игр, как шахматы, любая оценочная функция, имеющая практически приемлемую вычислительную сложность, по необходимости будет всего лишь эвристической оценкой. Такая оценка базируется на 'статических' свойствах позиции (например, на количестве фигур) и в одних позициях работает надежнее, чем в других. Допустим, например, что мы имеем именно такую оценочную функцию, основанную на соотношении материала, и представим себе позицию, в которой у белых лишний конь. Ясно, что оценка будет в пользу белых. Здесь все в порядке, если позиция 'спокойная' и черные не располагают какой-либо сильной угрозой. Но, с другой стороны, если на следующем ходу черные могут взять белого ферзя, то такая оценка может привести к фатальному просмотру из-за своей неспособности к динамическому восприятию позиции. Очевидно, что в спокойных позициях мы можем доверять такой статической оценке в большей степени, чем в активных позициях, когда с каждой из сторон имеются непосредственные угрозы взятия фигур. Поэтому статическую оценку следует использовать только для спокойных позиций. Что же касается активных позиций, то здесь существует такой стандартный прием: следует продолжить поиск из активной позиции за пределы ограничения по глубине и продолжать его до тех пор, пока не встретится спокойная позиция. В частности, таким образом производится просчет разменов фигур в шахматах.

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

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