«Стратегічні ігри. Доступний підручник з теорії ігор». Уривок

Розділ 3. Ігри з послідовними ходами

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

Більшість реальних ігор поєднують у собі аспекти ігор як з послідовними, так і з одночасними ходами. Однак концепції і методи аналізу легше зрозуміти, якщо спочатку вони вводяться окремо для двох чистих типів ігор. З урахуванням цього факту в даній главі ми розглядаємо тільки ігри з послідовними ходами. Глави 4 та 5 цілком і повністю присвячені іграм з одночасними ходами, а в главі 6 і в деяких розділах глави 7 показано, як об’єднати ці два типи аналізу в більш реалістичних змішаних ситуаціях. Аналіз, представлений в даному розділі, можна використовувати кожен раз, коли гра включає в себе послідовне прийняття рішень. Крім того, аналіз ігор з послідовними ходами дозволяє визначити, коли гравцеві вигідно робити хід першим, а коли другим. Далі гравці можуть розробити способи маніпулювання порядком гри на свою користь. Аналіз таких способів, які позначаються терміном «стратегічні ходи», представлений у главі 9.

1. Дерево гри

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

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

А. Вузли, гілки та шляхи ігри

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

Якщо Енн вибере «стоп», настане черга Боба робити хід. У вузлі дії Боба у нього є три варіанти вибору, позначені як 1, 2 і 3. Якщо Енн вибере варіант «вперед», тоді наступний хід робить Кріс з варіантами вибору «ризиковано» і «безпечно». Інші вузли і гілки йдуть один за одним, але замість того, щоб перераховувати їх всі кажучи, ми просто звернемо вашу увагу на деякі особливості цього дерева.

Якщо Енн вибере «стоп», після чого Боб вибере 1, Енн отримає право на наступний хід з новими варіантами вибору — «вгору» і «вниз». В реальних іграх з послідовними ходами досить типова ситуація, коли гравець робить кілька ходів, причому ці ходи можуть бути різними в різних вузлах. У шахах, наприклад, два гравці роблять ходи по черзі; кожен такий хід змінює ситуацію на дошці, а отже, змінюються і ходи, наявні в розпорядженні гравця, якому належить зробити наступний хід.

Б. Невизначеність і «ходи природи»

Якщо Енн вибере хід «вперед», а Кріс вибере «ризиковано», відбудеться випадкове подія — наприклад, монета підкидається, а результат гри залежить від того, випаде орел або решка. Цей аспект гри являє собою приклад зовнішньої невизначеності і відображається на дереві гри допомогою введення зовнішнього гравця під назвою «природа». Контроль над випадковою подією передається гравцеві, відомому як «природа», який начебто обирає одну з гілок, кожну з імовірністю 50%. В даному прикладі ймовірність визначена шляхом випадкового події одного типу, а саме підкидання монети, але за інших обставин можуть використовуватися і події інших типів. Наприклад, у разі кидання гральних кісток природа могла б назвати шість можливих варіантів, кожен з імовірністю 16⅔ відсотка. Використання гравця під назвою «природа» дозволяє ввести в гру фактор зовнішньої невизначеності і надає в наше розпорядження механізм, який робить можливим настання подій, що знаходяться поза контролем реальних учасників гри.

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

В. Результати і виграші

В останньому вузлі кожного шляху, який називається кінцевим вузлом, жоден гравець не може зробити черговий хід. (Зверніть увагу на те, що саме в цьому полягає відмінність кінцевих вузлів від вузлів дії.) Замість цього ми показуємо в цьому вузлі результат певної послідовності дій, виражений у виграші гравців. У випадку наших чотирьох гравців ми перераховуємо їх виграші в такому порядку: (Енн, Боб, Кріс, Деб). Важливо вказати, який виграш відповідає кожному гравцеві. Зазвичай прийнято перераховувати виграші в тому порядку, в якому гравці роблять ходи. Однак у деяких випадках цей метод може бути неоднозначним; в нашому прикладі незрозуміло, хто повинен зробити наступний хід, Боб або Кріс. Тому ми перерахували їх в алфавітному порядку (англ. Ann, Bob, Chris, Deb). Крім того, ми використовували кольорове маркування інформації про гравців. Так, ім’я Енн, її варіанти вибору і виграші виділені чорним кольором; у разі Боба це синій колір; для Кріс ми використовували сірий колір, а для Деб — блакитний. При побудові дерев для ігор, які ви будете аналізувати, можна вибрати будь-яку зручну для вас систему позначень, але ви повинні чітко сформулювати та пояснити цю систему того, хто буде читати дерево гри.

Виграш являє собою числову величину; як правило, для кожного гравця чим більше це число, тим краще результат гри. Таким чином, у разі Енн самий нижній шлях (виграш 3) краще самого верхнього шляху (виграш 2). Однак виграші різних гравців не обов’язково повинні бути порівнюваними. В даному прикладі не очевидно, що в кінці самого верхнього шляху Боб (виграш 7) домагається більшого, ніж Енн (виграш 2). В деяких випадках, наприклад,якщо виграш вимірюється у грошових одиницях, таке зіставлення виграшів гравців може мати сенс.

Гравці використовують інформацію про виграші, здійснюючи вибір із сукупності дій, наявних в їх розпорядженні. Включення випадкової події (в якості якого виступає вибір, зроблений «природою») означає, що гравцям необхідно визначити, що вони отримають в середньому, коли «природа» зробить свій хід. Наприклад, якщо Енн вибере «вперед» в якості першого ходу в грі, Кріс може вибрати «ризиковано», що призведе до підкидання монети і вибору «природою» варіанти «добре» або «погано». У такій ситуації Енн може розраховувати на виграш 6 в половині випадків і виграш 2 в половині випадків; іншими словами, статистичне середнє або очікуваний виграш складе 4 = (0,5 × 6) + (0,5 × 2).

Р. Стратегії

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

На даному дереві гри Боб, Кріс і Деб отримують можливість зробити хід максимум один раз; наприклад, Кріс зробить хід тільки у випадку, якщо Енн вибере «вперед» в якості першого ходу. Для цих гравців між ходом і стратегією немає різниці. Ми можемо визначити хід, вказавши умова, при якому він буде зроблений; так, у разі Боба може бути така стратегія: «Вибрати 1, якщо Енн вибере “стоп”». Однак у Енн є дві можливості зробити хід, тому її стратегія вимагає більш повного опису. Одна з стратегій Енн полягає в наступному: «Вибрати “стоп”, а якщо Боб вибере 1, вибрати “вниз”».

У більш складних іграх, таких як шахи, де є довгі послідовності ходів з великою кількістю варіантів вибору в кожній, опис стратегій стає дуже складним; ми обговоримо цей аспект більш докладно трохи нижче в даній главі. Однак загальний принцип побудови стратегій досить простий, за винятком однієї особливості. Якщо Енн вибере «вперед» на першому ході, вона так і не отримає можливості зробити другий хід. Чи слід у стратегії, згідно з якою вона вибирає «вперед», вказувати також те, що вона повинна зробити у гіпотетичному випадку, якби вона якимось чином опинилася у вузлі свого другої дії? Можливо ваша інтуїція говорить «ні», але формальна теорія ігор каже «так» — за двох причин.

По-перше, вибір Енн варіанту «вперед» в якості першого ходу може залежати від її міркувань з приводу того, що їй довелося б зробити на другому ході, якби на самому початку вона вибрала варіант «стоп». Наприклад, якщо Енн вибере «стоп», Боб може вибрати 1; тоді Енн отримає другий хід, а її кращим вибором буде варіант «вгору», що забезпечує їй виграш 2. Якщо Енн вибере «вперед» в якості першого ходу, Кріс вибере варіант «безпечно» (оскільки його виграш 3 у випадку вибору варіанту «безпечно» більше, ніж очікуваний виграш від варіанту «ризиковано»), і такий результат гри забезпечить Енн виграш 3. Для того щоб зробити цей процес роздумів більш зрозумілим, можна сформулювати стратегію Енн так: «Вибрати “вперед” на першому ході, і вибрати “вгору”, якщо з’явиться можливість зробити другий хід».

