Теория игр

 Во время игры много  зависит и от рационального  поведения игрока, то есть продуманного  выбора и оптимальной стратегии.  Разработке формализованного (в  виде моделей) описания конфликтных  ситуаций, в частности «формулы  равновесия», то есть устойчивости  решений противников в игре, занимался  Дж.-Ф. Нэш

 Нэш (Nash) Джон-Форбс (род в 1928) - американский экономист, лауреат Нобелевской премии (1994). Родился в г. Блуэфилд (штат Западная Вирджиния, США). Учился в Университете Карнеги-Меллона по специальности инженера-химика, но, увлекшись математикой, перевелся на математический факультет. Получил диплом бакалавра математики и одновременно магистра математики.

 

 

4 Пример математического  решения

 

Платежная матрица имеет  вид

 

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

Найдем нижнюю и верхнюю  цены игры.

aa

a=a – нижняя цена игры.

bb

b=b – верхняя цена игры.

Так как a=b=0, матрица игры имеет седловую точку.

Оптимальная стратегия первого  игрока - , второго . Из таблицы видно что отклонение первого игрока от оптимальной стратегии уменьшает его выигрыш, а отклонение второго игрока от увеличивает его проигрыш.

Найти решение игры, заданной матрицей

 

Найдем нижнюю и верхнюю  цены игры.

ababn

Игра не имеет седловой точки. Оптимальное решение следует искать в области смешанных стратегий.

Для определения оптимальной  стратегии игрока А имеем следующую задачу линейного программирования

 

 

 

Для нахождения оптимальной  стратегии игрока В имеем следующую задачу линейного программирования

n

можно найти оптимальные  стратегии игроков и цену игры:

n

 

 

5 Основная часть (программа)

5.1 Постановка задачи  с точки зрения программирования

 

Требуется написать программу  решения матричных игр, в которых  решение может присутствовать в  чистых и смешанных стратегиях.

Программа делится на несколько  подзадач:

1. Ввод исходных данных;
2. Проверка существования седловой точки;
3. Поиск решения в смешанных стратегиях, если седловая точка отсутствует.

5.2 Структура программы

 

Проект написан с использованием среды Delphi 7. Среда Delphi 7 представляет собой интегрированную оболочку разработчика, в которую входит набор специальных программ, ответственных за разные этапы создания готового приложения.

Исходный текст программы готовится в среде Delphi 7 с помощью встроенного редактора исходных текстов. Этот редактор специализирован. Он отличается гибкими возможностями цветового выделения различных элементов текста программы (ключевые слова, названия, операций, чисел строк) и предоставляет возможность быстрого ввода часто встречающихся конструкций.

Программа состоит из 6 модулей. Каждый модуль соответствует одной  из форм интерфейса пользователя.

Первая форма (unit 1) представляет собой заставку предназначенную для объяснения пользователю назначения программы.

Вторая форма (unit 2) предназначена для ввода числа стратегий каждого из игроков.

Третья форма (unit 3) предназначена для ввода матрицы игры. В этом модуле проводятся основные расчеты.

Определение верхней и  нижней цен игры проводится функцией sedlo, она возвращает значение true в случае если существует седловая точка и false в противном случае.

Поиск решения игры в смешанных  стратегиях проходит в процедуре  simp.

5.3 Текст программы

unit Unit1;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, ExtCtrls, StdCtrls, jpeg;

type

  TForm1 = class(TForm)

    Label1: TLabel;

    Shape1: TShape;

    Image1: TImage;

    Button1: TButton;

    procedure Button1Click(Sender: TObject);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form1: TForm1;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

begin

form2.show;

form1.Hide;

end;

end.

unit Unit2;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls;

type

  TForm2 = class(TForm)

    Label1: TLabel;

    Edit1: TEdit;

    Label2: TLabel;

    Edit2: TEdit;

    Button1: TButton;

    procedure Button1Click(Sender: TObject);

    procedure Edit1KeyPress(Sender: TObject; var Key: Char);

    procedure Edit2KeyPress(Sender: TObject; var Key: Char);

    procedure FormClose(Sender: TObject; var Action: TCloseAction);

  private

    { Private declarations }

  public

    { Public declarations }

  end;

