Антагонистические матричные игры

Самым простым случаем, подробно разработанным в теории игр, является конечная парная игра с нулевой суммой (антагонистическая игра двух лиц или двух коалиций). Рассмотрим такую игру G, в которой участвуют два игрока А и В, имеющие противоположные интересы: выигрыш одного равен проигрышу другого. Так как выигрыш игрока А равен выигрышу игрока В с обратным знаком, мы можем интересоваться только выигрышем а игрока А. Естественно, А хочет максимизировать, а В — минимизировать а. Для простоты отождествим себя мысленно с одним из игроков (пусть это будет А) и будем его называть «мы», а игрока В — «противник». Пусть у нас имеется т возможных стратегий А₁, A₂.,.., А_т, а у противника — п возможных стратегий В₁, В₂,..., В_п (такая игра называется игрой m × п). Обозначим a_ij наш выигрыш в случае, если мы пользуемся стратегией A_i„ а противник — стратегией B_j.

Таблица 1

Предположим, что для каждой пары стратегий A_i, B_j выигрыш a_ij нам известен. Тогда в принципе можно составить прямоугольную таблицу (матрицу), в которой перечислены стратегии игроков и соответствующие выигрыши (см. таблицу 1).

Если такая таблица составлена, то говорят, что игра G приведена к матричной форме. Заметим, что если игра приведена к матричной форме, то многоходовая игра фактически сведена к одноходовой — от игрока требуется сделать только один ход: выбрать стратегию. Будем кратко обозначать матрицу игры (a_ij).

Рассмотрим пример игры G (4X5) в матричной форме. В нашем распоряжении (на выбор) четыре стратегии, у противника — пять стратегий. Матрица игры дана в таблице 2.

Давайте, поразмышляем о том, какой стратегией нам (игроку А) воспользоваться? В матрице 2 есть соблазнительный выигрыш «10»; нас так и тянет выбрать стратегию А3, при которой этот «лакомый кусок» нам достанется. Но постойте: противник тоже не дурак! Если мы выберем стратегию А₃, он, назло нам, выберет стратегию В₃, и мы получим какой-то жалкий выигрыш «1». Нет, выбирать стратегию А₃ нельзя! Как же быть?

Оптимальная стратегия – максиминный и минимаксный подходы

		B1	B2	B3	B4	B5
	А1
	А2
	А3
	А 4

Таблица 2

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

Перепишем таблицу 2 и в правом добавочном столбце запишем минимальное значение выигрыша в каждой строке (минимум строки); обозначим его для j-й строки а, (см. таблицу 3).

Таблица 3

		B1	B2	B3	B4	B5	αi
	А1
	А2
	А3
	А 4
	bj

Из всех значений αi (правый столбец) выделено наибольшее (3). Ему соответствует стратегия А_4. Выбрав эту стратегию, мы во всяком случае можем быть уверены, что (при любом поведении противника) выиграем не меньше, чем 3. Эта величина — наш гарантированный выигрыш; ведя себя осторожно, меньше этого мы получить не можем (а, может быть, получим и больше). Этот выигрыш называется нижней ценой игры (или «максимином» — максимальный из минимальных выигрышей). Будем обозначать его α. В нашем случае α = 3.

Теперь станем на точку зрения противника и по­рассуждаем за него. Он ведь не пешка какая-нибудь, а тоже разумен! Выбирая стратегию, он хотел бы отдать поменьше, но должен рассчитывать на наше, наихудшее для него, поведение. Если он выберет стратегию В₁, мы ему ответим А₃, и он отдаст 10; если выберет В₂ — мы ему ответим А₂, и он отдаст 8 и т. д. Припишем к таблице 3 добавочную нижнюю строку и в ней запишем максимумы столбцов bj. Очевидно, осторожный противник должен выбрать ту стратегию, при которой эта величина минимальна (соответствующее значение 5 выделено в таблице 3). Эта величина b — то значение выигрыша, больше которого заведомо не отдаст нам разумный противник. Она называется верхней ценой игры (или «минимаксом» — минимальный из максимальных выигрышей). В нашем примере b = 5 и достигается при стратегии противника B₃ .

Итак, исходя из принципа осторожности (перестра­ховочного правила «всегда рассчитывай на худшее!»), мы должны выбрать стратегию А₄, а противник — стратегию В₃. Такие стратегии называются «минимаксными» (вытекающими из принципа минимакса). До тех пор, пока обе стороны в нашем примере будут придерживаться своих минимаксных стратегий, выигрыш будет равен а₄₃ = 3.

Теперь представим себе на минуту, что мы узнали о том, что противник придерживается стратегии В₃. А ну-ка, накажем его за это и выберем стратегию А₁ — мы получим 5, а это не так уж плохо. Но ведь противник — тоже не промах; пусть он узнал, что наша стратегия А₁ он тоже поторопится выбрать В₄, сведя наш выигрыш к 2, и т. д. (партнеры «заметались по стратегиям»). Одним словом, минимаксные стратегии в нашем примере неустойчивы по отношению к информации о поведении другой стороны; эти стратегии не обладают свойством равновесия.

Всегда ли это так? Нет, не всегда. Рассмотрим пример с матрицей, данной в таблице 4.

