Реализация алгоритма минимакс на примере игры «Собери 4» очень увлекательное занятия и, в связи с этим, появилось желание рассказать об этом увлечении еще кому-нибудь, что и сделал. Игра доступна по данному адресу . Поле игры можно варьровать, устанавливая константы, я принял 7 на 6 как в примере по ссылке. Смысл игры заключается в том, чтобы, совершая ходы, выстроить 4 своих фигуры (крестики или нолики) в один ряд: по горизонтали, вертикали, диагонали. Для создания игры (видимо любой) необходимы две вещи: генератор ходов и анализатор ходов (позиций). Правила игры таковы, что установить фигуру можно не в любое место доски, а лишь в низ, причем низом считается также и поле, находящееся сверху поля, занятого фигурой (любой). Доску представил в виде одномерного массива TicTac field;

Сами структуры могут быть таковы

Typedef enum {Tic, Tac, EMPTY} TicTac;

Для игры понадобятся множество процедур (относительно конечно), процедуру валидации кода реализовал так

Int validstep(const TicTac *field, int step){ return ((field==EMPTY)&&((step + NSIZE_J >= NSIZE_I*NSIZE_J)||((step + NSIZE_J < NSIZE_I*NSIZE_J)&&(field != EMPTY))));}

Генератор ходов выполнил простейшим и неоптимальным способом, но, наименее мозголомным - простым перебором уравнений вертикалей, горизонталей и диагоналей, получилось достаточно объемно, но, ничего сложного

Int c4getrait(const TicTac *field, TicTac Me){ int i, j, k, score=0, maxscore=-1; /* X X X */ for(i=0; i maxscore)?score:maxscore; score = 0; if(maxscore == WIN) return maxscore; } } maxscore = (score > maxscore)?score:maxscore; } /* XXX */ for(j=0; j maxscore)?score:maxscore; score = 0; if(maxscore == WIN) return maxscore; } } maxscore = (score > maxscore)?score:maxscore; } /*main up diag XXX XX X */ for(k=0; k=0; i++, j--){ //printf("i=%d; j=%d\n", i, j); if(field == Me) score++; else { maxscore = (score > maxscore)?score:maxscore; score = 0; if(maxscore == WIN) return maxscore; } } //printf("\n"); maxscore = (score > maxscore)?score:maxscore; }...

Конечно наиболее важная и сложная процедура в программе - это сам алгоритм минимакс. Суть алгоритма заключается в поиске оптимального хода, причем, оценка вырабатывается, как совокупность оценок ходов своего и противника. Процедура рекурсивная. На каждом шаге мы ищем оценку своего хода и оценку наилучшего хода противника. Например: наш ход оценим в 2 балла, ответ противника в 10 баллов, итого = 2 - 10 = -8 - это и есть оценка нашего хода, рекурсивно пробираясь вниз по дереву вариантов, оцениваем позицию на глубину N. Данная игра, хотя и достаточно простая, но перебор всех вариантов, а их - факториал 42 для пустого поля, задача невыполнимая на персональном компьютере (видимо только на супер ЭВМ). Невозможность просчитать до упора вынуждает применять эвристику - расчет позиции. Приведу процедуру минимакс

Step game(TicTac *field, int deep, WHO it, TicTac t){ int i=0; float rait, koeff = 1 - Koeff*deep; Step s, r; s.step = -1; s.rait = -1000.; if(deep > DEEPMAX){ s.rait = 0.; return s; } for(i=0; i= WIN){ field[i] = EMPTY; s.rait = 10.*koeff; s.step = i; return s; } else if(!isstep(field)){ rait = 0.; } else { r = game(field, deep+1, it, (t==Tic)?Tac:Tic); rait-=r.rait; } if(rait > s.rait){ s.rait = rait; s.step = i; } field[i] = EMPTY; } } s.rait = s.rait*koeff; return s; }

В процедуре производится перебор всех позиций в цикле

