Подумаем теперь за противника.
Он тоже хочет отдать поменьше, а получить побольше. Но, какую бы он стратегию ни выбрал, мы («красные») поведем себя таким образом, чтобы получить с него побольше. Значит противник («синие») должен в каждом столбце выписать не минимальное, а максимальное число (см. нижнюю добавочную строку в матрице (3)).
Из этих максимумов он должен найти минимальный (минимакс или верхняя цена игры β). Эта величина в нашем случае равна 4 и отмечена звездочкой. Чтобы не проиграть больше 4, «синие» должны придерживаться любой из своих двух стратегий С1, С2.
Значит, если каждому участнику предлагается выбрать одну единственную стратегию, то эти стратегии должны быть: К1 для «красных» и С1 или С2 для «синих».
Как мы выбрали эти стратегии? Руководствуясь принципом осторожности, который говорит: в игре веди себя так, чтобы получить наибольшую выгоду при наихудших для тебя действиях противника. Этот принцип называется принципом минимакса и является в теории игр основным.
Применяя этот принцип, мы пока что рекомендовали игроку К показывать один палец, игроку С - показывать один или два пальца.
Но нашли ли мы решение игры, т.е. такую пару стратегий, которая являемся равновесным положением? Легко убедиться, что нет. Найденные нами стратегии обладают досадным свойством: они неустойчивы.
Действительно, пусть оба игрока держатся рекомендованных чистых стратегий: К1 и, скажем, С1. Пока оба держатся этих стратегий, выигрыш будет равен 2, т.е. на каждую партию игры С проигрывает К два очка. К, может быть, и доволен, но С досадно. Он не хочет проигрывать.
Допустим, он откуда-то узнал что мы придерживаемся стратегии К1. Что он будет делать? Разумеется, немедленно перейдет к стратегии С2 и будет получать по 3 очка, т.е. сведет наш выигрыш к -3.
А если мы теперь узнаем о поведении С? Перейдем на стратегию К2. В ответ на это С перейдет на С3 и т.д.
Мы убедились, что пара стратегий, вытекающих из принципа минимакса, неустойчива: стоит одному игроку узнать, что делает другой, как равновесие нарушается...
Всегда ли это будет так? Оказывается, не всегда.
Седловая точка. Чистая цена игры.
Пример. Пусть дана матрица игры (4):
| C1 | C2 | C3 | C4 | Минимумы строк | |
| К1 | |||||
| К2 | |||||
| К3 | |||||
| Максимумы столбцов |
Требуется найти нижнюю цену игры α, верхнюю цену игры β и минимаксные стратегии и проверить, являются ли они устойчивыми.
Решение:
Из анализа дополнительных столбца и строки получаем: α = 5, β = 5. Максимин равен минимаксу! Случай особый. Что же из этого следует?
Возьмем пару минимаксных стратегий: К2 и С3. Если оба держатся этих стратегий, то выигрыш будет равен 5.
Теперь, допустим, мы узнали о поведении противника. Что будем делать? А ничего! Мы по-прежнему будем держаться стратегии К2, потому что любое отступление от нее нам невыгодно. Знаем мы или не знаем о поведении противника - все равно будем держаться стратегии К2! То же относится и к «синим» - им нет смысла менять свою стратегию С3.
В данном примере пара стратегий К2 и С3 устойчива, т. е. представляет собой положение равновесия и дает решение игры.
Почему так получилось? Потому что в матрице имеется особый элемент 5; он является минимальным в своей строке и одновременно максимальным в своем столбце. Такой элемент называется седловой точкой.
Если матрица имеет седловую точку (т. е. нижняя цена игры равна верхней), то игра имеет решение в чистых стратегиях: это - пара стратегий, пересекающихся в седловой точке. Сама же седловая точка дает цену игры - в нашем примере она равна 5.
Класс игр, имеющих седловую точку, имеет большое значение в теории игр. В частности, доказано, что если по правилам игры каждый из игроков знает результат всех предыдущих ходов, как своих, так и противника (так называемая игра с полной информацией), то игра имеет седловую точку и, значит, имеет решение в чистых стратегиях.
Примерами игр с полной информацией могут служить: шахматы, шашки, «крестики и нолики» и т. п.
Пример игры с полной информацией.
Два игрока - К и С - поочередно кладут одинаковые монеты на круглый стол. Положение каждой монеты выбирается произвольно, лишь бы она не перекрывалась другими. Выигрывает тот из игроков, который положит монету последним (когда места для других уже не остается).
Стоит немножко подумать, чтобы убедиться, что исход этой игры всегда предрешен и что существует вполне определенная стратегия, гарантирующая выигрыш тому из игроков, который кладет монету первым (пусть это будет К). А именно К должен положить первую монету в центр стола, а далее на каждый ход С отвечать в точности симметричным относительно центра стола ходом! Бедный С может при этом вести себя как угодно, спасения ему все равно нет...
Очевидно, такая игра имеет смысл только для тех, кто не знает решения.
Любопытно, что совершенно так же обстоит дело и с такой популярной игрой, как шахматы! Эта игра имеет смысл только до тех пор, пока не найдено ее решение.
Теоретически доказано, что решение существует и исход шахматной игры в сущности предрешен: если каждая сторона будет пользоваться своей оптимальной стратегией, то игра либо всегда будет кончаться выигрышем белых, либо всегда выигрышем черных, либо всегда ничьей! Но чем же именно? Мы пока этого не знаем, так как число возможных стратегий слишком велико, чтобы можно было построить матрицу шахматной игры и найти в ней седловую точку...
Наверное, любители шахмат заинтересованы в том, чтобы шахматная игра была решена еще не скоро.
Заметим в заключение, что седловых точек в матрице может быть несколько; тог да решений игры в чистых стратегиях существует столько, сколько имеется седловых точек. Каждое из них дает выигрыш, равный цене игры.
Пример. Игра «Поиск».
В игре участвуют две стороны: К и С.
К хочет найти С; С, наоборот, хочет спрятаться от К.
У С есть два места — убежища I и II, где он может прятаться. Выбирает он себе любое убежище. Игрок К по правилам игры тоже может искать С, где ему вздумается.
Если он нашел С, С проиграл одно очко, если не нашел, т. е. пошел не в то убежище, где спрятался С, то, наоборот, К проиграл одно очко.
Требуется записать игру в нормальной форме.
Решение:
Для К - 2 стратегии: К1 - искать в убежище I, К2 - искать в убежище II.
Для С - тоже 2 стратегии: C1 - прятаться в убежище I, C2 -прятаться в убежище II.
Игра конечная - 2x2, матрица игры будет:
| C1 | C2 | |
| К1 | -1 | |
| К2 | -1 |
К этой игре мы еще вернемся в дальнейшем и найдем ее решение.
Порассуждаем за игрока К.
Выберем, например, К1, т.е. будем искать всегда в убежище I. Но тогда разумный противник через несколько партий догадается о нашей стратегии и будет прятаться там, где мы его не ищем, т.е. в убежище II. Плохо! Выберем стратегию К2. Ничуть не лучше: противник снова догадается и будет прятаться в убежище I. Что же нам делать?
Попробуем применять стратегии К1 и К2 попеременно, через одну партию игры. Но ведь противник и об этом может догадаться и будет прятаться каждый раз не там, где мы его ищем. Как ни кинь — все клин! Что же, значит, наше положение безвыходно?