Друга причина для такого на перший погляд педантичного опису стратегій має відношення до стійкості рівноваги. Аналізуючи стійкість, ми запитуємо, що сталося б, якби вибір гравців був схильний до впливу невеликих перешкод. Однією з таких перешкод є те, що гравці допускають дрібні помилки. Наприклад, якщо б вибір потрібно було робити за допомогою натискання клавіші, Енн могла б спробувати натиснути клавішу «вперед», але є невелика вірогідність того, що у неї здригнулася б рука і вона натиснула б замість цього клавішу «стоп». За таких обставин важливо обумовити, як Енн буде діяти, коли виявить свою помилку, оскільки Боб вибере 1 і наступить черга Енн робити черговий хід. На більш просунутих рівнях теорії ігор такий аналіз стійкості обов’язковий, тому ми хочемо підготувати вас до цього, наполягаючи на тому, щоб ви з самого початку формулювали свої стратегії у вигляді вичерпних планів дій.

Д. Побудова дерева

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

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

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

2. Рішення ігор з допомогою дерев

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

Візьмемо в якості прикладу дівчину на ім’я Кармен, яка вирішує, курити їй чи ні. По-перше, вона повинна вирішити, чи варто їй взагалі пробувати курити. Якщо вона все ж спробує, у майбутньому їй потрібно прийняти рішення, чи продовжувати палити.

Вузли та гілки позначені наявними в розпорядженні Кармен варіантами вибору, проте нам необхідно пояснити виграші. Візьмемо результат гри «ніколи не буде курити» в якості еталону для порівняння і привласнимо йому виграш 0. У числа 0 в цьому контексті немає ніякого особливого сенсу; все, що має значення для порівняння результатів, а значить і для вирішення Кармен —відповідний виграш більше або менше за інших. Припустимо, Кармен найбільше подобається результат гри, при якому вона спробує курити якийсь час, але не стане продовжувати. Причина може бути в тому, що Кармен воліє випробувати все на власному досвіді, або в тому, що це дозволить їй більш переконливо заявити «Я це пробувала і знаю, що нічого хорошого в цьому немає», коли в майбутньому вона спробує відмовити своїх дітей від куріння. Присвоїмо цього результату виграш +1. Найгірший результат гри — коли Кармен спробує курити і продовжить робити це і далі. Навіть якщо залишити в стороні шкоду, що паління може завдати здоров’ю в довгостроковій перспективі, існують і більш актуальних проблем: волосся і одяг Кармен будуть неприємно пахнути, а друзі будуть уникати її. Присвоїмо такого результату виграш -1. У такому випадку вибір Кармен здається очевидним: вона повинна спробувати курити, але їй не варто продовжувати робити це.

Однак в цьому аналізі не враховується проблема залежності. Як тільки Кармен спробує курити якийсь час, у неї сформуються інші смаки і зміняться виграші. Рішення про те, чи варто продовжувати палити, буде приймати не нинішня Кармен з її поточною оцінкою результатів гри в такому вигляді, як показано на рис. 3.2, а майбутня Кармен, яка по-іншому оцінить майбутні альтернативи. Роблячи вибір у даний час, Кармен повинна проаналізувати наслідки цього вибору в майбутньому і врахувати це в поточному рішення, яке вона повинна прийняти на підставі поточних переваг. Іншими словами, проблема вибору, що стосується куріння — це насправді не рішення в тому сенсі, про який йшлося в главі 2 (вибір, зроблений в нейтральному середовищі), а гра у формальному сенсі, також представлена в розділі 2, в якій інший гравець — це майбутнє «я» Кармен зі своїми власними особливими перевагами. Коли нинішня Кармен приймає рішення, вона повинна вести гру з майбутньою Кармен.

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

