Гра без в'язнів
Мерріл Флад і Мелвін Дрешер з корпорації RAND придумали гру як математичну задачу. Історію про двох затриманих на допиті згодом вигадав Альберт Такер, і саме вона дала грі назву.
Двоє одночасно обирають: співпрацювати чи зрадити. Якщо обидва співпрацюють, кожен отримує 3 очки. Зрадник проти того, хто співпрацює, бере 5, а той 0. Якщо зраджують обидва, кожному по 1. Політолог Роберт Аксельрод влаштував турнір: програми грали цю гру по 200 раундів кожна з кожною. Яка стратегія набрала найбільше очок?
«Око за око» математика Анатоля Рапопорта: першим ходом співпрацювати, а далі повторювати попередній хід суперника. Вона не набрала більше за суперника в жодному матчі, бо ніколи не зраджує першою. Але разом зібрала найбільше: у середньому 504 очки за матч. Потім вона виграла і другий турнір, з 62 учасниками.
Почнімо з однієї гри, а потім повторимо її багато разів.
Двоє гравців одночасно й незалежно обирають один із двох ходів: співпрацювати або зрадити. Очки дає таблиця праворуч. Назва походить від історії про двох затриманих, яких допитують окремо: кожному пропонують скорочення строку, якщо він свідчитиме проти іншого.
Якщо суперник співпрацює, вам вигідніше зрадити: 5 більше за 3. Якщо суперник зраджує, теж вигідніше зрадити: 1 більше за 0. Тож в одному раунді зрада краща за будь-якого ходу суперника. Але коли так міркують обидва, кожен отримує по 1, хоча міг би по 3.
Ті самі двоє грають 200 раундів поспіль. Перед кожним раундом обидва бачать, хто як ходив раніше. Очки за всі раунди додаються. Два гравці, які весь час співпрацюють, отримують по 600 очок, а двоє, що весь час зраджують, по 200.
Учасники турніру — програми, кожна зі своєю стратегією. Кожна грає матч з кожною, а також зі своєю копією. Перемагає не той, хто виграв більше матчів, а той, хто набрав найбільше очок разом.
Яка стратегія набирає найбільше очок у такому турнірі?
«Виграє хитра стратегія, яка вміє обдурити»
Хитрі програми в турнірі були, і вони програли. Перемогло «Око за око», найпростіша з поданих програм: не зраджує першою, на зраду відповідає зрадою, а на співпрацю співпрацею.
Турнір по колу, кожен матч 200 раундів, учасників багато і вони різні. Зафіксуйте відповідь, перш ніж читати далі.
Тут з'явиться розбір вашої відповіді.
Важко вирішити? Відкривайте підказки по одній: спочатку легка, далі сильніша.
Порахуйте, скільки за матч із 200 раундів отримують двоє, що весь час співпрацюють, і двоє, що весь час зраджують. Яка різниця?
У турнірі рахують ваші очки, а не те, чи обіграли ви суперника. Чи важливо виграти матч, якщо в ньому обидва набрали мало?
Уявіть суперника, який на зраду відповідає зрадою наступного ходу. Що дає вам зрада проти нього через два раунди? А що дає зрада проти того, хто ніколи не мстить?
Ви граєте матч із ботом: щораунду обираєте співпрацю або зраду, бот ходить одночасно з вами. Скільки раундів у матчі, ви не знаєте: від 8 до 12. Після матчу вгадайте, яка стратегія була в бота. Список стратегій поруч.
Кожна вибрана стратегія грає з кожною і зі своєю копією по 200 раундів. Стовпчик — точне середнє очок за матч: сторінка рахує ймовірності всіх ходів раунд за раундом. Риска — симуляція: 50 турнірів, зіграних з випадковими ходами. Шум означає, що кожен хід із такою ймовірністю випадково перевертається: хотів співпрацювати, а вийшла зрада, і навпаки.
Ті самі учасники, але тепер це частки населення. Кожне покоління частка стратегії росте пропорційно до того, скільки очок вона набирає проти нинішньої суміші. Так Аксельрод перевіряв, хто виживе, коли невдахи поступово зникають.
У турнірі рахують ваші очки, а не різницю з суперником. Тому вигідно не обіграти іншого, а дати вам обом набрати багато.
Шар «На пальцях» приховано на всіх задачах.
Почнімо з простого, хоч і неповного пояснення. Зрадник ніколи не програє матч: проти «Ока за око» він бере 204 очки проти 199. Але 204 — це мізер: двоє, що співпрацюють, отримують по 600. «Око за око» програє кожному зрадникові кілька очок, зате з кожним, хто готовий співпрацювати, заробляє максимум.
Хитрі програми в турнірах Аксельрода часто ламалися на третій і четвертій рисі: їхні спроби зрадити «трішки» запускали довгі ланцюги взаємної відплати.
Шар «Строго» приховано на всіх задачах.
Рядок — стратегія, стовпець — її суперник, у клітинці середні очки рядка за матч з 200 раундів. Зеленим позначено матчі, де рядок набрав більше за суперника, червоним — менше. У рядку «Ока за око» немає жодної зеленої клітинки: вона не обігрує нікого. Зате з половиною суперників вона набирає 599 або 600, а найгірша клітинка 199, тоді як у Добряка 0, а в Терплячого 198.
В одному раунді зрада домінує: за будь-якого ходу суперника вона дає на 2 очки більше (5 проти 3) або на 1 більше (1 проти 0). Але у повторній грі ваш хід змінює наступні ходи суперника. Зрада проти «Ока за око» дає +2 зараз, але в наступному раунді воно відповість зрадою: ви отримаєте 0 замість 3, якщо повернетеся до співпраці, або 1 замість 3, якщо зраджуватимете й далі.
Тому важливо, хто ще є в турнірі. Якщо навколо багато стратегій, які мстять, зрада окупається лише в останньому раунді. Якщо навколо самі добряки, вигідно зраджувати завжди: у раунді 3 ви це побачите, увімкнувши «Наївне поле».
Нехай після кожного раунду гра триває з імовірністю w. Ви граєте проти «Ока за око». Очікувані очки трьох планів:
Співпраця не гірша за обидва інші плани, коли
Тут T = 5 (спокуса), R = 3 (нагорода), P = 1 (покарання), S = 0 (вас обдурили). Цю умову Аксельрод назвав тінню майбутнього: співпраця стійка, коли наступна зустріч досить імовірна. Якщо остання гра відома наперед, тінь зникає: в останньому раунді зрадити вигідно, тоді й у передостанньому, і так до першого.
Шар «Глибше» приховано на всіх задачах.
Гру придумали Мерріл Флад і Мелвін Дрешер у корпорації RAND 1950 року, а історію про в'язнів до неї дописав математик Альберт Такер. Аксельрод зібрав у першому турнірі 14 програм від учених, що вивчали цю гру, і додав п'ятнадцяту, випадкову. «Око за око» набрало в середньому 504 очки за матч і стало першим, хоча за кількістю виграних матчів було останнім: не виграло жодного.
До другого турніру учасники вже знали результати й пояснення. Програм прийшло 62, плюс випадкова, а кількість раундів не оголошували заздалегідь. Рапопорт знову надіслав «Око за око», і воно знову перемогло. Аксельрод описав обидва турніри в Journal of Conflict Resolution 1980 року, а 1984 року видав книжку «Еволюція співпраці».
У турнірах Аксельрода ходи виконувалися без помилок. Якщо хоч зрідка хід перевертається випадково, дві копії «Ока за око» після однієї помилки по черзі карають одна одну. 1992 року Мартін Новак і Карл Зігмунд у Nature показали на моделі зі змішаним населенням, що «Око за око» допомагає співпраці виникнути, але потім його витісняє щедріша стратегія, яка після зради суперника іноді все одно співпрацює. Для очок 3, 0, 5, 1 таку щедрість зазвичай беруть 1 з 3. 1993 року ті самі автори описали стратегію «виграв — повтори, програв — зміни», яку часто називають «Павлов»: вона теж швидко виходить із помилок.
Найкращої стратегії для повторної дилеми в'язня немає: все залежить від того, хто ще грає. Проти самих Зрадників краще зраджувати, проти самих Добряків теж. 2015 року психологи Амнон Рапопорт, Деррил Сіл і Ендрю Колман переграли перший турнір Аксельрода за іншими правилами і показали, що перемога «Ока за око» залежить від формату, критерію успіху і чисел у таблиці очок. Ми перевірили це на своєму полі з 10 стратегій без шуму: серед 502 можливих складів турніру з «Оком за око» і щонайменше трьома учасниками воно перше чи ділить перше місце в 244.
2012 року фізики Вільям Прес і Фрімен Дайсон знайшли в цій грі «стратегії з нульовим визначником». Деякі з них вимагання: вони змушують будь-якого суперника, що підлаштовується під них, віддавати їм більшу частку виграшу. «Око за око» в цьому класі — окремий чесний випадок: воно ділить очки порівну.
Математично подивимося, що робить із «Оком за око» навіть рідкісна помилка. Логічно — чому повторна гра взагалі змінює вибір. А на практиці перевіримо, коли вигідно обдурити партнера, з яким ви працюєте щомісяця.
Математика
Лінії: очки за раунд у дуже довгій грі залежно від шуму; пунктир — шум на повзунку.
Кожна копія повторює попередній хід іншої. Одна випадкова зрада запускає луну: зрада, відповідь, відповідь на відповідь. Наступна помилка може повернути співпрацю, а може зробити взаємну зраду. У дуже довгій грі всі чотири пари ходів трапляються однаково часто, тож середнє (3 + 0 + 5 + 1) / 4 = 2,25 очка за раунд, і це не залежить від того, наскільки рідкісні помилки. Рідкісні помилки лише розтягують шлях до цього середнього.
Щедре «Око за око» і «Павлов» виходять із луни за кілька раундів і, поки помилки рідкісні, тримаються біля 3. Злопам'ятний після першої помилки зраджує назавжди і скочується майже до 1. Таблиця рахує це точно: для 200 раундів і для дуже довгої гри.
Логіка
Ви граєте проти «Ока за око», і після кожного раунду гра триває з імовірністю w. Зрадити назавжди вигідніше, поки w менше 1/4. Між 1/4 і 2/3 вигідніше чергувати зраду й співпрацю: «Око за око» щоразу відповідає із запізненням на хід, і ви берете 5, коли воно співпрацює. А від 2/3 і вище найкраще співпрацювати весь час. Ідея ширша за цю гру: двоє, які напевно ще зустрінуться, поводяться інакше, ніж незнайомці на один раз.
Практика
Модель проста: поки ви чесні, партнер чесний; після обману він більше вам не довіряє. Перевірте на прикладі: 10 тисяч на місяць чесно, 25 тисяч разово за обман, 2 тисячі на місяць потім, шанс ще одного місяця 90%. Чесність дає в середньому 10 / (1 − 0,9) = 100 тисяч, обман 25 + 0,9 · 2 / 0,1 = 43 тисячі. Обман окупився б лише за шансу продовження нижче (25 − 10) / (25 − 2) ≈ 65%.
Найвідоміший приклад Аксельрода — окопи Першої світової. Батальйони місяцями стояли навпроти одних і тих самих супротивників, і на багатьох ділянках виникла система «живи і дай жити іншим»: не обстрілювати кухні та обози, не стріляти в певні години, але відповідати на постріл кількома. Аксельрод спирався на дослідження британського соціолога Тоні Ешворта. Система зламалася, коли штаби почали наказувати рейди, яких не можна було тихо імітувати: на кожен рейд відповідали, і відплата наростала.
Мерріл Флад і Мелвін Дрешер з корпорації RAND придумали гру як математичну задачу. Історію про двох затриманих на допиті згодом вигадав Альберт Такер, і саме вона дала грі назву.
Аксельрод запросив програми в учених, які вже вивчали дилему в'язня, і додав до 14 програм випадкову. Кожна пара грала 200 раундів.
За кількістю виграних матчів «Око за око» було останнім у першому турнірі. Воно не може набрати більше за суперника: зраджує лише у відповідь.
До другого турніру учасники знали, що «Око за око» виграло перший. Аксельрод підрахував, що «Терплячий», який мстить лише після двох зрад поспіль, виграв би перший турнір. У другому його подали, але «Око за око» знову опинилося попереду.
2004 року на турнірі до 20-ї річниці книжки Аксельрода команда Саутгемптонського університету подала 60 програм. Вони впізнавали одна одну за умовною послідовністю перших ходів, і «слуги» співпрацювали, поки «господар» зраджував. Три з них опинилися на верхніх місцях.
Фізик Фрімен Дайсон і астрофізик Вільям Прес показали, що гравець, який пам'ятає лише один попередній раунд, може в'язати очки суперника зі своїми лінійним правилом і так вимагати більшу частку.
Поділіться своїм поясненням, запереченням чи варіантом задачі. Для коментаря потрібен акаунт GitHub.
Рівень «Шкільна математика» відповідає задачі?
Дякуємо! Це допоможе точніше ставити рівні.
Я поступово додаю нові задачі, інші способи їх пояснити й розбори дискусій. Залиште email, і я напишу, коли з'явиться щось нове. Без спаму, відписатися можна в один клік.
Форма підписки з'явиться тут найближчим часом.