DataLife Engine > Версия для печати > Рішення матричних ігор

Зміст

1. Мета роботи .. 2

2. Завдання. 3

3. Короткі теоретичні відомості. 4

4. Реалізація програмного засобу. 12

4.1 Проектування. 12

4.2 Лістинг програмного коду. 12

5. Приклад роботи програми .. 20

Висновки .. 21

Використана література. 22

Використовувані програмні засоби. 22

1. Мета роботи

Необхідно розробити програмний засіб для вирішення матричних ігор.

програма матриця гра ітераційний лістинг
2. Завдання

1. Задати матрицю гри вручну і випадковим чином.

2. Знайти оптимальні стратегії гравців, використовуючи ітераційний метод і методом чистих стратегій.

3. Зробити можливість зберігати матрицю гри і завантажувати з файлу.

3. Короткі теоретичні відомості

Постановка загальної задачі теорії ігор

Теорія ігор - математична теорія конфліктних ситуацій. Економічні змагання, спортивні зустрічі, бойові операції - приклади конфліктних ситуацій. Найпростіші моделі конфліктних ситуацій - це салонні і спортивні ігри.

У грі можуть стикатися інтереси двох супротивників (Гра парна або гра двох осіб), інтереси n ( n > 2) супротивників (гра множинна або гра n осіб). Існують ігри з нескінченною безліччю гравців.

Стратегією гравця називається система правил, однозначно визначають вибір поведінки гравця на кожному ході в залежності від ситуації, що склалася в процесі гри. Залежно від числа можливих стратегій ігри поділяються на кінцеві і нескінченні.

Процес гри полягає у виборі кожним гравцем i однією своєю стратегіі.В результаті сформованої ситуації s гравець i отримує виграш.

Ігри, в яких метою кожного учасника є отримання якомога більшої індивідуального виграшу, називаються безкоаліційний на відміну від коаліційних, в яких дії гравців спрямовані на максимізацію виграшів колективів (коаліції) без подальшого поділу виграшу між учасниками.

За визначенням безкоаліційний грою називається система

в якій I і - множини, - функції на множині приймають речові значення.

безкоаліційний гра називається грою з постійною сумою, якщо існує таке постійне C , що для всіх ситуацій.

Ситуація s в грі називається прийнятною для гравця i , якщо цей гравець, змінюючи в ситуації s свою стратегію s i на яку-небудь іншу s i ', не може збільшити свого виграшу.

Ситуація s , прийнятна для всіх гравців, називається ситуацією рівноваги.

Процес знаходження ситуації рівноваги в безкоаліційний грі є процес вирішення гри.

Матричні ігри

Гра називається парною, якщо в ній стикаються інтереси двох супротивників. Гра називається з нульовою сумою, якщо один гравець виграє стільки, скільки другій програє в тій же партії.

Кожна фіксована стратегія, яку може вибрати гравець, називається його чистою стратегією.

Матричної називають парну гру з нульовою сумою при умови, що кожен гравець має кінцеве число чистих стратегій.

Нехай перший гравець має m чистих стратегій, а другий - n .

Парна гра з нульовою сумою задається 'формально системою чисел - матрицею, елементи якої визначають виграш першого гравця (і відповідно програш другого), якщо перший гравець вибере i -й рядок ( i -ю стратегію), а другий гравець j -й стовпець ( j -ю стратегію). Матриця називається платіжною матрицею або матрицею гри.

Завдання першого гравця - максимізувати свій виграш.

Завдання другого гравця - максимізувати свій виграш - зводиться до мінімізації програшу другого, що еквівалентно задачі мінімізації виграшу першого гравця.

Чисті стратегії

Гарантований виграш першого гравця, що застосовує чисту i -ю стратегію,

Число називається нижнім значенням гри, а відповідна чиста стратегія i 0 , при якої досягається називається Максимін стратегією першого гравця. Аналогічно, називається верхнім значенням гри а j 0 - мінімаксного стратегією другого гравця.

Завжди. Якщо то гра має сідлову точку в чистих стратегіях; число називається значенням гри (або ціною ігри ). Гра має сідлову точку в чистих стратегіях тоді і тільки тоді, коли існує елемент матриці, мінімальний у своєму рядку і в Водночас максимальний в стовпці

Будь-яка пара ( i 0 , j 0 ), володіє властивістю (10.1), називається сідловою точкою .

Змішані стратегії

Якщо позначити через x 1 , x 2 , ..., x m ймовірності (частоти), з якими перший гравець вибирає відповідно першу, другу,. . ., M -ю чисту стратегію, так що через; через y 1 , y 2 , ... , y n ймовірності, з якими другий гравець вибирає першу, другу,, .., n -ю свою чисту стратегію, причому, то набори чисел x = ( x 1 , x 2 , ..., x m ) і y = ( y 1 , y 2 , ..., y n ) називаються змішаними стратегіями першого і другого гравців відповідно. Кожен гравець має незліченну кількість змішаних стратегій. Безліч змішаних стратегій першого гравця позначимо через s 1 і безліч змішаних стратегій другого гравця - через s 2 .

