Альфа-бета алгоритм: эффективная реализация минимаксного принципа

Программа, показанная на рис. 15.3, производит просмотр в глубину дерева поиска, систематически обходя все содержащиеся в нем позиции вплоть до терминальных; она вычисляет статические оценки всех терминальных позиций. Как правило, для того, чтобы получить правильную минимаксную оценку корневой вершины, совсем не обязательно проделывать эту работу полностью. Поэтому алгоритм поиска можно сделать более экономным. Его можно усовершенствовать, используя следующую идею. Предположим, что у нас есть два варианта хода. Как только мы узнали, что один из них явно хуже другого, мы можем принять правильное решение, не выясняя, на сколько в точности он хуже. Давайте используем этот принцип для сокращения дерева поиска рис. 15.2. Процесс поиска протекает следующим образом:

(1) Начинаем с позиции а.

(2) Переходим к b.

(3) Переходим к d.

(4) Берем максимальную из оценок преемников позиции d, получаем V( d) = 4.

(5) Возвращаемся к b и переходим к е.

(6) Рассматриваем первого преемника позиции е с оценкой 5. В этот момент МАКС (который как раз и должен ходить в позиции е) обнаруживает, что ему гарантирована в позиции е оценка не меньшая, чем 5, независимо от оценок других (возможно, более предпочтительных) вариантов хода. Этого вполне достаточно для того, чтобы МИН, даже не зная точной оценки позиции е, понял, что для него в позиции b ход в е хуже, чем ход в d.

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

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

Как уже говорилось раньше, ключевая идея альфа-бета отсечения состоит в том, чтобы найти ход не обязательно лучший, но "достаточно хороший" для того, чтобы принять правильное решение. Эту идею можно формализовать, введя два граничных значения, обычно обозначаемых через Альфа и Бета, между которыми должна заключаться рабочая оценка позиции. Смысл этих граничных значений таков: Альфа -это самое маленькое значение оценки, которое к настоящему моменту уже гарантировано для игрока МАКС; Бета - это самое большое значение оценки, на которое МАКС пока еще может надеяться. Разумеется, с точки зрения МИН'а, Бета является самым худшим значением оценки, которое для него уже гарантировано. Таким образом, действительное значение оценки (т. е. то, которое нужно найти) всегда лежит между Альфа и Бета. Если же стало известно, что оценка некоторой позиции лежит вне интервала Альфа-Бета, то этого достаточно для того, чтобы сделать вывод: данная позиция не входит в основной вариант. При этом точное значение оценки такой позиции знать не обязательно, его надо знать только тогда, когда оценка лежит между Альфа и Бета. "Достаточно хорошую" рабочую оценку V( Р, Альфа, Бета) позиции Р по отношению к Альфа и Бета можно определить формально как любое значение, удовлетворяющее следующим ограничениям:

V( P, Альфа, Бета) <= Альфа если V( P) <= Альфа

V( P, Альфа, Бета) = V( P) если Альфа < V( P) < Бета

V( P, Альфа, Бета) >= Бета если V( P) >= Бета

Дерево рис. 15.2 после применения...

Дерево рис. 15.2 после применения альфа-бета алгоритма.
Пунктиром показаны ветви, отсеченные альфа-бета алгоритмом
для экономии времени поиска. В результате некоторые из
рабочих оценок стали приближенными (вершины c, е, f;
сравните с рис.15.2). Однако этих приближенных оценок
достаточно для вычисления точной оценки корневой
вершины и построения основного варианта.

Очевидно, что, умея вычислять "достаточно хорошую" оценку, мы всегда можем вычислить точную оценку корневой позиции Р, установив границы интервала следующим образом:

V( Р, -бесконечность, +бесконечность) = V( P)

На рис. 15.5 показана реализация альфа-бета алгоритма в виде программы на Прологе. Здесь основное отношение -

альфабета( Поз, Альфа, Бета, ХорПоз, Оц)

где ХорПоз - преемник позиции Поз с "достаточно хорошей" оценкой Оц, удовлетворяющей всем указанным выше ограничениям:

Оц = V( Поз, Альфа, Бета)

Процедура

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

находит достаточно хорошую позицию ХорПоз в списке позиций СписПоз; Оц - приближенная (по отношению к Альфа и Бета) рабочая оценка позиции ХорПоз.

Интервал между Альфа и Бета может сужаться (но не расширяться!) по мере углубления поиска, происходящего при рекурсивных обращениях к альфа-бета процедуре. Отношение

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

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

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

line();

% Альфа-бета алгоритм

        альфабета( Поз, Альфа, Бета, ХорПоз, Оц) :-
                ходы( Поз, СписПоз), !,
                прибл_лучш( СписПоз, Альфа, Бета, ХорПоз, Оц);
                стат_оц( Поз, Оц).

        прибл_лучш( [Поз | СписПоз], Альфа, Бета, ХорПоз, ХорОц) :-
                альфабета( Поз, Альфа, Бета, _, Оц),
                дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц).

дост_хор( [ ], _, _, Поз, Оц, Поз, Оц) :- !.
% Больше нет кандидатов

        дост_хор( _, Альфа, Бета, Поз, Оц, Поз, Оц) :-
                ход_мина( Поз), Оц > Бета, !;
                                                % Переход через верхнюю границу
                ход_макса( Поз), Оц < Альфа, !.
                                                % Переход через нижнюю границу

        дост_хор( СписПоз, Альфа, Бета, Поз, Оц, ХорПоз, ХорОц) :-
                нов_границы( Альфа, Бета, Поз, Оц, НовАльфа, НовБета),
                                                % Уточнить границы
                прибл_лучш( СписПоз, НовАльфа, НовБета, Поз1, Оц1),
                выбор( Поз, Оц, Поз1, Оц1, ХорПоз, ХорОц).

        нов_границы( Альфа, Бета, Поз, Оц, Оц, Бета) :-
                ход_мина( Поз), Оц > Альфа, !.
                                                % Увеличение нижней границы

        нов_границы( Альфа, Бета, Поз, Оц, Альфа, Оц) :-
                ход_макса( Поз), Оц < Бета, !.
                                                % Уменьшение верхней границы

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

        выбор( Поз, Оц, Поз1, Оц1, Поз, Оц) :-
                ход_мина( Поз), Оц > Оц1, !;
                ход_макса( Поз), Оц < Оц1, !.

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

line();

Фрагмент шахматной партии, полученный с использованием