Враховуючи переваги майбутньої Кармен, пристрастившейся до куріння, у вузлі прийняття рішень вона вибере варіант «продовжувати». Нинішня Кармен проаналізує цю перспективу і прийме його до уваги під час прийняття поточного рішення, усвідомлюючи той факт, що рішення спробувати курити неминуче призведе до того, що вона і надалі буде палити. Нинішня Кармен не хоче продовжувати палити в майбутньому, враховуючи її поточні переваги, проте вона не зможе реалізувати свій поточний кращий вибір у майбутньому, оскільки майбутня Кармен, у якої зовсім інші уподобання, зробить саме такий вибір. Отже, нинішня Кармен повинна передбачати те, що вибір варіанта «спробувати» призведе до подальшого вибору «продовжувати» і забезпечить їй виграш -1 з її поточними оцінками, тоді як вибір варіанта «ні» дасть виграш 0. Таким чином, Кармен слід вибрати друге.

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

В останньому дереві дві гілки, що виходять з першого вузла, в якому вибір робить нинішня Кармен; кожна з цих гілок веде безпосередньо до кінцевого вузла. Таке відсікання дозволяє нинішньої Кармен передбачати всі можливі наслідки кожного свого рішення. Вибір варіанта «спробувати» призведе до вибору «продовжувати» і забезпечить виграш -1 з точки зору переваг нинішньої Кармен, тоді як вибір варіанта «ні» забезпечить виграш 0. У такому разі в поточний момент Кармен повинна вибрати варіант «ні», а не «спробувати». Отже, ми можемо відсікти гілку «спробувати», витікаючу з першого вузла (разом з її передбачуваним продовженням). Показано «повністю обрізану» дерево: на ньому залишилася тільки одна гілка, яка виходить з початкового вузла і веде до кінцевого вузла. Єдиний шлях, що пролягає по дереву гри, показує, що відбудеться в грі, якщо всі гравці зроблять найкращий вибір на підставі правильногопрогнозирования всіх майбутніх наслідків.

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

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

Коли всі учасники гри виконують аналіз методом зворотних міркувань для вибору оптимальних стратегій, ми називаємо таку сукупність стратегій рівновагою зворотних міркувань у даній грі; результат гри, отриманий в результаті виконання цих стратегій — це результат рівноваги зворотних міркувань. У більш складних підручниках з теорії ігор ця концепція позначається як досконалу рівновагу під-ігри; можливо, ваш викладач віддає перевагу саме цьому терміну. Ми наводимо більш формальне пояснення і аналіз скоєного рівноваги під-ігри в главі 6, але ми віддаємо перевагу більш простий і інтуїтивно зрозумілий термін «рівновага зворотних міркувань». Теорія ігор прогнозує такий результат як рівноваги в грі з послідовними ходами, в якій всі гравці є раціональними обчислювачами, прагнуть до отримання максимального виграшу. Трохи нижче в даній главі ми проаналізуємо, як цей прогноз підтверджується практикою. А поки вам слід знати, що у всіх скінченних іграх з послідовними ходами, представлених в даній книзі, має місце мінімум одне рівновагу зворотних міркувань. У дійсності В більшості ігор присутній в точності одне таке рівновагу. У грі може бути більше одного рівноваги зворотних міркувань тільки у виняткових випадках, коли гравець отримує однакові виграші в результаті двох або більше наборів ходів, а значить не може віддати явну перевагу жодному з них.

