Игра в нормальной форме. Матрица игры

      Мы будем рассматривать только конечные игры, т. е. такие, в которых каждый участник располагает конечным числом стратегий.       Если у игрока К имеется в распоряжении m стратегий, а у игрока С имеется n стратегий игра называется игрой m X n.       Правила игры можно записать в виде таблицы

		Стратегии «синих»
		C1	C2	...	Cm
Стратегии «красных»	K1 K2 . Km	K11 K21 . Km1	K12 K22 . Km2	... ... ... ...	K1n K2n . Kmn

(или матрицы), в которой m строк и n столбцов. Строки соответствуют стратегиям «красных», которые мы обозначим:K₁, K₂, ..., K_m, а столбцы — стратегиям «синих»: C₁, C₂, ..., C_n.       В клетках таблицы помещены выигрыши (или средние выигрыши) «красных» при соответствующей паре стратегий. Например, k₁₂ — выигрыш, который получат «красные», если вы берут стратегию K₁, а «синие» — С₂; вообще, k_ij — выигрыш «красных» при комбинации стратегии K_i и C_j.       Такая таблица называется платежной матрицей или просто матрицей игры.       Если конечная игра записана в виде такой матрицы, то говорят, что она приведена к нормальной форме. Но попробуйте, например, записать и нормальной форме обыкновенные шахматы! Вы сразу столкнетесь с тем, что количество возможныx стратегий необозримо велико — настолько велико, что их перечисление выходит за пределы возможностей не только человека, но и современной вы числительной машины. А жаль! Потому что, если бы построение матрицы шахматной игры было возможно, это имело бы очень любопытные последствия... Но не будем забегать вперед.

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

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

	C1	C2
К1	1	-1
К2	-1	1

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

	C1	C2	C3
К1	2	-3	4
К2	-3	4	-5
К3	4	-5	6

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

	C1	C2	C3	Минимумы строк
К1	2	-3	4	-3*
К2	-3	4	-5	-5
К3	4	-5	6	-5
Максимумы столбцов	4*	4*	6

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