приблеженный метод решения игры

§ 6. ПРИБЛИЖЕННЫЕ МЕТОДЫ РЕШЕНИЯ ИГР

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

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

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

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

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

Проиллюстрируем применение итерационного метода на примере игры , решенной в примере 2 предыдущего параграфа.

Игра задана матрицей:

Таблица 6.1

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

приведены: минимальный средний выигрыш  равный минимальному накопленному выигрышу, деленному на число игр  максимальный средний выигрыш  равный максимальному накопленному выигрышу, деленному на , и их среднее арифметическое  При увеличении  все три величины v, v и v будут приближаться к цене игры  но величина V. естественно, будет приближаться к ней сравнительно быстрее.

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

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