XX Волков И.К., Загоруйко Е.А. Исследование операций (1081437), страница 44
Текст из файла (страница 44)
Существуют два основных способа описания и анализа любой конкретной игры. Первый способ предполагает следующее: 1) перечисление ходов, которые могут делать игроки; 2) определение информации, которой располагают игроки в процессе игры; 3) определение возможных вариантов действий игроков; 4) указание предельных размеров платежей в конце игры. Игру, описанную подобным образом, называют игрой в развернутпой, или энстпенсивнои, форме, а само описание, как правило, составляют в виде дерева игры, аналогичного дереву решений. Игры в развернутой форме называют также нозииионнылси игралси.
Пример 8.1. На рис. 8.1 изображено дерево игры для упрощенного варианта игры двух лиц в покер (карточная игра). В этой игре ставка каждого из игроков равна 5 денежным 11 П1 1м' у в п 5 ° . р О П Б ° В и с,м~ ~ — и — и Р О П вЂ” 1 т В [М,и> ~ — и — -1ΠР— О ~ П 1 В с рммр ~ и — о Р О Рис. 8.1 единицам. После сдачи карт на руках у игроков остается определенное количество карт. Набор карт может быть либо „старшим", который мы обозначим через С, либо „младшим", который мы обозначим через М. У первого игрока имеются две возможности: либо раскрыть карты 1Р), либо повысить игру (В).
При раскрытых картах старший набор карт выигрывает банк, если же карты у игроков равны, то банк делится пополам. Если первый игрок повышает игру, то он вкладывает в банк еще 5 денежных единиц. После этого у второго игрока имеются две альтернативы: либо пасовать (П), либо уравнивать (У). Если он пасует, то первый игрок выиграет банк при любых картах. Если же второй игрок уравнивает игру, то вносит в банк еще 5 денежных единиц, после чего либо старшие карты выиграют банк, либо при равных каргах банк делится пополам. На дереве игры (см.
рис. 8.1) изображены все возможные ситуации игры и указаны соответствующие им платежи. Римскими цифрами обозначены стадии игры; 1 — первый случайный ход, обозначающий определение ставок и сдачу карт; П вЂ” сложившаяся после сдачи карт ситуация: С обозначает старшую карту, а М вЂ” младшую, первая буква обозначает 8.2. Игры двух участников с нулевой суммой 318 318 и элементы теОРии иГР карту первого игрока, а вторая — второго. Например, (С,М) обозначает старшую карту у первого игрока и младшую — у второго; П1 — второй ход в игре, в котором решение за первым игроком: раскрыть карты (Р) или повысить ставки (В); 1Ч вЂ” третий ход в игре, в котором решение принимает второй игрок.
Он может пасовать (П) или уравнять игру (У); У вЂ” завершение партии, когда подводятся ее итоги. Прн этом положительное значение обозначает выигрыш первого игрока (и проигрыш второго), а отрицательное значение— выигрыш второго игрока (и проигрыш первого). й1 Игру в развернутой форме называют игрой с полной информацией, если в ней нельзя делать одновременно несколько ходов и если участникам известны выборы, сделанные при предшествующих ходах, включая и случайные ходы. Примером игры с полной информацией являются шахматы, Покер представляет собой игру с неполной информацией, так как игрокам неизвестно, какие карты находятся на руках у противника.
Второй способ описания игры предполагает рассмотрение всех возможных стратегий каждого игрока и определение платежей, соответствующих любым возможным комбинациям стратегий всех игроков. Игру, описанную вторым способом, обычно называют игрой в нормальной форме. Естественно, зная развернутую форму игры, всегда можно представить ее в нормальной форме. Нормальная форма игры двух участников состоит из двух плапяежных мапяриц, содержащих суммы выигрышей и проигрышей каждого из игроков для любой из возможных пар стратегий.
Обычно эти две матрицы объединяются в одну, как это изображено на рис. 8.2. Если первый игрок располагает множеством стратегий (Х1); „а второй игрок — множеством стратегий (Х2)" „то на пересечении 1-й строки и 1ъго столбца объединенной платежной матрицы находится пара чисел х; Х2 Х1 (П11 Пы) (П12 П2 ) (П П ) (П21з П21) (П22~ П22) (Паве П2н) Х' (П'„П„',) (П'„П',) ...
(П „,П'„) Рис. В.2 (П1;, П2 ), представляющих собой выигрыши первого и второго игроков при выборе ими стратегий Х1 и Х2 соответственно. Единая платежная матрица состоит из т строк и и столбцов, где т — число стратегий первого игрока, а п — второго (имеется в виду конечная игра).
Считается, что каждому из игроков известны все элементы единой платежной матрицы игры. 8.2. Игры двух участников с нулевой суммой Игры двух участников с нулевой суммой представляют собой наиболее разработанный раздел теории игр. Если игра двух участников с нулевой суммой представлена в нормальной форме, то для всех 1= 1, т и 1= 1, п где П; и П; — выигрыши первого и второго игроков при вы- 1 2 боре ими стратегий Х1 и Х2 соответственно. При этом первый игрок располагает т стратегиями, а второй — п стратегиями. Поэтому в данном случае вместо единой платежной матрицы используют платежную матрицу первого игрока (рис. 8.3), в которой 8.2. Игры двух участников с нулевой суммой 321 320 8.
ЭЛЕМЕНТЫ ТЕОРИИ ИГР Х2 Пг Пго хг Пгг Х2 х,' и Хг Пгг П22 Х~, П„,1 Пнг ° ° ° П Рис. 8.3 Пример 8.2. Первый и второй игроки одновременно и независимо друг от друга показывают один, два или три пальца. Выигрыш или проигрыш (в денежных единицах) равен общему количеству показанных пальцев. Если это количество четное, то выиграет первый игрок, а второй ему платит. Если же оно нечетное, то выиграет второй игрок, а первый ему платит.
Требуется построить платежную матрицу. В рассмотренном случае у каждого игрока имеется по три стратегии: показать один, два или три пальца. Если стратегия Х~ Й-го игрока заключается в том, чтобы показать и пальцев, и = 1, 2, а = 1, 3, то платежную матрицу можно записать следующим образом: 2 -3 4 (П)= — 3 4 — 5 й 4 — 5 6 Как мы уже знаем, в задачав иринлпгил решений выбор критер1 я оптимальности в значительной степени предопределяется информацией, которой располагает „лицо, принимающее решения". Игры двух лиц с нулевой суммой в определенном смысле представляют собой предельный случай полного отсутствия информации, когда противники находятся в состоянии конфликта. Именно поэтому в играх двух лиц с нулевой суммой в нормальной форме, называемых также ллатричными игралхи, как правило, используют наиболее и пессимистическийи миниллаксный (лхаксиминный) критаерий, рассмотренный выше при анализе задач принятия решений в условиях неопределенности.
Но ситуация в играх принципиально отличается от ситуации в задачах принятия решений в условиях неопределенности, в которых „природа" не рассматривалась нами как активный или недоброжелательный противник. В нашем случае каждый игрок действует разумно и пытается активно помешать противнику.
Поэтому попытаемся уяснить для себя обоснованность использования минимаксного (максиминного) критерия в играх двух лиц с нулевой суммой. Сначала предположим, что мы выступаем на стороне первого игрока. Мы располагаем стратегиями Х,1, ю' = 1, т, и делаем первый ход. Если мы выбираем стратегию Х, то второй игрок, являющийся разумным противником, будет стараться минимизировать наш выигрыш из множества возможных выигрышей П;, г' = 1, и, выбирая одну из стратегий Хг, г = 1, и.
Таким образом, величина П;, = пппП;,. 1 представляет наш гарантированный наименьший выигрыш при выборе стратегии Х; безотносительно к решениям второго 1 игрока. Естественно, что из всех возможных стратегий Х,! мы выбираем ту, которая максимизирует наш гарантированный наименьший выигрыш, равный П. = шахПсх = п1ахпп)пП; . г ' ' 1 Величину П. называют кизккей ценой игры, а соответствующую ей стратегию Х,1, — лвакеиминной стратегией. Очевидно, что если мы будем придерживаться максиминной стратегии, то при любых действиях противника нам гарантирован выигрыш П, который, во всяком случае, не меньше П.. Поэтому величину П, и называют нижней ценой игры.
Естественно, что аналогичные рассуждения можно провести и за второго игрока, который является нашим противником. Он заинтересован в минимизации нашего выигрыша, и, 8.2. Игры двух участников с нулевой суммой 323 322 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР как следствие, для каждой своей стратегии Х , 1' Хя '=1 и он должен сначала определить наш максимально возможный выигрыш: П'=шахП;, 1'=1,п, 1 а затем минимизировать зти максимально возможные выигрыши путем выбора соответствующей стратегии. Величину П' = пип П' = пип шах ПИ 1 П имер 8.3. Система противовоздушной обороны (ПВО) риме обороняет от воздушного налета участок территории, располагая двумя зенитно-ракетными комплексами (ЗРК), зоны действия которых не перекрываются (рис.
8.4). Каждый ЗРК с единичной вероятностью поражает самолет противника в зоне своего действия, если его система наведения начинает отслеживать цель и вырабатывать данные для стрельбы еще за пределами зоны. Противник располагает двумя самолетами, каждый из которых может быть направлен в зону действия любого ЗР Цель 2 Ф ,'! л Цель 1 ЗРК 2 ЗРК 1 Рис. 8.4 называют версией ценой верех, а соответствующую ей стратегию Хз- — мамтьмамсиой супратпееией. Придерживаясь *1 минимаксной стратегии, противник имеет гарантии, что в любом случае проиграет (а первый игрок выиграет) не больше чем П'. В момент, когда система ПВО решает задачу целераспределения, т.е. решает, какому ЗРК по какой цели стрелять, самолеты противника могут применить обманный маневр (см.
рис. 8.4) и изменить маршрут. Цель системы ПВΠ— поразить как можно больше самолетов противника, а цель противника — потерять как можно меньше самолетов. В рассматриваемом случае мы имеем игру двух лиц с нулевой суммой. В распоряжении первого игрока (система ПВО) имеются четыре стратегии: Х,' — система наведения каждого ЗРК отслеживает цель, направляющуюся в его зону, т.е. й-му ЗРК назначена й-я цель, й = 1, 2; Х~1 — система наведения первого ЗРК отслеживает вторую цель, а система наведения второго ЗРК отслеживает первую цель; Х' — системы наведения обоих ЗРК отслеживают первую цель; Хд — системы наведения обоих ЗРК отслеживают вторую цель.
У второго игрока (противника) также имеются четыре стратегии: Х~ — оба самолета не меняют своего курса, т.е. и-й самолет следует в зону действия й-го ЗРК, й = 1, 2; Хзз — оба самолета применяют обманный маневр и меняют курс, т.е. первый самолет следует в зону действия второго ЗРК, а второй самолет следует в зону действия первого ЗРК; Хзз — первый самолет применяет обманный маневр, а второй нет, т.е. оба самолета следуют в зону действия второго ЗРК; Хд — второй самолет применяет обманный маневр, а первый нет, т.е. оба самолета следуют в зону действия первого ЗРК.
325 8.2. Игры двух участников с нулевой суммой 8. ЭЛЕМЕНТЫ ТЕОРИИ ИГР Составим платежную матрицу: 2 О 1 1 О 2 1 1 (11И) = 1 1 1 1 определим верхнюю и нижнюю цены р иг ы а также минимаксную и максиминную стратегии игроков. Для первого игрока имеем П,.=П~=О; Пз, = Пз1 = О; Пз =Пз =1, 1=1,4; П4„= П41 = 1, у = 1, 4. Нижняя цена игры равна П, = 1, а первый игрок располагает Х' Х'. двумя максиминными стратегиями Хз, 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
