Игровые деревья поиска

Что происходит, когда мы играем в какую-нибудь игру? Игра начинается, например, с расстановки шахматных фигур, сдачи карт, распределения спичек и т. п. Решив, кто начнет игру, игроки делают ходы по очереди. После каждого хода позиция игры соответственно обновляется.

Превратим это туманное описание в простую базовую программу игры. Предложением верхнего уровня будет:

играть(Игра, Результат) ¬

инициализировать(Игра, Позиция, Игрок),

отобразить (Позиция, Игрок),

играть(Позиция, Игрок, Результат).

Предикат инициализировать(Игра, Позиция, Игрок) определяет начальную позицию Позиция игры Игра и игрока Игрок, начинающего игру.

Игра представляется последовательностью шагов, каждый из которых состоит в выборе игроком хода, выполнении хода и определении игрока, который должен выполнять следующий ход. Поэтому более точное описание дает процедура играть, имеющая три аргумента: позиция игры, игрок, выполняющий ход, и конечный результат. При этом удобно отделить выбор хода выбрать_ход/3 от его выполнения ходить/3. Остальные предикаты в представленном ниже предложении служат для отображения состояния игры и определения игрока, выполняющего следующий ход:

играть(Позиция,Игрок,Результат)¬

выбрать_ход (Позиция, Игрок, Ход),

ходить (Ход, Позиция, Позиция 1).

отобразить игру (Позиция!, Игрок),

следующий игрок (Игрок, Игрок 1),

!, играть (Позиция 1, Игрок 1, Результат).

Программа.18.8 определяет логическую основу игровых программ. Используя ее для написания программ конкретных игр, следует сосредоточить внимание на важных игровых вопросах: какие структуры данных должны быть использованы для представления позиции игры и какие должны быть выражены стратегии игры. Этот процесс будет продемонстрирован в гл. 20 на примерах написания программ для игр вНим и Калах.

 

играть(Игра) ¬

Играть игру с именем Игра.

играть(игра) ¬

инициализировать(Игра, Позиция, Игрок),

отобразить_игру(Позиция. Игрок),

играть(Позиция, Игрок. Результат).

играть (Позиция, Игрок, Результат) ¬

игра окончена (Позиция. Игрок. Результат),

объявить (Результат).

играть (Позиция, Игрок, Результат) ¬

выбрать-ход(Позиция, Игрок, Ход),

ходить (Ход. Позиция, Позиция1),

отобразить_игру (Позиция1, Игрок),

другой__игрок (Игрок, Игрок!).

!, играть(Позиция1. Игрок 1, Результат).

Программа 18.8. Базовая программа игры.

 

Базовые программы решения задач, представленные в предыдущих разделах, легко адаптируются для игр. Для заданного определенного состояния игры задача состоит в поиске последовательности ходов, ведущих к выигрышной позиции.

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

Деревья игры часто оказываются слишком большими для выполнения исчерпывающего поиска. В этом разделе обсуждаются методы, разработанные с целью «покорения» большого пространства поиска в играх двух лиц, В частности, мы остановимся на минимаксном алгоритме, расширенном альфа-бета-отсечением. Эта стратегия используется в гл. 20 в качестве базовой в программе для игры в калах.

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

Найти все возможные состояния игры, которые могут быть достигнуты за один ход.

Используя оценочную функцию, вычислить оценки состояний.

Выбрать ход, ведущий к позиции с наивысшей оценкой.

Этот алгоритм представлен программой 18.9. В ней предусматривается использование предиката ходить (Ход,Позиция,Позиция1), который для достижения состояния Позиция1 применяет к состоянию Позиция ход Ход. Связь с базовой программой 18.8. обеспечивается предложением

выбрать_ход( Позиция, компьютер. Ход)

установить (М,ход(Позиция,М), Ходы),

оценить_и_выбpaть (Ходы, Позиция, (nil, - 1000),Ход).

оценить_и_выбрать(Ходы, Позиция, Запись, ЛучшийХод)¬

Выбирает ЛучшийХод из множества ходов Ходы исходя из текущей позиции Позиция и записывает текущий лучший ход.

оценить_и_выбрать ([Ход | Ходы]. Позиция.Запись,ЛучшийХод) ¬

ходить(Ход, Позиция, Позиция1).

оценка(Познция1, Оценка),

