6.3. Метод минимакса и выбор очередного хода

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

Рис. 6.6. Дерево допустимых ходов с оценками стабильных позиций на различных глубинах.

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

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

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

Рис. 6.7. Получение оценок восхождением по дереву с помощью метода минимакса для предыдущего случая.

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

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

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

Алгоритм метода минимакса имеет следующий вид:

МИНИМАКС: (Спуститься до максимальной глубины и оценить позицию; выбрать позицию с минимальной или максимальной оценкой в зависимости от глубины; перейти к следующей ветви того же уровня, если она существует, в противном случае подняться на один уровень)

Нам потребуется использовать некоторые вспомогательные процедуры последующего назначения:

ПОИСК ХОДА (ПОЗИЦИЯ, ИГРАЮЩИЙ): поиск разрешенных ходов для текущей позиции.

ПАКЕТ ХОДОВ (ПОЗИЦИЯ, ЛАГЕРЬ): упорядоченное размещение найденных ходов в памяти.

ИГРА (ПОЗИЦИЯ, ХОД): определение позиции после данного хода.

ХОД НАЗАД (ПОЗИЦИЯ, ХОД): процедура, обратная предыдущей, — определение позиции, существовавшей до сделанного хода.

ОЦЕНКА (ПОЗИЦИЯ, ГЛУБ): определение числового значения, связанного с позицией.

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

Кроме того, используются следующие обозначения: ГЛУБ — текущая глубина анализа; МАКСГЛ — максимальная глубина анализа. Другие процедуры, встречающиеся в тексте алгоритма, служат для определения следующих величин: ОЦЕНКА (ПОЗИЦИЯ) — оценки текущей позиции; ОЦН (ГЛУБ) — оценки максимального значения, полученного для данного уровня; Е (ГЛУБ) — множества допустимых ходов в течение анализа.

Итак, значение 1 для оценки позиции получается, если мы принимаем решение сделать ход на третьем уровне. То же самое относится и к ходу поскольку противник и в этом случае имеет ответ, позволяющий не допустить наших надежд хорошую позицию и получить оценку, равную 1. Из всех ходои на этом уровне только ход имеет заметные преимущества. Действительно, в этом случае минимальная оценка позиции, которая может возникнуть после ответного хода противника, равна 5. Таким образом, мы получаем оценки трех позиций, возникающих в результате последовательных ходов Мы делаем ход, который приводит к позиции с максимальной оценкой, т. е. из рассмотренных выше оценок 1, 1 и 5 мы выбираем оценку 5, которая соответствует ходу Это значение становится оценкой позиции после ходов полученной с помощью метода минимакса.

На рис. 6.7 показан окончательный результат анализа дерева ходов с помощью метода минимакса. Рядом с каждой промежуточной позицией на рисунке проставлена оценка, подсчитанная по этому методу.

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

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

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

Подобные методы, основанные на глубоком знании предмета, начинают находить применение во многих других областях: в химии, медицине, математике (разд. 6.8, гл. 7).

Алгоритм минимакса

(см. скан)

(см. скан)