У грі «куріння» рівновага зворотних міркувань має місце у разі, якщо нинішня Кармен обирає стратегію «ні», а майбутня Кармен обирає стратегію «продовжити». Коли нинішня Кармен здійснює оптимальне дію, пристрастившаяся до куріння майбутня Кармен взагалі не з’являється на світ, а значить і не отримує реальної можливості зробити хід. Однак примарне присутність майбутньої Кармен і стратегія, якій вона віддала б перевагу, якщо б нинішня Кармен вибрала варіант «спробувати» і надала б їй можливість зробити хід — це важливий елемент гри. Насправді саме цей елемент відіграє ключову роль у визначенні оптимального ходу нинішньої Кармен.

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

3. Збільшення кількості гравців

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

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

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

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

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

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

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

Очевидно, що перший з усіх цих результатів гри найкращий, тоді як останній — найгірший. Ми хочемо, щоб більш високі показники виграшів відповідали більш сприятливим наслідків, тому ми присвоюємо першого результату у списку виграш 4, а останньому — виграш 1. (У деяких випадках виграші відповідають порядковому номеру результату у списку результатів. Отже, при наявності чотирьох випадків перший був би найкращим, а четвертий найгіршим, а менші числа позначали б кращі результати. Читаючи книгу з теорії ігор, зверніть особливу увагу на те, яку систему позначень використовує автор; якщо ви пишете про теорії ігор, вам слід точно вказати, яку систему позначень ви використовуєте.)

У двох середніх висліду має місце певна неоднозначність. Припустимо, кожен гравець цінує приємний сад більш високо, ніж свій власний внесок у його створення. У такому разі результат, зазначений у списку другим, забезпечить виграш 3, а результат, зазначений третім — виграш 2.

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

Для того, щоб застосувати до цієї гри метод зворотних міркувань, ми почнемо з тих вузлів дії, які розташовані безпосередньо перед кінцевими вузлами, а саме — з вузлів d, e, f і g. Талія робить хід у кожному з цих вузлів. У вузлі d вона стикається з ситуацією, в якій і Емілі, і Ніна внесли вклад у створення саду. Цей сад вже напевно буде красивим, тому вибравши варіант «не вносити вклад», Талія отримає свій максимальний виграш 4, тоді як вибравши варіант «зробити внесок», вона отримає наступний за розміром виграш 3. Отже, переважний варіант вибору Талії в даному вузлі — «не вносити вклад». Ми відображаємо це перевагу, виділивши відповідну верв жирною лінією і додавши до неї стрілку; будь-якого з цих способів було б достатньо для того, щоб проілюструвати вибір Талії. У вузлі e Емілі вибрала варіант «зробити внесок», а Ніна — «не вносити вклад», тому внесок Талії вкрай важливий для створення красивого саду. Талія отримає виграш 3, якщо вибере «внести вклад» і виграш 2, якщо вибере «не вносити вклад». Її кращий варіант вибору у вузлі e — «зробити внесок». Точно так само можна перевірити вибір Талії в двох вузлах.

Тепер давайте перенесемо аналіз на попередній етап — а саме, на вузли b і c, в яких настає черга Ніни робити вибір. У вузлі b Емілі вирішила внести вклад у створення саду. Тепер Ніна міркує так: «Якщо я виберу варіант “зробити внесок”, це призведе гру у вузол d, в якому, наскільки мені відомо, Талія вибере “не вносити внесок”, і мій виграш складе 3. (Сад буде красивим, а я зможу заощадити на витратах в зв’язку з моїм внеском.) Отже, я повинна вибрати варіант “не вносити вклад”». Аналогічні міркування показують, що у вузлі c Ніна вибере варіант «зробити внесок».

І, нарешті, розглянемо вибір Емілі в початковому вузлі a. Емілі може передбачити подальший вибір як Ніни, так і Талії. Вона знає, що якщо вибере варіант «зробити внесок», далі Ніна вибере «не вносити вклад», а Талія — «зробити внесок». Якщо дві учасниці гри внесуть свій внесок у створення саду, це буде гарний сад, але Емілі понесе витрати, а значить її виграш складе 3. Якщо Емілі вибере варіант «не вносити вклад», тоді у двох наступних один за одним вузлах буде вибрано варіант «зробити внесок», і при наявності гарного саду і відсутності витрат її виграш складе 4. Таким чином, кращий вибір Емілі у вузлі a — варіант «не вносити вклад».

