Prolog

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

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

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

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

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

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

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

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

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

                проигрыша

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

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

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

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