Минимакс на примере игры в зайца и волков / Хабрахабр Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа- бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом. Игра «Заяц и волки»На шахматной доске есть 4 волка сверху (на черных клеточках), и 1 заяц снизу (на одной из черных). Ходить можно только на одну клеточку по диагонали, притом волки могут ходить только вниз, а заяц в любую сторону. ООО «Резольвента», www.resolventa.ru, [email protected], (495) 509-28-10. Принцип минимакса Рассмотрим матричную игру типа m Заяц побеждает, когда достиг одной из верхних клеточек, а волки, когда они окружили или прижали зайца (когда зайцу некуда ходить). Перед продолжением чтения, рекомендую поиграть, так будет легче понимать. Эвристика. В практическом инженерном понимании, метод минимакса опирается на эвристику, которую мы рассмотрим прежде, чем переходить к сути алгоритмов. В контексте минимакса, эвристика нужна для оценки вероятности победы того или иного игрока, для какого- либо состояния. Задача состоит в том, чтобы построить эвристическую оценочную функцию, которая достаточно быстро и точно, в выбраной метрике, сможет указать оценку вероятности победы конкретного игрока для конкретного расположения фигур, не опираясь на то, каким образом игроки к этому состоянию пришли. В моем примере оценочная функция возвращает значения от 0 до 2. 66 моделей теории игр. Анализ математической стороны и основных принципов теории игр Был дан Джоном фон. Принцип минимакса и максимина.Оценка вероятности — не вероятность, и не обязана быть ограниченной, линейной, непрерывной. Пример оценочной функции 1. Чем заяц выше, тем больше у него шансов на победу. 66 моделей теории игр. Анализ математической стороны и основных принципов теории игр Был дан Джоном фон Принцип минимакса и максимина. В теории игр исследуются модели и методы принятия решений в кон- фликтных. При решении матричных игр используется принцип минимакса.
Такая эвристика эффективна с точки зрения быстродействия (О(1)), но совершенно не пригодна алгоритмически. Эта оценочная функция говорит зайцу двигаться вверх, но при небольшой глубине расчета будет приводить к тому, что заяц двигается вверх, не взирая на преграды, и попадает в ловушки. Пример оценочной функции 2. Заяц тем вероятней победит, чем меньше ему нужно сделать ходов для победы, при замороженных волках. Это более громоздкий алгоритм со сложностью О(n), где n – количество клеточек. Расчет количества ходов сводится к поиску в ширину: Внимание. Исходники, приведенные в статье, видоизменены таким образом, чтобы читатель смог понять их суть вне контекста основного приложения. Достоверные исходники ищите в конце статьи. Код, выполняющий поиск в ширину, а точнее заполнение карты значениями равными “расстоянию” от зайца: this- > queue. Position). while (! Несмотря на недостатки, которые я опишу ниже, именно эта эвристика используется в игре. Тем, кто будет смотреть исходники и разбираться — внимание! Архитектура приложения построена таким образом, чтобы оценочную функцию можно было переделать, не затрагивая другие части кода. Но, следует использовать ранее выбранную метрику, иначе алгоритмы не будут понимать показания функции оценки. Минимакс. Введем некоторые понятия и обозначения: Состояние, оно же узел дерева решений — расположение фигур на доске. Терминальное состояние — состояние, с которого больше нет ходов (кто- то победил / ничья). Vi — i- ое состояние. Vik — k- ое состояние, к которому можно прийти за один ход из состояния Vi. В контексте дерева решений, это дочерний узел Vi. Логично выбирать ход, для которого оценка вероятности будет максимально выгодной для игрока, который ходит. В нашей метрике, для волков — максимальная оценка, для зайцев минимальная. А оценка считается следующим образом: f(Vi) = g(Vi), если Vi — терминальное состояние, либо достигнут предел глубины расчетов. Vi) = max(f(Vi. 1), f(Vi. Мы ходим так, чтобы максимизировать оценку собственной победы P, но чтобы просчитывать хоть что- то, нам нужно знать, как будет ходить враг, а враг будет ходить так, чтобы максимизировать оценку своей победы (минимизировать оценку P). Другими словами, мы знаем как будет ходить враг, и таким образом можем строить оценки вероятностей. Самое время указать о том, что алгоритм является оптимальным, если у врага такая же оценочная функция, и он действует оптимально. В таком случае, интеллектуальность зависит от глубины просчета, и от качества оценочной функции. Самое время привести пример: На этом примере, игрок играет зайцем, а компьютер волками. После того как заяц походил, компьютер запускает алгоритм минимакса, на этом примере с глубиной 1. Алгоритм перебирает все возможные ходы для волка, и для них получает оценку вероятности победы. Эта оценка, как мы уже говорили ранее, состоит из того же запуска алгоритма минимакса, но уже для других состояний, и уже с ходом другого игрока, и уже с минимизацией, вместо максимизации. Это уже будет второй уровень, последний для указанной глубины 1, от того и дальше алгоритм минимакса не запускается, а возвращает функцию эвристической оценки. Этот пример будет легче понимать, если рассматривать его снизу. На втором уровне у нас состояния, для которых мы получаем эвристическую оценку (она записана числами). По второму уровню, первый получает свои оценки, соответственно выбрав минимальные значения из тех, что проверены на следующем уровне. Ну и нулевой уровень, выбирает максимальную оценку, из тех, что предоставлены ему первым уровнем. Теперь, когда у нас есть все оценки, что делать? Тут все очевидно, для волка выбирает ход тот, который показывает наибольшую оценку, для зайца тот, который показывает наименьшую. Но ведь оценки для разных ходов могут быть равны, и тогда в идеале нужно выбрать случайным образом, но тут начинаются нюансы. Сразу скажу, что у меня для волка берется первый ход из списка с максимальной оценкой, а для зайца – последний из списка с минимальной оценкой. И это печально, так как достаточно серьезная оптимизация опирается на то, что всегда будет выбираться первый ход из нужного списка. Но для зайца это совершенно не подходит. Дело в том, что волк очень часто (по мере возможностей) ходит так, чтобы оценка была равна бесконечности (2. Правильно было бы сделать так, чтобы функция эвристики учитывала то, как высоко заяц находится, но с меньшим коэффициентом, чем основная эвристика, но я сделал не так, а как уже описал ранее. Потому и выбирается последний из списка ход, который указывает зайцу идти вверх. Пример реализации алгоритма: //возвращает оценку текущего состояния f(Vi). Game: :run. Min. Max(Monster. Type monster, int recursive. Level). . 0- 7 - возможные ходы волков, 8- 1. Move = NOT? Тут переменная best. Move инкапсулирует много смысла (уточню при запросе), взываю вас никогда не вкладывать столько смысла в 4 бита, если вы не уверены в том, что вы делает все правильно. Будучи грамотными и образованными людьми, вы уже догадались, что там где есть деревья поиска решений, там есть и клад для оптимизаций. Данный пример не исключение. Альфа- бета отсечение. Альфа- бета отсечение основано на той идее, что анализ некоторых ходов можно прекратить досрочно, игнорируя результат их показаний. Альфа- бета отсечение часто описывается как отдельный алгоритм, но я считаю это недопустимым и буду описывать его как оптимизирующую модификацию. Альфа- бета относится к классу методов ветвей и границ. Грубо говоря, оптимизация вводит две дополнительные переменные alpha и beta, где alpha — текущее максимальное значение, меньше которого игрок максимизации (волки) никогда не выберет, а beta — текущее минимальное значение, больше которого игрок минимазации (заяц) никогда не выберет. Изначально они устанавливаются в - . Я считаю, что это не удачный пример для объяснения, а потому возьму пример из википедии, который чуть более удачный. Обозначения в примере: Vi — узлы дерева поиска решений, i никоим образом не коррелирует с порядком обхода дерева. Ci — i- ое альфа- бета отсечение. Будьте внимательны, состояния на уровне максимума будут выбирать свои максимумы из состояний следующего уровня, на которых указан MIN, и наоборот. То есть максимальный выбирается из тех, на которых написан MIN, а минимальный из тех, на которых написан MAX, не перепутайте. После того, как для узла 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 — лучше. Отсечение 3 намного интересней, внимание, пример на википедии явно в чем- то не прав. Он позволяет себе проводить отсечения, если (alpha > = beta), хотя альфа- бета должна была бы быть оптимизацией, и не влиять на выбор пути. Дело в том, что везде пишут, что отсечение должно срабатывать, когда alpha > = beta, хотя в общем случае, только когда alpha > beta. Допустим, для некоторого дерева решений, все дети показывают одинаковую оценку. Тогда можно было бы выбрать из них любую, случайным образом, и это было бы правильно. Но у вас не получится так делать, используя условия alpha > = beta, потому что после первой оценки все остальные могут быть отсечены. Но это не беда, допустим, не будет ваш алгоритм реализовывать стохастическое поведение, это не так важно, но если в вашем алгоритме выбор лучшего из значений с одинаковой оценкой важен, то такое условие отсечения приведет к тому, что алгоритм просто поломается, и будет ходить не оптимально. Будьте бдительны!
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |