Принцип минимакса
Поскольку для создания программ ведения многих интересных игр невозможно применить исчерпывающий поиск в деревьях игры, разработаны другие методы, которые основаны на поиске только в некоторой части дерева игры. К ним относится стандартный метод, применяемый при ведении на компьютере игр (таких как шахматы), который основан на принципе микимакса. Поиск в дереве игры осуществляется только до определенной глубины, как правило, на несколько ходов, а затем осуществляется оценка концевых узлов этого дерева поиска с помощью некоторой функции оценки. Идея состоит в том, что оценка этих заключительных позиций поиска происходит без выполнения поиска за их пределами, что позволяет сэкономить время. После этого оценки заключительных позиций распространяются вверх по дереву поиска в соответствии с принципом минимакса. Это позволяет определить оценки позиций для всех позиций в дереве поиска. Затем в игре фактически выполняется ход, который ведет от первоначальной, корневой позиции к ее наиболее перспективному преемнику (согласно этим оценкам).
Обратите внимание на то, что в приведенном выше описании проводится различие между понятиями "дерево игры" и "дерево поиска". Дерево поиска обычно представляет собой лишь (верхнюю) часть дерева игры, иными словами, часть, явно формируемую в процессе поиска. Поэтому заключительные позиции поиска не обязательно должны быть заключительными позициями игры.
Часть 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, (oyp]) .
% 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
Программа Prolog1, которая вычисляет минимаксное зафиксированное значение для заданной позиции, приведена в листинге 22.2. Основным отношением в этой программе является следующее: minimax{ Pos, BestSuccF Val)
где Val — минимаксное значение позиции Pos, a BestSucc — позиция, являющаяся наилучшим преемником позиции Pos (ход, который должен быть выполнен для достижения Val). Отношение moves( РОЕ, PosList)
соответствует правилам допустимого хода игры; PosList — это список допустимых позиций — преемников Pos. Предполагается, что предикат moves не достигает успеха, если Роз — заключительная позиция поиска (лист дерева поиска), А такое отношение: best) PosList, BestPos, BestVal;
Часть II. Применение языка Prolog в области искусственного интеллекта
выбирает "наилучшую" позицию BestPos из списка возможных позиций PosList. Переменная BestVal представляет собой значение BestPos и поэтому также значение Ро5. В данном случае "наилучший" рассматривается как максимальный или минимальный, в зависимости от того, чья сейчас очередь хода.