5.11. МИНИМАКСНАЯ ПРОЦЕДУРА ПРИ ПЕРЕБОРЕ НА ИГРОВЫХ ДЕРЕВЬЯХ

В гл. 4 мы видели, что игровые деревья можно представлять в виде «И/ИЛИ» деревьев. Пользуясь этим, мы пытаемся доказать, что игрок ПЛЮС может выиграть из некоторого начального положения игры. Тогда те позиции, которые возникают после хода игрока ПЛЮС, представляются «ИЛИ» вершинами, а позиции, возникающие после хода игрока МИНУС, представляются «И» вершинами. Мы примем, что ПЛЮС ходит первым и ходы ПЛЮСА и МИНУСА чередуются. Следовательно, дочерними для «И» вершин будут «ИЛИ» вершины, и обратно. В соответствии с принятым предположением мы будем считать, что начальной вершиной является «И» вершина. Заключительная вершина соответствует любой позиции, про которую известно, что она является выигрышной для игрока ПЛЮС. (Определение заключительной вершины должно быть изменено, если цель поиска состоит в доказательстве того, что ПЛЮС может добиться

ничьей, исходя из заданной позиции, или что ПЛЮС в данной позиции не может проиграть.)

Для многих простых игр (а также и для окончаний более сложных игр) можно применить перебор на «И/ИЛИ» деревьях, поскольку тогда доказательство выигрыша (или ничьей) можно найти, не строя больших деревьев перебора. Тогда дерево решения, доказывающее выигрыш (или ничью), дает полную игровую стратегию для игрока ПЛЮС. Примерами простых игр, в которых перебор на «И/ИЛИ» деревьях до получения ответа представляется реально осуществимым, являются игра Грандииз предыдущей главы, тик-так-ту (крестики-нолики), различные варианты игры ним и некоторые шахматные и шашечные эндшпили. Грубую оценку размеров дерева игры для тик-так-ту, например, можно получить, заметив, что начальная вершина имеет 9 дочерних вершин, каждая из которых в свою очередь имеет по 8 дочерних вершин и т. д., что приводит к вершинам в нижней части этого дерева. Однако многие пути обрываются на заключительных вершинах более высоких уровней, и, кроме того, значительного уменьшения размеров дерева можно достичь, если принять во внимание симметрии.

В случае более сложных игр, таких, как полная игра в шахматы или шашки, о переборе до конца на «И/ИЛИ» деревьях не может быть и речи. Число вершин в полном игровом дереве для шашек было оценено величиной 1040, а для шахмат — 10,2°. (Чтобы построить полное дерево для шашек, понадобилось бы около столетий, даже если предположить, что каждая дочерняя вершина образуется за наносекунды.) Процедуры упорядоченного перебора не настолько уменьшают фактор ветвления, чтобы что-то существенно изменилось. Следовательно, мы должны смириться с тем, что для сложных игр перебор до конца невозможен, т. е. следует отказаться от мысли доказать, что можно достичь выигрыша или ничьей (исключая, возможно, эндшпили).

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

Перебор должен производиться так же, как обычный перебор на «И/ИЛИ» графах. Можно воспользоваться либо методом полного перебора, либо перебором в глубину, либо методами упорядоченного перебора, однако условия окончания теперь необходимо изменить. Можно указать несколько искусственных условий окончания, основанных на таких факторах, как ограничение времени перебора, ограничение объема памяти или глубины самой глубокой концевой вершины в дереве поиска. К тому же в шахматах, например, не оканчивают

перебора, если любая из концевых вершин представляет «живую» позицию, например позицию, в которой нет непосредственно выгодного размена.

