Применение теории игр к игре с неполной информацией. Визуализация в среде VISUAL C++

Размещено на http://www.allbest.ru/

Применение теории игр к игре с неполной информацией. Визуализация в среде VISUAL C++

ВВЕДЕНИЕ

игра матричный бескоалиционный

Теория игр, как один из подходов в прикладной математике, применяется для изучения поведения человека и животных в различных ситуациях. Первоначально теория игр начала развиваться в рамках экономической науки, позволив понять и объяснить поведение экономических агентов в различных ситуациях. Позднее область применения теории игр была расширена на другие социальные науки; в настоящее время теория игр используется для объяснения поведения людей в политологии, социологии и психологии. Теоретико-игровой анализ был впервые использован для описания поведения животных Рональдом Фишером в 30-х годах XX века (хотя даже Чарльз Дарвин использовал идеи теории игр без формального обоснования). В работе Рональда Фишера не появляется термин «теория игр». Тем не менее, работа по существу выполнена в русле теоретико-игрового анализа. Разработки, сделанные в экономике, были применены Джоном Майнардом Смитом в книге «Эволюция и теория игр». Теория игр используется не только для предсказания и объяснения поведения; были предприняты попытки использовать теорию игр для разработки теорий этичного или эталонного поведения. Экономисты и философы применяли теорию игр для лучшего понимания хорошего (достойного) поведения. Вообще говоря, первые теоретико-игровые аргументы, объясняющие правильное поведения, высказывались ещё Платоном.

Теоретическая Часть

Матричная игра задаётся матрицей А размера [m x n] выигрышей первого игрока. Стратегии первого игрока соответствуют строкам, а стратегии второго - столбцам матрицы А. Первый игрок выбирает стратегию i, а второй - стратегию j. В результате первый игрок выигрывает сумму a_ij, а второй - -a_ij.

1. Решением матричной игры в чистых стратегиях называется пара чистых стратегий (i_0, j₀) первого и второго игроков, которые образуют седловую точку матрицы A. Стратегии i₀, j₀ в этом случае называются оптимальными чистыми стратегиями.

По теореме о максиминах матричная игра с матрицей игры A имеет решение в чистых стратегиях тогда и только тогда, когда нижняя чистая цена игры равна верхней чистой цене игры : В таком случае число называется чистой ценой игры. Чтобы вычислить нужно в каждой строке матрицы A найти минимальный элемент, а затем среди этих минимальных элементов выбрать максимальный. Аналогично, чтобы вычислить нужно в каждом столбце матрицы A найти максимальный элемент, а затем среди этих максимальных элементов выбрать минимальный. Если , то отметьте те строки, в которых минимальный элемент равен , и те столбцы, в которых максимальный элемент равен .Элементы, находящиеся на пересечении отмеченных строк и столбцов, это все седловые точки матрицы A

2. Напомним, что смешанной стратегией игрока в бескоалиционной игре называется полный набор вероятностей применения его чистых стратегий. В матричной игре с [mxn]-матрицей A выигрышей игрока 1, множество смешанных стратегий игрока 1 это симплекс , а множество смешанных стратегий игрока 2 есть симплекс . В матричной игре смешанную стратегию игрока 1 принято обозначать через p = ( p₁ ;…;p_m )^T , а игрока 2 через q = ( q₁;…;q_n)^T. Заметим, что единичные векторы и соответствуют i-й чистой стратегии игрока 1 и j -й чистой стратегии игрока 2 соответственно. Стоит также еще раз напомнить, что мы называем стратегии игроков чистыми, чтобы отличить их от смешанных стратегий, которые являются вероятностными правилами применения игроками их (чистых) стратегий

Алгоритм оценки сводится к следующему набору условий:

КОД ПРОГРАММЫ

Form.h

private: void Solve(array<int,2>^ A)

