Игры двух лиц с полной информацией
Игры, которые мы собираемся обсуждать в данной главе, относятся к классу так называемых игр двух лиц с полной информацией. Примерами таких игр могут служить шахматы, шашки и т.п. В игре участвуют два игрока, которые ходят по очереди, причем оба они обладают полной информацией о текущей игровой ситуации (это определение исключает большинство карточных игр). Игра считается оконченной, если достигнута позиция, являющаяся согласно правилам игры "терминальной" (конечной), например матовая позиция в шахматах. Правилами игры также устанавливается, каков исход игры в этой терминальной позиции.
Для игр такого рода возможно представление в виде дерева игры (или игрового дерева ). Вершины этого дерева соответствуют ситуациям, а дуги — ходам. Начальная ситуация игры — это корневая вершина; листьями дерева представлены терминальные позиции.
В большинстве игр этого типа возможны следующие исходы: выигрыш , проигрыш и ничья . Мы будем рассматривать здесь игры, имеющие только два возможных исхода — выигрыш и проигрыш . Игры, в которых возможна ничья, можно упрощенно считать играми с двумя исходами — выигрыш и не-выигрыш . Двух участников игры мы будем называть "игроком" и "противником". "Игрок" может выиграть в некоторой нетерминальной позиции с ходом игрока ("позиции игрока"), если в ней существует какой-нибудь разрешенный ход, приводящий к выигрышу. С другой стороны, некоторая нетерминальная позиция с ходом противника ("позиция противника") является выигранной для игрока, если все разрешенные ходы из этой позиции ведут к позициям, в которых возможен выигрыш. Эти правила находятся в полном соответствии с представлением задач в форме И/ИЛИ-дерева, которое мы обсуждали в гл. 13. Между понятиями, относящимися к И/ИЛИ-деревьям, и понятиями, используемыми в играх, можно установить взаимное соответствие следующим образом:
|
|
|
| позиции игры | вершины, задачи |
| терминальные позиции выигрыша | целевые вершины, тривиально решаемые задачи |
| терминальные позиции проигрыша | задачи, не имеющие решения |
| выигранные позиции | задачи, имеющие решение |
| позиции игрока | ИЛИ-вершины |
| позиции противника | И-вершины |
Очевидно, что аналогичным образом понятия, относящиеся к поиску в И/ИЛИ-деревьях, можно переосмыслить в терминах поиска в игровых деревьях.
Ниже приводится простая программа, которая определяет, является ли некоторая позиция игрока выигранной.
выигр( Поз) :-
терм_выигр( Поз).
% Терминальная выигранная позиция
выигр( Поз) :-
not терм_проигр( Поз),
ход( Поз, Поз1), % Разрешенный ход в Поз1
|
|
|
not ( ход( Поз1, Поз2),
not выигр( Поз2) ).
% Ни один из ходов противника не ведет к не-выигрышу
Здесь правила игры встроены в предикат ход( Поз, Поз1), который порождает все разрешенные ходы, а также в предикаты терм_выигр( Поз) и терм_проигр( Поз), которые распознают терминальные позиции, являющиеся, согласно правилам игры, выигранными или проигранными. В последнем из правил программы, содержащем двойное отрицание (not), говорится: не существует хода противника, ведущего к не выигранной позиции. Другими словами: все ходы противника приводят к позициям, выигранным с точки зрения игрока.
Рис. 15.1. Сложность игровых деревьев в шахматах. Оценки основаны на том, что в каждой шахматной позиции существуют приблизительно 30 разрешенных ходов я что терминальные позиции расположены на глубине 40 ходов. Один ход равен двум полуходам (по одному полуходу с каждой стороны).
Так же, как и аналогичная программа поиска в И/ИЛИ-графах, приведенная выше программа использует стратегию в глубину. Кроме того, в ней не исключается возможность зацикливания на одних и тех же позициях. Попытка устранить этот недостаток может привести к осложнениям, поскольку правила некоторых из игр допускают такое повторение позиций. Правда, разрешение повторять позиции часто носит условный характер, например по шахматным правилам после троекратного повторения позиции может быть объявлена ничья.
|
|
|
Программа, которую мы составили, демонстрирует основные принципы программирования игр. Но практически приемлемая реализация таких сложных игр, как шахматы или го, потребовала бы привлечения значительно более мощных методов. Огромная комбинаторная сложность этих игр делает наш наивный переборный алгоритм, просматривающий дерево вплоть до терминальных игровых позиций, абсолютно непригодным. Этот вывод иллюстрирует (на примере шахмат) рис. 15.1: пространство поиска имеет астрономические размеры — около 10120 позиций. Можно возразить, что в дереве на рис. 15.1 встречаются одинаковые позиции. Однако было показано, что число различных позиций дерева поиска находится далеко за пределами возможностей вычислительных машин обозримого будущего.
Проект
Напишите программу для какой-нибудь простой игры (такой, как ним ), использующую упрощенный алгоритм войска в И/ИЛИ-дереве.
Минимаксный принцип
Для игр, представляющих интерес, полный просмотр игрового дерева невозможен, поэтому были разработаны другие методы, предусматривающие просмотр только части дерева игры. Среди этих методов существует страндартный метод поиска, используемый в игровых (особенно в шахматных) программах и основанный на минимаксном принципе. Дерево игры просматривается только вплоть до некоторой глубины (обычно на несколько ходов), а затем для всех концевых вершин дерева поиска вычисляются оценки при помощи некоторой оценочной функции. Идея состоит в том, чтобы, получив оценки этих терминальных поисковых вершин, не продвигаться дальше и получить тем самым экономию времени. Далее, оценки терминальных позиций распространяются вверх по дереву поиска в соответствии с минимаксным принципом. В результате все вершины дерева поиска получают свои оценки. И наконец, игровая программа, участвующая в некоторой реальной игре, делает свой ход — ход, ведущий из исходной (корневой) позиции в наиболее перспективного (с точки зрения оценки) ее преемника.
|
|
|
Обратите внимание на то, что мы здесь делаем определенное различие между "деревом игры" и "деревом поиска". Дерево поиска — это только часть дерева игры (его верхняя часть), т.е. та его часть, которая была явным образом порождена в процессе поиска. Таким образом, терминальные поисковые позиции совсем не обязательно должны совпадать с терминальными позициями самой игры.
Очень многое зависит от оценочной функции, которая для большинства игр, представляющих интерес, является приближенной эвристической оценкой шансов на выигрыш одного из участников игры. Чем выше оценка, тем больше у него шансов выиграть и чем ниже оценка, тем больше шансов на выигрыш у его противника. Поскольку один из участников игры всегда стремится к высоким оценкам, а другой — к низким, мы дадим им имена МАКС и МИН соответственно. МАКС всегда выбирает ход с максимальной оценкой; в противоположность ему МИН всегда выбирает ход с минимальной оценкой. Пользуясь этим принципом (минимаксным принципом) и зная значения оценок для всех вершин "подножья" дерева поиска, можно определить оценки всех остальных вершин дерева. На рис. 15.2 показано, как это делается. На этом рисунке видно, что уровни позиций с ходом МАКС'а чередуются с уровнями позиций с ходом МИН'а. Оценки вершин нижнего уровня определяются при помощи оценочной функции. Оценки всех внутренних вершин можно определить, двигаясь снизу вверх от уровня к уровню, пока мы не достигнем корневой вершины. В результате, как видно из рис. 15.2, оценка корня оказывается равной 4, и, соответственно, лучшим ходом МАКС'а из позиции а — a-b . Лучший ответ МИН'а на этот ход — b-d , и т.д. Эту последовательность ходов называют также основным вариантом . Основной вариант показывает, какова "минимаксно-оптимальная" игра для обоих участников. Обратите внимание на то, что оценки всех позиций, входящих в основной вариант, совпадают.
Рис. 15.2. Статические (нижний уровень) и минимаксные рабочие оценки вершин дерева поиска. Выделенные ходы образуют основной вариант , т.е. минимаксно-оптимальную игру с обеих сторон.
Мы различаем два вида оценок: оценки вершин нижнего уровня и оценки внутренних вершин (рабочие оценки). Первые из них называются также "статическими", так как они вычисляются при помощи "статической" оценочной функции, в противоположность рабочим оценкам, получаемым "динамически" при распространении статических оценок вверх по дереву.
Правила распространения оценок можно сформулировать следующим образом. Будем обозначать статическую оценку позиции P через v (P ), а ее рабочую оценку — через V (P ). Пусть P1 , …, Рn — разрешенные преемники позиции P . Тогда соотношения между статическими и рабочими оценками можно записать так:
V (P ) = v (P )
если P — терминальная позиция дерева поиска (n= 0)
если P — позиция с ходом МАКС'а
если P — позиция с ходом МИН'а
% Минимаксная процедура: минимакс( Поз, ЛучшПоз, Оц)
% Поз - позиция, Оц - ее минимаксная оценка;
% лучший ход из Поз ведет в позицию ЛучшПоз
минимакс( Поз, ЛучшПоз, Оц) :-
оды( Поз, СписПоз), !,
% СписПоз - список разрешенных ходов
лучш( СписПоз, ЛучшПоз, Оц);
стат_оц( Поз, Оц). % Поз не имеет преемников
лучш( [Поз], Поз, Оц) :-
минимакс( Поз, _, Оц), !.
лучш( [Поз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).
Рис. 15.3. Упрощенная реализация минимаксного принципа.
Программа на Прологе, вычисляющая минимаксную рабочую оценку для некоторой заданной позиции, показана на рис. 15.3. Основное отношение этой программы —
минимакс( Поз, ЛучшПоз, Оц)
где Оц — минимаксная оценка позиции Поз, а ЛучшПоз — наилучшая позиция-преемник позиции Поз (лучший ход, позволяющий достигнуть оценки Оц). Отношение
ходы( Поз, СписПоз)
задает разрешенные ходы игры: СписПоз — это список разрешенных позиций-преемников позиции Поз. Предполагается, что цель ходы имеет неуспех, если Поз является терминальной поисковой позицией (листом дерева поиска). Отношение
лучш( СписПоз, ЛучшПоз, ЛучшОц)
выбирает из списка позиций-кандидатов СписПоз "наилучшую" позицию ЛучшПоз. ЛучшОц — оценка позиции ЛучшПоз, а следовательно, и позиции Поз. Под "наилучшей" оценкой мы понимаем либо максимальную, либо минимальную оценку, в зависимости от того, с чьей стороны ожидается ход.
Дата добавления: 2018-05-01; просмотров: 636; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!