Примеры конечных игр. Принцип минимакса

Приведем несколько примеров конечных игр. Каждую из них мы запишем в нормальной форме.

Пример 1. Рассматривается игра, которую назовем «Поиск». В ней участвуют две стороны: К и С. К хочет найти С; С, наоборот, хочет спрятаться от К. У С есть два места — убежища I и II, где он может прятаться. Выбирает он себе любое убежище. Игрок К по правилам игры тоже может искать С, где ему вздумается. Если он нашел С, С проиграл одно очко, если не нашел, т. е. пошел не в то убежище, где спрятался С, то, наоборот, К проиграл одно очко. Требуется записать игру в нормальной форме.

Решение.
У К — две стратегии:
К₁ — искать в убежище I,
К₂ — искать в убежище II.
У С — тоже две стратегии:
C₁ — прятаться в убежище I,
C₂ — прятаться в убежище II.
Игра конечная — 2x2, матрица игры будет:

К этой игре мы еще вернемся в дальнейшем и найдем ее решение. А пока что просто порассуждаем за игрока К. Представим себе, что мы игрок К и что нам предлагается выбрать себе стратегию. Что ж, попробуем! Выберем, на пример, К₁, т. е. будем искать всегда в убежище I. Но тогда разумный противник через несколько партий догадается о нашей стратегии и будет прятаться там, где мы его не ищем, т. е. в убежище II. Плохо! Выберем стратегию К₂. Ничуть не лучше: противник снова догадаётся и будет прятаться в убежище I. Что же нам делать? Попробуем применять стратегии К₁ и К₂ попеременно, через одну партию игры. Но ведь противник и об этом может догадаться и будет прятаться каждый раз не там, где мы его ищем. Как ни кинь — все клин! Что же, значит, наше положение безвыходно? При любом выборе стратегии нам придется проигрывать? Выходит, что так. Давайте теперь встанем на точку зрения противника. С удивлением мы обнаружим, что его положение — ничуть не лучше нашего! Какую бы стратегию он ни выбрал — все ему невыгодно. Позже мы с вами решим эту игру, т. е. найдем пару оптимальных стратегий К и С. Впрочем, о них можно по секрету сообщить заранее: каждому игроку надо будет чередовать свои стратегии, но не регулярно (через одну), а случайным образом (например, подбросить монету и, если она упадет гербом, искать в убежище I, а если цифрой -в убежище II). Аналогично должен будет действовать и С. При этом в среднем на одну партию будет приходиться нулевой выигрыш («цена этой игры будет равна нулю): К не будет ни выигрывать, ни проигрывать. Не очень приятно, но все-таки много лучше, чем всегда быть в проигрыше! Здесь мы впервые столкнулись с одним из важных понятий теории игр — с понятием смешанной стратегии, т. е. чередования нескольких «чистых» стратегий по случайному закону в определенных пропорциях, или, как говорят, с определенными частотами. В данном примере каждая из стратегий применяется с частотой 1/2. Рассмотрим теперь другую игру, решение которой уже не будет столь очевидным.

Пример 2. Игра «Три пальца». Два игрока К и С одновременно и не сговариваясь показывают друг другу один, два или три пальца. Если всего показанных пальцев (первым и вторым вместе) будет четное число, то выигрывает К: он получает столько очков, сколько всего было пальцев, если нечетное — выигрывает С, на тех же условиях. Требуется записать игру в нормальной форме.
Решение. Перенумеруем стратегии по числу показанных пальцев. Игра 3x3. Матрица игры будет:

Поразмыслим немного над стратегиями каж дой стороны. Станем сначала на сторону К. Предположим, что мы выбрали стратегию К₁. Что будет делать противник? Он разумен и хочет отдать поменьше. Ясно, он выберет стратегию С₂; наш выигрыш при этом будет равен —3, т. е. мы потеряем 3 очка. Плоховато! За пишем число —3 против первой строки в добавочном столбце (см. матрицу 3):

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