таблицы советов рис. 15.7 и иллюстрирующий применение стратегии
оттеснения короля в угол доски. В этой последовательности ходов
выполнялись элементарные советы: сохранить_ простр (выжидающий
ход, сохраняющий "жизненное пространство" черного короля) и
потеснить (ход, сокращающий "жизненное пространство"). Область,
в которой заключен черный король, выделена штриховкой. После
выполнения последнего совета потеснить эта область сократилась
с восьми до шести клеток.

Игры

Глава 15. ИГРЫ

В этой главе мы рассмотрим методы программирования игр двух лиц с полной информацией (таких, как шахматы). Для игр, представляющих интерес, деревья возможных продолжений слишком велики, чтобы можно было говорить о полном переборе, поэтому необходимы какие-то другие подходы. Один из таких методов, основанный на минимаксном принципе, имеет эффективную реализацию, известную под названием "альфа-бета алгоритм". В дополнение к этому стандартному методу, мы разработаем в этой главе программу на основе Языка Советов (Advice Language), который дает возможность вносить в шахматную программу знания о типовых ситуациях. Этот довольно подробный пример может послужить еще одной иллюстрацией того, насколько хорошо Пролог приспособлен для реализации систем, основанных на знаниях

Игры двух лиц с полной информацией

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

Для игр такого рода возможно представление в виде дерева игры (или игрового дерева). Вершины этого дерева соответствуют ситуациям, а дуги ходам. Начальная ситуация игры - это корневая вершина; листьями дерева представлены терминальные позиции.

В большинстве игр этого типа возможны следующие исходы: выигрыш, проигрыш и ничья. Мы будем рассматривать здесь игры, имеющие только два возможных исхода - выигрыш и проигрыш. Игры, в которых возможна ничья, можно упрощенно считать играми с двумя исходами - выигрыш и не-выигрыш. Двух участников игры мы будем называть "игроком" и "противником". "Игрок" может выиграть в некоторой нетерминальной позиции с ходом игрока ("позиции игрока"), если в ней существует какой-нибудь разрешенный ход, приводящий к выигрышу. С другой стороны, некоторая нетерминальная позиция с ходом противника ("позиция противника") является выигранной для игрока, если все разрешенные ходы из этой позиции ведут к позициям, в которых возможен выигрыш. Эти правила находятся в полном соответствии с представлением задач в форме И / ИЛИ-дерева, которое мы обсуждали в гл. 13.Между понятиями, относящимися к И / ИЛИ-деревьям, и понятиями, используемыми в играх, можно установить взаимное соответствие следующим образом:

позиции игры вершины, задачи

терминальные позиции целевые вершины,
выигрыша тривиально решаемые задачи

терминальные позиции задачи, не имеющие решения
проигрыша

выигранные позиции задачи, имеющие решение

позиции игрока ИЛИ-вершины

позиции противника И-вершины

Очевидно, что аналогичным образом понятия, относящиеся к поиску в И / ИЛИ-деревьях, можно переосмыслить в терминах поиска в игровых деревьях.

Ниже приводится простая программа, которая определяет, является ли некоторая позиция игрока выигранной.

        выигр( Поз) :-
                терм_выигр( Поз).
                                          % Терминальная выигранная позиция

        выигр( Поз) :-
                not терм_проигр( Поз),
                ход( Поз, Поз1),                         % Разрешенный ход в Поз1
                not ( ход( Поз1, Поз2),
                         not выигр( Поз2) ).
                  % Ни один из ходов противника не ведет к не-выигрышу

Здесь правила игры встроены в предикат ход( Поз, Поз1), который порождает все разрешенные ходы, а также в предикаты терм_выигр( Поз) и терм_проигр( Поз), которые распознают терминальные позиции, являющиеся, согласно правилам игры, выигранными или проигранными. В последнем из правил программы, содержащем двойное отрицание (not), говорится: не существует хода противника, ведущего к не выигранной позиции. Другими словами: все ходы противника приводят к позициям, выигранным с точки зрения игрока.

Литература

Минимаксный принцип, реализованный в форме альфа-бета алгоритма, - это наиболее популярный метод в игровом программировании. Особенно часто он применяется в шахматных программах. Минимаксный принцип был впервые предложен Шенноном (Shannon 1950). Возникновение и становление альфа-бета алгоритма имеет довольно запутанную историю. Несколько исследователей независимо друг от друга открыли либо реализовали этот метод полностью или частично. Эта интересная история описана в статье Knuth and Moore (1978). Там же приводится более компактная формулировка альфа-бета алгоритма, использующая вместо минимаксного принципа принцип "него-макса" ("neg-max" principle), и приводится математический анализ производительности алгоритма. Наиболее полный обзор различных минимаксных алгоритмов вместе с их теоретическим анализом содержится в книге Pearl (1984). Существует еще один интересный вопрос, относящийся к минимаксному принципу. Мы знаем, что статическим оценкам следует доверять только до некоторой степени. Можно ли считать, что рабочие оценки являются более надежными, чем исходные статические оценки, из которых они получены? В книге Pearl (1984) собран ряд математических результатов, имеющих отношение к ответу на этот вопрос. Приведенные в этой книге результаты, касающиеся распространения ошибок по минимаксному дереву, объясняют, в каких случаях и почему минимаксный принцип оказывается полезным.

Сборник статей Bramer (1983) охватывает несколько аспектов игрового программирования. Frey (1983) - хороший сборник статей по шахматным программам. Текущие разработки в области машинных шахмат регулярно освещаются в серии Advances in Computer Chess и в журнале ICCA.

Метод Языка Советов, позволяющий использовать знания о типовых ситуациях, был предложен Д. Мики. Дальнейшее развитие этого метода отражено в Bratko and Michi (1980 a, b) и Bratko (1982, 1984, 1985). Программа для игры в эндшпиле "король и ладья против короля", описанная в этой главе, совпадает с точностью до незначительных модификаций с таблицей советов, корректность которой была математически доказана в статье Bratko (1978). Ван Эмден также запрограммировал эту таблицу советов на Прологе (van Emden 1982).

Среди других интересных экспериментов в области машинных шахмат, преследующих цель повысить эффективность знаний (а не перебора), следует отметить Berliner (1977), Pitrat (1977) и Wilkins (1980).

Advances in Computer Chess Series (M.R.B. Clarke, ed). Edinburgh University Press (Vols. 1-2), Pergamon Press (Vol. 3).

