Обратная индукция: шахматы, стратегии и правдоподобные угрозы

Важность для курса: высокая — объясняет, почему одни игры быстро надоедают, а другие живут веками, и почему ИИ и сюжет не должны держаться на пустых угрозах.

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

В крестиках-ноликах, шашках и шахматах у идеальных игроков исход предрешён: победа первого, ничья или победа второго. Просто в шахматах этот ответ никто не может вычислить, вариантов слишком много. И ещё: угрозе стоит верить, только если угрожающему выгодно её выполнить.

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

• Ним: по стартовым кучкам видно, кто выиграет. Это частный случай теоремы Цермело. Если игроков двое, каждый видит все прошлые ходы, игра конечна, а исходы «победа, ничья, поражение», то либо первый может добиться победы, либо хотя бы ничьей, либо второй может добиться победы.
• Голосование про крестики-нолики: большинство верно ответило «ничья». Решение есть у шашек (Полак слышал, что их недавно просчитали) и у шахмат. Подвох: теорема не говорит, какое оно.
• Доказательство по индукции: длинная игра состоит из первого хода и игр покороче. Каждую короткую игру заменяем её результатом, и первый выбирает лучший.
• Игра с камнями. Камни лежат прямоугольником. Выбранный камень убирают вместе со всеми, что выше и правее. Взявший последний камень проиграл. Сыграли на полях 5×3 и 4×5, обе партии пришли к «уголку». Задание: найти решение для любого поля. Подсказка: полезно помнить, что оно существует.
• Стратегия: полный план, что игрок сделает в каждом своём узле, даже если туда не дойдёт.
• Пример: игрок 1 выбирает U или D, игрок 2 L или R, затем игрок 1 ещё раз u или d. У игрока 1 четыре стратегии, а не три. Обратная индукция даёт (Dd, R). Но в таблице 4×2 есть второе равновесие Нэша (Du, R) с глупым ходом u. Он «прощён», потому что до него не доходит.
• Игра входа. Монополист получает 3 млн в год. Если новичок вошёл на рынок, монополист воюет (новичок −1, монополист 0) или делит рынок (по 1). Равновесий Нэша два: «вошёл, не воюют» и «не вошёл, ведь воевали бы». Второе держится на неправдоподобной угрозе: войну невыгодно вести самому монополисту. Примеры: угрозы Билла Гейтса создателю новой операционной системы, визит от главы Boeing.
• Студент заметил: монополист может наказать одного, чтобы отпугнуть остальных. Это тема следующей лекции.

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

• Теорема Цермело (Zermelo's theorem) — у конечной игры двоих с совершенной информацией есть решение: при лучшей игре обоих исход предрешён.
• Совершенная информация (perfect information) — в момент хода игрок знает всё, что произошло раньше.
• Чистая стратегия (pure strategy) — полный план действий во всех своих узлах, включая те, до которых не дойдёт.
• Неправдоподобная угроза (non-credible threat) — угроза, которую невыгодно выполнять, когда приходит время. Равновесие Нэша может на ней держаться, обратная индукция её отбрасывает.

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

• Глубина живёт там, где решение есть, но его не найти. Крестики-нолики решены, поэтому взрослым скучно. У шахмат решение тоже есть, но дерево огромно. Может ли опытный игрок просчитать твою игру до конца? Если да, она скоро умрёт. Лекарства: большое дерево, скрытая информация, случай.
• ИИ-противник строится на обратной индукции. Алгоритм минимакс оценивает позиции с конца, как в доказательстве Цермело. В маленькой игре такой ИИ непобедим и потому скучен. Ограничивай глубину просчёта и добавляй «человеческие» ошибки.
• Стратегия означает план на все случаи. ИИ и квест должны знать, что делать даже в «невозможной» ситуации. Игроки туда попадут, и непродуманная ветка станет багом или эксплойтом.
• Угрозы персонажей должны быть правдоподобными. Если злодей грозит сжечь деревню и ничего не делает, игрок перестаёт верить любым угрозам. Выполняй их или делай выполнение выгодным угрожающему. В настольной «Дипломатии» договоры не обязательны, и вся игра о том, каким обещаниям верить.

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

«Отравленная шоколадка» (игра с камнями из лекции). 2 игрока, листок в клетку, 10 минут.

• Нарисуй прямоугольник из клеток. Левая нижняя клетка отравлена.
• За ход зачеркни любую клетку и все клетки выше и правее неё. Кто зачеркнул отравленную, проиграл.
• Сыграй на полях 2×4, 3×3 и 4×5, меняясь, кто начинает.
• Что заметить: ответ у каждого поля есть заранее, его просто не видно. На квадрате первый выигрывает: зачеркни клетку по диагонали от отравленной, останется уголок с равными сторонами, дальше повторяй ходы соперника зеркально. Уголок устроен как Ним с двумя кучками из прошлой лекции. На поле 4×5 первый тоже может выиграть, но найти как трудно. Это и есть глубина.
• В браузере: компьютер, который не ошибается. Весело ли с ним играть?

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

• «В шахматах нет решения, поэтому они интересны». Решение есть, но его не вычислить: дерево больше человеческих возможностей.
• «Стратегия описывает только то, что игрок сделал». Нет, это план на все ветки, даже несыгранные.
• «Любое равновесие Нэша годится как прогноз». Некоторые держатся на угрозах, которые никто не захотел бы выполнять.
• «Громкая угроза работает сама по себе». Работает та, которую выгодно выполнить, или та, за которой стоит репутация.

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

• Эрнст Цермело (1913) писал о шахматах. Гарольд Кун (1953) доказал: в любой конечной игре с совершенной информацией обратная индукция даёт равновесие в чистых стратегиях.
• Решённые игры: крестики-нолики (ничья), «Четыре в ряд» (1988, побеждает первый), английские шашки 8×8 (Шеффер и коллеги, 2007, ничья; к русским шашкам это не относится). В шахматах полностью просчитаны окончания до 7 фигур (таблицы Ломоносова, 2012).
• Игра с камнями известна как «Чомп» (Chomp, Дэвид Гейл, 1974). Рассуждение «кража стратегии» доказывает, что на любом поле больше 1×1 выигрывает первый. Как именно, в общем случае неизвестно.