Минимакс - Minimax

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

Теория игры

В общем игры

Максимальное значение - это максимальное значение, которое игрок может быть уверен, не зная действий других игроков; эквивалентно, это наименьшее значение, которое другие игроки могут заставить игрока получить, если они знают действия игрока. Его формальное определение:

Где:

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

Расчет максимального значения игрока выполняется в наихудшем случае: для каждого возможного действия игрока мы проверяем все возможные действия других игроков и определяем наихудшую возможную комбинацию действий - ту, которая дает игроку i наименьшую ценить. Затем мы определяем, какое действие игрок я могу предпринять, чтобы убедиться, что это наименьшее значение является максимально возможным.

Например, рассмотрим следующую игру для двух игроков, в которой первый игрок («игрок ряда») может выбрать любой из трех ходов, обозначенных T , M или B , а второй игрок (игрок «столбца») может выбрать любой из два хода, L или R . Результат комбинации обоих ходов выражается в таблице выплат:

L р
Т 3,1 2, -20
M 5,0 -10,1
B -100,2 4,4

(где первое число в каждой ячейке - это выплата игрока строки, а второе число - выплата игрока столбца).

Для примера мы рассматриваем только чистые стратегии . Проверьте каждого игрока по очереди:

  • Игрок строки может сыграть T , что гарантирует ему выигрыш не менее 2 (игра B рискованна, так как может привести к выплате.−100 , и игра M может привести к выплате в размере−10 ). Следовательно: .
  • Игрок столбца может сыграть L и получить выигрыш не менее0 (игра R подвергает их риску получить ). Следовательно: .

Если оба игрока разыгрывают свои соответствующие максимальные стратегии , вектор выигрыша равен .

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

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

  • Строка игрок может получить максимальное значение 4 (если другой игрок играет R ) или 5 (если другой игрок играет L ), так что : .
  • Столбец player может получить максимальное значение 1 (если другой игрок играет T ), 1 (если M ) или 4 (если B ). Следовательно: .

Для каждого игрока i максимин не превышает минимакс:

Интуитивно понятно, что при максимизации максимизация происходит после минимизации, поэтому игрок i пытается максимизировать свою ценность, прежде чем узнает, что будут делать другие; в минимаксе максимизация предшествует минимизации, поэтому игрок i находится в гораздо лучшем положении - он максимизирует свою ценность, зная, что сделали другие.

Другой способ понять обозначения - читать справа налево: когда мы пишем

исходный набор результатов зависит как от, так и от . Мы сначала изолировать вдали от , пути максимизации над (для каждого возможного значения ) , чтобы получить набор результатов маргинальных , которая зависит только от . Затем мы минимизируем эти результаты. (И наоборот для максимина.)

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

В играх с нулевой суммой

В играх с нулевой суммой для двух игроков минимаксное решение совпадает с равновесием по Нэшу .

В контексте игр с нулевой суммой теорема о минимаксе эквивалентна:

Для каждой игры двух лиц с нулевой суммой и конечным числом стратегий существует значение V и смешанная стратегия для каждого игрока, такие что

(a) Учитывая стратегию игрока 2, наилучший возможный выигрыш для игрока 1 равен V, и
(b) Учитывая стратегию игрока 1, наилучший возможный выигрыш для игрока 2 равен −V.

Точно так же стратегия Игрока 1 гарантирует ему выигрыш в размере V независимо от стратегии Игрока 2, и аналогично Игрок 2 может гарантировать себе выигрыш в размере -V. Название «минимакс» возникает из-за того, что каждый игрок минимизирует максимально возможный выигрыш для другого - поскольку игра ведется с нулевой суммой, они также минимизируют свой собственный максимальный проигрыш (т.е. максимизируют свой минимальный выигрыш). См. Также пример игры без значения .

Пример

Матрица выплат для игрока А
B выбирает B1 B выбирает B2 B выбирает B3
A выбирает A1 +3 −2 +2
A выбирает A2 −1 +0 +4
A выбирает A3 −4 −3 +1

