астосовує свою оптимальну стратегію, дорівнює гарантованому програшу другого гравця, застосовує свою оптимальну стратегію: - ціна гри.
Зведення задачі теорія ігор до задачі лінійного програмування
Задача максимізації гарантованого виграш першого гравця та завдання мінімізації гарантованого програшу другого гравця зводяться до пари взаємно двоїстих задач лінійного програмування:
Завдання першого гравця
Завдання другого гравця
Процес розв'язання завдань спрощується, якщо перейти до Змінним. Це можливо, якщо.
Маємо:
Завдання першого гравця
Завдання другого гравця
Оптимальні стратегії гравців не зміняться, якщо матрицю ігризаменіть на. Ціна гри при цьому збільшується на з .
Методи рішення задач теорії ігор багато в чому залежать від умов завдання і від матриці А виграшів першого гравця.
Якщо матриця А має сідлову точку, то рішення гри зводиться до знаходження сідлової точки матриці А. Оптимальні стратегії гравців визначаються при цьому координатами ( i , j ) сідлової точки матриці А, а ціна гри елементом в сідловій точці.
Якщо задача теорії ігор не має рішення в чистих стратегіях, то може бути вирішена ітераційним методом.
Ітераційний метод.
Розігрується уявний експеримент, в якому гравці А і В застосовують проти один
одного свої стратегії. Експеримент складається з послідовності партій. А вибирає стратегію
Аi, гравець В уже знає про цьому і відповідає своєю стратегією Вj, найбільш вигідною для нього в сформованій ситуації. Далі, перший гравець вибирає подальші стратегії грунтуючись на попередній грі. Таким чином, на кожному кроці ітераційного процесу гравець відповідає на крок іншого тій своєю стратегією, яка є оптимальною щодо всіх попередніх ходів. Якщо партії продовжувати досить довго, то середній виграш прагне до ціни гри, а частоти - до ймовірностям оптимальних стратегій. Головним достоїнством цього методу є незалежність його складності від розмірності гри.
4. Реалізація програмного засобу
середу розробки: С + + Builder XE
Мова програмування: C + +
4.1 Проектування
Список модулів з коротким описом:
1) Mainform.cpp - це головний модуль в якому, реалізовані функції: розрахунку в чистих стратегіях, збереження/завантаження і введення вихідних даних.
2) Iter. cpp - це допоміжний модуль в якому реалізований ітераційний метод розв'язання матричної гри.
4.2 Лістинг програмного коду
Модуль Mainform . cpp :
// --------------------------------------------- ------------------------------
# include
# pragma hdrstop
# include "Series.hpp"
# include "Iter.h"
# include "Pic.h"
# include "Mainform.h"
# include
# include
// --------------------------------------------- ------------------------------
# pragma package (smart_init)
# pragma resource "*. dfm"
TForm1 * Form1;
// --------------------------------------------- ------------------------------
__fastcall TForm1 :: TForm1 (TComponent * Owner)
: TForm (Owner)
{
}
// --------------------------------------------- ------------------------------
void __fastcall TForm1 :: RaschetClick (TObject * Sender)// розрахунок
{
double MaxMin = 0, MinMax = 0;
double MinRow [100];
double MaxCol [100];
int i, j, n, m;
double A0 [100] [100];
n = StrToInt (Edit4-> Text);
m = StrToInt (Edit5-> Text);
for (i = 0; i
for (j = 0; j
// переклад значень з таблиці в масив double матриці A0:
A0 [j] [i] = StrToFloat (StringGrid1-> Cells [i +1] [j +1]);
}
}
// --------------------- розрахунок у чистих стратегіях -----------------------------
for (i = 0; i
MinRow [i] = A0 [i] [0];
}
for (i = 0; i
MaxCol [i] = A0 [0] [i];
}
// очистимо стрінгріди 2 і 3:
for (register int i = 0; i RowCount; i + +)
{
StringGrid2-> Rows [i] -> Clear ();
}
for (register int i = 0; i RowCount; i + +)
{
StringGrid3-> Rows [i] -> Clear ();
}
StringGrid2-> Cells [0] [0] = "Min";
StringGrid3-> Cells [0] [0] = "Max";
// розрахунок мінімумів і максимумів
for (i = 0; i
for (j = 0; j
// пошук мінімального значення в рядках:
if (A0 [i] [j] <= MinRow [i]) {
MinRow [i] = A0 [i] [j];
}
}
// вивід мінімумів рядків у СтрінгГрід2:
StringGrid2-> Cells [0] [i +1] = MinRow [i];
}
for (j = 0; j
for (i = 0; i
// пошук максимального значення у стовпцях:
if (A0 [i] [j]> = MaxCol [j]) {
MaxCol [j] = A0 [i] [j];
}
}
// вивід максимумів стовпців в СтрінгГрід3:
StringGrid3-> Cells [j +1] [0] = MaxCol [j];
}
// знайдемо максимін
MaxMin = MinRow [0];
for (i = 0; i
if (MinRow [i]> = MaxMin) {MaxMin = MinRow [i];}
}
Edit2-> Text = MaxMin;
// знайдемо мінімакс
MinMax = MaxCol [0];
for (i = 0; i
if (MaxCol [i] <= MinMax) {MinMax = MaxCol [i];}
}
Edit3-> Text = MinMax;
if (MinMax == MaxMin) {
ShowMessage ("Гра вирішена в чистих стратегіях ");
Edit1-> Text = MinMax;
} else {ShowMessage ("Гра не вирішується в чистих стратегіях, спробуєте вирішити її ітераційним методом ");}
// --------------------------------------------- ---------------------------------
}
// --------------------------------------------- ---------------------------------
void __fastcall TForm1 :: Button1Click (TObject * Sender)
{
Form2-> Show ();
}
// --------------------------------------------- ------------------------------
void __fastcall TForm1 :: Button2Click (TObject * Sender)
{
int i, j, n, m;
double A0 [100] [100];
n = StrToInt (Edit4-> Text);
m = StrToInt (Edit5-> Text);
// очищаємо СтрінгГрід1:
for (register int i = 0; i RowCount; i + +) {
StringGrid1-> Rows [i] -> Clear ();
}
for (i = 0; i
StringGrid1-> Cells [0] [i +1] = "A" + String (i +1);
}
for (i = 0; i
StringGrid1-> Cells [i +1] [0] = "B" + String (i +1);
}
}
// --------------------------------------------- ------------------------------
void __fastcall TForm1 :: SaveClick (TObject * Sender)
{
int n, m;
n = StrToInt (Edit4-> Text);
m = StrToInt (Edit5-> Text);
// збереження у файл
SaveTextFileDialog1-> Execute ();
SaveTextFileDialog1-> FileName;
ofstream myfile (SaveTextFileDialog1-> FileName.t_str ());
for (int i = 0; i
for (int j = 0; j
myfile < Cells [j +1] [...