var

  Form2: TForm2;

implementation

uses Unit3, Unit1;

{$R *.dfm}

procedure TForm2.Button1Click(Sender: TObject);

var a,c:integer;

begin

if ((edit1.text='') or (edit2.text='')) then

   MessageBox(Application.Handle,'Вы не ввели одно из значений.','Ошибка', MB_OK)

else

  begin

    val(edit1.Text,a,c);

    if a>10 then

      begin

        MessageBox(Application.Handle,'Максимальное число стратегий равно 10.','Внимание', MB_OK);

        edit1.Text:='10';

      end;

    val(edit2.Text,a,c);

     if a>10 then

      begin

        MessageBox(Application.Handle,'Максимальное число стратегий равно 10.','Внимание', MB_OK);

        edit2.Text:='10';

      end;

  form3.show;

  form2.Hide;

  end;

end;

procedure TForm2.Edit1KeyPress(Sender: TObject; var Key: Char);

const Digit: set of Char=['1'..'9', '0'];

begin

with (Sender as TEdit) do

   begin

        if (not(Key in Digit))

        then Key:=#0;

   end;

end;

procedure TForm2.Edit2KeyPress(Sender: TObject; var Key: Char);

const Digit: set of Char=['1'..'9', '0'];

begin

with (Sender as TEdit) do

   begin

        if (not(Key in Digit))

        then Key:=#0;

   end;

end;

 

procedure TForm2.FormClose(Sender: TObject; var Action: TCloseAction);

begin

form1.close;

end;

end.

 

unit Unit3;

interface

uses

  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

  Dialogs, StdCtrls, Grids, Math;

type

  TForm3 = class(TForm)

    Label1: TLabel;

    StringGrid1: TStringGrid;

    Button1: TButton;

    procedure FormClose(Sender: TObject; var Action: TCloseAction);

    procedure FormActivate(Sender: TObject);

    procedure Button1Click(Sender: TObject);

    procedure StringGrid1KeyPress(Sender: TObject; var Key: Char);

  private

    { Private declarations }

  public

    { Public declarations }

    n,m:integer;

    matrix: array[1..10,1..10] of integer;

    simp: array[1..66,0..23] of real;

    minMatrix, maxMatrix:array[1..10] of integer;

    maxmin,minmax,kolshag:integer;

  end;

var

  Form3: TForm3;

  i,j,k,kod:integer;

implementation

uses Unit1, Unit2, Unit4;

{$R *.dfm}

function sedlo:boolean;

begin

  form3.minmax:=0;

  form3.maxmin:=0;

  // по стратегиям первого игрока

  for i:=1 to form3.m do

  begin

    form3.minMatrix[i]:=form3.matrix[i,1];

    for j:=2 to form3.n do

      if form3.minMatrix[i]>form3.matrix[i,j] then

         form3.minMatrix[i]:=form3.matrix[i,j];

  end;

    form3.maxmin:=form3.minMatrix[1];

    for j:=2 to form3.n do

      if form3.maxmin<form3.minMatrix[j] then

        form3.maxmin:=form3.minMatrix[j];

  // по стратегиям второго игрока

  for j:=1 to form3.n do

  begin

    form3.maxMatrix[j]:=form3.matrix[1,j];

    for i:=1 to form3.m do

      if form3.maxMatrix[j]<form3.matrix[i,j] then

         form3.maxMatrix[j]:=form3.matrix[i,j];

  end;

    form3.minmax:=form3.maxMatrix[1];

    for j:=2 to form3.m do

      if form3.minmax>form3.maxMatrix[j] then

        form3.minmax:=form3.maxMatrix[j];

  if form3.maxmin=form3.minmax then

    sedlo:=true

  else

    sedlo:=false;

end;

procedure simplex;

var mi,minSO,del,v:real; nomMi,shag,nomSO,neopt:integer; x,y:array[1..10]of real;