изменить (Ход. Оценка, Запись, Запись1),

оценить_и_выбрать (Ходы, Позиция. Запись1, Лучший Ход). оценить_и_выбрать([ ], Позиция, (Ход, Оценка), Ход).

изменить(Ход, Оценка, (Ход1, Оценка1), (Ход1, Оценка 1)) ¬

Оценка £ Оценка1.

изменить (Ход, Оценка, (Ход1, Оценка1). Ход, Оценка)) ¬

Оценка > Оценка1.

Программа 18.9. Выбор лучшего хода.

 

Предикат ход (Позиция, Ход) истинен, если ход Ход – возможный ход из текущей позиции.

Базовое отношение программы – оценить_и_выбрить (Ходы, Позиция, Запись, Ход) обеспечивает выбор лучшего хода Ход из возможных ходов Ходы, исходя из данной позиции Позиция. Для каждого возможного хода определяется соответствующая позиция, вычисляется ее оценка и выполняется ход с наивысшей оценкой. Переменная Запись используется для записи наилучшего текущего хода. В программе 18.9 она представлена парой (Ход, Оценка). Структура Запись должна быть частично абстрактной в процедуре изменение/4. Степень абстракции данных – вопрос стиля программирования и обеспечения противоречивых требований наглядности, компактности и эффективности программы.

Если оценочная функция была бы совершенной, т. е. ее значение отражало бы, какие позиции ведут к победе, а какие – к поражению, то в программе 18.9 достаточно было бы просмотра вперед на один шаг. Игры становятся интереснее, когда совершенная оценочная функция неизвестна. Выбор хода на основе просмотра вперед на один шаг в общем случае не является хорошей стратегией. Лучше просматривать на несколько ходов вперед и на основании результатов просмотра выбирать лучший ход.

Стандартный метод определения оценки позиции, основанный на просмотре вперед нескольких слоев дерева игры, называется минимаксным алгоритмом. Его идея состоит в следующем.

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

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

Минимаксный алгоритм основан на предположении о нулевой сумме выигрышей игроков, которое неформально означает: что хорошо для нас должно быть плохо для противника, и наоборот.

На рис. 18.2 изображено простое дерево игры глубиной в 2 слоя. В текущей позиции игрок имеет два хода и его противник-два ответных хода. Оценки на листьях деревьев являются оценками для игрока. Противник хочет минимизировать оценку, поэтому он будет выбирать минимальные значения, оценивая позиции на первом уровне дерева как + 1 и - 1. Игрок, желая максимизировать оценку, будет выбирать вершину со значением +1.

 

Оценить и выиграть (Ходы, Позиция, Глубина, Признак, Запись,ЛучшийХод) ¬

Выбирает лучший ход ЛучшийХод из множества ходов Ходы в текущей позиции Позиция использованием минимаксного алгоритма поиска с числом просматриваемых вперед слоев, определяемых параметром. Признак Признак указывает, что производится в текущий момент минимизация или максимизация. Переменная Запись используется для регистрации текущего лучшего хода.

оценить_и,выбрать([Ход| Ходы],Позиция,D,МаксМин.Запись, ЛучшийХод) ¬

ходить (Ход, Позиция,Позиция1),

минимакс(0,Позиция1,МаксМин,ХодХ,Оценка).

изменить(Ход,Оценка,Запись,Запись1).

оценить_и_выбрать(Ходы,Позиция.О.МаксМин,Запись1,ЛучшийХод).

оценить и _ выбрать([ ],Позиция,0,МаксМин,Запись,Запись).

минимакс(0, Позиция, Макс Мин, Ход, Оцснка) ¬

оценка(Позиция,V),

оценка : = V * МаксМин.

минимакс(0,Позиция,МаксМин.Ход. Оценка) ¬

D>0,

set_of(М, ход(Позиция, М),Ходы),

DI: = D - 1,

МинМакс: = - МаксМин,

оценить_и_выбрать(Ходы, Позиция, D1,МинМакс,(ni1,-1000),(Ход,Оценка)).

изменить(Ход,Оценка,Запись,Запись1) ¬ См. программу 18.9.

Программа 18.10. Выбор лучшего хода с использованием минимаксного алгоритма.

 