For(i=0; i

Делаем очередной ход

Field[i] = t;

Ищем оценку

Rait = c4getrait(field, t);

Если мы выйграли

If(rait >= WIN){

То смысла искать глубже - нет, рекурсия прекращается, если ходов не осталось(ничья) - возвращаем 0 (возможно неоптимально), иначе

R = game(field, deep+1, it, (t==Tic)?Tac:Tic); rait-=r.rait;

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

If(rait > s.rait){ s.rait = rait; s.step = i; } field[i] = EMPTY;

Возвращаем результат

S.rait = s.rait*koeff; return s;

Для правильной оценки необходимо ввести коэффициенты (теория чисто моя:). Связано с тем, что выйгрыш на разной глубине - это неравносильные понятия (да и вобщем оценка), потому как ценность выше, чем меньше глубина поиска. Пояснение: например при ходе А вы получаете проигрыш на глубине 5, а при ходе Б - на глубине 2. Ясно, что 2 случится раньше чем 5:), и поэтому в данной ситуации более предпочтительным для вас является ход 5, это же касается не только победы/поражения, но и просто оценки позиции. В связи с этим нужно формировать коэффициенты по принципу, чем глубже, тем меньше значимости придаем ходу. Но, тут вот как раз и начинаются сложности:) Необходимо чтобы алгоритм правильно взвесил позиции, несмотря на противоречие - думать глубже, но оценку занижать тем больше, чем больше глубина. Здесь возможна, видимо, строгая математика, но, специальной подготовки я не имею. Но можно и так очевидно: в цикле провести партии между программами с постепенным изменением коэффициентов и записью в лог. Затем по логу можно найти наилучшие варианты и списать коэффициенты. Для глубины перебора 6 - у меня получилось 0,2. Вот примерно на данном этапе я и завершаю, вижу, хотя, по-ходу, еще одно улучшение - варьировать глубину в зависимости от числа вариантов, ясно, что число вариантов в данной игре уменьшается пропорционально занятым полям… Сейчас алгоритм легко выигрывает у среднестатистического игрока:) С программой по ссылке выше проигрывает, если ходит вторым, первым - сводит вничью на максимальной сложности. Программка писалась 2 дня вместе с отладкой и настройкой. Спасибо за внимание.

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

Рис. 3.5. Дерево ходов

Развивая метод минимакса , назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах:

P(R) = 0; 8; P(R) = 0; 5;

P(R) = 0; 9;

P(R) = 0; 3; P(R) = 0; 3:

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

Альфа-бета-процедура

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

Основная идея метода состоит в сравнении наилучших оценок, полученных для полностью изученных ветвей, с наилучшими предполагаемыми оценками для оставшихся. Можно показать, что при определенных условиях некоторые вычисления являются лишними. Рассмотрим идею отсечения на примере рис. 3.6 . Предположим, позицияАполностью проанализирована и найдено значение ее оценки . Допустим, что один ход из позицииYприводит к позицииZ, оценка которой пометоду минимакса равнаz. Предположим, чтоz . После анализа узлаZ, когда справедливо соотношениеy z s, ветви дерева, выходящие из узлаY, могут быть отброшены (альфа-отсечение).

Рис. 3.6. - отсечение

Если мы захотим опуститься до узла Z, лежащего на уровне произвольной глубины, принадлежащей той же стороне, что и уровеньS, то необходимо учитывать минимальное значение оценкиβ, получаемой на ходах противника.

Отсечение типа βможно выполнить всякий раз, когда оценка позиции, возникающая после хода противника, превышает значениеβ. Алгоритм поиска строится так, что оценки своих ходов и ходов противника сравниваются при анализе дерева с величинами иβсоответственно. В начале вычислений этим величинам присваиваются значения+∞и-∞, а затем, по мере продвижения к корню дерева, находится оценка начальной позиции и наилучший ход для одного из противников.

Правила прекращения поиска:

На рис. 3.7 показаны -βотсечения для конкретного примера. Таким образом, -β-алгоритм дает тот же результат, что иметод минимакса , но выполняется быстрее.

Рис. 3.7. a-b отсечение для конкретного примера

Использование алгоритмов эвристического поиска для поиска на графе И, ИЛИ выигрышнойстратегии в более сложных задачах и играх (шашки, шахматы) не реален. По некоторым оценкам игровое дерево игры в шашки содержит 10 40 вершин, в шахматах 10 120 вершин. Если при игре в шашки для одной вершины требуется 1/3 наносекунды, то всего игрового времени потребуется 10 21 веков. В таких случаях вводятся искусственные условия остановки, основанные на таких факторах, как наибольшая допустимая глубина вершин в дереве поиска или ограничения на время и объем памяти.

