Методы приближённого решения матричных игр (стр. 3 из 4)
Таким образом, продолжая этот процесс далее, составим таблицу разыгрываний игры за 20 итераций (партий).
| но-мерпартии | Страте-гиявторогоигрока | выигрыш игрока 1 при его стратегиях | Страте-гияпервогоигрока | проигрыш игрока 2при его стратегиях | u | w | n | ||||
| 1 | 2 | 3 | 1 | 2 | 3 | ||||||
| 1234567891011121314151617181920 | 1 2 2 2 3 3 1 3 3 3 3 3 2 2 2 2 2 2 2 3 | 036910111112131415161922252831343738 | 45679111517192123252627272930313234 | 2222581013161922252525252525252528 | 2 2 1 1 1 1 2 2 2 2 2 2 2 2 2 2 1 1 1 1 | 4888881216202428323640444848484848 | 125811141516171819202122232427303336 | 2456781012141618202224262829303132 | 45/26/39/410/511/615/717/819/921/1023/1125/1226/1327/1427/1529/1631/1734/1837/1938/20 | 12/25/36/47/58/610/712/814/916/1018/1120/1221/1322/1423/1524/1627/1730/1831/1932/20 | 5/27/211/615/817/1019/1225/1427/1633/1837/2041/2245/2447/2649/2850/3053/3258/3464/3668/3870/40 |
Из таблицы видно, что в 20-ти проигранных партиях стратегии 1, 2, 3 для второго игрока встречаются соответственно 2, 10, 8 раз, следовательно, их относительные частоты равны 2/20, 10/20, 8/20. Стратегии 1, 2, 3 для игрока 1 встречаются соответственно 8, 12, 0 раз, следовательно, их относительные частоты равны 8/20, 12/20, 0, а приближённое значение цены игры равно 70/40.
Таким образом, получили приближённое решение игры: x20=(1/10, 1/2, 2/5), y20=(2/5, 3/5, 0), n=1,57.
Такой итеративный процесс ведёт игроков к цели медленно. Часто для получения оптимальных стратегий, дающих игрокам выигрыш, приходится проделывать сотни итераций. При этом скорость сходимости заметно ухудшается с ростом размерности матрицы и ростом числа стратегий игроков. Это также является следствием не монотонности последовательностей
и 
. Поэтому, практическая ценность этого метода имеет место, когда вычисления проводятся на достаточно быстродействующих вычислительных машинах. Но наряду с таким недостатком можно выделить и достоинства метода итераций:1. Этот метод даёт возможность найти ориентировочное значение цены игры и приближённо вычислить оптимальные стратегии игроков.
2. Сложность и объём вычислений сравнительно слабо возрастают по мере увеличения числа стратегий игроков (m и n).
Для рассмотренного алгоритма приведена реализация на языке Pascal (см. приложение).
§3. Монотонный итеративный алгоритм решения матричных игр
Предлагаемый для рассмотрения алгоритм реализуется только для одного игрока в отличие от первого, который работает для двух игроков. Алгоритм позволяет находить точно и приближенно оптимальную стратегию игрока 1 и значение цены игры n. С помощью алгоритма можно получить заданную точность решения, причём число шагов, необходимых для достижения результатов, слабо зависит от размерности матрицы выигрышей.
Особенность этого алгоритма в способности генерировать строго монотонно возрастающую последовательность оценок цены игры, что не свойственно ранее предлагаемому алгоритму.
Рассмотрим смешанное расширение
=(X,Y,K) матричной игры ГА с матрицей А размера (m´n). Процесс разыгрывания игры состоит из нескольких шагов. Пусть каждый из игроков имеет конечное число стратегий.Введём следующие обозначения:
аi – i-я строка матрицы выигрышей;
xN=(x1N,x2N,…,xmN) ÎX – m-мерный вектор, приближение оптимальной стратеги первого игрока на N-шаге (N-номер шага);
cN=(
) –n-мерный вектор, определяющий средний накопленный выигрыш на N-шаге.Зададим начальные условия. Пусть на 0-шаге с0=
, x0=(0,…, 1,…, 0), где 1 занимает i0-ю позицию.Определим итеративный процесс следующим образом: по известным векторам xN-1, cN-1 находим векторы xNи cN, которые вычисляются по следующим формулам:
где параметр 0£eN£1, а векторы 
вводятся далее.Как отмечалось, вектор сN определяет средний накопленный выигрыш игрока 1 на N шаге. Компоненты этого вектора – это числа. В худшем случае игрок 1 может получить минимальное из этих чисел. Примем его за нижнюю оценку цену игры, которую обозначим:
. (4)Запомним множество индексов JN-1=(
), (k<n), на которых будет достигается этот минимум, т. е. 
.Далее рассмотрим подыгру ГN игрыГА с матрицей выигрышей АN={
}, i=1,…,m, jN-1ÎJN-1. Матрица выигрышей состоит из столбцов данной матрицы, номера которых определяются множеством индексов JN-1. В этой подыгре ГN находим одну из оптимальных смешанных стратегий игрока 1: 
.После нахождения
, находим вектор 
по правилу: 
.И рассмотрим игру (2´n), в которой у игрока 1 две чистые стратегии, а у игрока 2 – n чистых стратегий. Эта игра задаётся матрицей
, решая которую, находим вероятность использования игроком 1 своей стратегии. Это даёт нам коэффициент eN.Далее вычисляем xN, сN и переходим к следующему шагу. Процесс продолжаем до тех пор, пока не выполнится равенство eN=0, потому что по теореме о минимаксе
, а их равенство (что и нужно) достигается в этом случае, или пока не будет достигнута требуемая точность вычислений.Сходимость алгоритма гарантируется теоремой.
Теорема. Пусть {xN}, {nN} – последовательности, определяемые равенствами (3), (4) . Тогда справедливы следующие утверждения:
1. 
т. е. последовательность {nN-1} строго монотонно возрастает.
2. 
3. 
, где x*ÎX* – оптимальная стратегия игрока 1.
Доказательства этой теоремы достаточно рутинно. Его можно посмотреть в [15].
Рассмотрим применение этого алгоритма к решению конкретной задачи.
Пример.Решить игру с матрицей А= 
.
Итерация 0. 1. Пусть игрок 1 выбрал свою 1-ю стратегию, т. е. А0=[0, 1, 2]. Тогда за начальные условия примем следующие: x0=(1, 0, 0) – приближение оптимальной стратегии игрока 1; c0=a1=(0, 1, 2) – возможный выигрыш игрока 1.
Найдём множество индексов
, на которых игрок 1 может получить, в худшем случае, наименьший выигрыш: 
, значит множество индексов J0={1}. Для этого индекса выигрыш равен 0. Это есть значение нижней оценки цены игры, т. е. 
.2. На этом шаге определим, пользуясь начальными значениями, компоненты векторов
. Для этого рассмотрим подыгру 
. Для этой подыгры оптимальной стратегией игрока 1 будет его 2-ая стратегия, так как она принесёт ему наибольший выигрыш.Обозначим её через
: =(0, 1, 0). Зная , можем вычислить 
=0а1+1а2+0а3=а2=(4, 2, 1).3. Найдём e1. Для этого рассмотрим подыгру (2´3) с матрицей
. Решая матрицу графическим способом, получаем, что e1=1/2.4. Проведённые вычисления позволяют найти значения векторов x1, c1:
x1=1/2x0+1/2
=1/2(1, 0, 0)+1/2(0, 1, 0)=(1/2, 1/2, 0);c1=1/2c0+1/2 =1/2(0, 1, 2)+1/2(4, 2, 1)=(2, 3/2, 3/2).