Минимакс

Перевод

Минимакс

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

где i — номера строк; j — номера столбцов; U_ij — выигрыш первого или потери второго игрока для элемента, находящегося на пересечении i -й строки и j -го столбца. Элемент платежной матрицы, в котором максимин первого игрока и М. второго равны, — седловая точка игры.

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

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

Развитием критерия М. является критерий минимаксных потерь («критерий Сэвиджа «, правило наименьшего риска). В соответствии с этим правилом для каждого столбца платежной матрицы рассчитывается разность между значением строки и максимальным значением («риск «): платежная матрица преобразуется в «матрицу потерь «. К ней применяется минимаксный критерий, выбору подлежитстратегия, которая минимизирует наибольший риск.

Верхняя и нижняя цена игры. Принцип минимакса

Платежная матрица

Антагонистические матричные игры

Рассмотрим конечную парную игру с нулевой суммой. Обозначим через a выигрыш игрока A, а через b – выигрыш игрока B. Так как a = – b, то при анализе такой игры нет необходимости рассматривать оба этих числа – достаточно рассматривать выигрыш одного из игроков. Пусть это будет, например, A. В дальнейшем для удобства изложения сторону A будем условно именовать "мы", а сторону B – "противник".

Пусть у нас имеется m возможных стратегий A ₁, A ₂, …, A_m, а у противника n возможных стратегий B ₁, B ₂, …, B_n (такая игра называется игрой m×n). Предположим, что каждая сторона выбрала определенную стратегию: мы выбрали A_i, противник B_j. Если игра состоит только из личных ходов, то выбор стратегий A_i и B_j однозначно определяет исход игры – наш выигрыш (положительный или отрицательный). Обозначим этот выигрыш через a_ij (выигрыш при выборе нами стратегии A_i, а противником – стратегии B_j).

Если игра содержит кроме личных случайные ходы, то выигрыш при паре стратегий A_i, B_j есть величина случайная, зависящая от исходов всех случайных ходов. В этом случае естественной оценкой ожидаемого выигрыша является математическое ожидание случайного выигрыша. Для удобства будем обозначать через a_ij как сам выигрыш (в игре без случайных ходов), так и его математическое ожидание (в игре со случайными ходами).

Предположим, что нам известны значения a_ij при каждой паре стратегий. Эти значения можно записать в виде матрицы, строки которой соответствуют нашим стратегиями (A_i), а столбцы – стратегиям противника (B_j):

Bj Ai	B 1	B 2	…	Bn
A 1	a 11	a 12	…	a 1 n
A 2	a 21	a 22	…	a 2 n
…	…	…	…	…
Am	am 1	am 2	…	amn

Такая матрица называется платежной матрицей игры или просто матрицей игры.

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

Рассмотрим пример 1 антагонистической игры 4×5. В нашем распоряжении есть четыре стратегии, у противника – пять стратегий. Матрица игры следующая:

Bj Ai	B 1	B 2	B 3	B 4	B 5
A 1
A 2
A 3
A 4

Какой стратегией нам (т.е. игроку A) воспользоваться? Какую бы мы ни выбрали стратегию, разумный противник ответит на нее той стратегией, для которой наш выигрыш будет минимальным. Например, если мы выберем стратегию A ₃ (соблазнившись выигрышем 10), противник в ответ выберет стратегию B ₁, и наш выигрыш будет всего лишь 1. Очевидно, исходя из принципа осторожности (а он – основной принцип теории игр), надо выбирать ту стратегию, при которой наш минимальный выигрыш максимален.

Обозначим через α_i минимальное значение выигрыша для стратегии A_i:

и добавим к матрице игры столбец, содержащий эти значения:

Bj Ai	B 1	B 2	B 3	B 4	B 5	минимум в строках αi
A 1
A 2
A 3
A 4							максимин

Выбирая стратегию, мы должны предпочесть ту, для которой значение α_i максимально. Обозначим это максимальное значение через α:

Величина α называется нижней ценой игры или максимином (максимум минимального выигрыша). Стратегия игрока A, соответствующая максимину α, называется максиминной стратегией.

