Prolog

                                                % Переход через нижнюю границу

        дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-

                нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета),

                                                % Уточнить границы

                прибл_лучш( СписПоз, НовАльфа, НовБета, Поз1, Оц1),

                выбор( Поз, Оц, Поз1, Оц1, ХорПоз, ХорОц).

        нов_границы( Альфа, Бета, Поз, Оц, Оц, Бета) :-

                ход_мина( Поз), Оц > Альфа,  !.

                                                % Увеличение нижней границы

        нов_границы( Альфа, Бета, Поз, Оц, Альфа, Оц) :-

                ход_макса( Поз), Оц < Бета,  !.

                                                % Уменьшение верхней границы

        нов_границы( Альфа, Бета, _, _, Альфа, Бета).

        выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-

                ход_мина( Поз), Оц > Оц1,  !;

                ход_макса( Поз), Оц < Оц1,  !.

        выбор( _, _, Поз1, Оц1, Поз1, Оц1).

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

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

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

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

Проект

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

Назад | Содержание | Вперёд

Назад | Содержание | Вперёд

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

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

Для оценки терминальных

поисковых позиций использовать подобранную специально для данной игры

оценочную функцию

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

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