Многие из рассмотренных выше идей были использованы А. Ньюэллом, Дж. Шоу и Г. Саймоном в их программе GPS. Процесс работы GPS в общем воспроизводит методы решения задач , применяемые человеком: выдвигаются подцели, приближающие к решению; применяетсяэвристический метод (один, другой и т. д.), пока не будет получено решение. Попытки прекращаются, если получить решение не удается.

Программа STRIPS (STanford Research Institut Problem Solver) вырабатывает соответствующий порядок действий робота в зависимости от поставленной цели. Программа способна обучаться на опыте решения предыдущих задач. Большая часть игровых программ также обучается в процессе работы. Например, знаменитая шашечная программа Самюэля, выигравшая в 1974 году у чемпиона мира, "заучивала наизусть" выигранные партии и обобщала их для извлечения пользы из прошлого опыта. Программа HACHER Зуссмана, управляющая поведением робота, обучалась также и на ошибках.

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

Рис. 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).

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

(см. скан)

). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.

Игра «Заяц и волки»

На шахматной доске есть 4 волка сверху (на черных клеточках), и 1 заяц снизу (на одной из черных). Заяц ходит первым. Ходить можно только на одну клеточку по диагонали, притом волки могут ходить только вниз, а заяц в любую сторону. Заяц побеждает, когда достиг одной из верхних клеточек, а волки, когда они окружили или прижали зайца (когда зайцу некуда ходить).

Перед продолжением чтения, рекомендую поиграть , так будет легче понимать.

Эвристика

В практическом инженерном понимании, метод минимакса опирается на эвристику , которую мы рассмотрим прежде, чем переходить к сути алгоритмов.

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

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

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



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

Код, выполняющий поиск в ширину, а точнее заполнение карты значениями равными “расстоянию” от зайца:

this->queue.enqueue(this->rabbitPosition); while (!this->queue.empty()) { QPoint pos = this->queue.dequeue(); for (int i = 0; i < 4; i++) if (canMove(pos + this->possibleMoves[i])) { QPoint n = pos + this->possibleMoves[i]; this->map = this->map + 1; this->queue.enqueue(n); } }
Результатом оценочной функции должно быть значение равное «расстоянию» до ближайшей верхней клеточки, либо 254, если дойти до них невозможно. Несмотря на недостатки, которые я опишу ниже, именно эта эвристика используется в игре.

Тем, кто будет смотреть исходники и разбираться - внимание! Архитектура приложения построена таким образом, чтобы оценочную функцию можно было переделать, не затрагивая другие части кода. Но, следует использовать ранее выбранную метрику, иначе алгоритмы не будут понимать показания функции оценки.

Минимакс

Введем некоторые понятия и обозначения:

• Состояние, оно же узел дерева решений - расположение фигур на доске.
• Терминальное состояние - состояние, с которого больше нет ходов (кто-то победил / ничья).
  
• Vi - i -ое состояние.
• Vik - k -ое состояние, к которому можно прийти за один ход из состояния Vi. В контексте дерева решений, это дочерний узел Vi.
• f(Vi) - расчетная оценка вероятности победы для состояния Vi.
• g(Vi) - эвристическая оценка вероятности победы для состояния Vi.

f(Vi) отличается от g(Vi) тем, что g(Vi) использует информацию только о Vi , а f(Vi) - также Vik и другие состояния, рекурсивно.

Метод разработан для решения проблемы о выборе хода с состояния Vi . Логично выбирать ход, для которого оценка вероятности будет максимально выгодной для игрока, который ходит. В нашей метрике, для волков - максимальная оценка, для зайцев минимальная. А оценка считается следующим образом:

• f(Vi) = g(Vi) , если Vi - терминальное состояние, либо достигнут предел глубины расчетов.
• f(Vi) = max(f(Vi1), f(Vi2)… f(Vik)) , если Vi - состояние, с которого ходит игрок с поиском максимальной оценки.
• f(Vi) = min(f(Vi1), f(Vi2)… f(Vik)) , если Vi - состояние, с которого ходит игрок с поиском минимальной оценки.

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

Самое время привести пример:



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

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

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

