Принцип минимакса

Рассмотрим конечную парную игру с нулевой суммой.

Игрок I имеет стратегий , а игрок II – стратегий . Такая игра называется игрой размерностью . Пусть каждая сторона выбрала определенную стратегию:

игрок I –

игрок II – .

Если такая таблица составлена, то игра приведена к матричной форме и называется матричной игрой.

Пусть – выигрыш игрока I в ситуации, когда игрок выбрал стратегию , а игрок II выбрал стратегию , Выигрыш игрока II в данной ситуации обозначим через .

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

Если игра состоит только из личных ходов, то выбор стратегии ( , ) однозначно определяет исход игры, например выигрыш игрока I.

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

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

Будем считать, что все . Этого всегда можно добиться прибавлением достаточно большого положительного числа ко всем строкам и столбцам матрицы. Такое изменение матрицы не повлияет на результат.

Таким образом, платежная матрица имеет следующий вид (табл. 5.1)

Таблица 5.1

II I	B1	B2	…	Bj	…	Bn	min
A1	a11	a12	…	a1j	…	a1n
A2	a21	a22	…	a2j	…	a2n
…	…	…	…	…	…	…	…
Ai	ai1	ai2	…	aij	…	ain
…	…	…	…	…	…	…	…
Am	am1	an2	…	amj	…	amn
max			…		…

Задача состоит в определении:

1) наилучшей (оптимальной) стратегии игрока I из стратегий ,

2) наилучшей (оптимальной) стратегии игрока II из стратегий .

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

Характерные оценки

Проанализируем последовательно каждую стратегию игрока I.

Если игрок I выбирает стратегию то его выигрыш будет равен наименьшему из чисел . Обозначим его :

т.е. – минимальное значение из всех чисел строки.

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

т.е. – максимальное значение из всех чисел столбца ( ).

Подставив вместо выражение (6.1), получим:

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

Игрок II заинтересован в том, чтобы уменьшить свой проигрыш, т.е. обратить выигрыш игрока I в минимум. Для выбора оптимальной стратегии он должен найти максимальное значение выигрыша в каждом столбце и среди этих значений выбрать наименьшее.

Обозначим через максимальное значение в каждом столбце:

Наименьшее значение обозначим через :

С учетом (6.4) получим:

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

Справедливо неравенство < .

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

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

Этот принцип был впервые сформулирован Дж. фон Нейманом в 1928 г.

Существуют матричные игры, для которых нижняя цена игры равна верхней, т.е. = . Такие игры называются играми с седловой точкой, в этом случае = = называется чистой ценой игры, а стратегии игроков и , позволяющие достичь этого значения, – оптимальными. Пара ( , ) называется седловой точкой матрицы, так как элемент одновременно является минимальным в i-й строке и максимальным -м столбце. Оптимальные стратегии и и чистая цена являются решением игры в чистых стратегиях, т.е. без привлечения механизма случайного выбора.

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