Тепер не складе праці підвести підсумки аналізу гри «вуличний сад» методом зворотних міркувань. Емілі вибере варіант «не вносити вклад», потім Ніна вибере «зробити внесок», і нарешті Талія вибере «зробити внесок». Ця послідовність вибору утворює конкретний шлях гри на цьому дереві, який проходить по нижній гілки, що виходить з початкового вузла, а потім по верхніх гілках в кожному з двох йдуть один за одним наступних вузлів, с та f. На рис. 3.6 цей шлях гри можна легко відстежити як безперервну послідовність стрілок, яка пролягає від початкового до п’ятого кінцевого вузла, якщо вести відлік від верхньої частини дерева. У цьому кінцевому вузлі показано виграші, які отримають учасниці гри.

Аналіз методом зворотних міркувань простий і привабливий. Нижче представлені деякі важливі аспекти такого аналізу. По-перше, зверніть увагу на те, що на рівноважному шляху гри з послідовними ходами відсутня більшість гілок і вузлів. Однак обчислення кращих дій, які були б зроблені, якби гра все ж досягла цих вузлів — це важлива частина процесу пошуку остаточного рівноваги. На ранніх етапах гри її учасниці роблять вибір під впливом своїх очікувань щодо того, що сталося б, якщо б вони обрали дію, відмінне від самого кращого дії, а також очікувань щодо того, що сталося б, якби будь-яка з інших учасниць гри воліла зробити щось таке, що не було б для неї найкращим. Ці очікування, які базуються на прогнозованих діях у вузлах, розташованих поза рівноважного шляху гри (тобто у вузлах, які відповідають гілкам, який знаходився в процесі аналізу методом зворотних міркувань) дозволяють учасницям гри вибирати оптимальні дії в кожному вузлі. Наприклад, оптимальний вибір Емілі «не вносити вклад», зроблений в першому вузлі, залежить від розуміння того, що якщо вона вибере варіант «зробити внесок», тоді Ніна вибере варіант «не вносити вклад», після чого Талія вибере «зробити внесок»; ця послідовність забезпечить Емілі виграш 3 замість виграшу 4, який вона могла б отримати, вибравши варіант «не вносити вклад» на першому ході.

Рівновага зворотних міркувань забезпечує вичерпний опис всього процесу аналізу за допомогою формулювання оптимальної стратегії для кожного гравця. Ми вже говорили про те, що стратегія — це вичерпний план дій. Емілі робить перший хід і у неї є два варіанти вибору, а значить її стратегія досить проста і по суті зводиться до одного ходу. Проте Ніна, яка робить другий хід, вчиняє дію в одному з двох вузлів: в одному — якщо Емілі вибрала варіант «зробити внесок», а в іншому — якщо Емілі вибрала варіант «не вносити вклад». У вичерпному плані дій Ніни повинно бути зазначено, що вона повинна зробити в кожному з цих випадків. Один такий план, або стратегія, зводиться до наступного: «Вибрати “зробити внесок”, якщо Емілі вибрала “зробити внесок”, і вибрати “не вносити вклад”, якщо Емілі вибрала “не вносити вклад”». Завдяки аналізу методом зворотних міркувань ми знаємо, що Ніна не вибере цю стратегію, але на даному етапі нам необхідно опис всіх можливих стратегій, з яких Ніна зможе зробити вибір згідно з правилами гри. Ми можемо скоротити опис стратегій, використовуючи позначення «В» замість «внести вклад» і «Н» замість «не вносити вклад». У такому разі згадану вище стратегію можна описати так: «якщо Емілі вибере, а значить гра перейде у вузол b, Н якщо Емілі вибере Н і гра перейде в вузол», або ще простіше — «В вb, Н c», або навіть «ВН», якщо обставини, при яких кожне з зазначених дій, очевидні або були роз’яснені раніше. Тепер можна побачити, що оскільки у Ніни є два варіанти вибору в кожному з двох вузлів, в яких вона може діяти, в її розпорядженні є чотири плану дій, або стратегії: «В вb, У вс»; «В вb, Н c»; «Н b, У вс» і «Н о b, Н c», або «ВВ», «ВН», «НВ» та «ПН». Аналіз методом зворотних міркувань, а також стрілки у вузлах b і c на рис. 3.6 показують, що оптимальна стратегія Ніни — «НВ».