Пример реализации алгоритма:
//возвращает оценку текущего состояния f(Vi) int Game::runMinMax(MonsterType monster, int recursiveLevel) { int test = NOT_INITIALIZED; //на последнем уровне дерева (на листах) возвращаем значение функции эвристики if (recursiveLevel >= this->AILevel * 2) return getHeuristicEvaluation(); //индекс выбранного пути. 0-7 - возможные ходы волков, 8-11 - возможные ходы зайца int bestMove = NOT_INITIALIZED; bool isWolf = (monster == MT_WOLF); int MinMax = isWolf ? MIN_VALUE: MAX_VALUE; //перебираем все возможные хода данного монстра for (int i = (isWolf ? 0: 8); i < (isWolf ? 8: 12); i++) { int curMonster = isWolf ? i / 2 + 1: 0; QPoint curMonsterPos = curMonster == 0 ? rabbit: wolfs; QPoint curMove = possibleMoves; if (canMove(curMonsterPos + curMove)) { //...ходим, после чего обрабатываем ситуацию temporaryMonsterMovement(curMonster, curMove); //оцениваем, насколько хорош ход, который мы выбрали test = runMinMax(isWolf ? MT_RABBIT: MT_WOLF, recursiveLevel + 1); //если он лучше всех, что были до этого - запомним, что он лучший if ((test > <= MinMax && monster == MT_RABBIT)) { MinMax = test; bestMove = i; } //... и восстанавливаем исходное состояние temporaryMonsterMovement(curMonster, -curMove); } } if (bestMove == NOT_INITIALIZED) return getHeuristicEvaluation(); //ну и собственно, ходим, коль уже выбрали лучший ход if (recursiveLevel == 0 && bestMove != NOT_INITIALIZED) { if (monster == MT_WOLF) wolfs += possibleMoves; else rabbit += possibleMoves; } return MinMax; }
Внимание! Тут переменная bestMove инкапсулирует много смысла (уточню при запросе), взываю вас никогда не вкладывать столько смысла в 4 бита, если вы не уверены в том, что вы делает все правильно.

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

Альфа-бета отсечение

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

Грубо говоря, оптимизация вводит две дополнительные переменные alpha и beta , где alpha - текущее максимальное значение, меньше которого игрок максимизации (волки) никогда не выберет, а beta - текущее минимальное значение, больше которого игрок минимазации (заяц) никогда не выберет. Изначально они устанавливаются в -∞, +∞ соответственно, и по мере получения оценок f(Vi) модифицируются:

• alpha = max(alpha, f(Vi)); для уровня максимизации.
• beta = min(beta, f(Vi)); для уровня минимизации.

Как только условие alpha > beta станет верным, что означает конфликт ожиданий, мы прерываем анализ Vik и возвращаем последнюю полученную оценку этого уровня.

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



Обозначения в примере:

• Vi - узлы дерева поиска решений, i никоим образом не коррелирует с порядком обхода дерева.
• Vi - узлы с указанными текущими значениями alpha, beta.
• Ci - i-ое альфа-бета отсечение.
• MIN, MAX - уровни максимизации и минимазации соответственно. Будьте внимательны, состояния на уровне максимума будут выбирать свои максимумы из состояний следующего уровня, на которых указан MIN, и наоборот. То есть максимальный выбирается из тех, на которых написан MIN, а минимальный из тех, на которых написан MAX, не перепутайте.

Рассмотрим отсечение 1. После того, как для узла V1 был полностью обработан вариант с узлом V3, и получена его оценка f(V3) = 6, алгоритм уточняет значение alpha для этого узла (V1), и передает его значение в следующий узел - V4. Теперь для всех дочерних узлов V4 минимальный alpha = 6. После того как узел V4 обработал вариант с узлом V5, и получил оценку f(V5) = 5, алгоритм уточняет значение beta для узла V4. После обновления, для узла V4 мы получили ситуацию в которой alpha > beta, и следовательно другие варианты узла V4 рассматривать не нужно. И нам не важно, какая оценка будет у отсеченного узла:

• Если значение отсеченного узла меньше или равно 5 (beta), то в узел V4 будет выбрана оценка, которая не больше 5, и соответственно вариант с узлом V4 никогда не будет выбран узлом V1, потому что оценка узла V3 - лучше.
• Если значение отсеченного узла больше или равно 6 (beta + 1), то узел тем более не будет рассматриваться, поскольку узел V4 выберет вариант с узлом V5, так как его оценка меньше (лучше).

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

Допустим, для некоторого дерева решений, все дети показывают одинаковую оценку. Тогда можно было бы выбрать из них любую, случайным образом, и это было бы правильно. Но у вас не получится так делать, используя условия alpha >= beta, потому что после первой оценки все остальные могут быть отсечены. Но это не беда, допустим, не будет ваш алгоритм реализовывать стохастическое поведение, это не так важно, но если в вашем алгоритме выбор лучшего из значений с одинаковой оценкой важен, то такое условие отсечения приведет к тому, что алгоритм просто поломается, и будет ходить не оптимально. Будьте бдительны!

