Зміст
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 * - оптимальна стратегія другого гравця, якщо
Гарантований виграш першого гравця, що з...
