Минимакс

Минимакс (иногда Минмакс , ММ ^[1] или седловая точка ^[2] ) — это правило принятия решений, используемое в искусственном интеллекте , теории принятия решений , теории игр , статистике и философии для минимизации возможных потерь в наихудшем случае ( максимальный проигрыш) . Когда речь идет о выигрышах, его называют «максимином» — максимизировать минимальный выигрыш. Первоначально сформулированное для теории игр с нулевой суммой для нескольких игроков , охватывающее как случаи, когда игроки делают поочередные ходы, так и случаи, когда они делают одновременные ходы, оно также было распространено на более сложные игры и на общее принятие решений в условиях неопределенности.

Теория игр

В общих играх

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

{\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}

Где:

$i$ — индекс интересующего игрока.
$-i$ обозначает всех остальных игроков, кроме игрока $i$ .
$a_{i}$ действие, предпринятое игроком $i$ .
$а_{-я}$ обозначает действия, предпринимаемые всеми остальными игроками.
$v_{i}$ — функция ценности игрока $i$ .

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

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

{\begin{array}{c|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}

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

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

Игрок ряда может сыграть $T$ , что гарантирует ему выигрыш не менее2 (игра $B$ рискованна, так как может привести к выигрышу−100 , а игра $M$ может привести к выигрышу−10 ). Следовательно: . ${\underline {v_{row}}}=2$
Игрок колонны может сыграть $L$ и получить выигрыш не менее0 (игра $R$ подвергает их риску получить ). Следовательно: . $-20$ ${\underline {v_{col}}}=0$

Если оба игрока используют свои соответствующие стратегии максимина , вектор выигрыша равен . $(Т,Л)$ $(3,1)$

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

{\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}

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

Игрок ряда может получить максимальное значение $4$ (если другой игрок играет $R$ ) или5 (если другой игрок играет $L$ ), поэтому: ${\overline {v_{row}}}=4\ .$
Игрок столбца может получить максимальное значение $1$ (если другой игрок играет $T$ ),1 (если $М$ ) или4 (если $B$ ). Следовательно: ${\overline {v_{col}}}=1\ .$

Для каждого игрока $i$ максимин не больше минимакса:

{\underline {v_{i}}}\leq {\overline {v_{i}}}

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

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

{\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}

начальный набор результатов зависит от обоих и Сначала мы делаем маргинализацию от , максимизируя по (для каждого возможного значения ), чтобы получить набор предельных результатов , который зависит только от Затем мы минимизируем по этим результатам. (И наоборот для максимина.) $\ v_{i}(a_{i},a_{-i})\$ $\ {a_{i}}\$ $\ {a_{-i}}\ .$ ${a_{i}}$ $v_{i}(a_{i},a_{-i})$ $\ {a_{i}}\$ ${a_{-i}}$ $\ v'_{i}(a_{-i})\,,$ $\ {a_{-i}}\ .$ $\ {a_{-i}}\$

Хотя всегда имеет место тот факт, что и вектор выигрыша, полученный в результате того, что оба игрока используют свои минимаксные стратегии, в случае или в случае нельзя аналогичным образом ранжировать относительно вектора выигрыша, полученного в результате того, что оба игрока используют свои максиминные стратегии. $\ {\underline {v_{row}}}\leq {\overline {v_{row}}}\$ $\ {\underline {v_{col}}}\leq {\overline {v_{col}}}\,,$ $\ (2,-20)\$ $\ (Т,Р)\$ $(-10,1)$ $\ (М,Р)\,,$ $\ (3,1)\$

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

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

В контексте игр с нулевой суммой теорема о минимаксе эквивалентна: ^[4]^{[ проверка не пройдена ]}

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

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

Пример

Следующий пример игры с нулевой суммой, где A и B делают одновременные ходы, иллюстрирует максиминные решения. Предположим, что у каждого игрока есть три выбора, и рассмотрим матрицу выплат для A, отображенную на столе («Матрица выплат для игрока 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.

Игрок А может избежать необходимости делать ожидаемый платеж в размере более ⁠1/ 3 ⁠ выбрав А1 с вероятностью ⁠1/ 6 ⁠ и А2 с вероятностью ⁠ 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 ⁠ , независимо от того, что выберет А , используя рандомизированную стратегию выбора В1 с вероятностью ⁠1/ 3 ⁠ и B2 с вероятностью ⁠2/ 3 ⁠ . Эти смешанные минимаксные стратегии не могут быть улучшены и теперь стабильны.

Максимин

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

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

В повторных играх

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

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

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

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

Алгоритм Минимакс с альтернативными ходами

Алгоритм минимакса ^[5] — это рекурсивный алгоритм выбора следующего хода в игре с n игроками , обычно в игре с двумя игроками. Значение связано с каждой позицией или состоянием игры. Это значение вычисляется с помощью функции оценки позиции и указывает, насколько хорошо было бы для игрока достичь этой позиции. Затем игрок делает ход, который максимизирует минимальное значение позиции, полученной из возможных следующих ходов противника. Если очередь хода за A, A присваивает значение каждому из его допустимых ходов.

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

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

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

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

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

Псевдокод

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

Функция minimax(node, depth, maximizingPlayer) возвращает эвристическое значение node , если depth = 0 или node является конечным узлом. Если maximizingPlayer , то  значение := −∞ для каждого потомка узла сделать значение := max(значение, минимакс(дочерний элемент, глубина − 1, ЛОЖЬ)) возвращаемое значение в противном случае  (* минимизация игрока *) значение := +∞ для каждого потомка узла сделать значение := min(значение, минимакс(дочерний элемент, глубина − 1, ИСТИНА)) возвращаемое значение

(* Первоначальный звонок *)минимакс(начало координат, глубина, ИСТИНА)

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

Minimax рассматривает двух игроков (максимизирующего и минимизирующего) по отдельности в своем коде. На основе наблюдения, что minimax часто может быть упрощен до алгоритма negamax . $\ \макс(a,b)=-\мин(-a,-b)\ ,$

Пример

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

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

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

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

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

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

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

В классической статистической теории принятия решений у нас есть оценщик , который используется для оценки параметра . Мы также предполагаем функцию риска , обычно определяемую как интеграл функции потерь . В этой структуре называется минимаксом , если он удовлетворяет $\ \дельта \$ $\ \theta \in \Theta \ .$ $\ R(\theta ,\delta )\ .$ $\ {\tilde {\delta }}\$

\sup _{\theta }R(\theta ,{\tilde {\delta }})=\inf _{\delta }\ \sup _{\theta }\ R(\theta ,\delta )\ .

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

\int _{\Theta }R(\theta ,\delta )\ \operatorname {d} \Pi (\theta )\ .

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

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

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

Минимакс в политике

Концепцию голосования « меньшего зла » (LEV) можно рассматривать как форму минимаксной стратегии, когда избиратели, столкнувшись с двумя или более кандидатами, выбирают того, который, по их мнению, является наименее вредным или «меньшее зло». Чтобы сделать это, «голосование не должно рассматриваться как форма личного самовыражения или морального суждения, направленного в отместку основным партийным кандидатам, которые не отражают наши ценности, или коррумпированной системы, призванной ограничить выбор тем, что приемлемо для корпоративной элиты», а скорее как возможность уменьшить вред или потери. ^[7]

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

В философии термин «максимин» часто используется в контексте «Теории справедливости » Джона Ролза , где он ссылается на него в контексте « Принципа различия» . ^[8] Ролз определил этот принцип как правило, которое гласит, что социальное и экономическое неравенство должно быть устроено таким образом, чтобы «оно приносило наибольшую пользу наименее обеспеченным членам общества». ^[9]^[10]

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

Ссылки

^ Бахус, Баруа (январь 2013 г.). Provincial Healthcare Index 2013 (PDF) (Отчет). Fraser Institute. стр. 25.
^ Профессор Рэймонд Флуд. Тьюринг и фон Нейман (видео). Колледж Грешем – через YouTube .
^ аб Машлер, Майкл; Солан, Эйлон ; Замир, Шмуэль (2013). Теория игр . Издательство Кембриджского университета . стр. 176–180. ISBN 9781107005488.
^ Осборн, Мартин Дж.; Рубинштейн, А. (1994). Курс теории игр (печатное издание). Кембридж, Массачусетс: MIT Press. ISBN 9780262150415.
^ Рассел, Стюарт Дж .; Норвиг, Питер. (2021). Искусственный интеллект: современный подход (4-е изд.). Хобокен: Pearson. стр. 149–150. ISBN 9780134610993. LCCN 20190474.
^ Hsu, Feng-Hsiung (1999). «Шахматные гроссмейстерские чипы IBM Deep Blue». IEEE Micro . 19 (2). Лос-Аламитос, Калифорния, США: IEEE Computer Society: 70–81. doi :10.1109/40.755469. Во время матча 1997 года поиск программного обеспечения расширил поиск примерно до 40 слоев вдоль линий форсинга, хотя нерасширенный поиск достиг только около 12 слоев.
↑ Ноам Хомский и Джон Халле, «Восемь пунктов краткого обзора LEV (голосование за меньшее зло)», New Politics, 15 июня 2016 г.
^ Роулз, Дж. (1971). Теория справедливости . стр. 152.
^ Эрроу, К. (май 1973 г.). «Некоторые ординалистско-утилитаристские заметки о теории справедливости Ролза». Журнал философии . 70 (9): 245–263. doi :10.2307/2025006. JSTOR 2025006.
^ Харсани, Дж. (июнь 1975 г.). «Может ли принцип максимина служить основой морали? Критика теории Джона Ролза» (PDF) . American Political Science Review . 69 (2): 594–606. doi :10.2307/1959090. JSTOR 1959090. S2CID 118261543.

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

Найдите значение слова «минимакс» в Викисловаре, бесплатном словаре.

В Викицитатнике есть цитаты, связанные с Минимаксом .

«Принцип минимакса», Энциклопедия математики , EMS Press , 2001 [1994]
«Смешанные стратегии». cut-the-knot.org . Учебная программа: Игры.— Апплет визуализации
"Принцип Максимина". Словарь философских терминов и имён . Архивировано из оригинала 2006-03-07.
«Минимакс». Словарь алгоритмов и структур данных . US NIST .