Альфа-бета отсечение – очень простой для реализации алгоритм, и суть его сводится к тому, что в функцию минимакса нужно добавить 2 переменные alpha и beta в интерфейс процедуры минимакса, и небольшой кусок кода в ее тело, сразу после получения оценки.

Пример модификации алгоритма минимакса с альфа-бета отсечением (для большей наглядности, внесенные модификации закомментированы, но помните, что это важный код, а не комментарии):

int Game::runMinMax(MonsterType monster, int recursiveLevel/*, int alpha, int beta*/) { int test = NOT_INITIALIZED; if (recursiveLevel >= this->AILevel * 2) return getHeuristicEvaluation(); int bestMove = NOT_INITIALIZED; bool isWolf = (monster == MT_WOLF); int MinMax = isWolf ? MIN_VALUE: MAX_VALUE; for (int i = (isWolf ? 0: 8); i < (isWolf ? 8: 12); i++) { int curMonster = isWolf ? i / 2 + 1: 0; QPoint curMonsterPos = curMonster == 0 ? this->rabbit: this->wolfs; QPoint curMove = this->possibleMoves; if (canMove(curMonsterPos + curMove)) { temporaryMonsterMovement(curMonster, curMove); test = runMinMax(isWolf ? MT_RABBIT: MT_WOLF, recursiveLevel + 1, alpha, beta); temporaryMonsterMovement(curMonster, -curMove); if ((test > MinMax && monster == MT_WOLF) || (test <= MinMax && monster == MT_RABBIT)) { MinMax = test; bestMove = i; } /* if (isWolf) alpha = qMax(alpha, test); else beta = qMin(beta, test); if (beta < alpha) break; */ } } if (bestMove == NOT_INITIALIZED) return getHeuristicEvaluation(); if (recursiveLevel == 0 && bestMove != NOT_INITIALIZED) { if (monster == MT_WOLF) this->wolfs += this->possibleMoves; else this->rabbit += this->possibleMoves; } return MinMax; }
Как я уже говорил ранее, альфа-бета отсечение очень эффективно, и доказательством тому является приведенные ниже показатели. Для каждого случая, на трех разных уровнях глубины расчетов, я замерял количество входов в функцию эвристической оценки (меньше – лучше), и вот что получилось:


Как вывод, могу сказать что использование этого алгоритма отсечения не только ускорит работу интеллекта, но и позволит повысить его уровень.

Нюансы

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

Еще раз, никогда не делайте условием для альфа-бета отсечения alpha >= beta, если вы не на 100% уверены, что для вашей реализации это допустимо. Иначе ваша альфа-бета ухудшит интеллектуальность алгоритма в целом, с высокой долей вероятности.

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

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

Колоссальное количество модификаций и позволяют компьютеру играть в шахматы, и даже обыгрывать человека. Без таких модификаций, минимакс к шахматам практически не применим, даже на современных супер компьютерах. Без оптимизаций, в шахматах для трех ходов нужно было бы проверить порядка 30^6 ходов (729 миллиардов), а нам нужно, чтобы глубина расчета была побольше…

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

Как и профессиональный шахматист, этот алгоритм просчитывает действия соперника на несколько ходов вперёд - до тех пор, пока не достигнет конца партии, будь то победа, поражение или ничья. Попав в это конечное состояние, ИИ начислит себе положительное количество очков (в нашем случае +10) за победу, отрицательное (-10) - за поражение, и нейтральное (0) - за ничью.

В то же время алгоритм проводит аналогичные расчёты для ходов игрока. Он будет выбирать ход с наиболее высоким баллом, если ходит ИИ, и ход с наименьшим, если ходит игрок. Используя такую стратегию, минимакс избегает поражения.

Попробуйте сыграть вот в такую игру.

Алгоритм «минимакс» проще всего описать в виде рекурсивной функции, которая:

1. возвращает значение, если найдено конечное состояние (+10, 0, -10),
2. проходит по всем пустым клеткам на поле,
3. вызывает минимакс-функцию для каждой из них (рекурсия),
4. оценивает полученные значения
5. и возвращает наилучшее из них.

