§ 27. Методы решения конечных игр

Перед тем, как решать игру нужно, прежде всего, попытаться ее упростить, избавившись от лишних стратегий. Это делается подобно тому, как мы когда-то отбрасывали заведомо невыгодные решения в § 6. Введем понятие «доминирования». Стратегия игрока А называется доминирующей над стратегией если в строке стоят выигрыши не меньшие, чем в соответствующих клетках строки и из них по крайней мере один действительно больше, чем в соответствующей клетке строки Если все выигрыши строки равны соответствующим выигрышам строки то стратегия называется дублирующей стратегию

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

Поясним сказанное примером. Пусть игра 5х5 задана матрицей таблицы 27.1.

Таблица 27.1

Прежде всего заметим, что в ней стратегия дублирует стратегию А 2, поэтому любую из них можно отбросить. Отбрасывая замечаем, что в строке все выигрыши больше (или равны) соответствующим выигрышам строки значит доминирует над Отбросим и получим матрицу 3х5 (таблица 27.2).

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

Таблица 27.2

Отбрасывая столбцы получаем игру 3х2 (таблица 27.3).

Наконец, в таблице 27.3 строка дублирует А и поэтому ее можно отбросить. Окончательно получим игру 2х2 (таблица 27.4).

Таблица 27.3

Таблица 27.4

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

В руководствах по теории игр обычно останавливаются на решении простейших игр , которое допускает геометрическую интерпретацию, но мы этого делать не будем — сразу возьмем «быка за рога» и покажем, как можно решить любую игру

Пусть имеется игра без седловой точки с матрицей (см. таблицу 27.5).

Таблица 27.5

Допустим, что все выигрыши положительны (этого всегда можно добиться, прибавляя ко всем членам матрицы достаточно большое число от этого цена игры увеличится на М, а решение SA, SB не изменится).

Если все положительны, то конечно, и цена игры, т. е. средний выигрыш при оптимальной стратегии, тоже положителен:

Мы хотим найти решение игры, т. е. две оптимальные смешанные стратегии

дающие каждой стороне максимально возможный для нее средний выигрыш (минимальный проигрыш).

Найдем сначала SA. Мы знаем, что если один из игроков (в данном случае это А) применяет свою оптимальную стратегию, то другой (В) не может улучшить свое цоложение, отступая от своей. Заставим противника (В) отступать от своей оптимальной стратегии, пользуясь чистыми стратегиями (а мы тем временем упорно держимся стратегии SA). В любом случае наш выигрыш будет не меньше, чем и:

Разделим неравенства (27.2) на положительную величину v и введем обозначения:

Тогда условия 127.2) примут вид

где — неотрицательные переменные. В силу (27.3) и того, что , переменные удовлетворяют условию

Но v есть не что иное, как наш гарантированный выигрыш; естественно, мы хотим сделать его максимальным, а значит, величину - минимальной.

Таким образом, задача решения игры свелась к математической задаче: найти неотрицательные значения переменных такие, - чтобы они удовлетворяли линейным ограничениям-неравенствам (27.4) и обращали в минимум линейную функцию этих переменных:

— скажет читатель, — что-то знакомое!» И точно — перед нами не что иное, как задача линейного программирования. Таким образом, задача решения игры свелась к задаче линейного программирования с ограничениями-неравенствами и переменными. Зная можно по формулам (27.3) найти и, значит, оптимальную стратегию и нцену игры .

Оптимальная стратегия игрока В находится совершенно аналогично, с той разницей, что В стремится минизировать, а не максимизировать выигрыш, а значит, 1 ооратить не в минимум, а в максимум величину—, а в ограничениях-неравенствах вместо знаков будут стоять Пара задач линейного программирования, по которой находятся оптимальные стратегии называется парой двойственных задач линейного программирования (доказано, что максимум линейной функции в одной из них равен минимуму линейной функции в другой, так что все в порядке — разных значений цены игры мы не получим).

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

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

Впрочем, лучше всего можно понять итерационный метод на конкретном примере. Продемонстрируем его на примере игры 3х3 предыдущего параграфа (таблица 26.5). Чтобы не иметь дела с отрицательными числами, прибавим к элементам матрицы таблицы 26.5 лисло 5 (см. таблицу 27.6); при этом цена игры увеличится на 5, а решение не изменится.

Начнем с произвольно выбранной стратегии игрока А, — например, со стратегии . В таблице 27.7 приведены первые 15 шагов итерационного процесса по методу Брауна — Робинсон (читатель может самостоятельно продолжить расчеты).

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

Таблица 27.6

Таблица 27.7

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

