Принцип минимакса

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

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

Часть II. Применение языка Prolog в области искусственного интеллекта

При этом многое зависит от функции оценки. Такая функция в большинстве ин­тересных игр должна представлять собой эвристическую функцию, позволяющую оценить шансы на выигрыш с точки зрения одного из игроков. Чем выше эта оцен­ка, тем больше шансов на выигрыш имеет игрок, а чем меньше это значение, тем выше шансы на выигрыш у его противника. Поскольку один из игроков получает возможность достичь позиции с высокой оценкой, а другой вынужден довольство­ваться низкой оценкой, эти два игрока соответственно именуются как МХ и MI N. Каждый раз, когда ход должен сделать игрок МАХ, он выбирает ход, который в мак­симальной степени увеличивает оценку своей позиции. В противоположность этому игрок MIN должен выбрать ход, который сводит к минимуму оценку позиции своего противника. Если известны значения позиций низкого уровня в дереве поиска, то такой принцип (называемый минимаксом) позволяет определить значения всех дру­гих позиций в дереве поиска, как показано на рис. 22.2. На этом рисунке уровни по­зиций, в которых должен ходить игрок МАХ, чередуются с позициями, в которых право сделать ход передается игроку MI N. Значения позиций нижнего уровня опреде­ляются с помощью функции оценки. Стоимости внутренних узлов .можно рассчитать, поднимаясь снизу вверх, от одного уровня к другому до тех пор, пока не будет дос­тигнут корневой узел. На рис. 22,2 результирующая стоимость корневого узла равна 4, поэтому наилучшим ходом для игрока МХ в позиции а является а-Ь. Наилучшим ответом для игрока MIN является b-d и т.д. Такая последовательность позиций в иг­ре называется также основным вариантом. Основной вариант определяет для обоих участников игру, оптимальную в соответствии с принципом минимакса. Обратите внимание на то, что стоимость позиций вдоль основного варианта не изменяется. В соответствии с этим правильными являются те ходы, которые позволяют сохра­нить стоимость игры.

M1N

Ход игрока МАХ

Стетичэские

оценки

Рис. 22.2. Статические значения (нижний уровень) и зафиксированные минимаксные значения в дереве поиска. Ходы, обозначенные жирными стрелками, составляют ос­новной вариант, т.е. игру обеих сторон, оптимальную е соответствии с принципом минимакса (описание этого дерева игры на языке Prolog приведено в листинге 22.1)

Листинг 22.1. Описание дерева игры, представленного на рис 22.2, на языке Prolog "'%""moves(" Position , PositionList): возможные'хода'""

moves ( a, moves t b, moves ( c, moves( d, moves ( e, moves( f,

b,c

Глава 22. Ведение игры

moves( g, (o_yp]) .

% min_tc_ move ( Pos) : игрок KIN должен сделать ход з позиции Pos

min_tKmove ( Ь) . rain_to_inove( с).

h max"to_move( РОЕ; : игрок МАХ лолжен сделать ход в позиции Роз

max_to_move{ a) .

ma>:_to_jnove { d) .

max_to_move{ e ) .

ma>:_to_move { f) .

max_t<3_move ( g) .

% staticval{ Pos, Value) : переменная Value - статическое значение для Pos

staticval[ i, 1) . staticvaK j , 4) . staticvaK k, 5) . staticval(1, 6} . staticvaK m, 2) . staticvaK n, 1) , staticvaK o, 1) . staticvaK P, 1) ,

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

Правила распространения значений можно формализовать следующим образом. Обозначим статическое значение позиции Р следующим образом:

v(P)

а зафиксированное значение таким образом:

V[P)

Предположим, что Pi, ,.., Р_г, — допустимые позиции-преемники Р. В таком случае отношение между статическими и зафиксированными значениями можно опреде­лить, как показано ниже.

• Если В — заключительная позиция в дереве поиска (п = 0), то V (Р) = v (P).

• Если Р - позиция хода игрока МАХ, то V (Р) = max ViPJ,

i

• Если Р - позиция хода игрока MIN, то V(P) = min V(Pi),

i

Программа Prolog¹, которая вычисляет минимаксное зафиксированное значение для заданной позиции, приведена в листинге 22.2. Основным отношением в этой программе является следующее: minimax{ Pos, BestSucc_F Val)

где Val — минимаксное значение позиции Pos, a BestSucc — позиция, являющаяся наилучшим преемником позиции Pos (ход, который должен быть выполнен для дос­тижения Val). Отношение moves( РОЕ, PosList)

соответствует правилам допустимого хода игры; PosList — это список допустимых по­зиций — преемников Pos. Предполагается, что предикат moves не достигает успеха, если Роз — заключительная позиция поиска (лист дерева поиска), А такое отношение: best) PosList, BestPos, BestVal;

Часть II. Применение языка Prolog в области искусственного интеллекта

выбирает "наилучшую" позицию BestPos из списка возможных позиций PosList. Переменная BestVal представляет собой значение BestPos и поэтому также значе­ние Ро5. В данном случае "наилучший" рассматривается как максимальный или ми­нимальный, в зависимости от того, чья сейчас очередь хода.