Если вы не знакомы с рекурсией, то вам стоит посмотреть эту лекцию из гарвардского курса CS50:

Чтобы разобраться в том, как устроен минимакс, давайте напишем его реализацию и смоделируем его поведение. Займёмся этим в двух следующих разделах.

Реализация минимакса

Мы рассмотрим ситуацию, когда игра подходит к концу (смотрите картинку ниже). Поскольку минимакс проходит по всем возможным состояниям игры (а их сотни тысяч), имеет смысл рассматривать эндшпиль - так нам придётся отслеживать меньшее количество рекурсивных вызовов функции (всего 9).

Пусть ИИ играет крестиками, человек - ноликами.

Чтобы упростить работу с полем, объявим его как массив из 9 элементов со значениями, равными содержимому клеток. Заполним его крестиками и ноликами, как на картинке выше, и назовём origBoard .

Var origBoard = ["O",1,"X","X",4,"X",6,"O","O"];

Затем объявим переменные aiPlayer и huPlayer и присвоим им значения "X" и "O" соответственно.

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

/* начальное состояние доски O | | X --------- X | | X --------- | O | O */ var origBoard = [“O”,1 ,”X”,”X”,4 ,”X”, 6 ,”O”,”O”]; // человек var huPlayer = “O”; // ИИ var aiPlayer = “X”; // возвращает список индексов пустых клеток доски function emptyIndices(board){ return board.filter(s => s != "O" && s != "X"); } // победные комбинации с учётом индексов function winning(board, player){ if((board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player) || (board == player && board == player && board == player)) { return true; } else { return false; } }

Итак, давайте определим минимакс-функцию с двумя аргументами: newBoard (новое поле) и player (игрок). Затем найдём индексы свободных клеток на поле и передадим их в переменную availSpots .

// основная минимакс-функция function minimax(newBoard, player){ //доступные клетки var availSpots = emptyIndices(newBoard);

Кроме того, нам нужно отслеживать конечные состояния и возвращать соответствующие значения. Если побеждает «нолик», нужно вернуть -10 , если «крестик» - +10 . Если размер массива availSpots равен нулю, значит, свободных клеток нет, игра закончится ничьёй, и нужно вернуть ноль.

// проверка на терминальное состояние (победа / поражение / ничья) //and returning a value accordingly if (winning(newBoard, huPlayer)){ return {score:-10}; } else if (winning(newBoard, aiPlayer)){ return {score:10}; } else if (availSpots.length === 0){ return {score:0}; }

После этого нужно собрать очки с каждой из пустых клеток. Для этого создадим массив ходов moves и пройдём в цикле по всем пустым клеткам, помещая индексы и очки каждого хода в объект move .

Затем зададим индекс пустой клетки, который хранился в виде числа в origBoard , равным свойству-индексу объекта move . Потом сходим за текущего игрока на пустую клетку нового поля newBoard и вызовем функцию minimax от другого игрока и получившегося поля newBoard . После этого нужно поместить свойство score объекта, возвращённого функцией minimax , в свойство score объекта move .

Если минимакс не находит конечное состояние, он продолжает рекурсивное углубление в ход игры до тех пор, пока не достигнет терминального состояния. После этого он передаёт очки этого «уровня» рекурсии на один уровень выше.

И наконец, функция сбрасывает изменения newBoard и помещает объект move в массив moves .

// массив для хранения всех объектов var moves = ; // цикл по доступным клеткам for (var i = 0; i < availSpots.length; i++){ //create an object for each and store the index of that spot var move = {}; move.index = newBoard]; // совершить ход за текущего игрока newBoard] = player; //получить очки, заработанные после вызова минимакса от противника текущего игрока if (player == aiPlayer){ var result = minimax(newBoard, huPlayer); move.score = result.score; } else{ var result = minimax(newBoard, aiPlayer); move.score = result.score; } // очистить клетку newBoard] = move.index; // положить объект в массив moves.push(move); }

Затем минимаксу нужно выбрать наилучший ход move из массива moves . Ему нужен move с наибольшим счётом, если ходит ИИ, и с наименьшим, если это ход человека. Таким образом, если значение player равно aiPlayer , алгоритм инициализирует переменную bestScore очень маленьким числом и идёт циклом по массиву moves: если ход move приносит больше очков score , чем bestScore , алгоритм запоминает этот move . В случае ходов с одинаковыми очками алгоритм запоминает первый из них.

