Обратная индукция: репутация и дуэли

Важность для курса: высокая — репутация игроков и ИИ и решения вида «когда?» дают самые напряжённые моменты в играх.

Суть простыми словами

Если ты однажды жёстко ответил обидчику, другие подумают дважды, прежде чем лезть. Это репутация. Она работает, даже когда про тебя просто не уверены до конца. А дуэль мокрыми губками показала: кто бросает слишком рано, обычно промахивается. Есть точный момент для броска, и до него лучше ждать.

Что было на лекции

• Ассистент Але превратился в монополиста с пиццериями в десяти городах. Десять студентов по очереди решали, входить ли на его рынок.
• Итог: вошли первый, седьмой и восьмой, и с каждым Але воевал. Остальные семеро не вошли. С десятым, признался Але, воевать бы не начал. Студенты объяснили: он строит репутацию жёсткого хозяина.
• Парадокс сети магазинов (Зельтен). В последнем городе воевать незачем, значит, десятый входит. Тогда незачем пугать девятого, и так до первого. По обратной индукции войти нужно всем.
• Решение: пусть с вероятностью 1% Але «бешеный» и любит драться. После первых драк соседи верят, что он бешеный, и не входят. Даже нормальному Але выгодно иногда изображать бешеного (точное равновесие в смешанных стратегиях).
• Выводы: крошечное сомнение резко меняет исход. Вспыльчивые друзья чаще добиваются своего. С захватчиками заложников не ведут переговоров, чтобы отпугнуть будущих. Врачи и аудиторы живут репутацией честности.
• Дуэль. У каждого одна мокрая губка. По очереди бросаешь или шагаешь вперёд. Попал, победил. Промахнулся, губку не вернуть, соперник подходит вплотную. В обеих парах первый бросивший (сначала Патрик, потом Джессика) промахнулся.
• Похожие игры: дуэли в «Войне и мире» и «Евгении Онегине», рывок от пелотона на «Тур де Франс», гонка фирм с новым продуктом. Вопрос тут не «что», а «когда».
• Кто бросит первым, меткий или мазила? Зал разделился. Разбор: если соперник следующим ходом бросать не будет, шагай (факт A). Если будет, бросай, когда твой шанс попасть не меньше его шанса промахнуться (факт B, заметил студент Осмонт): Pi(d) + Pj(d−1) ≥ 1. Первое такое расстояние: d*. До него ждать выгодно всегда, с него надо бросать. Первый бросок на d*, чей бы ни был ход.
• Против неопытного соперника раньше d* тоже не стоит. По словам Полака, в его аудиториях бросают рано и почти всегда мажут, хотя попадать нужно примерно в половине случаев. Причины: самоуверенность и «склонность действовать». Студенты оправдываются, что хотя бы проиграли в атаке. Полак: «цель не в том, чтобы проиграть в атаке, а в том, чтобы не проиграть».

Главные понятия

• Парадокс сети магазинов (chain store paradox) — по обратной индукции запугать новичков нельзя даже на многих рынках, хотя в жизни это работает.
• Репутация (reputation) — мнение других о твоём «типе» по прошлым поступкам. Ради неё выгодно иногда действовать себе в убыток.
• «Сумасшедший» тип (crazy type) — малая вероятность, что у игрока другие выигрыши. Она делает угрозы правдоподобными.
• Упреждение (pre-emption) — желание действовать раньше соперника, пока он не успел.
• Критическое расстояние d* — первое расстояние, где Pi(d) + Pj(d−1) ≥ 1. Там и надо бросать.

Зерно для создателя игр

• Репутация как механика. Фракции и враги, которые помнят поступки игрока, делают мир живым. Один жёсткий ответ даёт защиту потом. Фракция ИИ, которая иногда мстит себе в убыток, кажется опасной.
• Щепотка непредсказуемости делает угрозы ИИ правдоподобными. Всего 1% шанса, что соперник «бешеный», меняет всю игру. Предсказуемо «разумного» ИИ игроки быстро начинают эксплуатировать.
• Известный последний ход разрушает репутацию и доверие: всё распускается с конца. Чтобы угрозы и союзы работали до финала, скрывай точный конец. Например, замешай карту «Конец игры» в нижнюю часть колоды.
• Вопрос «когда?» рождает напряжение. Одноразовое умение, единственный выстрел и рывок в гонке устроены как дуэль. Настраивая, как растёт шанс успеха, дизайнер задаёт критический момент и длину паузы перед ним.
• Учитывай нетерпение. Люди действуют слишком рано. Новичкам помоги индикатором шанса. А ИИ, который умеет выждать, наказывает торопливых: удобный рычаг сложности.

Мини-игра для урока

«Дуэль на кубике» (по дуэли с губками). 2 игрока, кубик, полоска из 7 клеток, 10 минут.

• Фишки стоят в 6 клетках друг от друга. Ходят по очереди. В свой ход: шаг (расстояние уменьшается на 1) или выстрел.
• Выстрел: брось кубик. Попадание, если выпало не меньше расстояния (с 6 клеток нужна шестёрка, с 1 клетки попадаешь всегда). Попал, победил. Промахнулся, проиграл.
• Сыграй 5 партий, записывая дистанцию каждого выстрела.
• Что заметить: шанс стрелка сейчас плюс шанс соперника на следующем ходу впервые больше единицы на расстоянии 4 (3/6 + 4/6). Значит, стрелять надо с 4. Сверься с записями: часто ли стреляли раньше? Вариант: дай одному «прицел» (+1 к броску), и критический момент сдвинется на 5.

Ошибки и заблуждения

• «Меткому нужно стрелять первым» или «слабому нужно опередить». Ни то ни другое: момент задаёт сумма шансов обоих, а стреляет тот, чей ход на d*.
• «Лучше проиграть в атаке, чем ждать». Цель не красиво проиграть, а не проиграть.
• «Если правила и конец игры всем известны, угрозы работают». По обратной индукции они распускаются с конца. Репутации нужна неуверенность в том, кто перед тобой.

Для продвинутых

• Райнхард Зельтен, «The Chain Store Paradox» (1978). Нобелевская премия 1994 года вместе с Нэшем и Харсаньи.
• Решение через малую вероятность «жёсткого» типа: Kreps & Wilson (1982) и Milgrom & Roberts (1982).
• Дуэль относится к играм выбора момента (games of timing). Здесь дуэль «шумная»: бросок соперника виден. До d* выгоднее ждать при любом поведении соперника (доминирование), после d* работает обратная индукция.