Консультация № 140563
23.07.2008, 14:54
0.00 руб.
0 1 1
здравствуйте,дорогие эксперты! помогите, ложалуйста ,решить задачу в паскале:найти седловую точку в произвольной антагонистической игре при чистых стратегиях.Заранее огромное спасибо!

Обсуждение

давно
Старший Модератор
31795
6196
24.07.2008, 16:24
общий
это ответ
Здравствуйте, светлакова светлана !

Программа в приложении.
Теорию можете сами почитать тут или тут.
Цитата: кратко
Седловые точки и минимаксы
Устойчивое решение игры может быть получено путем следующих рассуждений:
В самом неблагоприятном случае выигрыш первого игрока не может быть уменьшен по вине противника, если он удовлетворяет условию: a ij* = min аij
С другой стороны, руководствуясь принципом выгоднгодности первый игрок будет стремиться увеличить свой выигрыш, сохраняя свойство устойчивости, поэтому vн = max min аij
Это нижняя цена игры. Рассуждая подобным образом за второго игрока получим верхнюю цену игры:
vв = min max аij
Интуитивно ясно, что значение ( цена ) игры лежит между и.
Равновесие в игре или седловая точка будет при условии: max min аij = min max аij

Программа ищет вернюю и нижнюю цену игры, если значения совпадают, то седловая точка существует. Проверял на матрицах:
n=4,m=3:((500,400,500),(100,600,650),(900,700,800),(400,200,300))
n=4,m=4:((7,-1,-4,1),(4,2,3,2),(2,2,5,2),(4,-3,7,2))

Удачи!

Приложение:
const
n=4;{количество стратегий первого игрока}
m=4;{количество стратегий второго игрока}
type
Tmas=array[1..n,1..m]of integer;{матрица стратегий}
var
mas_A:Tmas;{сама матрица стратегий}
i,j,max_A,max_B,min_A,min_B,tmp:integer;
begin
{вводим матрицу стратегий}
randomize;
for i:=1 to n do
begin
for j:=1 to m do
begin
write('a[',i,',',j,']:=');
readln(mas_A[i,j]);
end;
writeln;
end;
{поиск максмини выигрыша первого игрока}
writeln;
max_A:=1;
{поиск минимального значения выигрыша в первой стратегии игрока}
min_A:=1;
for i:=2 to m do
if mas_A[1,i]<mas_A[1,min_A]then min_A:=i;
{выводим найденое минимальное значение
оноже пока есть и максимальным}
write('max min',mas_A[max_A,min_A]:4);
{поиск максимального выигрыша среди всех минимальных}
for i:=2 to n do
begin
tmp:=1;
{поиск минимального значения выиграша для каждой стратегии}
for j:=2 to m do
if mas_A[i,j]<mas_A[i,tmp]then tmp:=j;
{поиск максимального значения среди минимальных}
if mas_A[i,tmp]>mas_A[max_A,min_A]then
begin
max_A:=i;
min_A:=tmp;
end;
{выводим текущее максимальное значение}
write(mas_A[max_A,min_A]:4);
end;
{поиск минимакса проигрыша второго игрока}
writeln;
min_B:=1;
{поиск максимального проигрыша в первой стратегии втрого игрока}
max_B:=1;
for i:=2 to n do
if mas_A[i,1]>mas_A[max_B,1]then max_B:=i;
write('min max',mas_A[max_B,min_B]:4);
{поиск минимального проигрыша среди всех максимальных}
for i:=2 to m do
begin
tmp:=1;
{поиск макимального значения проигрыша для каждой стратегии}
for j:=2 to n do
if mas_A[j,i]>mas_A[tmp,i]then tmp:=j;
{поиск минимального среди всех максимальных}
if mas_A[tmp,i]<mas_A[max_B,min_B]then
begin
max_B:=tmp;
min_B:=i;
end;
{выводим текущее значение минимальрого проигрыша}
write(mas_A[max_B,min_B]:4);
end;
writeln;
{выводим результаты поиска}
writeln('a(l)[',max_A,',',min_A,']:=',mas_A[max_A,min_A]:5,' a(h)[',max_B,',',min_B,']:=',mas_A[max_B,min_B]:5);
end.
Об авторе:
Мне безразлично, что Вы думаете о обо мне, но я рад за Вас - Вы начали думать.

Форма ответа