8. ИГРЫ 2xn И mx2

Мы убедились, что любая игра может быть решена элементарными приемами. Совершенно аналогично может быть решена любая игра , где у нас (А) имеются всего две стратегии, а у противника (В) — произвольное число (n).

Итак, пусть имеется матрица игры : она состоит из двух строк и столбцов. Аналогично случаю 2X2 дадим задаче геометрическую интерпретацию; стратегий противника изобразятся прямыми (рис. 9.10). Построим нижнюю границу выигрыша (ломаную ) и найдем на ней точку N с максимальной ординатой; эта ордината и будет ценой игры V, а абсцисса точки N будет равна вероятности стратегии в оптимальной смешанной стратегии игрока А:

Зная, какие стратегии пересекаются в точке N, можно указать активные стратегии противника. В нашем случае (рис. 9.10) оптимальная смешанная стратегия противника

состоит из смеси двух активных стратегий пересекающихся в точке N. Стратегия является заведомо невыгодной, а стратегия — невыгодной при оптимальной стратегии Вероятности относятся как длины отрезков КВЛ и на рис. 9.10.

Если А будет пользоваться своей оптимальной стратегией то выигрыш не изменится, какой бы из своих активных стратегий ни пользовался В. однако он изменится, если В перейдет к стратегиям или

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

Из этого, в частности, следует, что у игры всегда имеется решение, в котором с каждой стороны участвует не более двух активных стратегий. Стоит только найти эти стратегии — и игра превращается в игру 2x2, которая решается элементарно.

Рис. 9.10

Отсюда вытекает такой практический прием решения игры : строится геометрическая интерпретация (рис. 9.10), ищется пара стратегий, пересекающихся в точке N (если в ней пересекается более двух стратегий, берется любая пара) — эти стратегии представляют собой активные стратегии игрока В, и игра сведена к игре 2x2.

Очевидно, так же может быть решена и игра , с той разницей, что строится не нижняя, а верхняя граница выигрыша, и на ней ищется не максимум, а минимум (рис. 9.11).

Пример 1. Игра «самолеты и зенитные орудия».

Сторона А (самолеты) нападает на объект, сторона В (зенитные орудия) обороняет его. У стороны А два самолета, у стороны В — три зенитных орудия. Каждый самолет является носителем мощного поражающего средства: для поражения объекта достаточно, чтобы к нему прорвался хотя бы один самолет. Самолеты могут выбирать для подхода к объекту любое из трех направлений: l, 11 или Ш, не меняя его в дальнейшем (рис. 9.12). Противник (В) может разместить любое из своих орудий на любом направлении; каждое из орудий простреливает только область пространства, относящуюся к данному направлению, и не простреливает соседних направлений. Каждое орудие может обстрелять только один самолет; обстрелянный самолет поражается с полной достоверностью. Сторона А не знает, где размещены орудия; сторона В не знает, откуда прилетят самолеты. Задача стороны А — поразить объект, стороны В — не допустить поражения. Найти решение игры.

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

Однако можно ограничиться гораздо меньшим числом стратегий, если заранее их «смешать» и рассмотреть для А только две стратегии:

— послать по одному самолету на два разных (любых направления;

— послать оба самолета по одному (любому) направлению, а для противника — три стратегии:

— поставить по одному орудию на каждое направление;

— поставить два орудия на одно (любое) направление, одно — на другое, а третье оставить незащищенным;

— поставить все три орудия на одно (любое) направление, а два других оставить незащищенными.

Рис. 9.11

Рис. 9.12

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

Составим матрицу игры. Выигрыш А в данном случае — вероятность поражения объекта, иначе — вероятность того, что к объекту прорвется хотя бы один самолет.

Рассмотрим выигрыши для всех комбинаций стратегий.

— самолеты летят по разным направлениям, орудия расставлены по одному Выигрыш — вероятность того, что хотя бы один самолет прорвется к объекту — в данном случае равен нулю:

— самолеты летят по одному и тому же направлению, орудия расставлены по одному Очевидно, при этом один из самолетов, не будучи обстрелянным, наверняка прорвется к объекту:

— самолеты летят по одному; противник ставит два орудия на одно направление, одно — на другое и оставляет незащищенным третье ). Для того чтобы прорваться к объекту, хотя бы один из самолетов должен выбрать незащищенное направление. Вероятность этого события найдем через вероятность противоположного события: «оба самолета выберут защищенное направление».