{

array<bool>^ g=gcnew array<bool>(m);

array<bool>^ v=gcnew array<bool>(n);

array<int,2>^ a=SimplifyMatrix(A,v,g);

int Adding = Positive(a);

for(int i=0;i<this->n;++i)

{

if(v[i])

{

for(int j=0;j<this->m;++j)

numerics[i,j]->BackColor = System::Drawing::Color::Red;

}

}

for(int j=0;j<this->m;++j)

{

if(g[j])

{

for(int i=0;i<this->n;++i)

numerics[i,j]->BackColor = System::Drawing::Color::Red;

}

}

int n=a->GetLength(0),m=a->GetLength(1);

GraphicForm^ grF;

SaddleAnswer saddleAnswer=SaddlePoint(a);

if(saddleAnswer.hasSaddlePoint)

{

int t=saddleAnswer.A_strategy;

t=DeSimplify(t,v);

for(int i=0;i<this->m;++i)

if(!g[i])

numerics[t,i]->BackColor = System::Drawing::Color::Lime;

int tb=saddleAnswer.B_strategy;

tb=DeSimplify(tb,g);

for(int i=0;i<this->n;++i)

if(!v[i])

numerics[i,tb]->BackColor = System::Drawing::Color::Lime;

System::Windows::Forms::MessageBox::Show("В матрице присутствует седлoвая точка!\n"+

"Баланс достигается при соблюдении оптимальной стратегии игроками.\n"+

"Для игрока А стратегия №"+(t+1)+

"\nДля игрока стратегия №"+(tb+1)+

"\nЦена игры: "+(A[t,tb]+Adding),

"Седловая точка");

}

else if(n==2)

{

GraphicsAnswer graphicalAnswer=GraphicalSolve(a);

grF=gcnew GraphicForm(graphicalAnswer,a);

grF->Show();

int ta1=DeSimplify(0,v);

int ta2=DeSimplify(1,v);

int tb1=DeSimplify(graphicalAnswer.first,g);

int tb2=DeSimplify(graphicalAnswer.second,g);

numerics[ta1,tb1]->BackColor = System::Drawing::Color::Lime;

numerics[ta1,tb2]->BackColor = System::Drawing::Color::Lime;

numerics[ta2,tb1]->BackColor = System::Drawing::Color::Lime;

numerics[ta2,tb2]->BackColor = System::Drawing::Color::Lime;

System::Windows::Forms::MessageBox::Show("В матрице отсутствует седлoвая точка.\n"+

"Баланс достигается смешанными стратегиями №№("+(ta1+1)+","+(ta2+1)+

") c вероятностями ("+(1-graphicalAnswer.pmax)+","+(graphicalAnswer.pmax)+")\n"+

"Цена игры: "+(graphicalAnswer.ymax+Adding),

"Графический способ");

}

else if(m==2)

{

array<int,2>^ aT=Transpose(a);

int Add2=Positive(aT);

GraphicsAnswer graphicalAnswer=GraphicalSolve(aT);

grF=gcnew GraphicForm(graphicalAnswer,aT);

grF->Show();

int ta1=DeSimplify(0,g);

int ta2=DeSimplify(1,g);

int tb1=DeSimplify(graphicalAnswer.first,v);

int tb2=DeSimplify(graphicalAnswer.second,v);

numerics[tb1,ta1]->BackColor = System::Drawing::Color::Lime;

numerics[tb1,ta2]->BackColor = System::Drawing::Color::Lime;

numerics[tb2,ta1]->BackColor = System::Drawing::Color::Lime;

numerics[tb2,ta2]->BackColor = System::Drawing::Color::Lime;

System::Windows::Forms::MessageBox::Show("В матрице отсутствует седлавая точка.\n"+

"Баланс достигается смешанными стратегиями №№("+(tb1+1)+","+(tb2+1)+

") c вероятностями ("+(1-graphicalAnswer.pmax)+","+(graphicalAnswer.pmax)+")\n"+

"Цена игры: "+(-graphicalAnswer.ymax+Adding-Add2),

"Графический способ");

}

else

{

array<double>^ result=gcnew array<double>(m);

SimplexAnswer simplexAnswer=Simplex(a,result);

String^ p0=String::Empty;

int d=-1;

for(int i=0;i<m;++i)

{

int k=d+1;

d=DeSimplify(i,v);

for(int j=k;j<d-1;++j)

p0+="0, ";

p0+= result[i];

}

for(int i=d+1;i<this->m;++i)

p0+=" 0, ";

p0->Remove(p0->Length-2);

p0+")";

System::Windows::Forms::MessageBox::Show("Цена игры: "+

simplexAnswer.Vmax+

"Стратегия: "+p0

,"Симплекс метод");

}

}

