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

Число а называется нижним значением (нижней ценой) игры.

Принцип построения стратегии игрока А, основанный на максимизации минимальных выигрышей, называется принципом максимина, а выбираемая в соответствии с этим принципом стратегия At* - мак-симинной стратегией игрока А.

В. Действия игрока В.

1-й шаг. В каждом столбце матрицы А ищется максимальный элемент

Рk = maxtf, k = l, 2, п. Полученные числа

Л> 02> > Рп

приписываются к заданной таблице в виде нижней добавочной строки

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

2-й шаг. Среди чисел

Л> 02 > 0Л выбирается минимальное число

В = min В. =minmaxtf...

Г к * к I *

Выбранное число fi также является одним из элементов заданной матрицы А

Если игрок В будет придерживаться стратегии Вк*9 для которой число рк* является минимальным, (i = (5к*9 то при любом поведении игрока А игроку В гарантирован проигрыш, не больший /8.

Число (5 называется верхним значением (верхней ценой) игры.

Принцип построения стратегии игрока Д основанный на минимизации максимальных потерь, называется принципом минимакса, а выбираемая в соответствии с этим принципом стратегия Вк* - минимаксной стратегией игрока В.

Покажем, что нижнее значение игры а и верхнее значение игры /} всегда связаны соотношением

а <р.

В самом деле, из того, что для любого к и

<тахдЛ = £, для любого I, вытекает неравенство

справедливое для любых / и к.

Отсюда в силу произвольности / получаем, что

a = maxa, £ fi к

и (в силу произвольности к) -

a£mmfik = /?.

Замечание. Реализация описанного алгоритма требует 2тп - 1 сравнений элементов матрицы А:

(л - \)т + т - 1 = тп-1

сравнений для определения а,

(т - \)п + п - 1 = тп - 1

сравнений для определения fi и одно сравнение полученных чисел а и /?. Если

или, подробнее,

maxmin я,. = a,... = minmaxtf.,

/ к 1 к к I *

то ситуация {А9 В?} оказывается равновесной, и ни один из игроков не заинтересован в том, чтобы ее нарушить (в этом нетрудно убедиться путем рассуждений, подобных проведенным при анализе игры в примере 2).

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

Значение игры совпадает с элементом ак. матрицы игры А,

расположенным на пересечении /*-й строки (стратегия At* игрока А) и к*-то столбца (стратегия Вк* игрока В) - минимальным в своей строке и максимальным в своем столбце.

Условие a=fi можно записать и так:

ал. <агк. <я/ч, / = 1, m\ fc = l, п.

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

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

Замечание. Седловых точек в матричной игре может быть несколько, но все они имеют одно и то же значение.

Покажем это.

Пусть агк. и - две седловые точки матрицы А

- * */ч> V - at*k* * <W Поочередно используя эти соотношения, имеем

ai*k* ~ ai*r ~ ai*k - ark* ai*** Ясно, что здесь все знаки неравенства нужно заменить на знаки равенства.

Как возник термин седловая точка

Попробуем взглянуть на максиминную и минимаксную процедуры несколько по-иному.

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

Группа горных туристов, взобравшись на левую вершину, намерена покорить и правую. Существует несколько возможных маршрутов. Какой из них лучше?

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