минимакс что это такое
МИНИМАКС
Полезное
Смотреть что такое «МИНИМАКС» в других словарях:
Минимакс — Минимакс правило принятия решений, используемое в теории игр, теории принятия решений, исследовании операций, статистике и философии для минимизации возможных потерь из тех, которые лицу, принимающему решение, нельзя предотвратить при… … Википедия
МИНИМАКС — (minimax) Наиболее низкое значение среди ряда цифр, каждая из которых найдена путем нахождения максимума среди некоторого дальнейшего ряда. Это понятие активно используется в теории игр. Предположим, что i возможных стратегий фирмы А, которая… … Экономический словарь
МИНИМАКС — (Fire extinguisher) см. Огнетушитель. Самойлов К. И. Морской словарь. М. Л.: Государственное Военно морское Издательство НКВМФ Союза ССР, 1941 … Морской словарь
Минимакс — Минимакс [minimax] в теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход… … Экономико-математический словарь
минимакс — В теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход игрока, выбирающего… … Справочник технического переводчика
минимакс — минимум максимума например: принцип минимакса … Словарь сокращений и аббревиатур
Минимакс — в математике, значение вещественной функции двух переменных f(x, у). С понятием М. связано понятие максимина, равного В теории антагонистических игр (См. Антагонистические игры) основным принципом… … Большая советская энциклопедия
МИНИМАКС — смешанный экстремум и т. п. (см. также Максимин);может интерпретироваться (напр., в теории принятия решений, исследовании операций или статистике) как наименьшие потери из тех, к рые нельзя предотвратить принимающему решения субъекту в наихудших… … Математическая энциклопедия
МИНИМАКС — смешанный экстремум ф ции f(x, у) двух переменных: Значение М. не меньше значения соответствующего максимина. Условия их равенства весьма важны в. игр теории … Большой энциклопедический политехнический словарь
минимакс — миним акс, а (матем.) … Русский орфографический словарь
Минимакс
Смотреть что такое «Минимакс» в других словарях:
Минимакс — Минимакс правило принятия решений, используемое в теории игр, теории принятия решений, исследовании операций, статистике и философии для минимизации возможных потерь из тех, которые лицу, принимающему решение, нельзя предотвратить при… … Википедия
МИНИМАКС — (minimax) Понятие из области теории игр (game theory), иногда употребляется в качестве синонима термина максимин (maximin). Вот два примера использования данного понятия, дающие более точное представление о нем. 1. Теорема минимакс –… … Политология. Словарь.
МИНИМАКС — (minimax) Наиболее низкое значение среди ряда цифр, каждая из которых найдена путем нахождения максимума среди некоторого дальнейшего ряда. Это понятие активно используется в теории игр. Предположим, что i возможных стратегий фирмы А, которая… … Экономический словарь
МИНИМАКС — (Fire extinguisher) см. Огнетушитель. Самойлов К. И. Морской словарь. М. Л.: Государственное Военно морское Издательство НКВМФ Союза ССР, 1941 … Морской словарь
Минимакс — Минимакс [minimax] в теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход… … Экономико-математический словарь
минимакс — В теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход игрока, выбирающего… … Справочник технического переводчика
минимакс — минимум максимума например: принцип минимакса … Словарь сокращений и аббревиатур
МИНИМАКС — смешанный экстремум и т. п. (см. также Максимин);может интерпретироваться (напр., в теории принятия решений, исследовании операций или статистике) как наименьшие потери из тех, к рые нельзя предотвратить принимающему решения субъекту в наихудших… … Математическая энциклопедия
МИНИМАКС — смешанный экстремум ф ции f(x, у) двух переменных: Значение М. не меньше значения соответствующего максимина. Условия их равенства весьма важны в. игр теории … Большой энциклопедический политехнический словарь
минимакс — миним акс, а (матем.) … Русский орфографический словарь
Минимакс на примере игры в зайца и волков
Данная статья предназначена для разъяснения сути фундаментальных методов построения и оптимизации «искусственного интеллекта» для компьютерных игр (в основном антагонистических). На примере игры в зайца и волков будет рассмотрен алгоритм «Минимакс» и алгоритм его оптимизации «Альфа-бета отсечение». Помимо текстового описания, статья содержит иллюстрации, таблицы, исходники, и готовую кроссплатформенную игру с открытым кодом, в которой вы сможете посоревноваться с интеллектуальным агентом.
Игра «Заяц и волки»
На шахматной доске есть 4 волка сверху (на черных клеточках), и 1 заяц снизу (на одной из черных). Заяц ходит первым. Ходить можно только на одну клеточку по диагонали, притом волки могут ходить только вниз, а заяц в любую сторону. Заяц побеждает, когда достиг одной из верхних клеточек, а волки, когда они окружили или прижали зайца (когда зайцу некуда ходить).
Перед продолжением чтения, рекомендую поиграть, так будет легче понимать.
Эвристика
В практическом инженерном понимании, метод минимакса опирается на эвристику, которую мы рассмотрим прежде, чем переходить к сути алгоритмов.
В контексте минимакса, эвристика нужна для оценки вероятности победы того или иного игрока, для какого-либо состояния. Задача состоит в том, чтобы построить эвристическую оценочную функцию, которая достаточно быстро и точно, в выбраной метрике, сможет указать оценку вероятности победы конкретного игрока для конкретного расположения фигур, не опираясь на то, каким образом игроки к этому состоянию пришли. В моем примере оценочная функция возвращает значения от 0 до 254, где 0 — победа зайца, 254 — победа волка, промежуточные значения — интерполяция двух вышеуказанных оценок. Оценка вероятности — не вероятность, и не обязана быть ограниченной, линейной, непрерывной.
Пример оценочной функции 1. Чем заяц выше, тем больше у него шансов на победу. Такая эвристика эффективна с точки зрения быстродействия (О(1)), но совершенно не пригодна алгоритмически. «Высота» зайца коррелирует с вероятностью победы, но искажает основную цель зайца — победить. Эта оценочная функция говорит зайцу двигаться вверх, но при небольшой глубине расчета будет приводить к тому, что заяц двигается вверх, не взирая на преграды, и попадает в ловушки.
Пример оценочной функции 2. Заяц тем вероятней победит, чем меньше ему нужно сделать ходов для победы, при замороженных волках. Это более громоздкий алгоритм со сложностью О(n), где n – количество клеточек. Расчет количества ходов сводится к поиску в ширину:
Внимание. Исходники, приведенные в статье, видоизменены таким образом, чтобы читатель смог понять их суть вне контекста основного приложения. Достоверные исходники ищите в конце статьи.
Код, выполняющий поиск в ширину, а точнее заполнение карты значениями равными “расстоянию” от зайца:
Результатом оценочной функции должно быть значение равное «расстоянию» до ближайшей верхней клеточки, либо 254, если дойти до них невозможно. Несмотря на недостатки, которые я опишу ниже, именно эта эвристика используется в игре.
Тем, кто будет смотреть исходники и разбираться — внимание! Архитектура приложения построена таким образом, чтобы оценочную функцию можно было переделать, не затрагивая другие части кода. Но, следует использовать ранее выбранную метрику, иначе алгоритмы не будут понимать показания функции оценки.
Минимакс
Введем некоторые понятия и обозначения:
Метод разработан для решения проблемы о выборе хода с состояния Vi. Логично выбирать ход, для которого оценка вероятности будет максимально выгодной для игрока, который ходит. В нашей метрике, для волков — максимальная оценка, для зайцев минимальная. А оценка считается следующим образом:
Самое время привести пример:
На этом примере, игрок играет зайцем, а компьютер волками. После того как заяц походил, компьютер запускает алгоритм минимакса, на этом примере с глубиной 1. Что делает алгоритм? А кто его знает? Алгоритм перебирает все возможные ходы для волка, и для них получает оценку вероятности победы. Эта оценка, как мы уже говорили ранее, состоит из того же запуска алгоритма минимакса, но уже для других состояний, и уже с ходом другого игрока, и уже с минимизацией, вместо максимизации. Это уже будет второй уровень, последний для указанной глубины 1, от того и дальше алгоритм минимакса не запускается, а возвращает функцию эвристической оценки.
Этот пример будет легче понимать, если рассматривать его снизу. На втором уровне у нас состояния, для которых мы получаем эвристическую оценку (она записана числами). По второму уровню, первый получает свои оценки, соответственно выбрав минимальные значения из тех, что проверены на следующем уровне. Ну и нулевой уровень, выбирает максимальную оценку, из тех, что предоставлены ему первым уровнем.
Теперь, когда у нас есть все оценки, что делать? Радоваться. Нужно выбрать ход. Тут все очевидно, для волка выбирает ход тот, который показывает наибольшую оценку, для зайца тот, который показывает наименьшую. Но ведь оценки для разных ходов могут быть равны, и тогда в идеале нужно выбрать случайным образом, но тут начинаются нюансы. Сразу скажу, что у меня для волка берется первый ход из списка с максимальной оценкой, а для зайца – последний из списка с минимальной оценкой. И это печально, так как достаточно серьезная оптимизация опирается на то, что всегда будет выбираться первый ход из нужного списка. Но для зайца это совершенно не подходит. Дело в том, что волк очень часто (по мере возможностей) ходит так, чтобы оценка была равна бесконечности (254), что делает любой ход зайца “бессмысленным”, и если он будет выбирать любой ход – он будет ходить вниз, либо как попало, а нам нужно заставить его идти вверх, напролом, нарушая фронт волков. Правильно было бы сделать так, чтобы функция эвристики учитывала то, как высоко заяц находится, но с меньшим коэффициентом, чем основная эвристика, но я сделал не так, а как уже описал ранее. Потому и выбирается последний из списка ход, который указывает зайцу идти вверх.
Пример реализации алгоритма:
Внимание! Тут переменная bestMove инкапсулирует много смысла (уточню при запросе), взываю вас никогда не вкладывать столько смысла в 4 бита, если вы не уверены в том, что вы делает все правильно.
Будучи грамотными и образованными людьми, вы уже догадались, что там где есть деревья поиска решений, там есть и клад для оптимизаций. Данный пример не исключение.
Альфа-бета отсечение
Альфа-бета отсечение основано на той идее, что анализ некоторых ходов можно прекратить досрочно, игнорируя результат их показаний. Альфа-бета отсечение часто описывается как отдельный алгоритм, но я считаю это недопустимым и буду описывать его как оптимизирующую модификацию. Альфа-бета относится к классу методов ветвей и границ.
На нашем примере, на втором рисунке, с помощью альфа-бета отсечений, полностью отсекаются 3 нижних ряда, но без самого левого столбца. Я считаю, что это не удачный пример для объяснения, а потому возьму пример из википедии, который чуть более удачный.
Обозначения в примере:
Допустим, для некоторого дерева решений, все дети показывают одинаковую оценку. Тогда можно было бы выбрать из них любую, случайным образом, и это было бы правильно. Но у вас не получится так делать, используя условия alpha >= beta, потому что после первой оценки все остальные могут быть отсечены. Но это не беда, допустим, не будет ваш алгоритм реализовывать стохастическое поведение, это не так важно, но если в вашем алгоритме выбор лучшего из значений с одинаковой оценкой важен, то такое условие отсечения приведет к тому, что алгоритм просто поломается, и будет ходить не оптимально. Будьте бдительны!
Альфа-бета отсечение – очень простой для реализации алгоритм, и суть его сводится к тому, что в функцию минимакса нужно добавить 2 переменные alpha и beta в интерфейс процедуры минимакса, и небольшой кусок кода в ее тело, сразу после получения оценки.
Пример модификации алгоритма минимакса с альфа-бета отсечением (для большей наглядности, внесенные модификации закомментированы, но помните, что это важный код, а не комментарии):
Как я уже говорил ранее, альфа-бета отсечение очень эффективно, и доказательством тому является приведенные ниже показатели. Для каждого случая, на трех разных уровнях глубины расчетов, я замерял количество входов в функцию эвристической оценки (меньше – лучше), и вот что получилось:
Как вывод, могу сказать что использование этого алгоритма отсечения не только ускорит работу интеллекта, но и позволит повысить его уровень.
Нюансы
Алгоритм делает оптимальные ходы, только если его противник мыслит оптимально. Качество хода в основном зависит от глубины рекурсии, и от качества эвристики. Но следует отметить, что этот алгоритм оценивает качество хода достаточно глубоко, и никоим образом не завязывается (если явно не прописать где-то в эвристике) на количество ходов. Другими словами, если применить этот алгоритм к шахматам, без дополнительных модификаций, он будет ставить маты позже, чем мог бы. А в данном примере, если заяц поймет, что у него нет пути на победу, при оптимальной стратегии волков, он может покончить жизнь самоубийством, несмотря на то, что он мог бы оттягивать проигрыш.
Еще раз, никогда не делайте условием для альфа-бета отсечения alpha >= beta, если вы не на 100% уверены, что для вашей реализации это допустимо. Иначе ваша альфа-бета ухудшит интеллектуальность алгоритма в целом, с высокой долей вероятности.
Алгоритм фундаментальный, в том смысле, что он является фундаментом для большого множества разных модификаций. В том виде, в котором он представлен тут, его нельзя применять для шашек, шахмат, го. В основном модификации стремятся:
Минимакс
Минимакс [minimax] — в теории решений, теории игр (матричных) — наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход игрока, выбирающего решение, которое гарантирует ему минимальный уровень максимально возможного (для каждой стратегии противника) проигрыша. Критерий записывается так:
где i — номера строк; j — номера столбцов; Uij — выигрыш первого или потери второго игрока для элемента, находящегося на пересечении i-й строки и j-го столбца. Элемент платежной матрицы, в котором максимин первого игрока и М. второго равны, — седловая точка игры.
Принцип, по которому поведение или стратегии выбираются из расчета наихудшего для себя поведения противника, получил название принципа М.
Теорема о минимаксе является основной в теории игр двух лиц с нулевой суммой. Согласно этой теореме любая конечная игра имеет решение, если допускается использование смешанных стратегий (для бесконечных игр теорема о М. не выполняется).
Развитием критерия М. является критерий минимаксных потерь («критерий Сэвиджа«, правило наименьшего риска). В соответствии с этим правилом для каждого столбца платежной матрицы рассчитывается разность между значением строки и максимальным значением («риск«): платежная матрица преобразуется в «матрицу потерь«. К ней применяется минимаксный критерий, выбору подлежит стратегия, которая минимизирует наибольший риск.
Полезное
Смотреть что такое «Минимакс» в других словарях:
Минимакс — Минимакс правило принятия решений, используемое в теории игр, теории принятия решений, исследовании операций, статистике и философии для минимизации возможных потерь из тех, которые лицу, принимающему решение, нельзя предотвратить при… … Википедия
МИНИМАКС — (minimax) Понятие из области теории игр (game theory), иногда употребляется в качестве синонима термина максимин (maximin). Вот два примера использования данного понятия, дающие более точное представление о нем. 1. Теорема минимакс –… … Политология. Словарь.
МИНИМАКС — (minimax) Наиболее низкое значение среди ряда цифр, каждая из которых найдена путем нахождения максимума среди некоторого дальнейшего ряда. Это понятие активно используется в теории игр. Предположим, что i возможных стратегий фирмы А, которая… … Экономический словарь
МИНИМАКС — (Fire extinguisher) см. Огнетушитель. Самойлов К. И. Морской словарь. М. Л.: Государственное Военно морское Издательство НКВМФ Союза ССР, 1941 … Морской словарь
минимакс — В теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход игрока, выбирающего… … Справочник технического переводчика
минимакс — минимум максимума например: принцип минимакса … Словарь сокращений и аббревиатур
Минимакс — в математике, значение вещественной функции двух переменных f(x, у). С понятием М. связано понятие максимина, равного В теории антагонистических игр (См. Антагонистические игры) основным принципом… … Большая советская энциклопедия
МИНИМАКС — смешанный экстремум и т. п. (см. также Максимин);может интерпретироваться (напр., в теории принятия решений, исследовании операций или статистике) как наименьшие потери из тех, к рые нельзя предотвратить принимающему решения субъекту в наихудших… … Математическая энциклопедия
МИНИМАКС — смешанный экстремум ф ции f(x, у) двух переменных: Значение М. не меньше значения соответствующего максимина. Условия их равенства весьма важны в. игр теории … Большой энциклопедический политехнический словарь
минимакс — миним акс, а (матем.) … Русский орфографический словарь
МИНИМАКС
и т. п. (см. также Максимин);может интерпретироваться (напр., в теории принятия решений, исследовании операций или статистике) как наименьшие потери из тех, к-рые нельзя предотвратить принимающему решения субъекту в наихудших для него обстоятельствах.
Смотреть что такое «МИНИМАКС» в других словарях:
Минимакс — Минимакс правило принятия решений, используемое в теории игр, теории принятия решений, исследовании операций, статистике и философии для минимизации возможных потерь из тех, которые лицу, принимающему решение, нельзя предотвратить при… … Википедия
МИНИМАКС — (minimax) Понятие из области теории игр (game theory), иногда употребляется в качестве синонима термина максимин (maximin). Вот два примера использования данного понятия, дающие более точное представление о нем. 1. Теорема минимакс –… … Политология. Словарь.
МИНИМАКС — (minimax) Наиболее низкое значение среди ряда цифр, каждая из которых найдена путем нахождения максимума среди некоторого дальнейшего ряда. Это понятие активно используется в теории игр. Предположим, что i возможных стратегий фирмы А, которая… … Экономический словарь
МИНИМАКС — (Fire extinguisher) см. Огнетушитель. Самойлов К. И. Морской словарь. М. Л.: Государственное Военно морское Издательство НКВМФ Союза ССР, 1941 … Морской словарь
Минимакс — Минимакс [minimax] в теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход… … Экономико-математический словарь
минимакс — В теории решений, теории игр (матричных) наименьший из всех максимальных элементов строк платежной матрицы. Критерий минимакса в игре двух лиц с нулевой суммой симметричен критерию максимина и также означает осторожный подход игрока, выбирающего… … Справочник технического переводчика
минимакс — минимум максимума например: принцип минимакса … Словарь сокращений и аббревиатур
Минимакс — в математике, значение вещественной функции двух переменных f(x, у). С понятием М. связано понятие максимина, равного В теории антагонистических игр (См. Антагонистические игры) основным принципом… … Большая советская энциклопедия
МИНИМАКС — смешанный экстремум ф ции f(x, у) двух переменных: Значение М. не меньше значения соответствующего максимина. Условия их равенства весьма важны в. игр теории … Большой энциклопедический политехнический словарь
минимакс — миним акс, а (матем.) … Русский орфографический словарь