MathFile.cpp

#include "stdafx.h"

#include "MathFile.h"

SaddleAnswer SaddlePoint(array<int,2>^ a)

{

int n=a->GetLength(0),m=a->GetLength(1);

int t,res_a=0,res_a_index,res_b=0,res_b_index;

for(int i=0;i<n;++i)

{

t=0;

for(int j=1;j<m;++j)

if(a[i,t]>a[i,j])

t=j;

if(i==0 || res_a<a[i,t])

{

res_a_index=i;

res_a=a[i,t];

}

}

for(int j=0;j<m;++j)

{

t=0;

for(int i=0;i<n;++i)

if(a[t,j]<a[i,j])

t=i;

if(j==0 || res_b>a[t,j])

{

res_b_index=j;

res_b=a[t,j];

}

}

SaddleAnswer sa;

if(res_a==res_b)

{

sa.hasSaddlePoint=true;

sa.A_strategy=res_a_index;

sa.B_strategy=res_b_index;

}

else

sa.hasSaddlePoint=false;

return sa;

}

void Draw(array<int,2>^ b, int m1)

{

}

array<int,2>^ SimplifyMatrix(array<int,2>^ a, array<bool>^v,array<bool>^g)

{

int n=a->GetLength(0),m=a->GetLength(1);

for(int i=0;i<m;++i) g[i]=false;

for(int i=0;i<n;++i) v[i]=false;

int t=0,m1=m,n1=n;

while(true)

{

for(int i=0;i<m;++i)

for(int j=i+1;j<m;++j)

{

bool eq=true;

for(int k=0;k<n && eq;++k)

eq&=v[k] || (a[k,i]==a[k,j]);

if((g[i] ^ g[j]) && eq)

continue;

if(!g[j])

{

bool fl=true;

for(int k=0;k<n && fl;++k)

fl&=v[k] || (a[k,i]<=a[k,j]);

g[j]=fl&&!eq;

}

if(!g[i])

{

bool fl=true;

for(int k=0;k<n && fl;++k)

fl&=v[k] || (a[k,i]>=a[k,j]);

g[i]|=fl;

}

}

for(int i=0;i<m;t+=g[i++]?0:1);

if(t==m1 && t!=m) break;

m1=t;

t=0;

for(int i=0;i<n;++i)

for(int j=i+1;j<n;++j)

{

bool eq=true;

for(int k=0;k<m && eq;++k)

eq&=g[k] || (a[i,k]==a[j,k]);

if((v[i] ^ v[j]) && eq)

continue;

if(!v[j])

{

bool fl=true;

for(int k=0;k<m && fl;++k)

fl&=g[k] || (a[i,k]<=a[j,k]);

v[j]|=fl&&!eq;

}

if(!v[i])

{

bool fl=true;

for(int k=0;k<m && fl;++k)

fl&=g[k] || (a[i,k]>=a[j,k]);

v[i]|=fl;

}

}

for(int i=0;i<n;t+=v[i++]?0:1);

if(t==n1) break;

n1=t;

t=0;

}

array<int,2>^ b=gcnew array<int,2>(n1,m1);

for(int i=0,index=0;index<n1;++i)

{

if(!v[i])

{

for(int j=0,jndex=0;jndex<m1;++j)

{

if(!g[j])

{

b[index,jndex]=a[i,j];

jndex++;

}

}

index++;

}

}

return b;

}

int DeSimplify(int k, array<bool>^v)

{

int h=0;

int i=0;

while(v[i] || h<k)

{

if(!v[i]) h++;

i++;

}

return i;

}

array<int,2>^ Transpose(array<int,2>^ a)

