Метод --отсечений для позиционных игр с полной информацией
Рассмотрим игру двух лиц, состоящую в том, что игроки поочередно делают ход, переводящий игру из одной позиции в другую. Множество допустимых ходов зависит от текущей позиции. Все ходы, сделанные игроками, известны обоим игрокам (а стало быть, известна и текущая позиция). Некоторые позиции являются заключительными. В заключительной позиции игра завершается. Известна процедура, позволяющая для каждой позиции проверить, не является ли эта позиция заключительной, и определить для заключительной позиции выигрыш первого игрока (он же с противоположным знаком – выигрыш второго).
Подобная модель называется позиционной игрой двух лиц с полной информацией и нулевой суммой (понятие «нулевая сумма» означает, что выигрыш одного игрока в точности равен проигрышу другого). Этой моделью описывается множество реальных игр: шахматы, шашки, го, «крестики-нолики» и т.п. В большинстве случаев выигрыш может принимать одно из трех значений: 1 (партия выиграна), 0 (ничья) или -1 (партия проиграна).
Игровые модели применяются также для исследования и планирования действий в неигровых ситуациях (военные действия, рыночная конкуренция и т.п.).
Естественна следующая постановка задачи: для заданной позиции найти такой очередной ход игрока, который максимизирует его выигрыш при условии, что в дальнейшем оба игрока будут выбирать наилучшие ходы. При трех возможных исходах это значит: найти ход, гарантирующий выигрыш при всех возможных ответах противника; если же такого хода не существует, то найти по крайней мере ход, гарантирующий ничью. Если нет и ничейного хода, то, значит, данный игрок обречен на поражение и все его ходы в равной степени плохи.
Такая постановка задачи называется минимаксной (поскольку она предполагает поиск максимума выигрыша для одного игрока при условии, что другой игрок стремится к минимуму). Это не единственная разумная постановка и не всегда лучшая, ибо она исходит из пессимистического предположения, что противник никогда не ошибается. На практике игроки нередко ставят ловушки: делают ход, сам по себе не лучший, но провоцирующий противника на «очевидный», но проигрывающий ответ. Тем не менее, в теории игр минимаксная постановка рассматривается чаще других. Возможно, именно потому, что она и не пытается учесть такую неформализуемую вещь, как психология игрока.
Для отыскания наилучших ходов может быть применен метод перебора с возвратами, который имеет некоторые особенности для позиционных игр.
На рис.1.4 показано дерево перебора для некоторой (условной) игры, которая всегда завершается после второго хода первого игрока. Далее будем первого игрока именовать «белые», а второго – «черные». Квадратики изображают позиции, в которых ход принадлежит белым, а кружки – позиции, где ход у черных.
Рис.1.4
Внизу показаны значения выигрыша белых для каждой заключительной позиции. Предполагается, что белые стремятся максимизировать свой выигрыш, а черные – минимизировать выигрыш белых.
Каждой вершине дерева перебора можно сопоставить значение этой вершины, т.е. число, которое показывает, каков должен быть выигрыш белых, если игра начинается с данной позиции и обе стороны играют наилучшим образом.
Если ход в вершине принадлежит белым, то значение вершины равно максимальному из значений сыновей этой вершины (т.к. лучший ход белых – это такой ход, который приводит в позицию с максимальным ожидаемым выигрышем). Напротив, значение вершины, в которой ход принадлежит черным, равно минимальному из значений сыновей этой вершины.
Если организовать поиск значения корневой вершины как рекурсивный перебор с возвратами и условиться, что вершины одного уровня просматриваются слева направо, то можно показать, что те части дерева, которые на рисунке изображены пунктирными линиями, могут быть отброшены без рассмотрения. Давайте разберемся, почему это возможно.
Будем обозначать значения вершин буквой f. После того, как просмотрены вершины a, b и c, можно найти значение f(d) = max(f(a), f(b), f(c)) = 3. Заметим, что это значение может служить верхней оценкой для вершины m: f(m) £ f(d), т.е. f(m) £ 3. Это справедливо, поскольку в вершине m ход принадлежит черным, а минимум, к которому стремятся черные, не может быть больше значения одного из сыновей.
Далее будет просматриваться вершина e, затем f. Поскольку значение f больше, чем имеющаяся оценка для ее «деда» – вершины m, можно сделать вывод, что вершина h не годится (из-за верхней оценки f(h) ³ f(f) = 5) и остальных сыновей вершины h можно не рассматривать. Такая ситуация, когда просмотр потомства вершины с ходом белых прекращается после обнаружения сына со значением (или с нижней оценкой), большим, чем имеющаяся верхняя оценка его деда, называется -отсечением. Еще одно -отсечение будет применено к вершине l после просмотра ее сына i. В результате число 3 из верхней оценки становится точным значением вершины m. Но тем самым это число становится нижней оценкой вершины ы! (Потому что для ы ищется максимум, а он не меньше, чем значение любого сына).
Далее будет выполняться просмотр вершины z и ее потомства. После того, как для вершины q будет получено значение 2, это число становится верхней оценкой для вершины z, и эта оценка позволяет забраковать вершину z и прекратить просмотр ее потомков. Действительно, зачем белым делать ход z, попадая после этого в позицию с оценкой f(z) £ 2, если у них есть ход m, дающий выигрыш 3?
Ситуация, когда просмотр потомства вершины с ходом черных прекращается после обнаружения сына со значением (или с верхней оценкой), меньшим, чем имеющаяся нижняя оценка его деда, называется -отсечением.
После отсечения z перебор завершается и найденным значением вершины ы становится 3.
Рассмотренная на этом примере техника сокращения перебора называется методом --отсечений. Этот метод по своей сущности очень близок к методу ветвей и границ, но ориентирован на расчет позиционных игр по минимаксному критерию.
В рассмотренном маленьком примере получено не такое уж значительное сокращение перебора. В общем случае степень сокращения перебора сильно зависит как от конкретной игры, так и от порядка просмотра вершин – сыновей одного родителя. Если есть такая возможность, в первую очередь лучше рассматривать наиболее перспективные ходы, чтобы быстрее получить хорошие оценки, позволяющие отбросить без рассмотрения как можно большее количество ветвей дерева.
К сожалению, в нетривиальных играх (например, в шахматах) огромный размер дерева не позволяет выполнить перебор даже в сокращенном варианте. Тем не менее, метод --отсечений часто используется в реальных игровых программах. При этом вычисление точных значений вершин приходится заменять вычислением приближенных оценочных функций. На каждом ходу строят дерево перебора, искусственно ограниченное по высоте несколькими ходами, и для тех позиций игры, которые оказались в роли листьев усеченного дерева, вычисляют приближенную оценку позиции. Для шахмат, например, самая тупая оценочная функция учитывает только суммарную стоимость оставшихся фигур. Более изощренные функции учитывают различные позиционные факторы: контроль над центром, наличие проходных пешек и т.п. На основании таких оценок выполняется перебор с --отсечениями и выбирается наилучший ход. После получения ответного хода соперника вся процедура повторяется для новой корневой позиции.