У разі Талії ситуація ще складніша. Коли настане її черга, історія гра може являти собою будь-який з чотирьох можливих варіантів. Черга діяти переходить до Талії в одному з чотирьох вузлів дерева: один після того, як Емілі вибрала і Ніна вибрала (вузол d); другий після Емілі і Н Ніни (вузол e); третій після Н Емілі і В Ніни (вузол f) і четвертий після того, як та Емілі, і Ніна вибрали Н (вузол g). Кожна з стратегій (або вичерпних планів дій) Талії повинна визначати одне з двох дій по кожному з цих чотирьох сценаріїв, або одне з двох дій в кожному з можливих вузлів дії. При наявності чотирьох вузлів, в яких необхідно вказати дію, і двох дій, з яких необхідно вибрати один кожному вузлі, існує 2 × 2 × 2 × 2, або 16 можливих комбінацій дій. Отже, в розпорядженні Талії є 16 можливих стратегій. Одну з них можна було б записати так:

«У вd, Н в е, Н в f, Ввд» для стислості «ВННВ»

Тут ми зафіксували послідовність чотирьох сценаріїв (історій ходів Емілі і Ніни) в порядку розташування вузлів d, e, f і g. Далі з допомогою такої ж скороченої форми запису можна скласти список всіх 16 стратегій, наявних у розпорядженні Талії:

ВВВВ, ВВВН, ВВНВ, ВВНН, ВНВВ, ВНВН, ВННВ, ВННН, НВВВ, НВВН, НВНВ, НВНН, ННВВ, ННВН, НННВ, НННН

Аналіз методом зворотних міркувань дерева гри на рис. 3.6, а також стрілки у вузлах вузлів d, e, f і g показують, що оптимальна стратегія Талії — НВВН.

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

Ми можемо об’єднати оптимальні стратегії учасниць гри з тим, щоб знайти фактичний шлях гри, який приведе до рівноваги зворотних міркувань. Емілі почне з вибору Н. Ніна, дотримуючись своєї стратегії НВ, обере дію Ст відповідь на дію Емілі Н. (Пам’ятайте: стратегія НВ Ніни означає «вибрати Н, якщо Емілі вибрала, і вибрати, якщо Емілі вибрала Н»). Відповідно до прийнятої нами домовленості, фактичне дію Талії після Н Емілі і В Ніни (з вузла f) позначається третьою буквою в нашому складається з чотирьох букв описі її стратегій. Оскільки оптимальна стратегія Талії — НВВН, її дію шляхом гри — В. Таким чином, фактичний шлях гри складається з дії Н, обраного Емілі, і дії, обраного Ніною і Талією.

Отже, ми маємо три різні концепції.

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

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

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

4. Переваги порядку

