10. РЕШЕНИЕ КОНЕЧНЫХ ИГР МЕТОДОМ ИТЕРАЦИЙ

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

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

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

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

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

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

Продемонстрируем применение итерационного метода на примере игры «три пальца», решенной нами точно в предыдущем параграфе. Тот факт, что мы знаем решение игры и ее цену поможет нам оценить точность метода итераций.

Пример. Решить методом итераций игру с матрицей

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

- минимальный накопленный выигрыш, деленный на число - партий

— максимальный накопленный выигрыш, деленный на число партий

- их среднее арифметическое (помещено в таблице между

Величина v может служить (лучше чем v и v) приближенным значением цены игры.

Таблица 10.1

(см. скан)

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

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

Они оказались довольно близкими к известным нам из решения игры вероятностям:

Аналогично для игрока В находим частоты стратегий в первых 30 партиях:

Это уже сильнее отличается от решения игры, согласно которому:

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

то наш выигрыш (его проигрыш) будет не больше 5,10 (последняя строка в табл. 10.1), что лишь немного отличается от цены игры 5,0. Заметим, что, ставя практическую игровую задачу, мы обычно делаем упрощения и допущения, которые делают излишней погоню за большой точностью решения, так что ориентировочное решение игры, получаемое методом итераций (даже при небольшом числе «партий»), часто может оказаться достаточным.

Сделаем по поводу табл. 10.1 еще одно замечание. В ней встречаются строки (например, восьмая, двенадцатая, двадцатая и т. д.), где все три значения выигрышей подчеркнуты; это означает, что достигнуто «положение равновесия», при котором любое поведение противника дает нам один и тот же выигрыш, а именно, цеиу игры V. Обратим внимание на то, что для этих строк действительно величина v достигает точно значения v. По таким признакам можно находить приближенное значение цены игры: если в каких-то последовательных столбцах при всех стратегиях противной стороны обеспечивается приблизительно один и тот же выигрыш, это означает, что он может быть принят за приближенное значение цены игры. Знание приближенного значения цены игры важно для того, чтобы во время остановить процесс итераций.

Как же найти практически оптимальные стратегии после того, как процесс итераций прекращен? Вернемся к табл. 10.1 и рассмотрим в ней столбец V. Найдем в этом столбце максимальный элемент. В нашем случае это оказался (случайно равный цене игры, но, приступая к итерациям, мы ведь ее не знаем!). Из этого мы заключаем, что, применяя смешанную стратегию, соответствующую этой строке, мы обеспечиваем себе выигрыш, не меньший 5. Подсчитаем частоты стратегий для 20-й строки. Стратегия применялась нами 5 раз из 20, стратегия А в — тоже 5 раз, стратегия раз, откуда берем вероятности стратегий:

что, как и следовало ожидать, совпадает (в данном случае точно, а не приближенно) с оптимальной стратегией игрока А в решении игры. Сделаем то же для игрока В. Рассмотрим столбец v и найдем в нем минимальное число vmln. Это будет 5,04, достигаемое, например, в 29-й строке. Это значит, что если игрок В будет применять смешанную стратегию, соответствующую всему «прошлому» для этой строки: то он может гарантировать, что проиграет не больше чем 5,04. Это лучше, чем значение 5,10, достигаемое v в самой последней строке.

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