Таблица 2. Выбранные игроками стратегии и их выигрыши при них на первых двух шагах. 

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

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

   Таблица 3. Выбранные игроками стратегии и их выигрыши при них на 20 шагах.

   

   

   Из  таблицы видно, что в 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.

   Таким образом, получили приближённое решение  игры: (4.11), (4.12), n=1,57.

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

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

 

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

 

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

   

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

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

   Введём  следующие обозначения:

   аi – i-я строка матрицы выигрышей;

   xN=(x1N,x2N,…,xmN)(5.3) ÎX – m-мерный вектор,  приближение оптимальной стратеги первого игрока на N-шаге (N-номер шага);

   cN=( )(5.4) –n-мерный вектор, определяющий средний накопленный выигрыш на N-шаге. 

   Зададим начальные условия. Пусть на 0-шаге с0= , x0=(0,…, 1,…, 0)(5.6), где 1 занимает i0-ю позицию.

   Определим итеративный процесс  следующим образом: по известным векторам xN-1, cN-1   находим векторы   xN и cN , которые вычисляются по следующим формулам:

(5.7)

    где параметр 0£eN£1, а векторы     вводятся далее.

         Как отмечалось, вектор сN определяет средний накопленный выигрыш игрока 1 на N шаге. Компоненты этого вектора – это числа. В худшем случае игрок 1 может получить минимальное из этих чисел. Примем его за нижнюю оценку цену игры, которую обозначим:

   

. (5.8)

     Запомним  множество  индексов J^N-1=( ), (k<n), на которых    
 
 

будет достигается этот минимум, т. е.

.(5.9)

   Далее рассмотрим подыгру  ГN игры   ГА с матрицей выигрышей АN={ }(5.10), i=1,…,m, jN-1ÎJN-1. Матрица выигрышей состоит из столбцов данной матрицы, номера которых определяются множеством индексов JN-1. В этой подыгре ГN находим одну из оптимальных смешанных стратегий игрока 1:  (5.11).

После нахождения , находим вектор (5.12) по правилу:

(5.13).

   И рассмотрим игру (2´n), в которой у игрока 1 две чистые стратегии, а у игрока 2 – n чистых стратегий. Эта игра задаётся матрицей (5.14), решая которую, находим вероятность использования игроком 1 своей стратегии. Это даёт нам коэффициент eN.

   Далее вычисляем xN, сN и переходим к следующему шагу. Процесс продолжаем до тех  пор, пока не выполнится равенство eN=0, потому что по теореме о минимаксе , а их равенство (что и нужно) достигается в этом случае, или пока не будет достигнута требуемая точность вычислений.  

   Пример. Решить  игру с матрицей А= (5.15).

   Итерация 0. 1. Пусть игрок 1 выбрал свою 1-ю стратегию, т. е. А0 = [0, 1, 2]. Тогда за начальные условия примем следующие: x0 = (1, 0, 0) – приближение оптимальной стратегии игрока 1; c0=a1=(0, 1, 2) – возможный выигрыш игрока 1.

   Найдём  множество индексов , на которых игрок 1 может получить, в худшем случае, наименьший выигрыш: , значит множество индексов J0={1}. Для этого индекса выигрыш равен 0. Это есть значение нижней оценки цены игры, т. е. .

   На  этом шаге определим, пользуясь начальными значениями, компоненты векторов . Для этого рассмотрим подыгру (5.16). Для этой подыгры оптимальной стратегией игрока 1 будет его 2-ая стратегия, так как она принесёт ему наибольший выигрыш.

   Обозначим её через  :  =(0, 1, 0)(5.17). Зная  , можем вычислить =0а1+1а2+0а3=а2=(4, 2, 1)(5.18).

   Найдём e1. Для этого рассмотрим подыгру (2´3) с матрицей (5.19).  Решая матрицу графическим способом, получаем, что e1=1/2.

   Проведённые вычисления позволяют найти значения векторов x1, c1:

   x1=1/2x0+1/2 =1/2(1, 0, 0)+1/2(0, 1, 0)=(1/2, 1/2, 0);(5.20)

   c1=1/2c0+1/2 =1/2(0, 1, 2)+1/2(4, 2, 1)=(2, 3/2, 3/2).(5.21)

   

   Итерация1. Так как e1 не равно 0, то процесс продолжается дальше. Теперь за начальные условия примем найденные значения векторов x1, c1. С их помощью вычисляем , которые с большей точностью будут близки к истинным оптимальным стратегиям игрока 1.

   Итак, пусть x1=(1/2, 1/2, 0),  c1=(2, 3/2, 3/2)(5.22).

     Найдём множество индексов  , на которых игрок 1 может получить наименьший выигрыш: , значит, J1={2,3}. Для этих индексов выигрыш равен 3/2. Это есть значение нижней оценки цены игры, т. е. . Заметим, что .

   Далее найдём компоненты векторов . Для этого рассмотрим подыгру (5.23). В силу симметричности матрицы ее решением будет вектор (1/2, 1/2), т. е. 1/2a1+1/2a2+0a3=

   =(4/2, 3/2, 3/2).(5.24)

   Вычислим  коэффициент e2. Для этого решим подыгру (2´3): (5.25). Стратегии игроков совпадают, поэтому e2=0. В этом случае цена игры совпадает со своим нижним значением, т. е. .  Возвращаемся к предыдущему шагу.

   Итак, оптимальной стратегией игрока 1 является x*=x1=(1/2, 1/2, 0) и  .Задача решена.

   На  первый взгляд алгоритм практически  трудно реализовать, так как не известно, какого размера будет получена матрица для подыгры ГN. Но на самом деле с вероятностью 1 на каждом шаге придётся решать подыгру размера не больше чем m´2.[9]

   

         Инженерами-программистами алгоритм был реализован на языке  программирования Фортран-IV. Вычислительные эксперименты, проведённые на ЭЦВМ ЕС-1030, показали,  что для игр размерности от 25´25 до 100´100, элементы, матрицы выигрышей которых были заполнены случайными числами, алгоритм позволяет найти искомое приближение за 100-1000 итераций, причём их число слабо зависит от размера матрицы. Для решения одной задачи машина затрачивает не дольше 8 минут. Ими же были разработаны различные модификации алгоритма. [9]

 

  6. Конструкторская часть

6.1 Разработка архитектуры программной системы

 

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

   Для реализации "такой-то программы" была выбрана среда программирования Nokia QT версии 4.5.0 фирмы Nokia, так как она предоставляет наиболее широкие возможности для программирования приложений для различных платформ.

   

   С++ – это язык для быстрого создания приложений. Высокопроизводительный инструмент визуального построения приложений включает в себя настоящий компилятор кода и предоставляет средства визуального программирования, несколько похожие на те, что можно обнаружить в Microsoft Visual Basic или в других инструментах визуального проектирования. В QT также входят локальные библиотеки для работы с базами данных, библиотеки визуальных компонентов, и прочее хозяйство, необходимое для того, чтобы чувствовать себя совершенно уверенным при профессиональной разработке информационных систем или просто кросплатформеных приложений.

   Прежде  всего, QT c++ предназначен для профессиональных разработчиков, желающих очень быстро разрабатывать. QT cодержит большой набор компонентов и классов, поэтому в QT должны быть прежде всего заинтересованы те, кто разрабатывает продукты на продажу. С другой стороны небольшие по размерам и быстро исполняемые модули означают, что требования к клиентским рабочим местам существенно снижаются – это имеет немаловажное значение и для конечных пользователей.