Методы приближённого решения матричных игр
Отсюда получаем оценку разности пределов:
.
Из леммы следует, что
.
На
основании
неравенства
(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