logo
Шепеленко О

Алгоритм принципа максимина (минимакса)

1. В строке платежной матрицы, которая соответствует стратегии Аі, найти минимальное из чисел :

. (2.5.1)

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

2. Определить число по формуле (2.5.2)

=, (2.5.2)

и называется нижней ценой игры или максимином . Соответствующая стратегия называется максиминной.

Максимин – это гарантированный выигрыш, который игрок А может себе обеспечить в игре против разумного противника.

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

3. В столбце платежной матрицы, который соответствует стратегии Вj, найти максимальное с чисел :

. (2.5.3)

Это максимальный проигрыш игрока В, при использовании стратегии Вj – самый большой из проигрышей. Очевидно, что игрок В старается превратить выигрыш игрока А в минимальный, то есть он должен выбрать стратегию, которая дает самый маленький проигрыш.

4. Определить число , которое определяется по формуле (2.5.4)

, (2.5.4)

и называется верхней ценой игры или минимаксом . Соответствующая стратегия называется минимаксной.

Минимакс – это гарантированный проигрыш, который игрок В может себе позволить в игре против разумного противника.

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

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

Замечание. Нижняя цена игры всегда не превосходит верхнюю цену игры.

Цена игры – это объективно возможный средний выигрыш .

Если , то выигрыш А является определенным числом, а такая игра называется определенной игрой в чистых стратегиях или игрой с седловой точкой.

Выигрыш называется значением игры, равен элементу .

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

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

Пример 2.5.1. Решить матричную игру с платежной матрицей .