В этом примере нижняя цена игры равна верхней:
α= b = 6. Что из этого вытекает? Минимаксные стратегии игроков А и В будут устойчивыми. Пока оба игрока их придерживаются, выигрыш равен 6. Посмотрим, что будет, если мы (А) узнаем, что противник (В) держится стратегии В₂?

Таблица 4

		B1	B2	B3	B4	αi
	А1
	А2
	А3
	bj

А ровно ничего не изменится. Потому что любое отступление от стратегии А₂ может только ухудшить наше положение. Равным образом, информация, полученная противником, не заставит его отступить от своей стратегии В₂. Пара стратегий А₂, В₂ обладает свойством равновесия (уравновешенная пара стратегий), а выигрыш (в нашем случае 6), достигаемый при этой паре стратегий, называется «седловой точкой матрицы»). Термин «седловая точка» взят из геометрии — так называется точка на поверхности, где одновременно достигается минимум по одной координате и максимум по другой.

Признак наличия седловой точки и; уравновешенной пары стратегий — это равенство нижней и верхней цены игры; общее значение α и b называется ценой игры. Мы будем обозначать его v:

α= b = v. (1)

Стратегии А₂, В₂, при которых этот выигрыш достигается, называются оптимальными чистыми стратегиями, а их совокупность — решением игры. Про саму игру в этом случае говорят, что она решается в чистых стратегиях. Обеим сторонам А и В можно указать их оптимальные стратегии, при которых их положение — наилучшее из возможных. А что игрок А при этом выигрывает 6, а игрок В — проигрывает 6,— что же, таковы условия игры: они выгодны для А и невыгодны для В.

Может возникнуть вопрос: а почему оптимальные стратегии называются «чистыми»? Несколько забегая вперед, ответим на этот вопрос: бывают стратегии «смешанные», состоящие в том, что игрок применяет не одну какую-то стратегию, а несколько, перемежая их случайным образом. Так вот, если допустить кроме чистых еще и смешанные стратегии, всякая конечная игра имеет решение — точку равновесия. Но об этом речь еще впереди.

Наличие седловой точки в игре — это далеко не правило, скорее — исключение. Большинство игр не имеет седловой точки. Впрочем, есть разновидность игр, которые всегда имеют седловую точку и, значит, решаются в чистых стратегиях. Это — так называемые «игры с полной информацией». Игрой с полной информацией называется такая игра, в которой каждый игрок при каждом личном ходе знает всю предысторию ее развития, т. е. результаты всех предыдущих ходов, как личных, так и случайных. Примерами игр с полной информацией могут служить: шашки, шахматы, «крестики и нолики» и т. п.

В теории игр доказывается, что каждая игра с полной информацией имеет седловую точку, и значит, решается в чистых стратегиях. В каждой игре с полной информацией существует пара оптимальных стратегий, дающая устойчивый выигрыш, равный цене игры v. Если такая игра состоит только из личных ходов, то при применении каждым игроком своей оптимальной стратегии она должна кончаться вполне определенным образом — выигрышем, равным цене игры. А значит, если решение игры известно, самая игра теряет смысл!

Возьмем элементарный пример игры с полной ин­формацией: два игрока попеременно кладут пятаки на круглый стол, выбирая произвольно положение центра монеты (взаимное перекрытие монет не разрешается). Выигрывает тот, кто положит последний пятак (когда места для других уже не останется). Легко убедиться, что исход этой игры, в сущности, предрешен. Есть определенная стратегия, обеспечивающая выигрыш тому из игроков, кто кладет монету первым. А именно, он должен первый раз положить пятак в центре стола, а затем на каждый ход противника отвечать симметричным ходом. Очевидно, как бы ни вел себя противник, ему не избежать проигрыша. Точно так же обстоит дело и с шахматами и вообще играми с полной информацией: любая из них, записанная в матричной форме, имеет седловую точку, и значит, решение в чистых стратегиях, а следовательно, имеет смысл только до тех пор, пока это решение не найдено. Скажем, шахмат­ная игра либо всегда кончается выигрышем белых, либо всегда — выигрышем черных, либо всегда — ничьей, только чем именно — мы пока не знаем (к счастью для любителей шахмат). Прибавим еще: вряд ли будем знать и в обозримом будущем, ибо число стратегий так огромно, что крайне трудно (если не невозможно) привести игру к матричной форме и найти в ней седловую точку.

А теперь спросим себя, как быть, если игра не имеет седловой точки: α не равно b. Ну что же, если каждый игрок вынужден выбрать одну-единственную чистую стратегию, то делать нечего: надо руководствоваться принципом минимакса. Другое дело, если можно свои стратегии «смешивать», чередовать случайным образом с какими-то вероятностями. Применение смешанных стратегий мыслится таким образом: игра повторяется много раз; перед каждой партией игры, когда игроку предоставляется личный ход, он «передоверяет» свой выбор случайности, «бросает жребий», и берет ту стратегию, которая выпала.

Смешанные стратегии в теории игр представляют собой модель изменчивой, гибкой тактики, когда ни один из игроков не знает, как поведет себя противник в данной партии. Такая тактика (правда, обычно безо всяких математических обоснований) часто применяется в карточных играх. Заметим при этом, что лучший способ скрыть от противника свое поведение — это придать ему случайный характер и, значит, самому не знать заранее, как ты поступишь.

Дата добавления: 2014-01-03