Xreferat.com » Рефераты по математике » Методы приближённого решения матричных игр

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

height="33" align="BOTTOM" border="0" />. (2)

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

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

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

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

На основании неравенства (1) имеем: Методы приближённого решения матричных игр.

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

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

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

Методы приближённого решения матричных игр для "e>0.

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

Итак, Методы приближённого решения матричных игр.

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

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

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

но-мер

пар

тии

стратегия

второго

игрока

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

стратегия

первого

игрока

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

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

u w n


1 2 3
1 2 3


1 1 0 4 2 2 4 1 2 4 1 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

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

u w n


1 2 3
1 2 3


1

2

1

2

0

3

4

5

2

2

2

2

4

8

1

2

2

4

4

5/2

1

2/2

5/2

7/2


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

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


но-мер

пар

тии

Страте-

гия

второго

игрока

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

Страте-

гия

первого

игрока

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

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

u w n


1 2 3
1 2 3


1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

1

2

2

2

3

3

1

3

3

3

3

3

2

2

2

2

2

2

2

3

0

3

6

9

10

11

11

12

13

14

15

16

19

22

25

28

31

34

37

38

4

5

6

7

9

11

15

17

19

21

23

25

26

27

27

29

30

31

32

34

2

2

2

2

5

8

10

13

16

19

22

25

25

25

25

25

25

25

25

28

2

2

1

1

1

1

2

2

2

2

2

2

2

2

2

2

1

1

1

1

4

8

8

8

8

8

12

16

20

24

28

32

36

40

44

48

48

48

48

48

1

2

5

8

11

14

15

16

17

18

19

20

21

22

23

24

27

30

33

36


2

4

5

6

7

8

10

12

14

16

18

20

22

24

26

28

29

30

31

32

4

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

1

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.


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

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

Сложность и объём вычислений сравнительно слабо возрастают по мере увеличения числа стратегий игроков (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) . Тогда справедливы следующие утверждения:

Методы приближённого решения матричных игр т. е. последовательность {nN-1} строго монотонно возрастает.

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

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).

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

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

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

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

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

3. Вычислим коэффициент e2. Для этого решим подыгру (2ґ3):Методы приближённого решения матричных игр. Стратегии игроков совпадают, поэтому 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]


Приложение

В приложении приведена реализация итеративного метода Брауна-Робинсона решения матричных игр на языке программирования 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;

writeln ('Итеративный метод Брауна-Робинсона.');

writeln('Матрица пользователя? (y/n)');

if (readkey='y')or(readkey='Y') then begin {Матрица из памяти или вводит пользователь}

write ('Введите размеры матрицы:');

readln(n,m); {Ввод количества строк и столбцов}

writeln('Введите ',n,' строки по ',m,' элементов:');

nol:=true;

otr:=false;

min:=0;

for j:=1 to n do for i:=1 to m do begin {Ввод элементов матрицы}

read(matr[i,j]);

if matr[i,j]<>0 then nol:=false; {Установка флага, что не все элементы равны 0}

if matr[i,j]<0 then otr:=true; {Установка флага наличия отрицательных элементов}

if matr[i,j]<min then min:=matr[i,j];{Определение минимального элемента}

end

end else begin {Иначе берем матрицу из константы}

n:=3;m:=3;

for i:=1 to m do for j:=1 to n do matr[i,j]:=matr1[i,j];

end;

clrscr;

writeln ('Итеративный метод Брауна-Робинсона.');

if nol then writeln('Все элементы матрицы равны 0!') else begin {если установлен флаг нуля, то алгоритм не работает}

if otr then for j:=1 to n do for i:=1 to m do matr[i,j]:=matr[i,j]-min;{если есть отрицательные элементы,}

writeln('Начальная матрица:'); {Вывод окончательной матрицы}

for j:=1 to n do begin

for i:=1 to m do write(matr[i,j]:4);

writeln;

end;


write('Какой игрок начнет игру? '); {Вод стартовых значений}

readln(pl);

write('Какую стратегию выберет ',pl,' игрок? ');

readln(st);

write('Количество итераций? ');

readln(kl);

a:=1; {заглавие таблицы}

