Елементи теорії ігор 7 клас

ЕЛЕМЕНТИ ТЕОРІЇ ІГОР7 КЛАСГРУЗДЬОВА К.І.

ЗМІСТІгрові моделі прийняття рішень. Класифікація ігорІгри жарти

За умов ринкової економіки все частіше мають місце конфліктні ситуації, коли два або більше колективів (індивідуумів) мають протилежні цілі та інтереси, причому результат дії кожної із сторін залежить від дії супротивника. Класичний приклад - це відношення продавець покупець.

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

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

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

КЛАСИФІКАЦІЯ ІГОР1) за кількістю гравців; 2) за результатом гри; 3) за кількістю ходів; 4) за кількістю інформації про характер ситуації, що склалася, і про наміри противника; 5) за кількістю стратегій; 6) за характером взаємовідносин.

ЗА КІЛЬКІСТЮ ГРАВЦІВпарнімножинні

ЗА РЕЗУЛЬТАТОМ ГРИІгри з нульовою сумоюІгри з ненульовою сумою

повною інформацієюнеповною інформацією. ЗА КІЛЬКІСТЮ ІНФОРМАЦІЇ

Скінченна кільність стратегій. Нескінченна кількість стратегій. ЗА КІЛЬКІСТЮ СТРАТЕГІЙ

БезкоаліційніКооперативні, коаліційніЗА ХАРАКТЕРОМ ВЗАЄМОВІДНОСИН

ІГРИ ЖАРТИНайперший і простий клас ігор - ігри-жарти, в яких, насправді, немає ніякої стратегії (а нас хочуть обдурити, що вона нібито є!). Просто як би хто не ходив, або завжди виграє перший гравець (той, хто починає гру), або завжди другий.

ЗАДАЧА 1. Двоє по черзі ламають шоколадку 5x8. За хід можна розламати будь-який шматок по прямій лінії між часточками. Програє той, хто не може зробити хід (І це  стандартна  умова, що ми її будемо мати на увазі, якщо не сказано протилежне. Питання "хто виграє при правильній грі?")Часточок завжди буде 5x8 = 40 штук, а шоколадка на початку була одна. Зауважимо, що на кожному ходу один шматок шоколадки завжди розламується на 2, тобто кількість різних шматків шоколадки збільшується на 1. На початку ця кількість дорівнює 1, а в кінці, як ми помітили, 40. Значить, гра тривала рівно 39 ходів ("ходом" ми називаємо хід одного гравця, а не пару "хід - хід"). Тому останній (39-й) хід був обов'язково ходом першого (його ходи - перший, третій і всі з непарними номерами) - і перший виграв. Ось такий вийшов жарт - як не ходи, перший завжди виграє.

ЗАДАЧА 2. На дошці написані 10 нулів і 10 одиниць. За хід можна стерти дві будь-які цифри і написати замість них 0, якщо вони були однакові або 1, якщо вони були різні. Якщо на дошці залишається 1 - виграє перший. Якщо 0 - другий.{2 B7 CCC81-8680-4985-9 AF8-B8 EC5 FF913 B6}00111100001111000011 Ну, оскільки число цифр з кожним ходом зменшується рівно на 1 (2 стираємо, одну пишемо), а на початку їх 20 і в кінці повинна залишитися одна, то гра буде продовжуватися рівно 19 ходів. Останнім ходом буде хід  першого , тільки в цьому завданні не факт, що перший тоді виграє. Виграш залежить від парності останнього числа, звернемо на це увагу. Дійсно, сума двох однакових цифр - парна і, віднімаючи її, ми додаємо парний нуль. А сума двох різних цифр - непарна (0 +1 = 1), і ми додаємо замість неї непарну одиницю. Початкова сума всіх чисел парна, тому що серед них парне число непарних – одиниць, тому і в кінці буде парна. А це означає, що останнє число, що залишилося в кінці гри, буде парне, тобто воно буде нулем - і виграє другий.

ЗАДАЧА 3. На дошці 10x12 можна за хід викреслити одну лінію (горизонталь або вертикаль, тобто рядок або стовпець) якщо в ній ще є одна невикреслена клітина. Програє той, хто не зможе зробити хід. Нехай раптом після свого ходу залишили, скажімо, дошку з одним рядком. Звичайно, своїм ходом суперник може вирізати цей рядок - і ми програємо. Тому такий хід був «дурним» - давайте так його і називати. Подивимося, коли не можна буде не зробити «дурного»  ходу.  Якщо дошка 1x. N (або Nx1) - то такий хід уже зробив супротивник. Якщо ширина і висота дошки не менше 2, а більша з них - не менше 3 - то виріжемо лінію поперек більшої розмірності - і залишиться дошка хоча б 2x2. А от якщо перед ходом дошка - 2x2, то хід обов'язково буде «дурний». Ясно, що виграє той, хто залишить противнику дошку 2x2. На кожному ходу висота або ширина дошки зменшується на 1 (тобто, їх сума зменшується на 1). Початково ця сума дорівнює 10 +12 = 22, в кінці повинна стати 2 +2 = 4. Різниця 22-4 = 18 - парне число ходів, тому дошка 2x2 залишиться після ходу другого - і другий виграє (як у звичайній грі-жарті!).

ЗАДАЧА 3. На дошці 10x12 можна за хід викреслити одну лінію (горизонталь або вертикаль, тобто рядок або стовпець) якщо в ній ще є одна невикреслена клітина. Програє той, хто не зможе зробити хід. Строго кажучи: стратегія другого - грати як завгодно, тільки не роблячи «ідіотських» ходів. Якщо перший десь зробить «ідіотський» хід (а це формально заважає загнати його на дошку 2x2) - наступним ходом виграємо. Якщо ніхто не зробить «дурного» ходу - то після 18 ходів у першого буде дошка 2x2 - і тут він все одно зробить «дурний» хід. Симетрія. Це  потужний красивий, але дуже простий методом розв’язання  ігрових завдань - симетрична стратегія. Суть його - робити щоразу хід, симетричний ходу супротивника або доповнює його до чого-небудь.

ЗАДАЧА 4. Є дві купки каміння, по 17 у кожній. За хід можна взяти кілька каменів, з однієї купки. Програє той, хто не може зробити хід.І це теж симетрія! Виграє другий - він бере з іншої купки стільки каменів, скільки перший взяв з однієї. При цьому після кожного ходу другого каменів в обох купках буде порівну - тому стратегію можна продовжувати. А якби купки були нерівні, то виграв би перший. Першим ходом він взяв би з більшою купки стільки каменів, щоб зрівняти її з меншою, а далі користувався б стратегією симетрії. Насправді, нерідке явище: в залежності від вихідних даних одна і та ж стратегія приносить успіх то першому, то другому гравцеві.

ДОМАШНЄ ЗАВДАННЯДано клітчасту дошку 10 х 10. За хід дозволяється по­крити будь-які 2 сусідні клітинки прямокутником 1x2 так, щоб пря­мокутники не перекривались. Програє той, хто не може зробити хід. Хто забезпечить собі  виграш?