Berliner M. A. (1977); A representation and some mechanisms for a problem solving chess program. In: Advances in Computer Chess 1 (M.R.B. Clarke, ed). Edinburgh University Press.

Bramer M. A; (1983, ed). Computer Game Playing: Theory and Practice. Ellis Horwood and John Wiley.

Bratko I. (1978) Proving correctness of strategies in the AL1 assertional language. Information Processing Letters 7: 223-230.

Bratko I. (1982). Knowledge-based problem solving in AL3. In: Machine Intelligence 10 (J. Hayes, D. Michie, J. H. Pao, eds.). Ellis Horwood (an abbreviated version also appears in Bramer 1983).

Bratko I. (1984). Advise and planning in chess end-games. In: Artificial and Human Intelligence (S. Amarel, A. Elithorn, R. Banerji, eds.). North-Holland.

Bratko I. (1985). Symbolic derivation of chess patterns. In: Progress Artificial Intelligence (L. Steels, J. A. Campbell, eds.). Ellis Horwood and John Wiley.

Bratko I. and Michie D. (1980a). A representation of pattern-knowledge in chess end-games. In: Advances in Computer Chess 2 (M.R.B. Clarke, ed). Edinburgh University Press.

Bratko I. and Michie D. (1980b). An advice program for a complex chess programming task. Computer Journal 23: 353-359.

Frey P. W. (1983, ed.). Chess Skill in Man and Machine (second edition). Springer-Verlag.

Knuth D. E. and Moore R. W. (1975). An analysis of alpha-beta pruning. Artificial Intelligence 6: 93-326.

Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Pitrat J. (1977). A chess combination program which uses plans Artificial Intelligence 8: 275-321.

Shannon C.E. (1950). Programming a computer for playing chess. Philosophical Magazine 41: 256-275. [В сб. Шеннон К. Работы по теории информации и кибернетике. - М.: ИЛ., 1963.]

van Emden M. (1982). Chess end-game advice: a case study in computer utilisation of knowledge. In: Machine Intelligence 10 (J. Hayes, D. Michie, J.H. Pao, eds). Ellis Hordwood.

Wilkins D.E. (1980). Using patterns and plans in chess. Artificial Intelligence 14: 165-203.

Миниатюрный интерпретатор языка al0.

Миниатюрный интерпретатор языка AL0.

игра( Поз)

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

Форсированное дерево - это дерево ходов, представленное в программе следующей структурой:

Ход . . [ Ответ1 . . Фдер1, Ответ2 . . Фдер2, . . . ]

Здесь ".." - инфиксный оператор; Ход - первый ход "игрока"; Ответ1, Ответ2, ... - возможные ответы противника; Фдер1, Фдер2, ... - форсированные поддеревья для каждого из этих ответов.

    Программа на языке советов для эндшпиля
                 "король и ладья против короля"
2.    Программа на языке советов для эндшпиля
                 "король и ладья против короля"

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

line();

Повторять циклически, пока не будет поставлен мат (постоянно проверяя, что не возникла патовая позиция и что нет нападения на незащищенную ладью):

(1) Найти способ поставить королю противника мат в два хода.

(2) Если не удалось, то найти способ уменьшить ту область доски, в которой
король противника "заперт" под воздействием ладьи.

(3) Если и это не удалось, то найти способ приблизить своего короля к королю
противника.

    (4)        Если ни один из элементарных советов 1, 2, или 3 не выполним, то найти
                способ сохранить все имеющиеся к настоящему моменту "достижения" в
                смысле (2) и (3) (т. е. сделать выжидающий ход).

    (5)        Если ни одна из целей 1, 2, 3 или 4 не достижима, то найти способ получить
                позицию, в которой ладья занимает вертикальную или горизонтальную
                линию, отделяющую одного короля от другого.

line();

Описанные выше принципы реализованы во всех деталях в таблице советов на языке AL0, показанной на рис. 15.7. Эта таблица может работать под управлением интерпретатора рис. 15.6. Рис. 15.8 иллюстрирует смысл некоторых из предикатов, использованных в таблице советов, а также показывает, как эта таблица работает.

В таблице используются следующие предикаты:

Предикаты целей

мат мат королю противника

пат пат королю противника

потеря_ладьи король противника может взять ладью

ладья_под_боем король противника может напасть на ладью прежде, чем наш
король сможет ее защитить

уменьш_простр уменьшилось "жизненное пространство" короля противника,
ограничиваемое ладьей

раздел ладья занимает вертикальную или горизонтальную линию,
разделяющую королей

ближе_к_клетке наш король приблизился к "критической клетке" (см. рис. 15.9),
т.е. манхеттеновское расстояние до нее уменьшилось

l_конфиг "L-конфигурация" (рис. 15.9)

простр_больше_2 "жизненное пространство" короля противника занимает
больше двух клеток

Предикаты, ограничивающие ходы

    глубина = N                  ход на глубине N дерева поиска
    разреш                           любой разрешенный ход
    ход_шах                         ход, объявляющий шах
    ход_ладьей                   ход ладьей
    нет_хода                       ни один ход не подходит
    сначала_диаг               ход королем, преимущественно по диагонали

line();

% Окончание "король и ладья против короля" на языке AL0

% Правила

        правило_края:
                     если король_противника_на_краю и короли_рядом
                     то [мат_2, потеснить, приблизиться,
                             сохранить_простр, отделить_2, отделить_3].

        иначе_правило
                     если любая_поз
                     то [ потеснить, приблизиться, сохранить_простр,
                             отделить_2, отделить_3].

% Элементарные советы

        совет( мат_2,
                     мат :
                     не потеря_ладьи и король_противника_на_краю:
                     (глубина = 0) и разреш
                     затем (глубина = 2) и ход_шах :
                     (глубина = 1) и разреш ).

        совет( потеснить,
                     уменьш_простр и не ладья_под_боем и
                     раздел и не пат :
                     не потеря_ладьи :
                     (глубина = 0) и ход_ладьей :
                     нет_хода ).

        совет( приблизиться,
                     ближе _к_клетке и не ладья_под_боем и
                     (раздел или l_конфиг) и
                     (простр_больше_2 или не наш_король_на_краю):
                     не потеря_ладьи :
                     (глубина = 0) и сначала_диаг :
                     нет_хода ).

        совет( сохранить_простр,
                     ход_противиика и не ладья_под_боем и раздел
                     и не_дальше_от_ладьи и
                     (простр_больше_2 или не наш_король_на_краю):
                     не потеря_ладьи :
                     (глубина = 0) и сначала_диаг :
                     нет_хода ).

        совет( отделить_2,
                     ход_противника и раздел и не ладья_под_боем:
                     не потеря_ладьи :
                     (глубина < 3) и разреш :
                     (глубина < 2) и разреш ).

        совет( отделить_3,
                     ход_противника и раздел и не ладья_под_боем:
                     не потеря_ладьи :
                     (глубина < 5) и разреш :
                     (глубина < 4) и разреш ).