Завдання першого гравця полягає у виборі такої стратеги щоб при відсутності інформації про вибір іншого максимізувати свій виграш. Завдання другого гравця полягає у виборі такої стратегії, щоб при відсутності інформації про поведінку першого гравця мінімізувати виграш першого.

Якщо перший гравець застосовує стратегію, а другий - стратегію то середній виграш M ( x , y ) першого гравця дорівнює

Виграш M ( x , y ) називають функцією гри.

Наприклад, в задачі з матрицею

перший гравець має дві чисті стратегії, і незліченну безліч змішаних стратегій, таких, як, і т. д.; всі вони є елементами безлічі другий гравець має чотири чисті стратегії і незліченна безліч змішаних стратегій, таких, як, що є елементами безлічі

Якщо перший гравець застосовує змішану стратегію, а другий застосовує стратегію, то середній виграш першого гравця, який визначається функцією гри, виявиться рівним

Якщо ж перший гравець застосовує стратегію, а другий - стратегію, то. Оптимальна стратегія першого гравця другого гравця;-ціна гри.

Сідлова точка в змішаних стратегіях

Пара змішаних стратегій ( х * , у * ) називається сідловою точкою функції М ( х , у ), якщо

Кожна матрична гра з нульовою сумою має рішення в змішаних стратегіях, тобто існують такі змішані стратегії х * і y * першого і другого гравців відповідно, що виконується умова (10.2). Гарантований виграш першого гравця, який застосовує змішану стратегію

Стратегія х *, при якій гарантований виграш першого гравця досягає максимального значення, називається оптимальної стратегією першого гравця:

Гарантований програш другого гравця

y * - оптимальна стратегія другого гравця, якщо

Гарантований виграш першого гравця, що з...астосовує свою оптимальну стратегію, дорівнює гарантованому програшу другого гравця, застосовує свою оптимальну стратегію: - ціна гри.

Зведення задачі теорія ігор до задачі лінійного програмування

Задача максимізації гарантованого виграш першого гравця та завдання мінімізації гарантованого програшу другого гравця зводяться до пари взаємно двоїстих задач лінійного програмування:

Завдання першого гравця Завдання другого гравця

Процес розв'язання завдань спрощується, якщо перейти до Змінним. Це можливо, якщо.

Маємо:

Завдання першого гравця Завдання другого гравця

Оптимальні стратегії гравців не зміняться, якщо матрицю ігризаменіть на. Ціна гри при цьому збільшується на з .

Методи рішення задач теорії ігор багато в чому залежать від умов завдання і від матриці А виграшів першого гравця.

Якщо матриця А має сідлову точку, то рішення гри зводиться до знаходження сідлової точки матриці А. Оптимальні стратегії гравців визначаються при цьому координатами ( 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

// --------------------------------------------- ------------------------------

# 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] [...i +1]);

myfile <<"";

}

myfile <<" N";

}

myfile.close ();

}

// --------------------------------------------- ------------------------------

void __fastcall TForm1 :: Button4Click (TObject * Sender)

{

int n, m;

n = StrToInt (Edit4-> Text);

m = StrToInt (Edit5-> Text);

// Завантаження файлу

int a;

if (OpenDialog1-> Execute ()) {

OpenDialog1-> FileName;

ifstream loadfile (OpenDialog1-> FileName.c_str ());

for (int i = 0; i

for (int j = 0; j

loadfile>> A;

StringGrid1-> Cells [j +1] [i +1] = IntToStr (a);

}

// StringGrid1 [i +1] [j +1] = ch;

}

loadfile.close ();

}

// --------------------------------------------- ------------------------------

void __fastcall TForm1 :: Button5Click (TObject * Sender)

{

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

A0 [i] [j] = RandomRange (1, 10);

}

// Матрицю в СтрінгГрід1:

for (i = 0; i

for (j = 0; j

StringGrid1-> Cells [j +1] [i +1] = String (A0 [i] [j]);

}

5. Приклад роботи програми

1) Приклад випадково заданої матриці вирішеною в чистих стратегіях:

2) Приклад платіжної матриці не розв'язуваної в чистих стратегіях:

3) Приклад матриці гри розв'язуваної ітераційним методом:

Висновки

У результаті проробленої роботи було розроблено програмний засіб для вирішення матричних задач методом чистих стратегій і ітераційним методом.

Використовувана література

1) Гейл Д. Теорія лінійних економічних моделей. М.: Изд-во іноземної літератури, 1968.

2) Петросян Л.А. Зенкевич Н.А. Сьоміна Е.А. Теорія ігор: Учеб. посібник - М.: Вища. ШК.;: УНІВЕРСИТЕТ, 1998. - 300 с.

3) Орлов, А.І. Теорія прийняття рішень. Навчальний посібник/А.І.Орлов. - М.:

Видавництво В«МартВ», 2004. - 656 с

Використовувані програмні засоби

С + + Builder XE

Вернуться назад