В данном примере максимин α равен 3 (соответствующая клетка в таблице выделена серым цветом), а максиминная стратегия – A ₄. Выбрав эту стратегию, можем быть уверены, что при любом поведении противника выиграем не меньше, чем 3 (а может быть и больше при "неразумном" поведении противника"). Эта величина – наш гарантированный минимум, который мы можем себе обеспечить, придерживаясь наиболее осторожной ("перестраховочной") стратегии.

Теперь проведем аналогичные рассуждения за противника B. Он заинтересован в том, чтобы обратить наш выигрыш в минимум, то есть отдать нам поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Например, если он выберет стратегию B ₁, то мы ответим ему стратегией A ₃, и он отдаст нам 10. Если выберет B ₂ – мы ему ответим A ₂, и он отдаст 8 и т. д. Очевидно, осторожный противник должен выбрать ту стратегию, при которой наш максимальный выигрыш будет минимален.

Обозначим через β_j максимальные значения в столбцах платежной матрицы (максимальный выигрыш игрока A, или, что то же самое, максимальный проигрыш игрока B) для стратегии A_i:

и добавим к матрице игры строку, содержащую эти значения:

Bj Ai	B 1	B 2	B 3	B 4	B 5	минимум в строках αi
A 1
A 2
A 3
A 4							максимин
максимум в столбцах βj
			минимакс

Выбирая стратегию, противник предпочтет ту, для которой значение β_j минимально. Обозначим его через β:

Величина β называется верхней ценой игры или минимаксом (минимум максимального выигрыша). Соответствующая минимаксу стратегия противника (игрока B), называется минимаксной стратегией.

Минимакс – это значение выигрыша, больше которого заведомо не отдаст нам разумный противник (иначе говоря, разумный противник проиграет не больше, чем β). В данном примере минимакс β равен 5 (соответствующая клетка в таблице выделена серым цветом) и достигается он при стратегии противника B ₃.

Итак, исходя из принципа осторожности («всегда рассчитывай на худшее!»), мы должны выбрать стратегию A ₄, а противник – стратегию B ₃. Принцип осторожности является в теории игр основным и называется принципом минимакса.

Рассмотрим пример 2. Пусть игроки A и В одновременно и независимо друг от друга записывают одно из трех чисел: либо «1», либо «2», либо «3». Если сумма записанных чисел оказывается четной, то игрок B платит игроку A эту сумму. Если сумма нечетная, то эту сумму выплачивает игрок A игроку В.

Запишем платежную матрицу игры, и найдем нижнюю и верхнюю цены игры (номер стратегии соответствует записанному числу):

Bj Ai	B 1	B 2	B 3	минимум в строках αi
A 1		–3		–3	максимин
A 2	–3		–5	–5
A 3		–5		–5
максимум в столбцах βj
	минимакс

Игрок A должен придерживаться максиминной стратегии A ₁, чтобы выиграть не меньше –3 (то есть чтобы проиграть не больше 3). Минимаксная стратегия игрока B – любая из стратегий B ₁ и B ₂, гарантирующая, что он отдаст не более 4.

Тот же самый результат мы получим, если будем записывать платежную матрицу с точки зрения игрока В. Фактически, эта матрица получается путем транспонирования матрицы, построенной с точки зрения игрока A, и изменения знаков элементов на противоположный (так как выигрыш игрока A – это проигрыш игрока В):

Aj Bi	A 1	A 2	A 3	минимум в строках αi
B 1	–2		–4	–4	максимин
B 2		–4		–4
B 3	–4		–6	–6
максимум в столбцах βj
	минимакс

Исходя из этой матрицы следует, что игрок B должен придерживаться любой из стратегий B ₁ и B ₂ (и тогда он проиграет не более 4), а игрок A – стратегии A ₁ (и тогда он проиграет не более 3). Как видно, результат в точности совпадает с полученным выше, поэтому при анализе не важно, с точки зрения какого игрока мы его проводим.

Дата добавления: 2015-05-10