line();

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

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

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

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

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

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

Метод последовательного углубления влечет за собой некоторые накладные расходы (из-за повторного поиска в верхней части игрового дерева), но они незначительны по сравнению c суммарными затратами.

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

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

Знания в минимаксных игровых программах имеют следующие три основные формы: оценочная функция эвристики для отсечения ветвей эвристики для распознавания спокойных позиций

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

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

В оставшейся части главы мы рассмотрим еще один подход к программированию игр, основанный на внесении в программу знаний о типовых ситуациях при помощи так называемых "советов".

Минимаксный принцип

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

Обратите внимание на то, что мы здесь делаем определенное различие между "деревом игры" и "деревом поиска". Дерево поиска - это только часть дерева игры (его верхняя часть), т. е. та его часть, которая была явным образом порождена в процессе поиска. Таким образом, терминальные поисковые позиции совсем не обязательно должны совпадать с терминальными позициями самой игры.

Очень многое зависит от оценочной функции, которая для большинства игр, представляющих интерес, является приближенной эвристической оценкой шансов на выигрыш одного из участников игры. Чем выше оценка, тем больше у него шансов выиграть и чем ниже оценка, тем больше шансов на выигрыш у его противника. Поскольку один из участников игры всегда стремится к высоким оценкам, а другой - к низким, мы дадим им имена МАКС и МИН соответственно. МАКС всегда выбирает ход с максимальной оценкой; в противоположность ему МИН всегда выбирает ход с минимальной оценкой. Пользуясь этим принципом (минимаксным принципом) и зная значения оценок для всех вершин "подножья" дерева поиска, можно определить оценки всех остальных вершин дерева. На рис. 15.2 показано, как это делается. На этом рисунке видно, что уровни позиций с ходом МАКС'а чередуются с уровнями позиций с ходом МИН'а. Оценки вершин нижнего уровня определяются при помощи оценочной функции. Оценки всех внутренних вершин можно определить, двигаясь снизу вверх от уровня к уровню, пока мы не достигнем корневой вершины. В результате, как видно из рис. 15.2, оценка корня оказывается равной 4, и, соответственно, лучшим ходом МАКС'а из позиции а - a-b. Лучший ответ МИН'а на этот ход - b-d, и т.д. Эту последовательность ходов называют также основным вариантом. Основной вариант показывает, какова "минимаксно-оптимальная" игра для обоих участников. Обратите внимание на то, что оценки всех позиций, входящих в основной вариант, совпадают.

Проект

Напишите программу для какой-нибудь простой игры (такой, как ним), использующую упрощенный алгоритм войска в И / ИЛИ-дереве.

Проект

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

Проект

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

line();

% Библиотека предикатов для окончания
% "король и ладья против короля"

% Позиция представлена стуктурой:
% ЧейХод..Бх : Бу..Лх : Лу..Чх : Чу..Глуб
% ЧейХод - с чьей стороны ход в этой позиции ('б' или 'ч')
% Бх, Бу - координаты белого короля
% Лх, Лу - координаты белой ладьи
% Чх, Чу - координаты черного короля
% Глуб - глубина, на которой находится эта позиция в дереве
% поиска

% Отношения выбора элементов позиции

чей_ход( ЧейХод.._, ЧейХод).
        бк( _..БК.._, БК).                                         % Белый король
        бл( _.._..БЛ.._, БЛ).                                     % Белая ладья
        чк( _.._.._..ЧК.._, ЧК).                                % Черный король
        глуб( _.._.._.._..Глуб, Глуб).

восст_глуб( ЧХ..Б..Л..Ч..Г, ЧХ..Б..Л..Ч..0).
% Формируется копия позиции, глубина устанавливается в 0

% Некоторые отношения между клетками доски

        сосед_чсл( N, N1) :-             % Соседнее число "в пределах доски"
                ( N1 is N + 1;
                  N1 is N - 1 ),
                внутри( N1).

внутри( N) :-
N > 0, N < 9.

        сосед_диаг( X : Y, X1 : Y1) :-
                                    % Соседние клетки по диагонали
                сосед_чсл( X, X1 ), сосед_чсл( Y, Y1).

        сосед_верт( X : Y, X : Y1) :-
                                    % Соседние клетки по вертикали
                сосед_чсл( Y, Y1).

        сосед_гор( X : Y, X1 : Y) :-
                                    % Соседние клетки по горизонтали
                сосед_чсл( X, X1).

        сосед( S, S1) :-
                                    % Соседние клетки (предпочтение - диагонали)
                сосед_диаг( S, S1);
                сосед_гор( S, S1);
                сосед_верт( S, S1).

конец_игры( Поз) :-
мат( Поз).

% Предикаты, ограничивающие ходы
% Специализированное генераторы ходов вида:
% ход( Ограничение, Поз, Ход, Поз1)

        ход( глубина < Макс, Поз, Ход, Поз1) :-
                глуб( Поз, Г),
                Г < Макс, !.

ход( глубина = Г, Поз, Ход, Поз1) :-
глуб( Поз, Г), !.

        ход( сначала диаг, б..Б..Л..Ч..Г, Б-Б1,
                                            ч..Б1..Л..Ч..Г1) :-
                Г1 is Г + l,
                сосед( Б, Б1),
                                    % "сосед" порождает сначала диагональные ходы
                not сосед( Б1, Ч),                                 % Не попасть под шах
                Б1 \== Л.                                              % Не столкнуться с ладьей

        ход( ход ладьей, б..Б..Лх : Лу..Ч..Г, Лх : Лу-Л,
                                                                ч..Б..Л..Ч..Г1) :-
                Г1 is Г + 1,
                коорд( I),                                               % Число между 1 и 8
                ( Л = Лх : I; Л = I : Лу),
                                    % По горизонтали или по вертикали
                Л \== Лх : Лу,                                      % Обязательно двигаться
                not мешает( Лх : Лу, Б, Л).                % Мешает белый король

        ход( ход_шах, Поз, Л-Лх : Лу, Поз1) :-
                бл( Поз, Л),
                чк( Поз, Чх : Чу),
                ( Лх = Чх; Лу = Чу),
                                    % Ладья и черный король на одной линии
                ход( ход_ладьей, Поз, Л-Лх : Лу, Поз1).

        ход( разреш, б..П, М, П1) :-
                ( Огр = сначала_диаг; Огр = ход ладьей),
                ход( Огр, б..П, М, П1).

        ход( разреш, ч..Б..Л..Ч..Г, Ч-Ч1, б..Б..Л..Ч1..Г1) :-
                Г1 is Г + 1,
                сосед( Ч, Ч1),
                not шах( б..Б..Л..Ч1..Г1).

