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

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.

Таким образом, получили приближённое решение игры: x²⁰ =(1/10, 1/2, 2/5), y²⁰ =(2/5, 3/5, 0), n=1,57.

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

1. Этот метод даёт возможность найти ориентировочное значение цены игры и приближённо вычислить оптимальные стратегии игроков.

2. Сложность и объём вычислений сравнительно слабо возрастают по мере увеличения числа стратегий игроков (m и n).

Для рассмотренного алгоритма приведена реализация на языке Pascal (см. приложение).

§3. Монотонный итеративный алгоритм решения матричных игр

Предлагаемый для рассмотрения алгоритм реализуется только для одного игрока в отличие от первого, который работает для двух игроков. Алгоритм позволяет находить точно и приближенно оптимальную стратегию игрока 1 и значение цены игры n. С помощью алгоритма можно получить заданную точность решения, причём число шагов, необходимых для достижения результатов, слабо зависит от размерности матрицы выигрышей.

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

Рассмотрим смешанное расширение =(X,Y,K) матричной игры Г_А с матрицей А размера (m´n). Процесс разыгрывания игры состоит из нескольких шагов. Пусть каждый из игроков имеет конечное число стратегий.