Вероятность этого события равна откуда вероятность интере сующего нас события: .

4. — самолеты летят вместе; орудия поставлены по схеме Снова найдем вероятность того, что оба самолета будут поражены. Для этого они должны выбрать направление, защищенное двумя орудиями; вероятность этого , вероятность противоположного события:

5. — самолеты летят порознь, орудия поставлены все три на одно направление Очевидно, в этом случае оба самолета сбиты не могут быть, и .

6. — самолеты летят вместе, орудия поставлены все три на одно направление Для того чтобы оба самолета были поражены, они должны выбрать то направление, на котором стоят все три орудия. Вероятность этого 1/3. Вероятность того, что хотя бы один самолет прорвется к объекту, будет

Составляем матрицу игры:

Из матрицы видно, что нижняя цена игры равна верхней: значит, игра имеет седловую точку и решается в чистых стратегиях: сторона А (самолеты) должна всегда пользоваться стратегией (лететь вместе), а сторона В должна всегда расставлять орудия по схеме т. е. ставить два орудия на одно какое-то направление, одно орудие — на другое, и одно направление оставлять вообще незащищенным.

На рис. 9.13 дана геометрическая интерпретация игры.

Пример 2 (вариант той же игры). Условия те же, но для стороны А возможны не три, а четыре направления подхода к объекту, а сторона В располагает четырьмя орудиями.

Решение. У нас по-прежнему две возможные стратегии:

— посылать самолеты порознь,

— посылать самолеты вместе.

У противника пять возможных стратегий: — ставить по одному орудию на каждое направление;

— ставить два орудия на одно направление, по одному — на два других и одно оставить незащищенным; — ставить по два орудия на два направления, а два оставить незащищенными;

— ставить три орудия на одно направление, одно — на другое, и два оставить незащищенными;

— ставить все четыре орудия на одно направление, а остальные три оставить незащищенными.

Стратегии можно заранее отбросить как заведомо невыгодные. Действительно, если по одному направлению летят не более чем два самолета и каждый из них поражается с вероятностью единица одним орудием — ставить на одно направление более двух орудий излишне. Рассуждая, как в предыдущем примере, построим матрицу игры.

Рис. 9,13

Рис. 9.14

Эта игра 2x3 не имеет седловой точки (). Ищем решение в смешанных стратегиях. Выделяем активные стратегии противника: это (рис. 9.14). После этого игра сводится к игре 2x2:

Решая эту игру, находим оптимальные стратегии сторон:

Таким образом, можно сформулировать следующие рекомендации сторонам А и В: сторона А должна с вероятностью посылать самолеты порознь, а с вероятностью 5/8 — вместе; сторона В должна с вероятностью применять расстановку орудий , а с вероятностью 3/4 — расстановку При этом выигрыш — вероятность поражения объекта — равен что больше нижней цены игры и меньше верхней.

Пример 3. Игра «распределение сил в наступлении и обороне».

Сторона А, располагающая тремя батальонами пехоты, стремится захватить некоторый объект В; сторона В, располагающая четырьмя батальонами пехоты, стремится воспрепятствовать этому. Каждый из наступающих батальонов может быть направлен к объекту по любой из двух дорог: I и II (рис. 9.15).

Рис. 9.15

Сторона В также может расположить любой из своих батальонов на любой из дорог. Если на дороге силы стороны В встречаются с превосходящими силами стороны А, последние оттесняют оборону, проходят к объекту и занимают его; если же на дороге оборона численно превышает нападение, атака отбивается, силы стороны А отходят и больше не возобновляют нападение. Если на дороге встречаются силы одинаковой численности, сторона А с вероятностью 0,4 побеждает и проходит к объекту, а с вероятностью 0,6 атака оказывается отбитой.