разрход( Поз, Ход, Поз1) :-
ход( разреш, Поз, Ход, Поз1).

        шах( _..Б..Лх : Лу..Чх : Чу.._ ) :-
                сосед( Б, Чх : Чу);                                  % Короли рядом
                ( Лх = Чх; Лу = Чу),
                Лх : Лу \== Чх : Чу,                                % Нет взятия ладьи
                not мешает( Лх : Лу, Б, Чх : Чу).

мешает( S, S1, S1) :- !.

мешает( X1 : Y, X2 : Y, Х3 : Y) :-
упоряд( X1, Х2, Х3), !.

мешает( X : Y1, X : Y2, X : Y3) :-
упоряд( Y1, Y2, Y3).

        упоряд( N1, N2, N3) :-
                N1 < N2, N2 < N3;
                N3 < N2, N2 < N1.

коорд( 1). коорд( 2). коорд( 3). коорд( 4).

коорд( 5). коорд( 6). коорд( 7). коорд( 8).

% Предикаты целей

любая_поз( Поз).

ход_противника( б.._ ). % Противник ходит белыми

        мат( Поз) :-
                чей_ход( Поз, ч),
                шах( Поз),
                not разрход( Поз, _, _ ).

        пат( Поз) :-
                чей_ход( Поз, ч),
                not шах( Поз),
                not разрход( Поз, _, _ ).

        уменьш_простр( Поз, КорнПоз) :-
                простр( Поз, Пр),
                простр( КорнПоз, КорнПр),
                Пр < КорнПр.

        ладья_под_боем( ЧейХод..Б..Л..Ч.._ ) :-
                расст( Б, Л, Р1),
                расст( Ч, Л, Р2),
                ( ЧейХод = б, !, Р1 > Р2 + 1;
                  ЧейХод = ч, !, Р1 > Р2 ).

        ближе_к_клетке( Поз, КорнПоз) :-
                расст_до_клетки( Поз, Р1),
                расст_до_клетки( КорнПоз, Р2),
                Р1 < Р2.

        расст_до_клетки( Поз, Мрасст) :-
                                                          % Манхеттеновское расстояние
                бк( Поз, БК),                   % между БК и критической клеткой
                кк( Поз, КК),                   % Критическая клетка
                манх_расст( БК, КК, Мрасст).

        раздел( _..Бх : Бу..Лх : Лу.. Чх : Чу.._ ) :-
                упоряд( Бх, Лх, Чх), !;
                упоряд( Бу, Лу, Чу).

        l_конфиг( _..Б..Л..Ч.._ ) :-                           % L - конфигурация
                манх_расст( Б, Ч, 2),
                манх_расст( Л, Ч, 3).

        не дальше_от_ладьи( _..Б..Л.._, _..Б1..Л1.._ ) :-
                расст( Б, Л, Р),
                расст( Б1, Л1, Р1),
                Р =< Р1.

        простр_больше_2( Поз) :-
                простр( Поз, Пр),
                Пр > 2.

        наш_король_на_краю( _..Х : Y.._ ) :-
                                                          % Белый король на краю
                ( X = 1, !; X = 8, !; Y = 1, !; Y = 8).

        король_противника_на_краю( _..Б..Л..Х : Y.._ ) :-
                                                          % Черный король на краю
                ( X = 1, !; X = 8, !; Y = 1, !; Y = 8).

        короли_рядом( Поз) :-                                       % Расстояние между королями < 4
                бк( Поз, БК), чк( Поз, ЧК),
                расст( БК, ЧК, Р),
                Р < 4.

потеря_ладьи( _..Б..Л..Л.._ )- % Ладья взята

        потеря_ладьи( ч..Б..Л..Ч.._ ) :-
                сосед( Ч, Л),                    % Черный король напал на ладью
                not сосед( Б, Л).              % Белый король не защищает ладью

        расст( X : Y, X1 : Y1, Р) :-                                % Расстояние до короля
                абс_разн( X, X1, Рх),
                абс_разн( Y, Y1, Ру),
                макс( Рх, Ру, Р).

        абс_разн( А, В, С) :-
                А > В, !, С is A - В;
                С is В - А.

        макс( А, В, М) :-
                А >= В, !, М = А;
                М = В.

манх_расст( X : Y, X1 : Y1, Р) :- % Манхеттеновское расстояние

                абс_разн( X, X1, Рх),
                абс_разн( Y, Y1, Ру),
                P is Рх + Ру.

        простр( Поз, Пр) :-
                                    % Область, в которой "заперт" черный король
                бл( Поз, Лх : Лу),
                чк( Поз, Чх : Чу),
                ( Чх < Лх, СторонаХ is Лх - 1;
                  Чх > Лх, СторонаХ is 8 - Лх ),
                ( Чу < Лу, СторонаY is Лу - 1;
                  Чу > Лу, СторонаY is 8 - Лу ),
                Пр is СторонаХ * СторонаY, !;
                Пр = 64.      % Ладья и черный король на одной линии

        кк( _..Б..Лх : Лу.. Чх : Чу.._, Кх : Ку) :-
                                    % Критическая клетка
                ( Чх < Лх, !, Кх is Лх - 1; Кх is Лх + 1),
                ( Чу < Лу, !, Ку is Лу - 1; Ку is Лу + 1).

% Процедуры для отображения позиций

        отобр( Поз) :-
                nl,
                коорд( Y), nl,
                коорд( X),
                печ_фиг( X : Y, Поз),
                fail.

        отобр( Поз) :-
                чей_ход( Поз, ЧХ), глуб( Поз, Г),
                nl, write( 'ЧейХод='), write( ЧХ),
                write( 'Глубина='), write( Г), nl.

        печ_фиг( Клетка, Поз):-
                бк( Поз, Клетка), !, write( 'Б');
                бл( Поз, Клетка), !, write( 'Л');
                чк( Поз, Клетка), !, write( 'Ч');
                write( '.').

