Главная » Алгоритмы, Игры » MiniMax и NegaMax

0

Стратегия поиска лучшего хода была описана еще Клодом Шенноном. Впрочем, она очевидна, и любой человек, знакомый с программированием и рекурсией, может вывести ее самостоятельно. Коротко о рекурсии. Рекур­сия — это когда функция вызывает сама себя, и каждый раз при входе в функцию в стеке программы создается новая копия блока переменных. Это не относится к статическим переменным, общим для всех вызовов функ­ции, просто, если они описаны в теле функции, их область видимости ог­раничена данной функцией. Чем же так примечательна рекурсия? Она по­зволяет описать некоторые процессы, просто определив законы их разви­тия, а как конкретно будет развиваться алгоритм, не так уж и важно. Главное, мы задаем его параметры развития, и совершенно очевидно, что он работает. Формальные доказательства нас в данном случае не интересу­ют. Некоторые задачи, легко решаемые с помощью рекурсии, часто невоз­можно или сложно решить другими способами. Это же относится к поиску лучшего хода. Допустим, у нас есть некоторая воображаемая игра, где на доске (размеры которой не важны), ходят белые и черные фигуры. Есть правила игры, и фигуры им подчиняются. Эта игра может быть шахматами, шашками, уголками и т. д. Алгоритма лучшего хода мы не знаем. Как же нам найти если не лучший, то хоть осмысленный ход? Предположим, у нас уже есть функция, дающая оценку каждому ходу. Устройства этой функции мы не знаем, но можем ей пользоваться и оценивать каждый ход. Как же нам для некоторой позиции в игре найти лучший ход? Очевидно, надо по­лучить все перемещения, сделать оценку каждого из них и найти перемеще­ние с максимальной оценкой. Рассмотрим некоторый код в листинге:

PMove SearchBestMove(void) (

int score    = -INFINITY; //минимально возможное значение

PMove bestMove = 0;      //лучший ход

PMove move = GenerateAllMoves(); //получим все перемещения

while(move) {

MakeMove(move);               //сделаем ход

int tmp = EvaluatePosition(); //оценка позиции

UnMakeMovS(move);             //восстановим исходную позицию

if(tmp > score) {

score = tmp; bestMove = move;

}

move = move->next;

return bestMove;

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

Давайте теперь перепишем функцию так, чтобы она возвращала оценку лучшего хода, а не сам ход. Это не вызовет затруднений. Единственное, введем переменную color, обозначающую цвет фигур данной позиции, в которой мы ищем лучший ход и его оценку. Функция EvaluatePosition будет возвращать оценку относительно цвета конкретных фигур. Чем же отличаются оценки относительно белых и относительно черных для одной и той же позиции? Только знаком. Если в какой-то позиции у белых есть преимущество, то оценка относительно черных для этой позиции будет та­кой же, но со знаком минус. Оценка описывается следующим кодом:

int SearchBestMove(int color) {

int score    = -INFINITY; //минимально возможное значение

PMove move = GenerateAllMoves(); //получим все перемещения

int opColor = (color == BLACK7WHITE:BLACK); //цвет фигур противника

while(move) {

MakeMove(move);

int tmp = -EvaluatePosition(opColor); //оценка позиции

UnMakeMove(move);

if(tmp > score) score = tmp;

move = move->next;

}

return score;

Обратите внимание, что мы определили цвет фигур противника и использо­вали результат функции EvaiuatePosition со знаком минус. Что же это за неведомая функция, которая оценивает нашу позицию? Эта и есть наша функция searchBestMove. Происходит рекурсия. Функция вызывает сама се­бя для оценки позиции противника. Нужно только ввести переменную Depth, которая будет ограничивать глубину рекурсии, говоря другими слова­ми, определять, на сколько полуходов мы считаем. При каждом вызове Depth уменьшается на 1. Когда Depth равно нулю, рекурсия прекращается, и мы вызываем действительно оценочную функцию. Простейшая оценочная функция для шахмат считает фигуры на доске. Условимся о весе фигур:

?    пешка — 1;

?    конь и слон — 3;

?   ладья — 5; П ферзь — 9;

?    король — infinity (максимально возможная оценка).

Если съели короля — это выигрыш. Расчет досрочно прекращается. Сейчас мы не будем заострять на этом внимание. Что должна сделать наша оце­ночная функция, чтобы получить оценку для белых? Она должна суммиро­вать вес всех белых фигур и вычесть из полученного результата сумму всех черных фигур. Если фигур поровну, функция вернет 0. Если у белых есть преимущество в одну пешку, вернет 1. Если у черных лишний конь, вернет —3. Эта оценка приближенная, но чем глубже мы считали, тем ближе эта оценка к истинной. Вот наша переписанная функция:

int SearchBestMove(int Depth, int color) {

int score    = -INFINITY; //минимально возможное значение

int opColor = (color = BLACK?WHITE:BLACK); //цвет фигур противника

PMove move;

if(Depth — 0) return Evaluate!); //оценка конечной точки move = GenerateAllMoves(); //получим все перемещения

while(move) {

MakeMove(move);

int tmp = -SearchBestMove(Depth-1,opColor); //оценка позиции

UnMakeMove(move);

if(tmp > score) score = tmp;

move = move->next;

}

return score;

Функция Evaluate просто подсчитывает материал в конце перебора. Если мы вызовем такую функцию в шахматах с глубиной 4 (Depth = 4), то она не даст нам уже поставить программе известный мат в 3 хода.

Этот алгоритм осуществляет полный перебор всех вариантов. Число рас­смотренных позиций будет оцениваться как W в степени D, где W — при­мерное количество ходов в одной позиции, D — глубина просчета.

Для шахмат среднее количество возможных перемещений из одной позиции примерно равно 40. Это значит, что, считая на глубину 4, мы должны пере­брать 40 х 40 х 40 х 40 = 2560 тыс. позиций, на глубину 5 — 10 240 тыс. и т. д. Если мы будем продолжать дальше, то получим число, превышающее количество атомов во Вселенной. Дерево перебора, которое строит этот ал­горитм, растет экспоненциально. В этом и заключается основная проблема программирования логических игр методом перебора. Считать надо очень глубоко, а все варианты глубоко просмотреть невозможно. На сегодняшний день на самых мощных процессорах при самом оптимальном коде можно считать на глубину 6 в реально оцениваемый промежуток времени. Данный алгоритм называется NegaMax. Он использует инвертированную оценку. Есть еще один вариант этого алгоритма — MiniMax, в нем оценка с одним знаком, но существуют две функции: одна максимизирует результат, вторая минимизирует. Оба алгоритма делают одно и то же, но NegaMax более ком­пактен и удобен для понимания. Все дальнейшие усовершенствования ис­пользуют NegaMax в качестве своей основы.

Литература:

Корнилов Е. Н.  Программирование шахмат и других логических игр. — СПб.: БХВ-Петербург, 2005. – 272 е.: ил.

По теме:

  • Комментарии