Следующий пример игры с нулевой суммой, в которой A и B делают одновременные ходы, иллюстрирует максиминные решения. Предположим, что у каждого игрока есть три варианта выбора, и рассмотрим матрицу выплат для A, показанную справа. Предположим, что матрица выплат для B - это та же матрица с обратными знаками (т. Е. Если выбраны A1 и B1, то B платит 3 A ). Тогда выбор максимина для A - это A2, поскольку в этом случае за худший возможный результат придется заплатить 1, в то время как выбор простого максимина для B - это B2, поскольку наихудший возможный результат - это отсутствие оплаты. Однако это решение нестабильно, поскольку, если B считает, что A выберет A2, то B выберет B1, чтобы получить 1; тогда, если A считает, что B выберет B1, тогда A выберет A1, чтобы получить 3; а затем B выберет B2; и в конце концов оба игрока осознают сложность выбора. Так что нужна более стабильная стратегия.

Некоторые варианты выбора преобладают над другими и могут быть исключены: A не выберет A3, поскольку либо A1, либо A2 дадут лучший результат, независимо от того, что выберет B ; B не выберет B3, поскольку некоторые смеси B1 и B2 дадут лучший результат, независимо от того, что выберет A.

A может избежать выплаты ожидаемого платежа более 1∕3, выбрав A1 с вероятностью 1∕6 и A2 с вероятностью 5∕6: ожидаемый выигрыш для A будет 3 × (1∕6) - 1 × (5 ∕ 6) = −1∕3 в случае, если B выбрал B1, и −2 × (1∕6) + 0 × (5∕6) = −1/3 в случае, если B выбрал B2. Точно так же B может обеспечить ожидаемый выигрыш не менее 1/3, независимо от того, что выбирает A , используя рандомизированную стратегию выбора B1 с вероятностью 1∕3 и B2 с вероятностью 2∕3. Эти смешанные минимаксные стратегии теперь стабильны и не могут быть улучшены.

Максимин

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

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

В повторяющихся играх

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

Комбинаторная теория игр

В комбинаторной теории игр существует минимаксный алгоритм игровых решений.

Простой вариант минимаксном алгоритма , указанных ниже, рассматриваются такие игры, как крестики-нолики , где каждый игрок может выиграть, проиграть или рисовать. Если игрок А может выиграть за один ход, его лучший ход - это выигрышный ход. Если игрок B знает, что один ход приведет к ситуации, когда игрок A может выиграть одним ходом, а другой ход приведет к ситуации, когда игрок A может, в лучшем случае, взять ничью, тогда лучший ход игрока B - тот, который ведет к рисовать. В конце игры легко увидеть, какой ход «лучший». Алгоритм Minimax помогает найти лучший ход, работая в обратном направлении с конца игры. На каждом этапе предполагается, что игрок A пытается максимизировать шансы на выигрыш A, в то время как на следующем ходу игрок B пытается минимизировать шансы на выигрыш A (т. Е. Максимизировать собственные шансы B на выигрыш).

Алгоритм минимакс с чередующимися ходами

Минимаксное алгоритм является рекурсивным алгоритмом для выбора следующего шага в п-плеер игре , как правило , два-игрока игра. Ценность связана с каждой позицией или состоянием игры. Это значение вычисляется с помощью функции оценки позиции и показывает, насколько хорошо игроку было бы достичь этой позиции. Затем игрок делает ход, который максимизирует минимальное значение позиции в результате возможных последующих ходов противника. Если это очередь «s двигаться, дает значение каждому из них юридических шагов.

Возможный метод распределения состоит в том, чтобы присвоить определенный выигрыш для A как +1 и для B как −1. Это приводит к комбинаторной теории игр, разработанной Джоном Хортоном Конвеем . Альтернативой является использование правила, согласно которому, если результат хода является немедленным выигрышем для A, ему присваивается положительная бесконечность, а если это немедленный выигрыш для B , отрицательная бесконечность. Ценность любого другого хода для A - это максимальное значение, полученное в результате каждого из возможных ответов B. По этой причине A называется максимизирующим игроком, а B называется минимизирующим игроком , отсюда и название минимаксный алгоритм . Вышеупомянутый алгоритм присваивает значение положительной или отрицательной бесконечности любой позиции, поскольку значение каждой позиции будет значением некоторой окончательной выигрышной или проигрышной позиции. Часто это, как правило, возможно только в самом конце сложных игр, таких как шахматы или го , поскольку с вычислительной точки зрения невозможно заглядывать вперед до завершения игры, кроме как ближе к концу, и вместо этого позициям присваиваются конечные значения. как оценки степени уверенности в том, что они приведут к победе того или иного игрока.