После того как перебор будет закончен, мы должны извлечь из дерева перебора оценку «лучшего» первого хода. Эту оценку можно получить, применив к концевым вершинам дерева перебора статическую оценочную функцию. Оценочная функция измеряет «достоинства» позиции, отвечающей концевой вершине, и основана она на различных элементах позиции, которые, как полагают, влияют на ее достоинства. Например, в шашках такими полезными элементами являются относительная продвинутость своих шашек, контроль центра доски, контроль центра доски дамками и т. д. При анализе игровых деревьев обычно принимается соглашение, по которому в игровых позициях, где ПЛЮС имеет преимущество, оценочная функция положительна, а для позиций, где преимущество за игроком МИНУС, оценочная функция отрицательна. Значения вблизи нуля соответствуют игровым позициям, не дающим преимущества ни одному из игроков.

Хороший первый ход можно найти с помощью минимаксной процедуры. Мы предполагаем, что если бы игроку ПЛЮС пришлось выбирать между концевыми вершинами, то он выбрал бы ту из них, которая имеет наибольшую оценку. Следовательно, вершине (типа «И»), являющейся родительской для концевых вершин типа «ИЛИ», приписывается обращенная величина (backed-up value), равная максимуму оценок концевых вершин. С другой стороны, если бы между концевыми вершинами пришлось выбирать игроку МИНУС, то он, вероятно, предпочел бы выбрать такую вершину, которая имела бы наименьшую оценку (т. е. самую отрицательную). Следовательно, вершине (типа «ИЛИ»), являющейся родительской для концевых «И» вершин, приписывается обращенная величина, равная минимуму оценок концевых вершин. После того как всем родительским вершинам концевых вершин приписаны обращенные величины, этот процесс «прослеживания в обратном направлении» переносится на уровень выше при условии, что ПЛЮС выбирает вершину с наибольшей обращенной величиной, а МИНУС — с наименьшей обращенной величиной.

Такое прослеживание в обратном направлении продолжается с уровня на уровень до тех пор, пока, наконец, обращенные величины не будут приписаны всем вершинам, являющимся дочерними для начальной вершины. Мы предполагаем, что если первый ход должен делать игрок ПЛЮС (т. е. дочерними для начальной вершины являются «ИЛИ» вершины), то он должен выбратьв качестве своего первого хода ход, соответствующий дочерней вершине с наибольшим значением этой обращенной величины.

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

Проиллюстрируем минимаксный метод на простом примере, использующем игру тик-так-ту. Предположим, что ПЛЮС ставит крестики (X), а МИНУС ставит нолики и пусть первым ходит ПЛЮС. Мы будем производить полный перебор до тех пор, пока не будут построены все вершины на уровне 2, а затем применим статическую оценочную функцию к позициям, соответствующим этим вершинам. Пусть наша оценочная функция позиции задается следующим образом:

Если не является позицией выигрыша, то

Если позиция выигрышна для игрока ПЛЮС, то

Если позиция выигрышна для игрока МИНУС, то

Таким образом, если есть то . При построении дочерних позиций мы будем учитывать симметрии. Так, все позиции

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

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

(кликните для просмотра скана)

позиции имеет обращенную величину с наибольшим значением, она выбирается как первый ход. (Кстати, оказывается, что это лучший первый ход для игрока ПЛЮС.)

Предположим теперь, что ПЛЮС делает этот ход, и МИНУС отвечает позицией (Плохой ход для бедного игрока МИНУС, который, видимо, не пользуется хорошей стратегией перебора.) Далее ПЛЮС осуществляет перебор на глубину 2 (отправляясь от позиции что приводит к дереву перебора, изображенному на рис. 5.11. ПЛЮС делает наилучший ход, а МИНУС делает ход, благодаря которому он избегает лемедленного поражения; в результате получается позиция Затем ПЛЮС снова осуществляет перебор, что приводит к дереву, изображенному на рис. 5.12. Некоторые из концевых вершин этого дерева (например, вершина А) представляют позиции, в которых МИНУС выигрывает, и поэтому они имеют оценку Проследив эти оценки в обратном направлении, мы видим, что наилучшим ходом для игрока ПЛЮС является здесь тот единственный ход, который позволяет ему избежать немедленного поражения. Теперь даже МИНУС может видеть, что ПЛЮС должен выиграть при следующем своем ходе, и потому он с достоинством уступает.