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

Рассмотрим игру mxn с платежной матрицей выше. Следует определить:

1). наилучшую стратегию игрока I среди стратегий А_1, А_{2, …,} А_i, …, А_m.

2). наилучшую стратегию игрока II среди стратегий B_1, B_{2, …,} B_j, …, B_n.

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

Используя этот принцип, найдем наилучшую стратегию игрока I, для чего проанализируем последовательно все его стратегии. Выбирая стратегию А_i игрока I, мы должны рассчитать, что игрок II ответит на нее той из своих стратегий B_j, для которой выигрыш игрока I будет минимальным. Найдем минимальное число a_ij в каждой строке матрицы и, обозначив его a_i (i=1,2,…,m), запишем рядом с платежной матрицей в добавочный столбец:

a_i= min a_{i j} i=1,2,…,m.

	B1	B2	….	Bn	ai
A1	а11	а12	….	а1n	a1
A2	а21	а22	….	а2n	a2
….	….	….	….	….	….
Am	аm1	аm2	….	аmn	am
bj	b1	b2	….	bn-	a b

Зная числа a_i (свои минимальные выигрыши при применении стратегий А_i), игрок I должен предпочесть другим стратегиям ту, для которой a_i максимально. Обозначим это максимальное значение через a, тогда a= max a_i.. Подставив вместо a_i правую часть

I

выражения предыдущего, получим a= max min a_ij.

I j

Величина a -гарантированный выигрыш, который может обеспечить себе игрок I, называется нижней ценой игры (максимином). Стратегия, обеспечивающая получение нижней цены игры a, называется максиминной стратегией. Если игрок I,будет придерживаться своей максиминной (перестраховочной) стратегии, то ему гарантирован выигрыш, не меньший a при любом поведении игрока II. Игрок II заинтересован уменьшить свой проигрыш или, что тоже самое, выигрыш игрока I обратить в минимум. Поэтому для выбора своей наилучшей стратегии он должен найти максимальное значение выигрыша в каждом из столбцов и среди этих значений выбрать наименьшее. Максимальный элемент в каждом столбце обозначим через b_j. Эти элементы будем записывать в дополнительной строке таблицы.

Наименьшее значение среди b_j обозначим b - это верхняя цена игры (минимакс), которая определяется по формуле: b= min max a_{i j.}

J i

Стратегия игрока II, обеспечивающая “выигрыш” b, является его минимаксной стратегией. Если игрок II будет придерживаться своей минимаксной стратегии, то он гарантирован, что в любом случае проиграет не больше b.

Для нижней и верней цены игры всегда справедливо неравенство:

max min a_{i j} ≤ min max a_{i j} i=1,2,…,m

i j j i j=1,2,…,n

т.о.

a ≤ b

7 игр, для которых нижняя цена равна верхней, т.е. a= b. Такие игры называются играми с седловой точкой. Общее значение нижней и верхней цены игры в играх с седловой точкой называется чистой ценой игры, а стратегии А^*_i и В^*_I, позволяющие достичь этого значения, - оптимальными. Пара оптимальных стратегий (А^*_i, В^*_I) называется седловой точкой матрицы, т.к. элемент a_{i j}=γ является одновременно минимальным в i-ой строке и максимальным в j-ом столбце. Оптимальные стратегии и чистая цена являются решением игры. Оптимальные стратегии определяют в игре “положение равновесия”, которое заключаются в том, что каждый из игроков не заинтересован в отходе от своей оптимальной стратегии, т.к. ему это невыгодно. Чистую цену игры γ в игре с седловой точкой при условии одинаковой разумности партнеров игрок I не может увеличить, а игрок II уменьшить. Если игра имеет седловую точку, то говорят, что она решается в чистых стратегиях. Под чистой стратегией понимается такая стратегия, которая выбрана игроком сознательно, без привлечения механизма случайного выбора.