writeln(' № стр. выигрыш 1-го игр. стр. выигрыш 2-го игр. V W Y');

repeat

write(a:2,st:6,' '); {формирование таблицы: номер итерации, стратегия 1игр.}

if pl=2 then begin

for i:=1 to n do begin

win_one[a,i]:=matr[st,i]+win_one[a-1,i];{формирование матрицы выигрышей 1 игр.}

write(win_one[a,i]:4); {вывод на экран}

end;

st1:=igr_one; {определение ответной стратегии 2 игр.}

gotoxy(32,wherey);

write(st1:10,' '); {вывод на экран}

for i:=1 to m do begin

win_two[a,i]:=matr[i,st1]+win_two[a-1,i]; {формирование матрицы выигрышей 2 игр.}

write(win_two[a,i]:4); {вывод на экран}

end;

gotoxy(64,wherey);

write(win_one[a,st1]:4); {вывод наибольшего суммарного выигрыша 1 игр.}

st:=igr_two; {определение ответной стратегии 1 игр.}

write(win_two[a,st]:4); {вывод наибольшего суммарного выигрыша 2 игр.}

write((win_one[a,st1]+win_two[a,st])/(a*2):6:2);{приближенное значение цены игры}

end

else

begin

for i:=1 to m do begin

win_one[a,i]:=matr[i,st]+win_one[a-1,i];{формирование матрицы выигрышей 1 игр.}

write(win_one[a,i]:4);

end;

st1:=igr_one; {определение ответной стратегии 2 игр.}

gotoxy(32,wherey);

write(st1:10,' ');

for i:=1 to n do begin

win_two[a,i]:=matr[st1,i]+win_two[a-1,i];{формирование матрицы выигрышей 2 игр.}

write(win_two[a,i]:4);

end;

gotoxy(64,wherey);

write(win_one[a,st1]:4); {вывод наибольшего суммарного выигрыша 1 игр.}

st:=igr_two; {определение ответной стратегии 1 игр.}

write(win_two[a,st]:4); {вывод наибольшего суммарного выигрыша 2 игр.}

write((win_one[a,st1]+win_two[a,st])/(a*2):6:2);{приближенное значение цены игры}

end;

a:=a+1; {увеличение счетчика итераций}

writeln;

until a=kl+1;


end;

readln;

readln;

end.


Список литературы


Беленький В.З. Итеративные методы в теории игр и программировании. М.: «Наука», 1977

Блекуэлл Д.А. Теория игр и статистических решений. М., Изд. иностранной литературы, 1958

Вентцель Е.С. Элементы теории игр. М., Физматгиз, 1961

Вилкас Э.И. Оптимальность в играх и решениях. М.: «Наука», 1986

Воробьёв И.Н. Математическая теория игр. М.: «Знание», 1976

Давыдов Э.Г. Методы и модели теории антагонистических игр. М.: «Высшая школа», 1990

Дрешер М. Стратегические игры. Теория и приложения. М., 1964

Исследование операций в экономике / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н. Фридман. М.: «Банки и биржи», Юнити, 1997

Итеративный алгоритм решения матричных игр// Доклады Академии наук СССР, том 238, №3, 1978

Карлин С. Математические методы в теории игр, программировании и экономике. М.: «Мир», 1964

Крапивин В.Ф. Теоретико-игровые методы синтеза сложных систем в конфликтных ситуациях. М.: «Советское радио», 1972

Крушевский А.В. Теория игр: [Учебное пособие для вузов]. Киев: «Вища школа», 1977

Льюис Р., Райфа Х. Игры и решения. М.,1961

Морозов В.В., Старёв А.Г., Фёдоров В.В. Исследование операций в задачах и упражнениях. М.: «Высшая школа», 1996

Матричные игры. [Сборник переводов]. Под ред. Воробьёва И.Н. М., Физматгиз, 1961

Оуэн Г. Теория игр. [Учебное пособие]. М.: «Мир», 1973

Петросян Л.А., Зенкевич Н.А., Семен Е.А. Теория игр. М., 1989

Школьная энциклопедия математика. Ред. С. М. Никольский, М.: 1996, с. 380

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: