Детализация поведения игроков во времени — многошаговые игры

Лекция 8 Многошаговые игры В предыдущих лекциях мы рассматривали такие игры, динамика развития которых не оказывала влияния на поведение участников. При этом все возможные стратегии каждого игрока задавались перед началом игры, а процесс игры сводился к независимому выбору каждым игроком одной из своих стратегий. Вместе с тем, во многих практически важных играх, исходя из динамики развития игры и степени информированности участников о ходах противника полезно использовать стратегии, которые могут изменяться в процессе игры. Игры, в которых детализируется поведение игроков во времени называются многошаговыми играми. Частным случаем многошаговых игр являются позиционные игры. Пример позиционной игры и ее развернутая форма (дерево игры) были приведены в первой лекции. Позиционной игрой с полной информацией называется игра, в которой каждый игрок делает очередной ход, зная, какие альтернативы были выбраны на всех предыдущих ходах. Основная особенность игры с полной информацией состоит в том, что ее нормальная форма (матрица выигрышей) имеет хотя бы одну седловую точку. Обобщением позиционных игр с полной информацией являются позиционные игры с полной памятью, в которых каждый из игроков, делая ход, помнит свои предыдущие ходы, но может не знать, какой выбор сделал другой игрок. Если игроками являются отдельные лица, то условие запоминания предыдущего хода, как правило, соблюдается. Но игроком может быть и некая группа людей (например, фирма или воюющая сторона). Такой игрок может попеременно «забывать» или «вспоминать» свои выборы. В этом случае позиционная игра не будет игрой с полной памятью. Мы будем рассматривать многошаговые игры, в которых оба игрока располагают полной информацией. Сама игра рассматривается на некотором заданном наборе интервалов. Отдельный интервал называется шагом игры. Важно отметить, что для решения многошаговых игр можно использовать методы динамического программирования. 55 Вообще говоря, многошаговую игру можно представить в виде набора «игровых элементов» (позиций) или циклов игры Г 1 , Г 2 , , Г k . Общая схема цикла, как правило, включает в себя независимые выборы стратегий. После этого каждый из двух игроков информируется о выборе противника и об исходе игры на данном шаге. На этом цикл заканчивается и действия сторон прекращаются (конец игры) или повторяются (переход к следующему циклу). Из сказанного ясно, что каждый цикл Г k можно представить в виде матрицы размера mk  nk :   1k1  k  Г k   21   k  m1  1k2   1kn    2k2   2kn      mk n    mk 2 . Элементы данной матрицы представляют собой платежи игроку 1, а формируются следующим образом:  ikj  a ik j   p ik jl Г l , l где aik j - платеж игроку 1; pikjl - вероятность перехода в l -ю позицию. Ясно, что все вероятности pik jl  0 и p kl ij  1 (сумма всех вероятностей l переходов на q возможных позиций может быть не равна единице, так как в любой момент игра может закончиться). Таким образом, если в момент времени t игра находится в позиции Г k , а игроки выбирают свои i -ю и j -ю стратегии, то выигрыш игрока 1 равен aik j плюс вероятность перехода в позицию Г l в момент времени t  1 . В зависимости от вида вероятностного распределения P многошаговые игры делятся на 1) детерминированные; 2) стохастические; 3) рекурсивные. 56 Детерминированные игры Простейшей является ситуация, когда игра должна закончиться после фиксированного числа N ходов. В таком случае можно проранжировать позиции в соответствии с максимальным числом оставшихся ходов и, очевидно, что переход возможен в позиции более низкого ранга: pikjl  0 только если ранг Г l ниже ранга Г k . Пример. Пусть игра может продолжаться N шагов, на каждом шаге игроки имеют по две чистые стратегии.  a1k1 Г k   k  a2 1 a1k2   , Г 0  a 20 2 , k  0 ,1, , N . Г k 1  Набор матриц Г k  задает детерминированную игру. Игра начинается с позиции Г N . Игроки выбирают по чистой стратегии i , j  . Если i , j   2 ,2  , то игрок 2 осуществляет платеж игроку 1, равный aiNj , и игра заканчивается. В противном случае, переходим на позицию Г N 1 и все повторяется. Наконец, если игра не закончилась за N  1 шаг, то игроки разыгрывают матричную игру Г 1 :  a111 Г 1   1  a2 1 a112  , a 20 2  после чего игра заканчивается. Общий метод решения детерминированной игры сводится к составлению рекуррентных соотношений для значения цены игры на каждом шаге, начиная с последнего. На основании этих рекуррентных соотношений и граничных условий вычисляются значения цены игры и оптимальные стратегии для каждого шага (от первого до последнего) и, тем самым находится решение всей игры. Пример. Пусть первоначально игроки 1 и 2 имеют запасы по a и b единиц соответственно. Каждый имеет по две чистые стратегии. Если игроки выбирают одинаковые стратегии, то запас игрока 2 уменьшается на единицу, если разные — то игрока 1. Игра заканчивается, когда запас одного из игроков становится 57 равным нулю. Этот игрок получает –1 балл (игрок с ненулевым запасом получит соответственно +1 балл). Обозначим через Г k ,l многошаговую игру, в которой игрок 1 имеет k  1,2 , , a единиц, игрок 2 соответственно имеет l  1,2 , ,b единиц. Такая многошаговая детерминированная игра имеет вид: Г Г k ,l   k ,l 1  Г k 1,l Г k 1,l   1 1 ;   1  1  ; Г k ,0    Г 0 ,l    1  1 . Г k ,l 1  1 1     Рассмотрим первый от конца шаг, то есть когда у обоих игроков осталось по одной единице. В этом случае многошаговая игра превращается в обычную матричную:  1  1 . Г 1,1     1 1  Решим эту игру. Пусть игрок 1 применяет смешанную стратегию x ,1  x  , а игрок 2 смешанную стратегию  y ,1  y  . Тогда 1  1  E  x , y   xy  1  y x  y 1  x   1  y 1  x   4 x   y    0 . 2  2  Следовательно, на этом шаге оптимальные стратегии игроков выглядят так: 1 1 1 1 X 1*,1   ,  , Y1*,1   ,  , 2 2 2 2 V1 ,1  0 - цена игры равна нулю. На втором от конца шаге, когда у игроков в сумме оставалось три единицы, разыгрывается одна из игр: Г Г 1,2   1,1  1 1   1  или Г 2 ,1   Г 1,1   Г 1,1 Г 1,1  . 1  При выборе игроками элемента Г 1,1 они должны играть матричную игру Г 1,1 , решение которой нам уже известно: V1,1  0 . Поэтому вместо игры Г 1,1 мы можем подставить в матрицы Г 1,2 и Г 2 ,1 ее решение: 1 V  1 V1,1   или Г 2 ,1   Г 1,2   1,1 . V1,1 1    1 V1,1  Решая эти матричные игры, получим соответственно их цены V1 ,2 и V2 ,1 . На третьем от конца шаге разыгрывается одна из детерминированных игр: 58 Г Г 1,3   1,2  1 1  Г  ; Г 2 ,2   2 ,1 Г 1 ,2   Г 1 ,2 Г 1 ,2   1  ; Г 3 ,1   Г 2 ,1   Г 2 ,1 Г 2 ,1  , 1  которые могут быть заменены обычными матричными играми: 1 V1,2  V V  1 V2 ,1  Г 1,3   1,2  ; Г 2 ,2   2 ,1  ; Г 3 ,1   . 1    1 V1,2  V1,2 V2 ,1  V2 ,1 Продолжая этот процесс, на N -м шаге от конца (или первом шаге от начала) получим следующую детерминированную игру: Г Г a ,b   a ,b 1  Г a 1,b Г a 1,b  , Г a ,b 1  которая заменяется матричной игрой Va 1,b  V Г a ,b   a ,b 1  . Va 1,b Va ,b 1  Решим ее: 1  1 1  E  x , y   2Va 1,b  Va ,b 1  x   y    Va 1,b  Va ,b 1  , 2  2 2  откуда видно, что оптимальные стратегии равны  * 1 1  X a , b    2 , 2  ,     Y * a , b    1 , 1  ,  2 2 а цена игры может быть найдена с помощью следующего рекуррентного соотношения: Vab  1 Va 1,b  Va ,b1  . 2 Стохастические игры q Эти игры характеризуются условием P l 1 kl ij  1 , которое означает, что на каждом шаге существует положительная вероятность остановки. Вследствие этого выигрыш всегда имеет конечное математическое ожидание. Пример. Два игрока играют в соответствии со следующей матрицей: 59  1 1  . A   1  1 Они имеют общий капитал в десять единиц и договорились остановиться, как только один из них выиграет все. После каждого хода они бросают монету. Если выпадает орел, игра прекращается, даже если ни один из игроков не выиграл весь капитал. Запишем формальную матрицу такой стохастической игры. Пусть Г k 1  k  9  - позиция, в которой находятся игроки, когда игрок 1 имеет k единиц. Тогда можно записать: 1    1  Г k 1 2 Гk   1  1  Г k 1  2 1  Г k 1  2 . 1  1  Г k 1  2  1 Если игроки выбирают одинаковые стратегии, игрок 1 теряет одну единицу, после чего игра с вероятностью 1 2 переходит на позицию Г k 1 , а с вероятностью 1 2 - заканчивается. Если игроки выбирают разные стратегии, то игрок 1 получает одну единицу, после чего игра с вероятностью 1 2 переходит на позицию Г k 1 , а с вероятностью 1 2 - заканчивается. Рекурсивные игры Рекурсивные игры отличаются от стохастических тем, что вероятность окончания игры на любом фиксированном шаге может быть равна нулю. Таким образом, в зависимости от выбранной стратегии существует положительная вероятность того, что партия будет продолжаться бесконечно. Поэтому выигрыш a  определяется и для случая бесконечной партии (выигрыш выживания). Пример. Военный отряд окружен в крепости. Командир может вывести отряд по двум дорогам: на запад и на восток. Каждую ночь можно попытаться уйти по одной из этих дорог. Противник может устроить засаду на одной из них. 60 Если отряд попытается уйти по охраняемой дороге, то он попадает в плен (-1 балл). Если оказывается, что противник охраняет другую дорогу, то попытка выйти оказывается успешной (+1 балл). Если отряд остается на ночь в крепости – игра повторяется. Игру можно представить в рекурсивном виде:   1  1 Г    1  1  . Г Г   Для таких игр, очевидно, необходимо знать a  (выигрыш в бесконечной партии), чтобы определить оптимальные стратегии. Если a  0 (то есть если можно чего-то достичь, оставаясь в крепости), то командир должен выбрать третью строку. Если же a  0 , то третью строку необходимо вычеркнуть. Для оставшейся матрицы нам известен ответ: необходимо выбирать первую и вторую строки с вероятностью 1 2 . 61