2i.SU
Математика

Математика

Содержание раздела

Теория игр

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

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

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

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

  С1 С2 С3 C4
К1,2 50% 50% 75% 75%
К3 100% 100% 50% 50%

Поступим так же со стратегиями "синих", т. е. объединим C1 и С2, С3 и C4. Получим игру 2 X 2:

  С1,2 С3,4
К1,2 50% 75%
К3,4 100% 50%

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

3450-1.jpg

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

3450-2.jpg

т. е. "красные" должны одинаково часто применять каждую из своих стратегий 12- ставить оба отряда на какую-то одну из дорог и K3 - ставить по одному отряду на каждую дорогу), "синие" - в одной трети всех случаев пользоваться стратегией C12, т. е. посылать все три отряда на одну (любую) из дорог, а в остальных двух третях распределять их по дорогам так: два на одну и один на другую (стратегия Сз4).

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

Решение.

3450-3.jpg

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

  С1 С2
K1 1 -1
K2 -1 1

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

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

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

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

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

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

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

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

  C1 С2 С3
К1 2
-3
4
K2 -3 4 -5
K3 4 -5 6

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

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

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

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

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

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

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

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

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

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

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

перейти к началу страницы


2i.SU ©® 2015 Яндекс.Метрика Рейтинг@Mail.ruРейтинг@Mail.ru