показать_ход( Ход) :-
nl, write( Ход), nl.

line();

Программа на языке al0 для игры в шахматном эндшпиле

Программа на языке AL0 для игры в шахматном эндшпиле

При реализации какой-либо игровой программы на языке AL0 ее можно для удобства разбить на три модуля:

    (1)        интерпретатор языка AL0,
    (2)        таблица советов на языке AL0,
    (3)        библиотека предикатов, используемых в таблице советов (в том числе
                 предикаты, задающие правила игры).

Эта структура соответствует обычной структуре системы, основанной на знаниях: Интерпретатор AL0 выполняет функцию машины логического вывода. Таблица советов вместе с библиотекой предикатов образует базу знаний. Миниатюрный интерпретатор языка AL0
1. Миниатюрный интерпретатор языка AL0

Реализация на Прологе миниатюрного, не зависящего от конкретной игры интерпретатора языка AL0 показана на рис. 15.6. Эта программа осуществляет также взаимодействие с пользователем во время игры. Центральная задача этой программы - использовать знания, записанные в таблице советов, то есть интерпретировать программу на языке советов AL0 с целью построения форсированных деревьев и их "исполнения" в процессе игры. Базовый алгоритм порождения форсированных деревьев аналогичен поиску с предпочтением в И / ИЛИ-графах гл. 13, при этом форсированное дерево соответствует решающему И / ИЛИ-дереву. Этот алгоритм также напоминает алгоритм построения решающего дерева ответа на вопрос пользователя, применявшийся в оболочке экспертной системы (гл. 14).

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

line();

% Миниатюрный интерпретатор языка AL0
%
% Эта программа играет, начиная с заданной позиции,
% используя знания, записанные на языке AL0

        :- ор( 200, xfy, :).
        :- ор( 220, xfy, ..).
        :- ор( 185, fx, если).
        :- ор( 190, xfx, то).
        :- ор( 180, xfy, или).
        :- ор( 160, xfy, и).
        :- ор( 140, fx, не).

        игра( Поз) :-                                                 % Играть, начиная с Поз
                игра( Поз, nil).
                                          % Начать с пустого форсированного дерева

        игра( Поз, ФорсДер) :-
                отобр( Поз),
                ( конец_игры( Поз),                            % Конец игры?
                        write( 'Конец игры'), nl, !;
                  сделать_ход( Поз, ФорсДер, Поз1, ФорсДер1), !,
                        игра( Поз1, ФорсДер1) ).

% Игрок ходит в соответствии с форсированным деревом

        сделать_ход( Поз, Ход .. ФДер1, Поз1, ФДер1) :-
                чей_ход( Поз, б),                                 % Программа играет белыми
                разрход( Поз, Ход, Поз1),
                показать_ход( Ход).

% Прием хода противника

        сделать_ход( Поз, ФДер, Поз1, ФДер1) :-
                чей_ход( Поз, ч),
                write( 'Ваш ход:'),
                read( Ход),
                ( разрход( Поз, Ход, Поз1),
                        поддер( ФДер, Ход, ФДер1), !;
                                          % Вниз по форс. дереву
                  write( 'Неразрешенный ход'), nl,
                        сделать_ход( Поз, ФДер, Поз1, ФДер1) ).

% Если текущее форсированное дерево пусто, построить новое

        сделать_ход( Поз, nil, Поз1, ФДер1) :-
                чей_ход( Поз, б),
                восст_глуб( Поз, Поз0),
                                        % Поз0 = Поз с глубиной 0
                стратегия( Поз0, ФДер), !,
                                        % Новое форсированное дерево
                сделать_ход( Поз0, ФДер, Поз1, ФДер1).

% Выбрать форсированное поддерево, соответствующее Ход' у

поддер( ФДеревья, Ход, Фдер) :-
принадлежит( Ход . . Фдер, ФДеревья), !.

поддер( _, _, nil).

        стратегия( Поз, ФорсДер) :-
                                        % Найти форс. дерево для Поз
                Прав : если Условие то СписСов,
                                        % Обращение к таблице советов
                удовл( Условие, Поз, _ ), !,
                                        % Сопоставить Поз с предварительным условием
                принадлежит( ИмяСовета, СписСов),
                                        % По очереди попробовать элем. советы
                nl, write( 'Пробую'), write( ИмяСовета),
                выполн_совет( ИмяСовета, Поз, ФорсДер), !.

        выполн_совет( ИмяСовета, Поз, Фдер) :-
                совет( ИмяСовета, Совет),
                                        % Найти элементарный совет
                выполн( Совет, Поз, Поз, ФДер).
                % "выполн" требует две позиции для сравнивающих предикатов

        выполн( Совет, Поз, КорнПоз, ФДер) :-
                поддержка( Совет, ЦП),
                удовл( ЦП, Поз, КорнПоз),
                                        % Сопоставить Поз с целью-поддержкой
                выполн1( Совет, Поз, КорнПоз, ФДер).

        выполн1( Совет, Поз, КорнПоз, nil) :-
                главцель( Совет, ГлЦ),
                удовл( ГлЦ, Поз, КорнПоз), !.
                                        % Главная цель удовлетворяется

        выполн1( Совет, Поз, КорнПоз, Ход .. ФДеревья) :-
                чей_ход( Поз, б), !,                                  % Программа играет белыми
                ходы_игрока( Совет, ХодыИгрока),
                                        % Ограничения на ходы игрока
                ход( ХодыИгрока, Поз, Ход, Поз1),
                                        % Ход, удовлетворяющий ограничению
                выполн( Совет, Поз1, КорнПоз, ФДеревья).

        выполн1( Совет, Поз, КорнПоз, ФДеревья) :-
                чей_ход( Поз, ч), !,                                 % Противник играет черными
                ходы_противника( Совет, ХодыПр),
                bagof ( Ход . . Поз1, ход( ХодыПр, Поз, Ход, Поз1), ХПспис),
                выполн_все( Совет, ХПспис, КорнПоз, ФДеревья).
                                        % Совет выполним во всех преемниках Поз

