Приближенное решение игры методом итераций.

На практике часто нет необходимости находить точное решение игры, достаточно найти средний выигрыш игроков, близкий к цене игры. В таком случае можно получить прибиженное решение с помощью численного метода итераций.

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

Если итерационный процесс продолжается достаточно долго, то средний выигрыш, приходящийся на одну игру, будет стремиться к цене игры, а частоты , с которыми игроки выполняют свои стратегии, будут приближаться к частотам, определяющим оптимальные стратегии.

Проиллюстрируем этот метод на примере игры Эдварда и Фионы, которая задана платежной матрицей : .

Пусть Эдвард вначале выбирает первую стратегию. Тогда Фиона выбирает свою вторую стратегию, определяющую наименьший выигрыш Эдварда при его первой стратегии. В ответ на это Эдвард выберет свою вторую стратегию, при которой он получает максимальный выигрыш при второй стратегии Фионы.

Теперь Фиона складывает выигрыши Эдварда почленно при его двух выбранных стратегиях (получается строка: -1, 1) и выбирает первую стратегию, при которой Эдвард получает минимальный выигрыш и т.д. Выполним этот процесс 10 раз, и результаты представим в таблице:

Таблица 10

n	i			j
			–		–3		0.5
		–			–1
		–				–2	–0.5
		–				–5	0.125
			–			–1	–0.1
			–		–3		–0.083
		–			–1		–0.071
		–				–3	–0.188
		–				–6	0.055
			–			–

В первом столбце таблицы записан номер элементарной игры n, во втором – номер i выбранной стратегии первого игрока, в следующих двух – «накопленнный» выигрыш за первые n игр второго игрока при его стратегиях , . Минимальное из этих значений подчеркнуто. В пятом столбце записан номер j стратегии, выбранной вторым игроком. В следующих двух столбцах записан «накопленнный» выигрыш за первые n игр первого игрока при его стратегиях , . В последнем столбце вычисляется средний накопленный выигрыш V, приходящийся на одну игру.

Частоту каждой стратегии можно вычислить, разделив на 10 количество строк, где применяется игроком эта стратегия. Таким образом, приближенными оптимальными стратегиями Эдварда и Фионы будут смешанные стратегии:

Приближенное значение цены игры: V = 0. Получились довольно грубые приближения оптимальных стратегий игроков и цены игры, но если применить компьютер, и количество элементарных игр увеличить до числа g = 20000, получим результаты, совпадающие с точными, если оставить в записи чисел 3 цифры после запятой:

и и V = – 0.083

Ниже приводится программа вычисления приближенного решения игры методом итераций. Предполагается, что размеры платежной матрицы не превышают 20. Информация о платежной матрице хранится в текстовом файле ‘input.txt’. В его первой строке записаны 2 целых числа – размеры m и n. Далее в m строках располагаются элементы платежной матрицы A по n чисел в каждой строке. Для игры Эдварда и Фионы файл ‘input.txt’ имеет вид:

2 2

2 –3

–3 4

Процедура readf считывает данные из файла, процедура print выводит эти данные на экран. Процедуры max и min определяют на каждом шаге итерационного процесса номера оптимальных стратегий игроков с учетом накопленных средних выигрышей за исполненные шаги процесса.

program analis; {решение игры размера m*n методом итераций}

{$N+}

uses crt;

const nn=20; mm=20; g=20000;

type te = extended;

var a:array[1..mm,1..nn] of te; u,c,r,t,i,j,m,n:integer;

p:array[1..mm] of te; q:array[1..nn] of te;

x:array[1..mm] of te; y:array[1..nn] of te;

f:text;

procedure readf;

begin assign(f,'input.txt');

reset(f); readln(f,m,n);

for i:=1 to m do

for j:=1 to n do read(f,a[i,j]);

close(f)

end;

procedure print;

begin writeln (' Игра размера ',m,'*',n);

writeln (' Платежная матрица игры:');

for i:=1 to m do

begin

for j:=1 to n do write(a[i,j]:4:1,' '); writeln

end

end;

procedure max;

begin r:=1;

for i:=2 to m do

begin if (x[i]=x[r]) and (random<0.5) then r:=i;

if x[i]>x[r] then r:=i

end

end;

procedure min;

begin c:=1;

for j:=2 to n do

begin if (y[j]=y[c]) and (random<0.5) then c:=j;

if y[j]<y[c] then c:=j

end

end;

begin clrscr;

writeln(' Решение игры методом итераций') ;

readf;

for i:=1 to m do

begin p[i]:=0; x[i]:=0

end;

for j:=1 to n do

begin q[j]:=0; y[j]:=0

end;

print; writeln;

r:=random(m)+1;

for u:=1 to g do

begin for j:=1 to n do

y[j]:=y[j]+a[r,j];

min;

q[c]:=q[c]+1;

for i:=1 to m do

x[i]:=x[i]+a[i,c];

max;

p[r]:=p[r]+1

end;

{ v1:=y[c]/g;

v2:=x[r]/g; }

writeln('получены результаты:');

writeln('приблизительные смешанные оптимальные стратегии ');

writeln('первого игрока:');

for i:=1 to m do

write((p[i]/g):5:3,' ' ); writeln;

writeln('второго игрока:');

for j:=1 to n do

write((q[j]/g):5:3,' '); writeln;

writeln('цена игры V=',(x[r]+y[c])/g/2:5:3);

readkey

end.

Вопросы и упражнения

1. Приведите пример конечной игры с седловой точкой и найдите оптимальные стратегии игроков и цену игры.

2. Приведите пример конечной игры без седловой точки и определите нижнюю и верхнюю цену игры.

3. Приведите пример конечной игры размера 2×2 без седловой точки, постройте смешанные стратегии игроков и определите соответствующую среднюю цену игры.

4. Используя геометрическую интерпретацию, найдите решение игры, определяемой платежной матрицей: