Минимаксный принцип
Поскольку полный просмотр игрового дерева в большинстве игр невозможен были разработаны другие методы, предусматривающие просмотр только части дерева игры. Среди этих методов существует стандартный метод поиска, используемый в игровых (особенно в шахматных) программах и основанный на минимаксном принципе. Дерево игры (И/ИЛИ-граф) просматривается только вплоть до некоторой глубины (обычно на несколько ходов), а затем для всех концевых вершин дерева поиска вычисляются оценки позиций при помощи некоторой оценочной функции. Идея состоит в том, чтобы, получив оценки этих терминальных поисковых вершин, не продвигаться дальше и получить тем самым экономию времени. Далее оценки терминальных позиций распространяются вверх по дереву поиска в соответствии с минимаксным принципом. В результате все вершины дерева поиска получают свои оценки. И, наконец, игровая программа, участвующая в некоторой реальной игре, делает свой ход - ход, ведущий из исходной (корневой) позиции в наиболее перспективного (с точки зрения оценки) ее преемника.
Обратите внимание на то, что мы здесь делаем определенное различие между "деревом игры" и "деревом поиска". Дерево поиска - это только часть дерева игры (его верхняя часть), т. е. та его часть, которая была явным способом порождена в процессе поиска. Таким образом, терминальные поисковые позиции совсем не обязательно должны совпадать с терминальными позициями самой игры.
Очень много зависит от оценочной функции, которая для большинства игр, представляющих интерес, является приближенной эвристической оценкой шансов на выигрыш одного из участников игры. Чем выше оценка, тем больше у него шансов выиграть и чем ниже оценка, тем больше шансов на выигрыш у его противника. Поскольку один из участников игры всегда стремиться к высоким оценкам, а другой - к низким, мы дадим им имена МАКС и МИН соответственно. МАКС всегда выбирает ход с максимальной оценкой; в противоположность ему МИН всегда выбирает ход с минимальной оценкой. Пользуясь этим принципом (минимаксным принципом) и зная значения оценок для всех вершин "подножья" дерева поиска, можно определить оценки всех остальных вершин дерева.
На рис. 2. 11 показано, как это делается. На этом рисунке видно, что уровни позиций с ходом МАКСа чередуются с уровнями позиций с ходом МИНа. Оценки вершин нижнего уровня определяются при помощи оценочной функции. Оценки всех внутренних вершин можно определить, двигаясь снизу вверх от уровня к уровню, пока мы не достигнем корневой вершины. в результате, как видно на рис. 2.11, оценка корня оказывается равной 4, и, соответственно, лучшим ходом МАКСа из позиции a - a-b. Лучший ответ МИНа на этот ход - b-d, и т.д. Эту последовательность ходов называют также основным вариантом. Основной вариант показывает, какова "минимаксно-оптимальная" игра для обоих участников. Обратите внимание на то, что оценки всех позиций, входящих в основной вариант совпадают.
 |
Рис. 2.11. Статический (нижний уровень) и минимаксные рабочие
оценки вершин дерева поиска. Выделенные ходы образуют
основной вариант, т. е. минимаксно-оптимальную игру
с обеих сторон
Мы различаем два вида оценок: оценки вершин нижнего уровня и оценки внутренних вершин (рабочие оценки). Первые из них называют также "статическими", так как они вычисляются при помощи "статической" оценочной функции, в противоположность рабочим оценкам, получаемых "динамически" при распространении статических оценок вверх по дереву.
Правила распространения оценок можно сформулировать следующим образом. Будем обозначать статическую оценку позиции P через v(P), а ее рабочую оценку - через V(P). Пусть P1, P2, … Pn - разрешенные преемники позиции P. Тогда соотношения между статическими и рабочими оценками можно записать так:
V(P) = v(P)
если P - терминальная вершина позиции дерева поиска (n=0);
V(P) =
если P - позиция с ходом МАКСа;
V(P) =
если P - позиция с ходом МИНа.
Приведем упрощенную программу на Прологе, вычисляющую минимаксную рабочую оценку для некоторой заданной позиции.
% Минимаксная процедура: minimax(P,GP,V)
% P - позиция, V - ее минимаксная оценка;
% лучший ход из позиции P ведет в позицию GP
minimax(P,GP,V):-
'ходы'(P,List),!, % List - список разрешенных ходов
'лучшая'(List,GP,V);
'статическая оценка'(P,V). % позиция P не имеет преемников
'лучшая'([P],P,V):-
minimax(P,_,V),!.
'лучшая'([P1|List],GP,GV):-
minimax(P1,_,V1),
'лучшая'(List,P2,V2),
'выбор'(P1,V1,P2,V2,GP,GV).
'выбор'(P0,V0,P1,V1,P0,V0):-
'ход МИНа'(P0),V0>V1,!;
'ход МАКСа'(P0),V0<V1,!.
'выбор'(P0,V0,P1,V1,P1,V1).
Основное отношение этой программы minimax(P,GP,V), где V - минимаксная оценка позиции P, а GP - наилучшая позиция-преемник позиции P ( лучший ход, позволяющий достигнуть оценки V). Предикат 'ходы'(P,List) задает разрешенные ходы игры: List - это список разрешенных позиций-преемников позиции P. Предполагается, что цель 'ходы' имеет неуспех, если P является терминальной поисковой вершиной (листом дерева поиска). Отношение 'лучшая'(List,GP,V) выбирает из списка позиций-кандидатов List "наилучшую" позицию GP. V - оценка позиции GP, а, следовательно, и позиции-предка. Под "наилучшей" оценкой мы понимаем либо максимальную, либо минимальную оценку, в зависимости от того, с чьей стороны ожидается ход.