Как видно, величина v незначительно колеблется около цены игры (цена исходной игры была 0, но мы прибавили к элементам матрицы по 5). Подсчитаем по таблице 27.7 частоты стратегий игроков. Получим:

что не так уж сильно отличается от вероятностей равных, как мы указывали раньше, для первой, второй и третьей стратегий соответственно Такие сравнительно хорошие приближения мы получили уже при 15 итерациях — это обнадеживает! К сожалению, дальше процесс приближений будет идти не так резво. Сходимость метода Брауна — Робинсон, как показывает опыт, очень медленная, Существуют способы, позволяющий как бы «подхлестнуть» еле плетущийся процесс, но мы на них останавливаться не будем.

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

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

Скажем несколько критических слов по поводу этой теории и ее практической значимости. В свое время, когда теория игр еще только появилась, на нее возлагались большие надежды в смысле выбора решений для конфликтных ситуаций. Эти надежды оправдались лишь в малой степени.

Прежде всего, на практике не так уж часто встречаются строго антагонистические конфликты — разве только в настоящих «играх» (шашки, шахматы, карты и т. п.). Вне этих искусственных ситуаций, где одна сторона стремится во что бы то ни стало обратить выигрыш в максимум, а другая - в минимум, такие конфликты почти не встречаются. Казалось бы, где, как не в области боевых действий должна была бы с успехом применяться теория игр? Ведь здесь мы встречаемся с самыми «свирепыми» антагонизмами, с самой резкой противоположностью интересов! Но оказывается, что конфликтные ситуации в этой области сравнительно редко удается свести к парным играм с нулевой суммой. Схема строгого антагонизма применима, как правило, только к операциям малого масштаба, ограниченным по значению. Например, сторона А — группа самолетов, налетающих на объект, сторона В — средства противовоздушной обороны объекта; первая стремится максимизировать вероятность уничтожения объекта, вторая — ее минимизировать. Здесь схема парной игры с нулевой суммой может найти применение. Но возьмем чуть более сложный пример: две группировки боевых единиц (типа танков, самолетов, кораблей) ведут бой. Каждая сторона стремится поразить как можно больше боевых единиц противника. В этом примере антагонизм ситуации теряет свою чистоту: она уже не сводится к парной игре с нулевой суммой. Если цели участников конфликта не прямо противоположны, а просто не совпадают, математическая модель становится много сложнее: мы уже не можем интересоваться выигрышем только одной стороны; возникает так называемая «биматричная игра», где каждый из участников стремится максимизировать свой выигрыш, а не просто минимизировать выигрыш противника. Теория таких игр гораздо сложнее, чем теория антагонистических игр, а главное, из этой теории не удается получить четких рекомендаций по оптимальному образу действий сторон [26].

Второе критическое замечание будет касаться понятия «смешанных стратегий». Если речь идет о многократно повторяемой ситуации, в которой каждая сторона может легко (без дополнительных затрат) варьировать свое поведение от случая к случаю, оптимальные смешанные стратегии в самом деле могут повысить средний выигрыш. Но бывают ситуации, когда решение надо принять одно-единственное (например, выбрать план строительства системы оборонительных сооружений). Разумно ли будет «передоверить свой выбор случаю», - грубо говоря, бросить монету, и если выпал герб, выбрать первый вариант плана, а если решка — второй? Вряд ли найдется такой руководитель, который в сложной и ответственной ситуации решится делать выбор случайным образом, хотя бы это и вытекало из принципов теории игр!

Наконец, последнее соображение: в теории игр считается, что каждому игроку известны все возможные стратегии противника, неизвестно лишь то, какой именно из них он воспользуется в данной партии игры. В реальном конфликте это обычно не так: перечень возможных стратегий противника как раз неизвестен, и наилучшим решением в конфликтной ситуации нередко будет именно выйти за пределы известных противнику стратегий, «ошарашить» его чем-то совершенно новым, непредвиденным!

Как видно из вышеизложенного, теория игр в качестве основы для выбора решения (даже в остроконфликтной ситуации) имеет много слабых мест. Значит ли это, что ее не нужно изучать, что она вовсе не нужна в исследовании операций? Нет, не значит. Теория игр ценна прежде всего самой постановкой задач, которая учит, выбирая решение в конфликтной ситуации, не забывать о том, что противник тоже мыслит, и учитывать его возможные хитрости и уловки. Пусть рекомендации, вытекающие из игрового подхода, не всегда определенны и не всегда осуществимы — все же полезно, выбирая решение, ориентироваться, в числе других, и на игровую модель. Не надо только выводы, вытекающие из этой модели, считать окончательными и непререкаемыми.