Урок 7 · Часть 2. Противостояние
Думай с конца
Лучший ход ищут от конца игры к началу. Если рецепт победы легко найти, игра умирает.
Сыграй
На столе 15 монет. Ты и компьютер по очереди берёте 1, 2 или 3 монеты. Кто заберёт последнюю, побеждает. Сыграй пару партий. Если компьютер всё время выигрывает, нажми «Подсказка с конца».
Загружаем мини-игру…
Главное
Почему компьютер почти всегда выигрывает? Он не перебирает всю партию вперёд, а смотрит с конца. Если перед твоим ходом 1, 2 или 3 монеты, ты забираешь все и побеждаешь. А если 4? Что ни возьми, сопернику останется 3, 2 или 1, и последняя монетка его. Значит, 4 — ловушка для того, кто ходит.
Теперь шаг назад. Из 5, 6 или 7 монет можно оставить сопернику 4, и это выигрыш. Из 8 нельзя: что ни возьми, соперник оставит тебе 4. Так находятся все ловушки: 4, 8 и 12. Рецепт победы: оставляй сопернику число, которое делится на 4. При 15 монетах первый игрок берёт 3, оставляет 12 и побеждает, как бы ни играл второй.
Закон урокаЛучший ход ищут с конца: сначала последний шаг, потом шаг перед ним. Если рецепт победы легко найти, игра умирает.
Учёные называют этот способ обратной индукцией: игру решают от последнего хода к первому. Экономист Бен Полак говорил студентам, что это, может быть, самое важное, чему они научатся в Йеле. Через пять минут он устроил игру «Голодные львы», и приёмом не воспользовался никто. Знать приём ещё не значит им пользоваться.
Начни с ответа
Думать с конца полезно не только в споре с соперником. В лабиринте иногда проще идти от выхода к входу. Головоломку тоже удобно строить с ответа: возьми решённое положение и делай шаги назад, запутывая его. Тогда решение точно есть, и оно не длиннее твоих шагов назад. Проверь, нет ли пути короче.
Кто ходит первым
В «Последней монетке» всё решено ещё до первого хода: при 15 монетах побеждает первый, если знает рецепт. При 16 монетах побеждал бы второй. Полак предупреждал: начинать выгодно не всегда. В «камень, ножницы, бумагу» лучше, когда соперник показывает жест первым.
Проверь свою игру: кто побеждает чаще, первый или второй? Если перекос большой, уравновесь игру. Если менять, кто начинает, честной станет серия партий, но в каждой партии перекос останется. Поэтому дай второму игроку фору или бонус либо пусти ходы «змейкой»: 1-2-3, потом 3-2-1.
Угроза, которой верят
С конца проверяют и угрозы. Брат говорит: «Возьмёшь мою приставку — больше никогда с тобой не играю». Но одному ему скучно. Когда дойдёт до дела, исполнять угрозу ему невыгодно, значит, она пустая. Угроза работает, только если её выгодно исполнить.
Пустую угрозу можно сделать настоящей, если сжечь мосты: сделать шаг, после которого пути назад нет. Полак рассказывает историю о Вильгельме Завоевателе: высадившись с войском в Англии, тот сжёг свои корабли. Бежать его воинам некуда, они будут биться до конца, и нападать на них страшнее. Полак честно добавляет, что в настоящей битве англичане всё равно напали. Но суть приёма понятна: он работает, только если соперник его видит. В игре это ставка, которую нельзя забрать, или карта, открыто выложенная на стол.
Рецепт убивает игру
Когда рецепт найден, «Последняя монетка» превращается в счёт до четырёх: выбирать больше нечего. Так было с крестиками-ноликами из урока 1: взрослые знают, что при правильной игре будет ничья, и им скучно. Чтобы рецепт не находился, создатели игр добавляют тайну (скрытые карты), случайность (кубик) и больше вариантов (большое поле, разные ходы).
В настоящих играх
- Шахматы и го. Ответ в них существует, но его никто не знает: вариантов слишком много. Первый ход даёт небольшое преимущество, поэтому в шахматных турнирах цвета чередуют, а в го белые получают коми — дополнительные очки за то, что чёрные начинают.
- «Колонизаторы». Первые поселения ставят «змейкой»: по кругу, а потом в обратном порядке. Кто ставил последним, сразу ставит второе. Так игра уравновешивает порядок ходов.
- Нарды. Кубики не дают просчитать партию до конца. Опытный игрок выигрывает чаще, но новичок тоже иногда побеждает мастера. Случайность прячет рецепт и держит игру живой.
- «Пятнашки». Если вынуть фишки и сложить их как попало, в половине случаев головоломку не собрать. Честный способ перемешать — сдвигать фишки из собранного положения. Тогда путь назад точно есть.
Частые ошибки
Первый игрок почти всегда побеждает
Если начинать слишком выгодно, второй проигрывает ещё до первого хода. Игроки замечают это за пару партий, и спор «кто начинает» становится важнее самой игры.
сыграй десять партий и запиши, кто побеждает. Если первый побеждает намного чаще, дай второму компенсацию: фору, лишний ход, бонусные очки или право выбрать сторону.
Угрозы, в которые никто не верит
Злодей грозит сжечь деревню и ничего не делает. Правило обещает наказание, которое бьёт по самому наказывающему. Игроки быстро это понимают и перестают бояться любых угроз.
проверь угрозу с конца: выгодно ли её исполнить, когда до неё дойдёт? Если нет, сделай исполнение выгодным или автоматическим и покажи его всем заранее.
Головоломка без проверки с конца
Пазл придумали ход за ходом вперёд и не проверили. А у него нет решения или есть короткий обходной путь, который убивает задумку.
строй головоломку от ответа назад, потом пройди её с конца шаг за шагом. И дай решить другу, молча наблюдая.
Простой рецепт победы
Если выигрышный способ находится за несколько партий, дальше все играют одинаково. Выбора нет, и игру откладывают.
добавь тайну, случайность или больше вариантов. После каждой правки снова ищи рецепт: иногда он просто переезжает в другое место.
Проверь себя
Ответы видны только тебе. Ничего не отправляется и не считается.
Новая игра: 10 монет, за ход берут 1 или 2, кто заберёт последнюю, побеждает. Какие числа монет — ловушки для того, кто ходит?
С конца: из 1 или 2 ты забираешь всё. Из 3 что ни возьми, сопернику останется 1 или 2. Дальше ловушка — каждое третье число. Значит, первому стоит взять 1 и оставить 9.
Это ловушки игры, где берут до трёх монет. Здесь можно взять не больше двух, и узор другой: шаг 3, а не 4.
Из 2 ты забираешь обе монеты и сразу побеждаешь. Значит, 2 — не ловушка.
По правилам игры ты можешь ответить соседу ударом на удар, но ответный удар отнимает у тебя больше, чем у соседа. Ты грозишь: «Нападёшь — отвечу». Что сделает сосед, который думает с конца?
Пугает угроза, которую выгодно исполнить. Эту исполнять невыгодно тому, кто грозит, то есть тебе.
Сосед смотрит, что будет, когда дойдёт до дела. Отвечать тебе невыгодно, значит, угроза пустая.
Громкость ничего не меняет. Важно другое: выгодно ли исполнить угрозу и можно ли её отменить.
В твоей игре первый игрок побеждает в 8 партиях из 10. Что лучше попробовать?
8 из 10 — это не везение, а перекос правил. Игроки его быстро заметят.
Так делают в го: белые получают дополнительные очки за то, что чёрные начинают. Потом проверь новую версию ещё на нескольких партиях.
Жребий решает, кому достанется преимущество, но само преимущество остаётся.
Ты меняешь правила «Последней монетки»: перед ходом бросают кубик, и он решает, сколько монет можно взять (на 1–2 — одну, на 3–4 — до двух, на 5–6 — до трёх). Что станет с рецептом «оставляй число, которое делится на 4»?
Рецепт держался на том, что из любого числа можно взять 1, 2 или 3. Теперь это решает кубик, и оставить сопернику 4 получается не всегда.
Наоборот: случайность мешает просчитать партию до конца.
Случайность ломает простой рецепт. Хорошие ходы остаются, но гарантии победы нет, и думать снова интересно.
Создай
Сломай рецепт победы. Понадобятся 15 монет, пуговиц или фишек и один друг. Если больше хочется головоломку, есть второй вариант.
- Сыграй с другом в «Последнюю монетку» три партии. Если друг не знает рецепта, покажи его после игры.
- Придумай одно новое правило, которое ломает рецепт. Например: можно брать 1, 2 или 4 монеты; монеты лежат в двух кучках; кто заберёт последнюю, проигрывает; сколько брать, решает кубик.
- Найди новые ловушки с конца: начни с 1, 2 и 3 монет и иди назад. Выпиши, какие числа выигрывают, а какие нет.
- Нашёлся новый простой рецепт? Поменяй правило ещё раз или добавь тайну: например, часть монет лежит под платком.
- Сыграй новую версию с другом три–пять партий. Записывай, кто побеждает и долго ли друг думает над ходом.
Второй вариант. Придумай головоломку из трёх шагов, начиная с ответа. Нарисуй решённое положение, сделай три хода назад и запиши их. Дай другу решить с последнего положения и проверь, найдёт ли он путь.
друг сыграл по новым правилам хотя бы три партии, и никто из игроков не знает хода, который побеждает всегда. Или друг решил твою головоломку, а ты заранее знаешь, что решение есть.
теория игр за этим урокомОбратная индукция, теорема Цермело, обязательства и угрозы, лекции 13–16 Полака
Обратная индукция (backward induction). Игру решают с последнего хода к первому, считая, что каждый выберет лучшее для себя. В «Последней монетке» числа, кратные 4, — проигрышные позиции для того, кто ходит (в теории комбинаторных игр их называют P-позициями), остальные — выигрышные (N-позиции). Если за ход можно взять от 1 до k монет, ловушками будут числа, кратные k + 1.
Теорема Цермело (1913). В конечной игре двоих, где каждый видит все прошлые ходы и нет случайности, либо первый может обеспечить себе победу, либо второй, либо оба могут обеспечить ничью. Крестики-нолики — ничья. Английские шашки просчитаны в 2007 году, тоже ничья (к русским шашкам это не относится). Для шахмат ответ существует, но неизвестен. Полак разбирает теорему в лекции 15.
Ним. Игра с несколькими кучками, где за ход берут сколько угодно предметов из одной кучки. Её полностью решил Чарльз Бутон в 1901 году. В лекции 14 студенты Полака нашли правило для двух кучек: если кучки неравны, выгодно начинать и каждым ходом уравнивать их; если равны, выгодно, чтобы начинал соперник. «Последняя монетка» — родственница Нима: одна кучка и не больше трёх монет за ход.
Преимущество первого хода (first-mover advantage). Полак показывает, что оно бывает не всегда: в «камень, ножницы, бумагу» выгоднее отвечать вторым ходом, а в дележе «я режу, ты выбираешь» преимущества нет ни у кого. Способы уравнять игру: компенсация второму (коми в го), «правило пирога» в игре Hex (после первого хода второй игрок может забрать этот ход себе), чередование и «змейка».
Правдоподобная угроза (credible threat) и обязательство (commitment). Угроза правдоподобна, если её выгодно исполнить, когда до неё дойдёт. В лекции 15 Полак разбирает игру входа на рынок: монополист грозит ценовой войной, но вести её невыгодно ему самому, и обратная индукция отбрасывает такую угрозу. Обязательство — ход, который отрезает часть своих выборов и этим меняет поведение соперника: сожжённые корабли (лекция 13), построенная типография в споре газет (лекция 14), «машина судного дня» из фильма «Доктор Стрейнджлав», бесполезная, потому что о ней не сказали врагу.
Голодные львы (лекция 13). Съесть овцу может только вожак, но потом он засыпает, и его может съесть следующий лев, и так по цепочке. Разбор с конца цепочки показывает: при нечётном числе львов вожаку стоит есть, при чётном нет.
Дуэль (лекция 16). Студенты по очереди шагали навстречу друг другу с мокрыми губками, и в обеих парах первый бросок оказался промахом. Обратная индукция находит точный момент: бросать стоит, когда твой шанс попасть сейчас плюс шанс соперника попасть следующим ходом впервые не меньше единицы. До этого выгоднее ждать.
Моральный риск (moral hazard, лекция 13). В игре «Деньги в шляпе» второй игрок может забрать вложенные деньги, поэтому первый вкладывает мало, хотя большой вклад выгоднее обоим. Решение первого зависит от того, что сделает второй, — та же логика «думай с конца».
Источники:
- Бен Полак, лекция 13 «Последовательные игры: моральный риск, стимулы и голодные львы»: видео, стенограмма.
- Лекция 14 «Обратная индукция: обязательства, шпионы и преимущество первого хода»: видео, стенограмма.
- Лекция 15 «Обратная индукция: шахматы, стратегии и правдоподобные угрозы»: видео, стенограмма.
- Лекция 16 «Обратная индукция: репутация и дуэли»: видео, стенограмма.
- Charles L. Bouton. «Nim, a Game with a Complete Mathematical Theory». Annals of Mathematics, 1901–1902 — первое полное решение Нима.
- Томас Шеллинг. «Стратегия конфликта» (The Strategy of Conflict, 1960) — классика об обязательствах и угрозах.
- Разборы лекций для этого курса — в разделе «Лекции и источники».
как провести урок с группой45 минут, от 2 до 30 человек, нужны монеты или пуговицы
- 10 минИгра. Пары, у каждой 15 монет или пуговиц. По очереди берут 1, 2 или 3, кто заберёт последнюю, побеждает. Три партии, меняясь, кто начинает. Пусть записывают, кто начинал и кто победил.
- 10 минРазбор. Напиши на доске числа от 15 до 0 в четыре столбика, как в мини-игре. Спроси: что делать, если перед ходом 2 монеты? А 4? А 5? Раскрашивай числа вместе с группой, двигаясь с конца. Рецепт не подсказывай: пусть группа найдёт его сама.
- 5 минЗакон. Запиши на доске: «Лучший ход ищут с конца. Простой рецепт победы убивает игру». Спроси, какие игры надоели группе именно потому, что рецепт известен.
- 15 минСоздание. Пары придумывают одно правило, которое ломает рецепт. Потом меняются правилами с соседней парой и пробуют найти новый рецепт с конца.
- 5 минИтог. Каждая пара говорит, какое правило сломало рецепт лучше всего. Без оценок: «что сработало» и «что ещё попробовать».
С детьми лучше играть на конфеты или наклейки и разбирать числа только до 8. Со взрослыми можно добавить «Голодных львов» из лекции 13 или разобрать угрозы в знакомых им настольных играх.