Теория игр

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

Приведем несколько примеров конечных игр. Каждую из них мы запишем в нормальной форме. Рассматривается игра, которую назовем "Поиск". В ней участвуют две стороны: К и С. K хочет найти С; С, наоборот, хочет спрятаться от K.

У С есть два места - убежища I и II, где он может прятаться. Выбирает он себе любое убежище. Игрок K по правилам игры тоже может искать С где ему вздумается. Если он нашел С, то С проиграл одно очко, если не нашел, т. е. пошел не в то убежище, где спрятался С, то, наоборот, K проиграл одно очко. Требуется записать игру в нормальной форме.

Решение. У К. - две стратегии: K₁ - искать в убежище I, K₂ - искать в убежище II. У С - тоже две стратегии: С₁- прятаться в убежище I, С₂ - прятаться в убежище II.

Поступим так же со стратегиями "синих", т. е. объединим C₁ и С₂, С₃ и C₄. Получим игру 2 X 2:

Решение этой игры будет:

Ответ к стр. 416.

т. е. "красные" должны одинаково часто применять каждую из своих стратегий (К₁₂- ставить оба отряда на какую-то одну из дорог и K₃ - ставить по одному отряду на каждую дорогу), "синие" - в одной трети всех случаев пользоваться стратегией C₁₂, т. е. посылать все три отряда на одну (любую) из дорог, а в остальных двух третях распределять их по дорогам так: два на одну и один на другую (стратегия Сз4).

Для розыгрыша стратегии можно бросить обычную игральную кость: если выпадет 1, 2, 3 или 4 - применять K₁₂если 5 или 6 - применять K₃ В каждом равенстве, как видите, присутствуют все 10 цифр. Возможны и другие решения.

Решение.

Игра - конечная 2 x 2, матрица игры будет:

К этой игре мы еще вернемся в дальнейшем и найдем ее решение. А пока что просто порассуждаем за игрока K. Представим себе, что мы игрок К, и что нам предлагается выбрать себе стратегию. Что ж, попробуем! Выберем, например, К₁, т. е. будем искать всегда в убежище I. Но тогда разумный противник через несколько партий догадается о нашей стратегии и будет прятаться там, где мы его не ищем, т. е. в убежище II. Плохо! Выберем теперь стратегию K₂.

Ничуть не лучше: противник снова догадается и будет прятаться в убежище I. Что же нам делать? Попробуем применять стратегии К₁и К₂попеременно, через одну партию игры. Но ведь противник и об этом может догадаться и будет прятаться каждый раз не там, где мы его ищем. Как ни кинь - все клин! Что же, значит, наше положение безвыходно? При любом выборе стратегии нам придется проигрывать? Выходит, что так. Давайте теперь встанем на точку зрения противника. С удивлением мы обнаружим, что его положение ничуть не лучше нашего! Какую бы стратегию он ни выбрал - все ему невыгодно.

Позже мы с вами решим эту игру, т. е. найдем пару оптимальных стратегий K и С. Впрочем, о них можно по секрету сообщить заранее: каждому игроку надо будет чередовать свои стратегии, но не регулярно (через одну), а случайным образом (например, подбросить монету и, если она упадет гербом, искать в убежище I, а если цифрой - в убежище II). Аналогично должен будет действовать и С. При этом в среднем на одну партию будет приходиться нулевой выигрыш (цена этой игры будет равна нулю): K не будет ни выигрывать, ни проигрывать. Не очень приятно, но все-таки много лучше, чем всегда быть в проигрыше!

Здесь мы впервые столкнулись с одним из важных понятий теории игр - с понятием смешанной стратегии, т. е. чередования нескольких "чистых" стратегий по случайному закону в определенных пропорциях, или, как говорят, с определенными частотами. В данном примере каждая из стратегий применяется с частотой ¹/₂.

Рассмотрим теперь другую игру, решение которой уже не будет столь очевидным.

Пример 2. Игра "Три пальца".

Два игрока К, к С одновременно и не сговариваясь показывают друг другу один, два или три пальца. Если общее число показанных пальцев (первым и вторым игроками вместе) будет четное, то выигрывает K: он получает столько очков, сколько всего было пальцев, если нечетное - выигрывает С, на тех же условиях. Требуется записать игру в нормальной форме.

Решение. Перенумеруем стратегии по числу показанных пальцев. Игра 3 x 3. Матрица игры будет:

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

Попробуем другую стратегию - К₂. На нее разумный противник ответит С₃. Мы тогда потеряем 5 очков. Еще хуже! Третья стратегия - K₃ - дает точно тот же результат: выигрыш ( - 5). Что же делать? Пожалуй, лучше других будет все-таки стратегия К₁ - при ней мы по крайней мере не проиграем больше 3 очков! Ведь против этой стратегии стоит максимальное число дополнительного столбца - в таблице мы его отметили звездочкой.

Выбрав стратегию К₁, мы гарантируем себе, что, как бы ни вел себя противник, мы никак не проиграем больше 3 очков (т. е. не выиграем меньше (- 3) очков). Величина (- 3) есть максимальный гарантированный выигрыш, который мы ("красные") можем себе обеспечить, применяя только одну-единственную стратегию. Такой стратегией должна быть K₁. Как мы получили ( - 3)? Нашли минимум каждой строки и из этих минимумов взяли максимальный. Эта величина называется максимином или нижней ценой игры. Будем обозначать ее а.

Подумаем теперь за противника. Он тоже хочет отдать поменьше, а получить побольше. Но, какую бы он стратегию ни выбрал, мы ("красные") поведем себя таким образом, чтобы получить с него побольше. Значит, противник ("синие") должен в каждом столбце выписать не минимальное, а максимальное число (см. нижнюю добавочную строку в матрице).

Из этих максимумов он должен найти минимальный (он называется минимаксом или верхней ценой игры); обозначим его бета. Эта величина в нашем случае равна 4 и отмечена звездочкой. Чтобы не проиграть больше 4, "синие" должны придерживаться любой из своих двух стратегий С₁, С₂.

Значит, если каждому участнику предлагается выбрать одну-единственную стратегию, то эти стратегии должны быть K₁ для "красных" и C₁ или С₂для "синих". Как мы выбрали эти стратегии? Руководствуясь принципом осторожности, который говорит: в игре веди себя так, чтобы получить наибольшую выгоду при наихудших для тебя действиях противника. Этот принцип называется принципом минимакса и является в теории игр основным.

Применяя этот принцип, мы пока что рекомендовали игроку К, показывать один палец, игроку С -показывать один или два пальца.

Но нашли ли мы решение игры, т. е. такую пару стратегий, которая является равновесным положением? Легко убедиться, что нет. Найденные нами стратегии обладают досадным свойством: они неустойчивы.

Действительно, пусть оба игрока держатся рекомендованных чистых стратегий: К₁и, скажем, С₁. Пока оба держатся этих стратегий, выигрыш будет равен 2, т. е. на каждую партию игры С проигрывает K два очка. К, может быть, и доволен, но С досадно. Он не хочет проигрывать. Допустим, он откуда-то узнал, что мы придерживаемся стратегии K₁. Что он будет делать? Разумеется, немедленно перейдет к стратегии С₂ и будет получать по 3 очка, т. е. сведет наш выигрыш к -3. А если мы теперь узнаем о поведении С? Перейдем на стратегию K₂. В ответ на это С перейдет на стратегию С₃. И т. д.

Мы убедились, что пара стратегий, вытекающих из принципа минимакса, неустойчива: стоит одному игроку узнать, что делает другой, как равновесие нарушается... Всегда ли это будет так? Оказывается, не всегда.