Лабораторна робота №3

Тема: Основи теорії ігор.

Мета: Навчитися розв’язувати ігрові задачі.

 

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

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

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

Правила гри. Гравці по черзі беруть сірники з загальної купи, яка спочатку містить N сірників. За один хід можна взяти 1, 2 або 4 сірники. Пропускати ходи не можна. Програє той, хто бере останній сірник (або сірники), тобто, той, хто робить останній хід, після якого подальша гра неможлива.

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

Отже, оскільки можливість взяти 1, 2 або 4 сірники існує завжди, то ці ходи можна представити альтернативним правилом хід_гравця (скільки_взяв)

 

хід_гравця (скільки_взяв):- скільки_взяв = 1.

хід_гравця (скільки_взяв):- скільки_взяв = 2.

хід_гравця (скільки_взяв):- скільки_взяв = 4.

 

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

скільки_залишається = загальна_кількість - скільки_взяв,

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

Правило виграшу. Для представлення умови виграшу спробуйте сконцентрувати правила гри в невеликій кількості тверджень, які ми будемо називати «Виграє». Отже, наново сформулюємо умови гри так:

«Виграє при загальній кількості такий хід гравця, після якого залишається така загальна кількість, при якій суперник не виграє».

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

 

Виграє (загальна_кількість, скільки_взяв):-

         хід_гравця (скільки_взяв),

         скільки_залишається = загальна_кількість - скільки_взяв,

        скільки_залишається>0,

        not (Виграє (скільки_залишається, довільний_хід)).

 

Зрештою, всі виграшні ходи можна представити таблицею: ігрова ситуація – виграшний хід.

Мета програми – це перше твердження, з якого починається процес обчислень. Отже, в нашому випадку можна сформулювати таку мету:

 

Знаходження_вірного_ходу:-  загальна_кількість=15,

                                               Виграє(загальна_кількість, скільки_взяв),

                                                write("Треба взяти", скільки_взяв), fail.

 

Завдання 1. Знайдіть таблицю виграшних ходів, коли загальна_кількість коливається від 1 до 20. Для цього скористайтеся твердженням циклу:

cycle (N, Begin, End):- End = Begin, N = Begin.

cycle (N, Begin, End):- End > Begin, N = Begin.

cycle (N, Begin, End):- End > Begin, New=Begin+1, cycle (N, New, End).   Прокоментуйте отримані результати.

Завдання 2. Модифікуйте програму так, щоб гравець 1 міг брати {1,2,4} сірників, а гравець 2 міг брати {1,2,3} сірники. Який гравець має більше можливостей виграти?

Завдання 3. Модифікуйте програму так, щоб було 3 учасники, і гравці 2 і 3 об’єдналися проти першого за правилом {1,2,4}. В яких випадках гравець 1 може перемогти?