выполн_все( _, [ ], _, [ ]).

        выполн_все( Совет, [Ход . . Поз | ХПспис], КорнПоз,
                                                                [Ход . . ФД | ФДД] ) :-
                выполн( Совет, Поз, КорнПоз, ФД),
                выполн_все( Совет, ХПспис, КорнПоз, ФДД).

% Интерпретация главной цели и цели-поддержки:
% цель - это И / ИЛИ / НЕ комбинация. имен предикатов

        удовл( Цель1 и Цель2, Поз, КорнПоз) :- !,
                удовл( Цель1, Поз, КорнПоз),
                удовл( Цель2, Поз, КорнПоз).

        удовл( Цель1 или Цель2, Поз, КорнПоз) :- !,
                ( удовл( Цель1, Поз, КорнПоз);
                удовл( Цель2, Поз, КорнПоз) ).

удовл( не Цель, Поз, КорнПоз) :- !,
not удовл( Цель, Поз, КорнПоз ).

        удовл( Пред, Поз, КорнПоз) :-
                ( Усл =.. [Пред, Поз];
                                            % Большинство предикатов не зависит от КорнПоз
                    Усл =.. [Пред, Поз, КорнПоз] ),
                call( Усл).

% Интерпретация ограничений на ходы

        ход( Ходы1 и Ходы2, Поз, Ход, Поз1) :- !,
                ход( Ходы1, Поз, Ход, Поз1),
                ход( Ходы2, Поз, Ход, Поз1).

        ход( Ходы1 затем Ходы2, Поз, Ход, Поз1) :- !,
                ( ход( Ходы1, Поз, Ход, Поз1);
                ход( Ходы2, Поз, Ход, Поз1) ).

% Доступ к компонентам элементарного совета

главцель( ГлЦ : _, ГлЦ).

поддержка( ГлЦ : ЦП : _, ЦП).

ходы_игрока( ГлЦ : ЦП : ХодыИгрока : _, Ходы Игрока).

ходы_противника( ГлЦ : ЦП: ХодыИгр : ХодыПр :_,
ХодыПр).

принадлежит( X, [X | Спис]).

принадлежит( X, [Y | Спис]) :-
принадлежит( X, Спис).

line();

"критическая клетка" отмечена крестиком.

(а) "Критическая клетка" отмечена крестиком. Она

используется при маневрировании с целью оттеснить черного
короля. Белый король приближается к "критической клетке",
двигаясь, как указано на рисунке. (б) Три фигуры образуют
конфигурацию, напоминающую букву L.

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

На рис. 15.8 показано, как играет наша программа, основанная на механизме советов. При продолжении игры из последней позиции рис. 15.8 она могла бы протекать так, как в приведенном ниже варианте (в предположении, что "противник" ходит именно так, как указано). Здесь использована алгебраическая шахматная нотация, в которой вертикальные линии пронумерованы, как 'а', 'b', 'с', .... а горизонтальные - как 1, 2, 3, ... . Например, ход ЧК b7 означает: передвинуть черного короля на клетку. расположенную на пересечении вертикальной линии 'b' с горизонтальной линией 7.

    ...                        ЧК b7
    БК d5                 ЧК с7
    БК с5                 ЧК b7
    БЛ с6                 ЧК а7
    БЛ b6                 ЧК а8
    БК b5                 ЧК а7
    БК с6                 ЧК а8
    БК с7                 ЧК а7
    БЛ с6                 ЧК а8
    БЛ а6                 мат

Теперь уместно задать некоторые вопросы. Во-первых, является ли наша программа-советчик корректной в том смысле, что она ставит мат при любом варианте защиты со стороны противника и при любой начальной позиции, в которой на доске король и ладья против короля? В статье Bratko (1978) приведено формальное доказательство того, что таблица советов, практически совпадающая с таблицей рис. 15.7, действительно является корректной в указанном смысле.

Другой возможный вопрос: является ли программа оптимальной, то есть верно ли, что она ставит мат за минимальное число ходов? Нетрудно показать на примерах, что игру нашей программы в этом смысле нельзя назвать оптимальной. Известно, что оптимальный вариант в этом окончании (т.е. предполагающий оптимальную игру с обеих сторон) имеет длину не более 16 ходов. Хотя наша таблица советов и далека от этого оптимума, было показано, что число, ходов наверняка не превосходит 50. Это важный результат в связи с тем, что в шахматах существует "правило 50-ти ходов": в эндшпилях типа "король и ладья против короля" противник, имеющий преимущество, должен поставить, мат не более, чем за 50 ходов; иначе может быть объявлена ничья.

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

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

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

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

Игры двух лиц поддаются формальному

Резюме

Игры двух лиц поддаются формальному представлению в виде И / ИЛИ-графов. Поэтому процедуры поиска в И / ИЛИ-графах применимы для поиска в игровых деревьях. Простой алгоритм поиска в глубину в игровых деревьях легко программируется, но для игр, представляющих интерес, он не эффективен. Более реалистичный подход - минимаксный принцип в сочетании с оценочной функцией и поиском, ограниченным по глубине. Альфа-бета алгоритм является эффективной реализацией минимаксного принципа. Эффективность альфа-бета алгоритма зависит от порядка, в котором просматриваются варианты ходов. Применение альфа-бета алгоритма приводит, в лучшем случае, к уменьшению коэффициента ветвления дерева поиска, соответствующему извлечению из него квадратного корня. В альфа-бета алгоритм можно внести ряд усовершенствований. Среди них: продолжение поиска за пределы ограничения по глубине вплоть до спокойных позиций, последовательное углубление и эвристическое отсечение ветвей. Численная оценка позиций является весьма ограниченной формой представления знаний о конкретной игре. Более богатый по своим возможностям метод представления знаний должен предусматривать внесение в программу знаний о типовых ситуациях. Язык Советов (Advice Language) реализует такой подход. На этом языке знания представляются в терминах целей и средств для их достижения. В даннной главе мы составили следующие программы: программная реализация минимаксного принципа и альфа-бета процедуры, интерпретатор языка AL0 и таблица советов для окончания "король и ладья против короля". Были введены и обсуждены следующие понятия:

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

Языки Советов

цели, ограничения, элементарные советы,
таблица советов

Сложность игровых деревьев в шахматах. Оценки основаны

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

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

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

Статические (нижний уровень) и...

Статические (нижний уровень) и минимаксные рабочие
оценки вершин дерева поиска. Выделенные ходы образуют основной
вариант, т. е. минимаксно-оптимальную игру с обеих сторон.

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