{

int n=a->GetLength(0),m=a->GetLength(1);

array<int,2>^ b=gcnew array<int,2>(m,n);

for(int i=0;i<n;++i)

for(int j=0;j<m;++j)

b[j,i]=a[i,j];

return b;

}

GraphicsAnswer GraphicalSolve(array<int,2>^ a)

{

int m1=a->GetLength(1);

GraphicsAnswer result;

result.ymax=0.0;

double p;

double y;

for(int i=0;i<m1;++i)

for(int j=i+1;j<m1;++j)

{

p=a[0,j]-a[0,i];

p/=a[1,i]-a[0,i]-a[1,j]+a[0,j];

y=a[0,j]+(a[1,j]-a[0,j])*p;

if(y>result.ymax)

{

bool fl=true;

for(int k=0;k<m1 && fl;++k)

fl=y<=(a[0,k]+(a[1,k]-a[0,k])*p);

if(fl)

{

result.pmax=p;

result.ymax=y;

result.first=i;

result.second=j;

}

}

}

return result;

}

SimplexAnswer Simplex(array<int,2>^ a,array<double>^ result)

{

SimplexAnswer simplexAnswer;

int n=a->GetLength(0),m=a->GetLength(1);

array<double,2>^ matrix=gcnew array<double,2>(n+1,n+m+1);

array<int>^ base=gcnew array<int>(n);

for(int i=0;i<n;++i)

{

for(int j=0;j<m;++j)

{

matrix[i,j]=a[i,j];

}

for(int j=0;j<n;++j)

matrix[i,j+m]=(i==j?1:0);

matrix[i,n+m]=1;

base[i]=i+m;

}

for(int j=0;j<m+n+1;++j)

matrix[n,j]=j<m?1:0;

while(true)

{

int r=0;

for(int i=1;i<m+n;++i)

if(matrix[n,r]<matrix[n,i])

r=i;

if(matrix[n,r]<=0)

break;

int s=-1;

for(int i=0;i<n;++i)

{

if(matrix[i,r]>0 && (s==-1 || matrix[i,n+m]*matrix[s,r]<matrix[s,n+m]*matrix[i,r]))

s=i;

}

if(s==-1)

{

simplexAnswer.hasAnswer=false;

return simplexAnswer;

}

base[s]=r;

for(int i=0;i<=n+m;++i)

if(i!=r)

matrix[s,i]/=matrix[s,r];

for(int i=0;i<=n;++i)

{

if(i==s)

continue;

for(int j=0;j<=n+m;++j)

{

if(j==r)

continue;

matrix[i,j]-=matrix[i,r]*matrix[s,j];

}

}

for(int i=0;i<=n;++i)

{

matrix[i,r]=i==s?1:0;

}

}

simplexAnswer.Vmax=-1/matrix[n,n+m];

for(int i=0;i<n;++i)

{

if(base[i]<m)

result[base[i]]=matrix[i,n+m]*simplexAnswer.Vmax;

}

return simplexAnswer;

}

int Positive(array<int,2>^ a)

{

int min=a[0,0];

for(int i=0;i<a->GetLength(0);++i)

for(int j=0;j<a->GetLength(1);++j)

if(min>a[i,j])

min=a[i,j];

for(int i=0;i<a->GetLength(0);++i)

for(int j=0;j<a->GetLength(1);++j)

a[i,j]-=min;

return min;

}

ЗАКЛЮЧЕНИЕ

В данной работе:

· Предложен, реализован и апробирован алгоритм оценки матричной игры с неполной информацией

СПИСОК ЛИТЕРАТУРЫ

1. Писарук, Н.Н. Введение в теорию игр / Н.Н. Писарук. - Минск : БГУ, 2010. - 108с.

2. [Электрон. ресурс - http://emm.ostu.ru/lect/lect2_2.html]

3. [Электрон. ресурс _ http://www.cas.fpmi.bsu.by/CourseDesigning/ReadMeCD/tabid/187/language/ru-RU/Default.aspx … #КурсовойПроект2011].

Размещено на Allbest.ru