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

Дополним матрицу игры столбцом с минимальными значениями в строках и строкой с максимальными значениями в столбцах:

B A	B1	B2	…	Bn	min в строке
A1	a11	a12	…	a1n	a1
A2	a21	a22	…	a2n	a2
…	…	…	…	…
Am	am1	am2	…	amn	am
max в столбце	b1	b2		bn

Величина

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

Стратегия игрока A, соответствующая максимину a, называется максиминной стратегией игрока A.

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

Величина

называется верхней ценой игры (или минимаксным выигрышем, или минимаксом).

Стратегия игрока B, соответствующая минимаксу b, называется минимаксной стратегией игрока B.

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

Принцип минимакса. Если оба игрока разумны, то игрок A будет выбирать свою максиминную стратегию, а игрок B – минимаксную.

Пример. Расширенная матрица игры "поиск" имеет вид:

B A	B1	B2	min в строке
A1	-1		-1
A2		-1	-1
max в столбце			-1

нижняя цена игры a = -1, верхняя цены игры b = 1.

Таким образом, если игрок будет делать личные ходы, а его противник об этом узнает, то игрок A получит минимальный выигрыш -1, то есть он будет в проигрыше, а игрок B получит минимальный проигрыш 1, то есть он будет выигрывать.

Аналогичное утверждение справедливо и для игрока B.

Определение.

Игра называется игрой с седловой точкой, если нижняя и верхняя цена игры совпадают.

Общее значение нижней и верхней цены игры n = a = b называется чистой ценой игры.

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

Примечание. Седловой точкой матрицы называется такой её элемент, который является минимальным в своей строке и максимальным в своём столбце.

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

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

Пример 2. Игра "защита от воздушного налёта". Сторона A обороняет от воздушного налёта два объекта, имея два орудия. Каждое орудие может поразить только тот самолёт, который находится в его зоне действия, но для этого оно должно до входа самолёта в зону следить за ним. Обстрелянная цель поражается. Сторона B атакует эти объекты двумя самолётами, которые могут быть направлены к любому объекту. Каждый самолёт может маневрировать, например, показав, что он направляется к объекту № 2, самолёт № 2 перед входом в зону действия орудия № 2, изменяет маршрут и атакует объект № 1.

Целью стороны A является защита, а стороны B поражение максимального количества объектов.

Стратегии сторон:

Сторона A
A1		Каждое орудие следит за целью, направляющейся в его зону.
A2		Каждое орудие следит за целью, направляющейся к другому объекту.
A3		Оба орудия следят за самолётом № 1.
A4		Оба орудия следят за самолётом № 2.
Сторона B
B1		Оба самолёта не меняют направление.
B2		Оба самолёта применяют обманный манёвр.
B3		Первый самолёт совершает манёвр, а второй – нет.
B4		Второй самолёт совершает манёвр, а первый – нет.

Матрица игры:

B A	B1	B2	B3	B4	min в строке
A1
A2
A3
A4
max в столбце					a =1 b = 1

в этой матрице числа означают количества защищённых объектов стороной A или количества потерянных самолётов стороной B.

Так как нижняя a и верхняя b цены игры совпадают, то игра имеет седловую точку (на самом деле седловых точек несколько), поэтому игра решается в чистых стратегиях с чистой ценой игры n = 1.

Оптимальные стратегии сторон: сторона A обоими орудиями следит за одним самолётом (любым), сторона B обоими самолётами атакует один объект (любой).

Результат: один объект будет уничтожен и потерян один самолёт.