Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

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

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

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

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

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

 x^N=(x₁^N,x₂^N,…,x_m^N) ÎX – m-мерный вектор, приближение оптимальной стратеги первого игрока на N-шаге (N-номер шага);

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

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

Определим итеративный процесс следующим образом: по известным векторам x^{N -1} , c^{N -1}  находим векторы x^N и c^N , которые вычисляются по следующим формулам:

 

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

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

                                             .              (4)

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

.

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

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

.

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

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

Сходимость алгоритма гарантируется теоремой.

Теорема. Пусть  { x^N }, { n ^N } – последовательности, определяемые равенствами (3), (4) . Тогда справедливы следующие утверждения:

1.  т. е. последовательность { n ^{N -1} } строго монотонно возрастает.

2.

3. , где x ^* Î X * – оптимальная стратегия игрока 1.

Доказательства этой теоремы достаточно рутинно. Его можно посмотреть в [15].

Рассмотрим применение этого алгоритма к решению конкретной задачи.

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

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

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

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

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

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

    4. Проведённые вычисления позволяют найти значения векторов x ¹ , c ¹:

x ¹=1/2 x ⁰ +1/2 =1/2(1, 0, 0)+1/2(0, 1, 0)=(1/2, 1/2, 0);

c ¹ =1/2 c ⁰ +1/2 =1/2(0, 1, 2)+1/2(4, 2, 1)=(2, 3/2, 3/2).

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

1. Итак, пусть x ¹ =(1/2, 1/2, 0), c ¹ =(2, 3/2, 3/2).

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

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

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

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

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

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

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

 

 

Приложение

В приложении приведена реализация итеративного метода Брауна-Робинсона решения матричных игр на языке программирования Turbo Pascal 7.0.

Пользователь вводит матрицу выигрышей размера m×n, где m≥3, n≥3.

Далее машина запрашивает информацию о том, кто из игроков начинает игру, какую стратегию он выбирает и количество итераций.

На дисплее выводится таблица разыгрываний игры за определённое число итераций.

 

program br;

uses crt;

const matr1:array[1..3,1..3] of byte=((0,4,2),

(3,1,0),

(1,2,3));                { Начальная матрица }

Var

matr : array [1..10,1..10] of integer ;        {Матрица, введенная пользователем}

win_one:array[0..150,1..10] of word;    { Массив для выигрышей игр .1}

win_two:array[0..150,1..10] of word;    { Массив для выигрышей игр .2}

max,min:integer;

a,i,j,m,n,pl,st,st1,st2,kl:byte;

nol,otr:boolean;

function igr _ one : byte ;                               {Функция определения следующего}

var a1,a2,max:integer;                              { хода для игрока 1}

Begin

max:=win_one[a,1];

igr_one:=1;

if pl=1 then a2:=m else a2:=n;

for a1:=1 to a2 do if win_one[a,a1]>max then begin

max:=win_one[a,a1];

igr_one:=a1;

end;

end;

function igr_two:byte;                                    {Функция определения следующего}

var a1,a2,min:integer;                   { хода для игрока 2}

Begin

min:=win_two[a,1];

igr_two:=1;

if pl=1 then a2:=n else a2:=m;

for a1:=1 to a2 do if win_two[a,a1]<min then begin

min:=win_two[a,a1];

igr_two:=a1;

end;

end;

Begin

clrscr;