Это можно расширить, если мы сможем предоставить функцию эвристической оценки, которая дает значения незавершенным игровым состояниям без учета всех возможных следующих полных последовательностей. Затем мы можем ограничить алгоритм минимакса, чтобы он смотрел только на определенное количество ходов вперед. Это число называется «упреждающим» и измеряется в « слоях ». Например, шахматный компьютер Deep Blue (который первым обошел действующего чемпиона мира Гарри Каспарова на тот момент) смотрел вперед как минимум на 12 уровней, а затем применил функцию эвристической оценки.

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

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

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

Псевдокод

Псевдокод для глубины ограничена минимаксного алгоритма приведен ниже.

function  minimax(node, depth, maximizingPlayer) is
    if depth = 0 or node is a terminal node then
        return the heuristic value of node
    if maximizingPlayer then
        value := −∞
        for each child of node do
            value := max(value, minimax(child, depth − 1, FALSE))
        return value
    else (* minimizing player *)
        value := +∞
        for each child of node do
            value := min(value, minimax(child, depth − 1, TRUE))
        return value
(* Initial call *)
minimax(origin, depth, TRUE)

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

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

Пример

Пример минимаксного дерева
Анимированный педагогический пример, который пытается быть дружелюбным к человеку, подставляя начальные бесконечные (или произвольно большие) значения для пустоты и избегая использования упрощений негамаксного кодирования.

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

Алгоритм оценивает каждый листовой узел с помощью функции эвристической оценки, получая показанные значения. Хода , где максимизация игрок выигрывает присвоенные с положительной бесконечностью, в то время как шаги , которые приведут к победе на минимизируя игрок присваивается с отрицательной бесконечностью. На уровне 3 алгоритм выберет для каждого узла наименьшее из значений дочернего узла и назначит его этому же узлу (например, узел слева выберет минимум между «10» и «+ ∞», поэтому присвоив себе значение «10»). Следующий шаг на уровне 2 состоит в выборе для каждого узла наибольшего из значений дочернего узла . И снова значения присваиваются каждому родительскому узлу . Алгоритм продолжает оценивать максимальное и минимальное значения дочерних узлов поочередно, пока не достигнет корневого узла , где он выбирает ход с наибольшим значением (представлен на рисунке синей стрелкой). Это шаг , который игрок должен сделать для того , чтобы свести к минимуму в максимально возможной потери .

Минимакс для индивидуальных решений

Минимакс перед лицом неопределенности

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

Кроме того, были разработаны деревья expectiminimax для игр с двумя игроками, в которых шанс (например, игра в кости) является фактором.

Минимаксный критерий в статистической теории принятия решений

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

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

Невероятностная теория принятия решений

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

Кроме того, минимакс требует только порядкового измерения (для сравнения и ранжирования результатов), а не интервальных измерений (которые включают в себя «насколько лучше или хуже»), и возвращает порядковые данные, используя только смоделированные результаты: вывод минимаксного анализа : «эта стратегия является минимаксной, так как наихудший случай - (результат), который менее плох, чем любая другая стратегия». Сравните с анализом ожидаемого значения, вывод которого имеет форму: «эта стратегия дает E ( X ) = n». Таким образом, Minimax может использоваться для порядковых данных и может быть более прозрачным.

Максимин в философии

В философии термин «максимин» часто используется в контексте « Теории справедливости» Джона Ролза , где он ссылается на него (Rawls 1971, стр. 152) в контексте Принципа различия . Ролз определил этот принцип как правило, согласно которому социальное и экономическое неравенство должно быть устроено таким образом, чтобы «оно приносило наибольшую пользу наименее обеспеченным членам общества».

Смотрите также

Примечания

внешние ссылки