Минимаксный алгоритм реализуется программой 18.10. Основное отношение программы минимакс (D,Позиция, МаксМин, Хм),Оценка) истинно, если Ход - ход с наивысшей оценкой Оценка позиции Позиция, полученной в результате поиска на слое D дерева игры. Признак МаксМин указывает, что производится - максимизация (1) или минимизация (-1). Обобщение программы 18.9 используется для выбора хода из множества ходов. В предикат оценить_и_выбрать должны быть введены два дополнительных аргумента: число слоев D и признак МаксМин. Последний аргумент(ЛучшийХод) предиката используется для записи не только хода, но и оценки. Процедура минимакс производит необходимые вычисления, а также изменение числа просмотренных вперед ходов и признака. Исходное значение записи Запись устанавливается равным (nil, -1000), где nil представляет произвольный ход, а -1000 – это оценка, меньшая любого возможного значения оценочной функции.

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

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

В программе 18.11, представляющей собой модификацию программы 18.10, реализована альфа-бета-процедура. В программе появилась новая реляционная схема альфа_беma(Глубина,Позиция,Альфа,Бета,Ход.Оценка), в которой в отличие от реляционной схемы мини.микг вместо признака МаксМин помещены переменные Альфа и Бета. Аналогичное изменение претерпела и схема отношения оценить_и_выбрать.

 

oценить_u_ выбрать( Ходы,Позиция,Глубина,Альфа,Бета,Ход1,ЛучшийХод) ¬

Выбирает лучший ход ЛучшийХод из множества ходов Ходы в текущей позиции Позиция, используя минимаксный алгоритм поиска с альфа-бета-отсеченисм и с числом просматриваемых вперед слоев, определяемых параметром Глубина.

Альфа и Бета- параметры алгоритма. Параметр Ход1 используется для регистрации текущего лучшего хода.

оценить_и_выбрать([Ход | Ходы], Позиция, D,Альфа,Бета.Ход1.ЛучшийХод) ¬

ходить(Ход,Позиция, Позиция1),

альфа_бета(0,Позиция1,Альфа, Бета,ХодХ, Оценка),

Оценка1: = -Оценка.

отсечение(Ход,Оценка1,D,Альфа,Бета,Ходы, Позиция, Ход1,ЛучшийХод).

оценить_и_выбрать([ ],Позиция, Альфа, Бета, Ход, (Ход. Альфа)).

альфа бета(0,Позиция. Альфа. Бета, Ход, Оценки) ¬

оценка(Позиция,Оценка).

альфа_бета(0,Позиция,Альфа.Бета,Ход,Оценка) ¬

set_оf(М,ход(Позиция,М),Ходы),

Альфа1: = -Бета,

Бета!: = -Альфа.

D1 := D - 1,

оценить_и_выбрать(Ходы,Позиция,D1,Альфа1,Бета1,nil,(Ход,Оценка)).

отсечение(Ход,Оценка,D,Альфа,Бета,Ходы,Позиция,Ход1,(Ход,Оценка)) ¬

Оценка ³ Бета.

отсечение(Ход,Оценка,0,Альфа, Бета, Позиция, Ход1,ЛучшийХод) ¬

Альфа < Оценка,0ценка < Бета,

оценить_и_выбрать(Ходы, Позиция,D,0ценка, Бета, Ход, ЛучшийХод). отсечение(Ход,Оценка,0,Альфа,Бета,Ходы.Позиция,Ход 1,ЛучшийХод) ¬

Оценка £ Альфа,

оценить_и_выбрать(Ходы,Позиция,D,Альфа,Бста.Ход1,ЛучшийХод).

Программа 18.11. Выбор хода с использованием минимаксного алгоритма с альфа-бета-отсечением.

 

В отличие от программы 18.10 процедура оценить_и_выбрать в программе 18.11 не должна просматривать все возможности. Это достигается введением предиката отсечение, который либо останавливает поиск по текущей ветви, либо продолжает поиск, обновляя значение альфа (альфа-оценку) и соответственно изменяя лучший текущий ход.

Например, в дереве игры, изображенном на рис. 18.2, не надо рассматривать последнюю вершину. Как только обнаруживается ход с оценкой -1, которая меньше, чем оценка +1, игрок может быть уверен, что нет других вершин, которые могли бы повлиять на конечную оценку.

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

 

Рис. 18.2. Простое дерево игры