Дуель як гра

Дуель – кристально виражена ситуація конфлікту між двома учасниками. Жоден вестерн не обходиться без дуелей. Теорії ігор також є що сказати з цього приводу. Для представлення дуелі у формі гри потрібно визначити гравців, їх стратегії та функції виграшу. Отже, уявимо двох суперників, які розійшлися на 100 кроків і кожен має пістолет з одним патроном. Для спрощення ми розіб'ємо процес дуелі на дискретні кроки – на кожному кроці гравці вирішують, що робити: або стріляти або зробити крок уперед. Гра закінчується, коли один з учасників мертвий або не залишилось куль.
Якщо гравець вже вистрілив, а гра ще не закінчена, то він завжди робить крок вперед. Визначимо виграші учасників. Якщо гравець вистрілив і влучив, то він отримує 1, а той, кого вбили, одержує -1. Якщо гравець не влучив, то інший підходить на надійну відстань і стріляє. У цьому разі він влучає з ймовірністю 1. Якщо обоє гравців вистрілили одночасно і одночасно влучили або схибили, вони отримують нульові виграші.

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

Кожен гравець вибирає відстань, з якої він буде стріляти, – це його стратегія. Припустимо, вибрані стратегії X та Y. Якщо відстань першого учасника Х більша, то він стріляє раніше, влучає з ймовірністю P(X). З ймовірністю 1 – P(X) він хибить і тоді другий гравець спокійно підходить впритул і вбиває його напевно (з ймовірністю 1). Якщо ж відстань першого учасника менша, то він має витримати постріл суперника (Q(Y) що той влучив і 1 – Q(Y) що ні). Ситуація для другого учасника аналогічна з точністю до заміни результату на його функцію точності.
Що вони отримують в результаті? Виграш першого учасника дорівнює 1 з ймовірністю P(X) і -1 з ймовірністю 1 – P(X). Тобто його очікуваний виграш дорівнює 2 P(X) – 1 для першого випадку і 1 – 2Q(Y) для другого випадку. Якщо ж відстані пострілу однакові, то вони стріляють одночасно і виграш першого дорівнює P(X) – Q(X) (а другого Q(X) – P(X)).

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

Нанесемо на графік виграші першого гравця. Тут червона лінія «вмикається» для відстані X > Y, синя для X < Y і зелена для X = Y. Як це працює?

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

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

Визначається ця точка рівнянням P(X) + Q(X) = 1 – і для розглянутої задачі вона завжди існує і єдина.
Сідлова точка є розв'язком для всіх скінченних ігор двох гравців з нульовою сумою.
Нейман особливо пишався цією теоремою (а він був одним з найбільш яскравих математиків / фізиків двадцятого сторіччя):

«Наскільки я розумію, ніяка теорія ігор неможлива… без цієї теореми…. Я вважаю, що до доведення Теореми про мінімакс в цій області взагалі не було нічого вартого опублікування.»
Джон фон Нейман"

Цікаві наслідки:

  1. Якщо є двое ідентичних гравців з функцію точності P(X) = X, то для них найкраще рішення – підійти впритул (на 50 кроків) і вистрелити. Результат – гарантована смерть обох, але вони максимізували свої шанси.
  2. Для довільних функцій точності учасники дуелі мають стріляти одночасно. Це дає їм найкращі шанси. Це цілком відповідає сценам дуелей з вестернів. Щоправда там є додатковий елемент, який не враховано в нашій простій моделі – той, хто вихоплює зброю першим, є порушником закону. Після такого вбивства прямий шлях на побачення з вішальником. Тому потрібно вихопити зброю другим (або хоча б одночасно), але вистрелити першим.
  3. У ситуації коли висококласний стрілок зустрічається з посереднім виявляється, що найкраща можливість для посереднього стрілка стріляти здалеку за першої ліпшої нагоди (коли сума ймовірностей дорівнює 1). Отже, коли в головного героя не можуть влучити 30 чоловік з різних дистанцій – це не тому, що фільм поганий. Просто у інших учасників погані функції точності (що є математичним способом сказати, що вони криворукі), а так вони діють цілком раціонально.

Труелі. Парадокс слабкого гравця.

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

Питання: Ким би Ви хотіли бути у цій дуелі А, Б чи В? В кого найбільші шанси вижити, в кого найменші? Як впливає порядок ходів на результат?
Як ми пам'ятаємо з попереднього розділу, у дуелях шанси кращі у більш точного гравця. Чи виконується те саме для труелі? (відповідь після картинки)

Виявляється, ні! Найкращі шанси у В, потім А і в кінці Б. Більш того, це ніяк не залежить від вибраного порядку.

Причина такого стану речей полягає у природі стратегічної взаємодії. Учасники намагаються діяти найкращим для себе чином. Тому найращі снайпери А та Б знають, що В не є для них великою загрозою. Кожен з них досить легко переможе його один на один.
Тому ні А, ні Б не будуть стріляти в В. Вони будуть стріляти один в одного, аж поки хтось не буде застрелений. Отже, В обов'язково доживе до фіналу і потім буде стріляти першим! Цікаво також, що цей результат не залежить від порядку ходів. Припустимо. Що В ходить першим. Тоді навіщо стріляти в А чи Б і ризикувати влучити? Краще вистрілити у повітря и почекати.
Порахуємо ймовірність для одного порядку ВАБ:
В стріляє у повітря, А стріляє у Б (бо Б більш небезпечний суперник) і вбиває його з ймовірністю 1. В стріляє у А і вбиває його з ймовірністю 0.5. Якщо А вижив, то на наступному кроці він вбиває В.
Загальний результат для довільного порядку (повні викладки є цікавою задачею з теорії ймовірності. Розв'язок, наприклад, тут) такий:
В перемагає у 52% випадків, А – у 30% і Б у 18%.

Загальні висновки для труелей (і дуелей з більшою кількістю учасників):

  1. Якщо Ви найслабша ланка то найкраща стратегія – просто чекати поки сильніші гравці вирішують хто буде Вашим суперником.
  2. Сильному гравецю дуже вигідно створити собі репутацію слабкого.

The good, bad and ugly. Труель Серджіо Леоне.

(аналіз Філа Мелінгера)

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

За сюжетом Клінт Іствуд написав на камені ім'я, яке приводить до грошей, але чи повинні інші йому вірити? Можливо там нічого не написано (а так насправді і є). Тоді вони не можуть ризикувати і стріляти у Клінта – так вони втратять шанс отримати золото. Це означає, що їх найкращий шанс – стріляти один в одного і сподіватись, що потім буде можливість обеззброїти або домовитись з Іствудом.

Що вони не знали так це те, що одному з них Клінт дав незаряджений пістолет. Тому Клінт міг ігнорувати суперника з незарядженим пістолетом та зосередитись на тому, чий пістолет був з кулями. "Хороший" Клінт гарантував собі безпеку у першому раунді і використав Туко у якості приманки… Єдине чого він чекав – це розуміння у Ангельских Очах, що його найкращий шанс — стріляти у Туко. Ця гра була спланована ще до початку, і шансів у інших не було.
Чудовий приклад того, як люди вибирають найкращі рішення на основі доступної їм інформації… і хтось інший маніпулює цією інформацією.

Як потім виявилось, золото було заховане у могилі з написом Невідомий. Тобто, коли Клінт не написав на камені нічого, він власне не збрехав, але і нічого не сказав.

Джерела
1. https://mindyourdecisions.com/blog/2007/09/25/game...
2. Alexander Mehlmann The Game"s Afoot! Game Theory in Myth and Paradox.