Требуется дать рекомендации сторонам по количеству батальонов, которое следует направить на каждую из дорог.

Решение. Выигрыш А в данном случае — вероятность занятия объекта. Рассмотрим следующие стратегии нападения (А):

) — направить два батальона по одной из дорог (любой) и один — по другой;

— направить все три батальона по одной из дорог (любой).

Стратегии обороны (В) будут:

— направить по два батальона на каждую из дорог;

— направить три батальона на одну из дорог (любую), а один — на другую;

— направить все четыре батальона на одну из дорог (любую а другую дорогу оставить незащищенной).

Составим матрицу игры. Найдем выигрыш для всех комбинаций стратегий.

1. На одной дороге встречаются один батальон нападения с двумя батальонами обороны; атака на этой дороге отбивается. На другой дороге встречаются два батальона нападения с двумя обороны; согласно условию нападение побеждает с вероятностью

2. АВ. При этом на одной из дорог с полной достоверностью будет перевес сил нападения, и

3. . Так как выбор любой дороги для каждой стороны равновероятен, то с вероятностью 1/2, на одной дороге встретятся два батальона А с тремя В, на другой — один батальон А с одним В; на первой дороге атака будет отбита, на другой — произойдет занятие объекта с вероятностью 0,4. С той же вероятностью 1/2 встретятся на одной дороге один батальон А с тремя В, на другой — два батальона А с одним В, и объект будет занят с полной достоверностью. Применяя формулу полной вероятности, находим:

4. . С вероятностью 1/2 на одной дороге встретятся три батальона А с тремя В, на другой — столкновения не будет; в этом случае вероятность занятия объекта 0,4. С той же вероятностью 1/2 три батальона А встретятся только с одним батальоном В, пройдут и займут объект. По формуле полной вероятности:

5. Так как силы А идут по двум дорогам, а силы В расположены только на одной из дорог, сторона А с достоверностью займет объект: .

6. . С вероятностью 1/2 силы А пойдут по той дороге, где нет обороны, и займут объект; с вероятностью 1/2 они будут отбиты превосходящими силами обороны; отсюда

Матрица игры имеет вид:

Нижняя цена игры верхняя цена игры игра не Имеет седловой точки. Ищем решение в смешанных стратегиях. Геометрическая интерпретация игры дана на рис. 9.16. Нижняя граница выигрыша достигает максимума в точках на всем участке между ними; этот максимум есть цена игры В данном случае решение игры получилось неоднозначным: сторона А может применить любую из своих смешанных стратегий, соответствующих точкам оси абсцисс от К до

Таким образом, у стороны А существует несчетное множество оптимальных стратегий. Найдем абсциссы точек . Они будут равны соответственно — границам, в которых заключена вероятность стратегии в оптимальной смешанной стратегии игрока А. Из чертежа имеем:

откуда Аналогично получаем

откуда

Итак, в качестве оптимальной смешанной стратегии сторона А может применять любую в которой вероятности лежат: первая — между 0,4 и 0,5; вторая соответственно между 0,6 и 0,5.

Разумеется, крайние значения тоже дают оптимальные стратегии игрока А:

Рис. 9.16

Таким образом, оптимальная стратегия игрока А найдена: она состоит в том, чтобы с вероятностью, принимающей любое значение между 0,4 и 0,5, направлять два батальона по одной из дорог (любой), а оставшийся батальон — по другой дороге; во всех же остальных случаях посылать все три батальона по одной из дорог (любой).

Что касается оптимальной стратегии противника (В), то, как видно из рис. 9.16, она сводится к применению одной единственной чистой стратегии, а именно

т. е. обороняющийся всегда должен выставлять три батальона на одну дорогу (любую), а один батальон — на другую дорогу. Цена игры, т. е. устойчивый выигрыш стороны А при этом будет равен верхней цене игры 0,7