В случае, когда player равен huPlayer , всё аналогично - только теперь bestScore инициализируется большим числом, а минимакс ищет ход move с наименьшим количеством очков.

В итоге минимакс возвращает объект, хранящийся в bestMove .

// если это ход ИИ, пройти циклом по ходам и выбрать ход с наибольшим количеством очков var bestMove; if(player === aiPlayer){ var bestScore = -10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score > bestScore){ bestScore = moves[i].score; bestMove = i; } } }else{ // иначе пройти циклом по ходам и выбрать ход с наименьшим количеством очков var bestScore = 10000; for(var i = 0; i < moves.length; i++){ if(moves[i].score < bestScore){ bestScore = moves[i].score; bestMove = i; } } } // вернуть выбранный ход (объект) из массива ходов return moves; }

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

Минимакс в действии

Пользуясь схемой ниже, разберем пошаговую модель алгоритма.

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

1. Алгоритму подаются origBoard и aiPlayer . Он составляет список из трёх найденных пустых клеток, проверяет конечность состояния, и проходит циклом по всем пустым клеткам. Затем алгоритм меняет newBoard , помещая aiPlayer в первую пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer и ждёт, пока второй вызов вернёт значение.
2. Пока первый вызов функции всё ещё работает, запускается второй, создавая список из двух пустых клеток, проверяя конечность состояния и проходя циклом по всем пустым клеткам. Затем второй вызов изменяет newBoard , помещая huPlayer в первую пустую клетку. После этого он вызывает сам себя от newBoard и aiPlayer и ждёт, пока третий вызов вернёт значение.
3. 
   

   Поскольку второй вызов обнаружил две пустые клетки, минимакс изменяет newBoard , помещая huPlayer во вторую свободную клетку. Затем он вызывает сам себя от newBoard и aiPlayer .

4. Алгоритм составляет список пустых клеток и фиксирует победу игрока после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным (-10).
   

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

   На этот момент первый вызов функции получил оценку хода aiPlayer в первую пустую клетку. Затем он изменяет newBoard , помещая aiPlayer во вторую пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer .

5. В пятом вызове функции алгоритм составляет список пустых клеток и фиксирует победу ИИ после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным +10.
   

   После этого первый вызов изменяет newBoard , помещая aiPlayer в третью пустую клетку. Затем он вызывает сам себя от newBoard и huPlayer .

6. Шестой вызов составляет список из двух пустых клеток, проверяет конечность состояния и идёт циклом по всем пустым клеткам. Затем он изменяет newBoard , помещая huPlayer в первую пустую клетку. Потом он вызывает сам себя от newBoard и aiPlayer и ждёт, пока седьмой вызов вернёт значение.
7. Новый вызов составляет список из одной пустой клетки, проверяет конечность состояния и изменяет newBoard , помещая aiPlayer в пустую клетку. После этого он вызывает сам себя от newBoard и huPlayer и ждёт, пока этот вызов вернёт значение.
8. Восьмой вызов составляет пустой список пустых клеток и фиксирует победу aiPlayer после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным (+10), на уровень выше, седьмому вызову.
   

   Седьмой вызов получил лишь одно, положительное значение от нижних уровней. Поскольку это значение было получено в ход aiPlayer , алгоритм возвращает наибольшее из полученных значений. Поэтому он возвращает положительное значение (+10) на уровень выше, шестому вызову.

   Поскольку шестой вызов обнаружил две пустых клетки, минимакс изменяет newBoard , помещая huPlayer во вторую пустую клетку. Затем он вызывает сам себя от newBoard и aiPlayer .

9. После этого алгоритм составляет список пустых клеток и фиксирует победу aiPlayer после проверки конечности состояния. Поэтому он возвращает объект с полем счёта, равным (+10), на уровень выше.
   

   На этом этапе шестой вызов должен выбрать между счётом (+10), который вернул седьмой вызов, и счётом (-10), который вернул девятый вызов. Поскольку ход huPlayer принёс эти два результата, алгоритм выбирает наименьший из них и возвращает его на уровень выше в виде объекта с полями счёта и индекса.

   Наконец, все три ветви первого вызова оцениваются (-10, +10, -10). Поскольку ход aiPlayer принёс эти три результата, алгоритм выбирает объект, содержащий наибольшее количество очков (+10) и его индекс (4).

В рассмотренном выше сценарии минимакс решает, что оптимальным выбором будет ход в центральную клетку поля.