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

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]

Приложение

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