Презентація на тему «Теорія Ігор»

Теорія Ігор

Коротко з історії
Математична теорія ігор бере свій початок з неокласичної економіки. Вперше математичні аспекти та застосування теорії були викладені у класичній книзі 1944 Джона фон Неймана і Оскара Моргенштерна "Теорія ігор і економічна поведінка".

Поняття теорії ігор
Логічною основою теорії ігор є формалізація трьох понять, які входять в її визначення і є фундаментальними для всієї теорії:
Конфлікт
Прийняття рішення в конфлікті
Оптимальність прийнятого рішення

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

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

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

Симетричні і несиметричні ігри
Гра буде симетричною тоді, коли відповідні стратегії у гравців будуть рівні, тобто матимуть однакові платежі.
У прикладі праворуч гра на перший погляд може здатися симетричною через схожі стратегії, але це не так - адже виграш другого гравця при профілях стратегій (А, А) і (Б, Б) буде більше, ніж у першого.
А
Б
А
1, 2
0, 0
Б
0, 0
1 ,2

Математика в іграх двох осіб
Ігри двох осіб – це конкретні інтелектуальні ігри. Вони характеризуються такими основними рисами:
у кожній грі беруть участь двоє гравців;
суть гри в тому, що суперники по черзі виконують певні дії – «ходи»; кількість ходів скінченна (хоча, можливо, і як завгодно велика);
умовою (правилами) гри обумовлено, в чому полягає заключна виграшна позиція; виграє той з гравців, хто першим досягне виграшної позиції;
гра є відкритою для обох гравців, тобто в будь-який момент гри кожен із гравців має повну інформацію про її перебіг.

Приклади ігорПриклад 1
Правила гри такі. На купці лежать 53 камінці. Кожен із двох гравців за один хід може взяти будь-яку кількість камінців від 1 до 4. Виграє той, хто забере останній камінець. У кого з гравців – того, який робить перший хід (назвемо його першим), чи його суперника (назвемо його другим), - є виграшна стратегія і в чому вона полягає?

Розв'язання
Розмістимо умовно ці камінці в ряд, пронумерувавши їх числами від 1 до 53 у порядку, зворотному до того, в якому їх братимуть з купки (тобто вважатимемо, що першим братиметься камінець з номером 53, а останнім – з номером 1. Для того щоб останнім ходом (нехай під номером n) забрати камінець з номером 1 (і таким чином виграти гру), першому гравцеві після попереднього n-1 ходу суперника повинна залишитися будь-яка кількість камінців від 1 до 4. Для того щоб примусити другого гравця залишити саме таку кількість камінців, а не, скажімо, 6 чи 7 (що для першого гравця було б «катастрофою»), першому гравцеві після n-2 ходу потрібно залишити рівно 5 камінців. Тоді яку б кількість – 1, 2, 3 чи 4 не взяв другий гравець, перший останнім своїм ходом зможе забрати залишок.
53 52 51 50 49… …3 2 1

Відповідно, після n-4 ходу першого гравця повинно залишитися 10 камінців, після n-6 ходу – 15 камінців і т.д.
Отже, «вихід» на номери, кратні, 5, забезпечує першому гравцю можливість гарантовано здобути перемогу в грі. А для цього йому потрібно першим своїм ходом взяти 3 камінці з даних 53-х. Далі після кожного ходу суперника слід брати таку кількість камінців, щоб залишилося число, кратне 5. Це і є виграшна стратегія, причому існує вона для першого гравця.

Приклад 2
Альоша Попович і Добриня Микитич воюють з дев'ятиглавим змієм. По черзі богатирі ходять до його печери й відрубують 1, 2 чи 3 голови. Як Альоша, який почав бій першим, зможе одержати славу переможця змія (тобто відрубає останню голову)?

Розв'язання
Альоша відрубує 1 голову.
Якщо Добриня відрубує 1 голову,
Альоша відрубує 3 голови.
Добриня – 2 голови,
Альоша - 2 голови.
або
Добриня – 3 голови,
Альоша – 1 голову.
У будь-якому випадку у змія залишається 4 голови. Далі скільки голів не відрубав Добриня, Альоша відрубує решту голів одним ударом.
VS

Приклад 3
У грі «Хто першим назве число 100» беруть участь двоє. Один називає будь-яке натуральне число від 1 до 9 включно. Другий додає до названого числа будь-яке натуральне число від 1 до 9, і називає нову суму. До цієї суми перший також додає будь-яке натуральне число від 1 до 9, і називає суму. Виграє той, хто першим називає число 100. Який найкращий початок цієї гри?

Розв'язання
Як почати гру, не має значення. Другий гравець виграє, називаючи числа, які діляться на 10.

Висновки
Під час написання наукової роботи я опрацювала теоретичний матеріал з теми “Теорія ігор”. Також я опрацювала літературу з данної тематики, розібралася із розв'язаними прикладами та на їх основі за допомогою вказівок до задач самостійно розв'язала деякі приклади.

ДЯКУЮ ЗА УВАГУ!