Быстрый поиск

Дипломная работа: Методы приближённого решения матричных игр

. (2)

Отсюда получаем оценку разности пределов:

Из леммы следует, что

На основании неравенства (1) имеем: .

Следовательно, в силу ограниченности пределов

Получаем оценку для разности пределов:

для "e>0.

Можем заключить, что . Осталось показать равенство пределов n. Это следует из неравенства (2).

Итак, .

Пример. Найти приближённое решение игры с матрицей

А=.

Пусть игру начнёт игрок 2. Он произвольно выбирает одну из своих чистых стратегий. Предположим, что он выбрал свою 1-ю стратегию, а игрок 1 отвечает своей 2-й стратегией. Занесём данные в таблицу.

но-мер

пар

тии

стратегия

второго

игрока

выигрыш игрока 1 при его стратегиях

стратегия

первого

игрока

проигрыш игрока 2

при его стратегиях

5/2

В столбце u находится наибольший средний выигрыш 4 игрока 1, полученный им в первой партии; в столбце w стоит наименьший средний проигрыш 1, полученный игроком 2 в первой партии; в столбце n находится среднее арифметическое n=(u+w)/2=5/2, т. е. приближенное значение цены игры, полученное в результате проигрывания одной партии.

Так как игрок 1 выбрал 2-ю стратегию, то игрок 2 может проиграть:

4, если применит свою 1-ю стратегию;

1, если применит свою 2-ю стратегию;

2, если применит свою 3-ю стратегию.

Поскольку он желает проиграть как можно меньше, то в ответ применит свою 2-ю стратегию.

Тогда первый игрок получит выигрыш равный 3, 1, 0 соответственно при своих 1-й, 2-й, 3-й стратегиях, а его суммарный выигрыш за две партии составит:

0+3=3 при его 1-й стратегии;

4+1=5 при его 2-й стратегии;

2+0=2 при его 3-й стратегии.

Из всех суммарных выигрышей наибольшим является 5, который получается при 2-й стратегии игрока 1. Значит, в этой партии он должен выбрать именно эту стратегию.

При 1-й стратегии игрока 1 игрок 2 проигрывает 4, 1, 2 соответственно 1-й, 2-й, 3-й его стратегиям, а суммарный проигрыш за обе партии составит:

4+4=8 при его 1-й стратегии;

1+1=2 при его 2-й стратегии;

2+2=4 при его 3-й стратегии.

Все полученные данные занесём в таблицу. В столбец u ставится наибольший суммарный выигрыш игрока 1 за две партии, деленный на число партий, т. е. 5/2; в столбец w ставится наименьший суммарный проигрыш игрока 2, деленный на число партий, т. е. 2/2; в столбец n ставится среднее арифметическое этих значений, т. е. 7/2.

но-мер

пар

тии

стратегия

второго

игрока

выигрыш игрока 1 при его стратегиях

стратегия

первого

игрока

проигрыш игрока 2

при его стратегиях

5/2

2/2

5/2

7/2

В третьей партии игрок 2 выбирает свою 2-ю стратегию, так как из всех суммарных проигрышей наименьшим является 2.

Таким образом, продолжая этот процесс далее, составим таблицу разыгрываний игры за 20 итераций (партий).

но-мер

пар

тии

Страте-

гия

второго

игрока

выигрыш игрока 1 при его стратегиях

Страте-

гия

первого

игрока

проигрыш игрока 2

при его стратегиях

5/2

6/3

9/4

10/5

11/6

15/7

17/8

19/9

21/10

23/11

25/12

26/13

27/14

27/15

29/16

31/17

34/18

37/19

38/20

2/2

5/3

6/4

7/5

8/6

10/7

12/8

14/9

16/10

18/11

20/12

21/13

22/14

23/15

24/16

27/17

30/18

31/19

32/20

5/2

7/2

11/6

15/8

17/10

19/12

25/14

27/16

33/18

37/20

41/22

45/24

47/26

49/28

50/30

53/32

58/34

64/36

68/38

70/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, потому что по теореме о минимаксе , а их равенство (что и нужно) достигается в этом случае, или пока не будет достигнута требуемая точность вычислений.