Правила распространения оценок можно сформулировать следующим образом. Будем обозначать статическую оценку позиции Р через v( P), а ее рабочую оценку - через V( Р). Пусть Р1, ..., Рn - разрешенные преемники позиции Р. Тогда соотношения между статическими и рабочими оценками можно записать так:

V( Р) = v( P)

если Р - терминальная позиция дерева поиска (n=0)

V( Р) = max V( Рi )
i

если P - позиция с ходом МАКС'а

V( Р) = min V( Рi )
i

если Р - позиция с ходом МИН'а

line();

% Минимаксная процедура: минимакс( Поз, ЛучшПоз, Оц)
% Поз - позиция, Оц - ее минимаксная оценка;
% лучший ход из Поз ведет в позицию ЛучшПоз

        минимакс( Поз, ЛучшПоз, Оц) :-
                ходы( Поз, СписПоз), !,
                                        % СписПоз - список разрешенных ходов
                лучш( СписПоз, ЛучшПоз, Оц);
                стат_оц( Поз, Оц).                 % Поз не имеет преемников

лучш( [Поз], Поз, Оц) :-
минимакс( Поз, _, Оц), !.

        лучш( [Поз1 | СписПоз], ЛучшПоз, ЛучшОц) :-
                минимакс( Поз1, _, Оц1),
                лучш( СписПоз, Поз2, Оц2),
                выбор( Поз1, Оц1, Поз2, Оц2, ЛучшПоз, ЛучшОц).

        выбор( Поз0, Оц0, Поз1, Оц1, Поз0, Оц0) :-
                ход_мина( Поз0), Оц > Оц1, !;
                ход_макса( Поз0), Оц < Оц1, !.

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

line();

Таблица советов на языке al0 для...

Таблица советов на языке AL0 для окончания "король
и ладья против короля". Таблица состоит из двух правил и шести
элементарных советов.

Упрощенная реализация минимаксного принципа.

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

минимакс( Поз, ЛучшПоз, Оц)

где Оц - минимаксная оценка позиции Поз, а ЛучшПоз - наилучшая позиция-преемник позиции Поз (лучший ход, позволяющий достигнуть оценки Оц). Отношение

ходы( Поз, СписПоз)

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

лучш( СписПоз, ЛучшПоз, ЛучшОц)

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

Знания о типовых ситуациях и механизм "советов"

В этом разделе рассматривается метод представления знаний о конкретной игре с использованием семейства Языков Советов. Языки Советов (Advice Languages) дают возможность пользователю декларативным способом описывать, какие идеи следует использовать в тех или иных типовых ситуациях. Идеи формулируются в терминах целей и средств, необходимых для их достижения. Интерпретатор Языка Советов определяет при помощи перебора, какая идея "работает" в данной ситуации.

Цели и ограничения на ходы
1. Цели и ограничения на ходы

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

Рассмотрим, например, шахматный эндшпиль "король и пешка против короля". Здесь применима следующая очевидная идея: провести пешку в ферзи, продвигая ее вперед. В форме совета это выражается так: главная цель: провести пешку; цель-поддержка: не потерять пешку; ходы игрока: продвигать пешку; ходы противника: приближаться королем к пешке . Выполнимость совета
2. Выполнимость совета

Мы говорим, что элементарный совет выполним в данной позиции, если игрок может форсированным образом достигнуть главной цели, указанной в совете, при условии, что:

(1) ни разу не нарушается цель-поддержка;

(2) все ходы игрока удовлетворяют наложенным на них ограничениям;

(3) противнику разрешено делать только те ходы, которые предусмотрены соответствующими ограничениями.

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

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

Правила и таблицы советов
3. Правила и таблицы советов

В Языках Советов отдельные элементарные советы объединяются в полную схему представления знаний, имеющую следующую иерархическую структуру. Элементарный совет является частью "если-то"-правила. Набор "если-то"-правил образует таблицу советов. Множество таблиц советов имеет структуру иерархической сети. Каждая таблица советов выполняет роль эксперта в своей узкой области и работает с какой-нибудь специфической подзадачей. Примером такого специализированного эксперта может служить таблица советов, содержащая знания о том, как поставить мат королем и ладьей. Эта таблица вызывается в том случае, когда в процессе игры возникает соответствующее окончание.

Мы рассмотрим здесь упрощенную версию Языка Советов, допускающую только одну таблицу советов. Будем называть эту версию Язык Советов 0 или, для краткости, AL0 (Advice Language 0). Ниже описывается структура языка AL0, синтаксически специально приспособленная для удобной реализации на Прологе.

Программа на AL0 называется таблицей советов. Таблица советов представляет из себя упорядоченное множество "если-то"-правил. Каждое правило имеет вид:

ИмяПравила: если Условие то СписокСоветов

Условие - это логическое выражение, состоящее из имен предикатов, соединенных между собой логическими связками и, или, не. СписокСоветов - список имен элементарных советов. Приведем пример правила под названием "правило_края" из окончания "король и ладья против короля":

правило_края:

если король_противника_на_краю и короли_рядом

то [мат_2, потеснить, приблизиться,
сохранить_простр, отделить].

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

Для представления элементарных советов в виде прологовских предложений предназначен еще один формат:

        совет( ИмяСовета,
                    ГлавнаяЦель:
                    ЦельПоддержка:
                    ХодыИгрока:
                    ХодыПротивника).

Цели представляются как выражения, состоящие из имен предикатов и логических связок и, или, не. Ограничения на ходы сторон - это тоже выражения, состоящие из имен предикатов и связок и и затем: связка и имеет обычный логический смысл, а затем задает порядок. Например, ограничение, имеющее вид

Огр1 затем Огр2

означает: сначала рассмотреть ходы, удовлетворяющие ограничению Oгp1, а затем - ходы, удовлетворяющие Огр2.

Например, элементарный совет, относящийся к мату в два хода в окончании "король и ладья против короля", записанный в такой синтаксической форме, имеет вид:

        совет( мат_2,
                    мат:
                    не потеря_ладьи:
                    (глубина = 0) и разреш затем
                    (глубина = 2) и ход_шах :
                    (глубина = 1) и разреш ).

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

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

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

Таким образом, таблица советов это программа в высшей степени непроцедурного характера. Интерпретатор языка AL0 принимает на входе некоторую позицию, а затем, "исполняя" таблицу советов, строит форсированное дерево, определяющее стратегию игры в этой позиции.