begin

    // заполнение первоначальной  матрицы

   for i:=1 to form3.n do

     form3.simp[i,0]:=form3.m+i;

 

   for i:=1 to form3.n do

   begin

    for j:=1 to form3.m do

      form3.simp[i,j]:=form3.matrix[j,i];

    for j:=form3.m+1 to form3.m+form3.n do

      if i=j-form3.m then

        form3.simp[i,j]:=1

      else

        form3.simp[i,j]:=0;

    end;

    for j:=1 to form3.m do

      form3.simp[form3.m+1,j]:=-1;

    for j:=1 to form3.n do

      form3.simp[j,form3.m+form3.n+1]:=1;

    for j:=form3.m+1 to form3.m+form3.n+1 do

      form3.simp[form3.m+1,j]:=0;

      shag:=0;

    repeat

    // поиск минимального в F строке

    mi:=form3.simp[shag+form3.n+1,1];

    nomMi:=1;

    for j:=1 to form3.m+form3.n do

      if mi>form3.simp[shag+form3.m+1,j] then

      begin

        mi:=form3.simp[shag+form3.m+1,j];

        nomMi:=j;

      end;

    for i:=1 to form3.n do

      if form3.simp[shag+i,nomMi]<>0 then

        form3.simp[shag+i,form3.m+form3.n+2]:=form3.simp[shag+i,form3.m+form3.n+1]/form3.simp[shag+i,nomMi];

    // минимальное с.о.

    i:=1;

    while form3.simp[shag+i,form3.m+form3.n+2]=0 do i:=i+1;

    minSO:=form3.simp[shag+i,form3.m+form3.n+2];

    nomSO:=shag+i;

    for j:=i+1 to form3.n do

      if minSO>form3.simp[shag+j,form3.m+form3.n+2] then

      begin

         minSO:=form3.simp[shag+j,form3.m+form3.n+2];

         nomSO:=shag+j;

      end;

      shag:=shag+11;

    //шаг С.М.

    del:=form3.simp[nomSO,nomMi];

    for j:=1 to form3.m+form3.n+1 do

      form3.simp[nomSO+11,j]:=form3.simp[nomSO,j]/del;

    for i:=1 to form3.n do

     form3.simp[i+shag,0]:=form3.simp[i+shag-11,0];

    form3.simp[nomSO+11,0]:=nomMi;

    for i:=shag-10 to shag+form3.n-10 do

    if i<>nomSO then

    begin

       del:=form3.simp[i,nomMi];

       for j:=1 to form3.m+form3.n+1 do

        form3.simp[i+11,j]:=form3.simp[i,j]-form3.simp[nomSO+11,j]*del;

    end;

    //проверка на  оптимальность

    neopt:=0;

    for i:=1 to form3.m+form3.n do

      if form3.simp[form3.n+1+shag,i]<0 then

        neopt:=1;

    until neopt=0;

    form3.kolshag:=(shag div 11)+1;

    // получение решения

    v:=1/form3.simp[(form3.kolshag-1)*11+form3.n, form3.m+form3.n+1];

    for i:=1 to form3.n do

      y[round(form3.simp[i+shag,0])]:= form3.simp[i+shag,form3.m+form3.n+1];

    for i:=1 to form3.m do

      x[i]:= form3.simp[form3.n+1+shag,i+form3.n];

    form4.label4.caption:='Стратегия первого игрока (';

    for i:=1 to form3.m-1 do

        form4.label4.caption:=form4.label4.caption+FloatToStr(RoundTo(x[i],-2))+';';

    form4.label4.caption:=form4.label4.caption+FloatToStr(RoundTo(x[form3.m],-2))+')';

    form4.label5.caption:='Стратегия второго игрока (';

    for i:=1 to form3.n-1 do

        form4.label5.caption:=form4.label5.caption+FloatToStr(RoundTo(y[i],-2))+';';

    form4.label5.caption:=form4.label5.caption+FloatToStr(RoundTo(y[form3.n],-2))+')';

    form4.label6.caption:='Цена игры равна '+FloatToStr(RoundTo(v,-2));