У рівновазі зворотних міркувань у грі «вуличний сад» Емілі отримує найкращий результат (виграш 4), оскільки вона може скористатися можливістю зробити перший хід. Прийнявши рішення не вносити свій внесок у створення саду, Емілі перекладає тягар відповідальності на двох інших учасниць гри: кожна з них може отримати наступний кращий результат лише за умови, якщо вони обидві виберуть варіант «зробити внесок». Більшість людей не мають досвіду ведення стратегічних ігор, дотримуються упередженої думки, ніби така перевага першого ходу повинно бути присутнім у всіх іграх. Однак насправді це не так. Можна без праці знайти ігри, в яких перевага полягає в можливості зробити хід другим. Уявіть собі стратегічне взаємодія між двома компаніями, які продають аналогічні товари за каталогами — скажімо, Land’sEnd і L. L. Bean. Якщо б одна компанія випустила свій каталог першої, друга ще до випуску свого каталогу отримала б можливість дізнатися, які ціни встановила перша компанія. Це дозволило б другої компанії запропонувати більш низькі ціни на всі товари, ніж у конкурента, і отримати величезну конкурентну перевагу.

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

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

5. Збільшення кількості ходів

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

Багато широко поширені ігри, такі як хрестики-нулики, шашки та шахи — це стратегічні ігри з двома учасниками, в яких робляться такі чергуються послідовні ходи. Використання дерева ігри і аналізу методом зворотних міркувань теоретично дозволяє вирішити такі ігри, тобто визначити рівноважний результат гри методом зворотних міркувань, а також рівноважні стратегії, що забезпечують такий результат. На жаль, по мірі того як гра стає більш складною, а стратегії більш заплутаними, пошук оптимальної стратегії також стає все більш важким. У таких випадках, коли знайти рішення гри вручну неможливо, на допомогу приходять стандартні комп’ютерні програми, такі як згадана у главі 2 програма Gambit.

А. Хрестики-нулики

Почнемо з гри в хрестики-нулики, найпростішою з згаданих вище ігор, і розглянемо більш легкий варіант гри, в якій кожен з двох гравців (Х і О) намагається першим заповнити двома своїми символами будь-стовпець, ряд або діагональ в грі на полі два на два. У першого гравця є чотири можливі дії або позиції, в яких він може поставити свій хрестик. В такому разі у другого гравця є три можливі дії у кожному з чотирьох вузлів прийняття рішень. Коли перший гравець отримує право зробити другий хід, у нього є два можливі дії у кожному з 12 (4 × 3) вузлів прийняття рішень. Як показано на рис. 3.7, навіть у цій міні-гри «хрестики-нулики» дуже складне дерево гри. Насправді це дерево не таке вже складне, оскільки гра обов’язково закінчиться, після того як перший гравець зробить другий хід. Тим не менш, на цьому дереві все ж є 24 кінцевих вузла, які необхідно проаналізувати.

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

Хоча у цій версії гри в хрестики-нулики цікаве дерево, її рішення не відрізняється особливою змістовністю. Перший гравець завжди виграє, тому вибір, зроблений обома гравцями, не може вплинути на кінцевий результат. Більшості з нас більше знайома гра в хрестики-нулики на полі три на три. Для того щоб проілюструвати цю версію деревом гри, нам довелося б показати, що у першого гравця є дев’ять можливих дій на початковому вузлі, у другого гравця є вісім можливих дій в кожному з дев’яти вузлів прийняття рішення, а потім у першого гравця на його другому процесі є сім можливих дій в кожному з 8 × 9 = 72 вузлів, тоді як у другого гравця на другому ході є шість можливих дій в кожному з 7 × 8 × 9 = 504 вузлів. Ця закономірність триває до тих пір, поки дерево не припинить стрімко розростатися, оскільки певні комбінації ходів призводять до перемоги першого гравця, після чого гра закінчується. Однак мінімум до п’ятого ходу перемога неможлива. Для того щоб намалювати повне дерево цієї гри, знадобився б дуже великий аркуш паперу або дуже дрібний почерк.

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

Книгу можна придбати онлайн на сайті видавництва

Свої побажання та побоювання, свої найщиріші вітання та обурення Ви можете надсилати безпосередньо до Столиці Світу на [email protected]. Ми раді допомогти всім, хто радий допомогти нам. Щира подяка, пані та панове!

Залишити відповідь

Ваша e-mail адреса не оприлюднюватиметься. Обов’язкові поля позначені *