Назад | Содержание| Вперёд Глава 15 ИГРЫ ...

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

Глава 15

ИГРЫ

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

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

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

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

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

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

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

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

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

проигрыша

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

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

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

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

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

выигр( Поз) :-

терм_выигр( Поз).

% Терминальная выигранная позиция

выигр( Поз) :-

not терм_проигр( Поз),

ход( Поз, Поз1), % Разрешенный ход в Поз1

not ( ход( Поз1, Поз2),

not выигр( Поз2) ).

% Ни один из ходов противника не ведет кне-выигрышу

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

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

на том, что в каждой шахматной позициисуществуют приблизительно

30 разрешенных ходов я что терминальныепозиции расположены на

глубине 40 ходов. Один ход равен двумполуходам (по одному

полуходу с каждой стороны).

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

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

Проект

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

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

Оглавление