Теория игр: выигрышные стратегии

В простые игры — шашки, крестики-нолики, камешки — играют миллионы людей, но выигрывают далеко не все. Математики доказали поразительный факт: в любой конечной игре с полной информацией у одного из игроков с самого начала есть выигрышная стратегия — план ходов, который приводит к победе, что бы ни делал соперник. В крестики-нолики при правильной игре обоих всегда получается ничья, и это доказано, а не подмечено. На экзамене ЕГЭ по информатике задания 19, 20 и 21 проверяют именно умение доказывать, кто и почему выигрывает. Разберём метод, который решает их почти механически: дерево игры и анализ позиций с конца.

Дерево игры: карта всех партий

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

Позиции делятся на два типа. Выигрышная позиция — та, из которой ходящий может выиграть при правильной дальнейшей игре; достаточно хотя бы одного удачного хода. Проигрышная позиция — та, из которой выиграть нельзя, что бы ходящий ни сделал: любой ход отдаёт сопернику выигрышную позицию. Важная деталь: тип позиции определяется для того, чей сейчас ход. После каждого хода роли меняются, поэтому анализ всегда идёт с оглядкой: «а если бы сейчас ходил соперник?» Стратегия — это правило, выбирающее верный ход в каждой выигрышной позиции, встретившейся на пути.

Терминальная позиция#

лист дерева: партия окончена по условию

Обратная индукция#

разметка позиций от финиша к старту

Раунд#

ход первого игрока и ответ второго

Полная информация#

оба игрока видят всю позицию целиком

Ход#

преобразование позиции по правилам игры

Игра с камнями: анализ от конца к началу

Возьмём базовую игру заданий 19-21. В куче S камней, игроки по очереди добавляют один или два камня; выигрывает тот, кто первым сделает кучу из N камней или больше. Разбирать её удобно обратной индукцией — от конца к началу. Позиции, где до цели остался один камень, выигрышны: добавь один — победа. Два до цели — тоже выигрышны: добавь два. А вот три до цели — проигрышные: любой ход оставляет сопернику один или два до цели, то есть победу. Дальше картина повторяется с шагом три: шесть до цели проигрывает, потому что любой ход даёт сопернику пять или четыре до цели — обе позиции выигрышные для него.

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

Вторая классическая разновидность — камни забирают, а не добавляют: за ход берут один или два камня, и выигрывает взявший последний. Анализ тот же, только цель другая: проигрышные позиции — кучки, кратные трём. Первый игрок берёт столько, чтобы оставить сопернику кратное трём, а дальше зеркалит ходы: соперник взял один — бери два, соперник взял два — бери один. Пара ходов всегда снимает ровно три камня, и последний камень достанется тебе. Если стартовая кучка сама кратна трём, первым выигрывает отвечающий — он и применяет зеркальную стратегию. Такая «зеркальная» схема — популярный гость задач олимпиад и ЕГЭ.

Третий тип хода в экзаменационных играх — умножение: за ход кучу можно удвоить. Ровной периодичности, как у ходов плюс один и плюс два, здесь уже нет, поэтому дерево рисуют целиком на несколько уровней и размечают руками. Приём тот же — считать от финиша: сначала помечаем позиции, из которых победа достигается одним ходом, затем находим позиции, откуда все ходы ведут в уже помеченные выигрышные, — это проигрышные. С каждым новым уровнем разметка поднимается вверх по дереву, пока не дойдёт до старта. Именно многоуровневый анализ проверяет задание 20: оно просит найти стартовую кучу, при которой победитель добирается до цели ровно вторым ходом, — для этого нужно видеть два уровня дерева и не спешить с выводами после первого.

Задания ЕГЭ 19-21: как их решать

Задание 19 — разбор одной позиции: даны ходы и условие победы, спрашивается, кто выигрывает при правильной игре. Решение — таблица позиций и один вывод. Задание 20 — то же дерево, но с фильтром: нужно найти стартовые S, при которых Петя выигрывает не первым ходом, а вторым, или назвать минимальное такое S. Здесь без полного дерева двух-трёх уровней не обойтись. Задание 21 — самый тонкий анализ: у кого стратегия выигрыша не одна, у кого ровно одна, или при каких S выигрывающий обязан сделать единственный верный ход. Все три задания решаются одним аппаратом — типами позиций, — меняется только вопрос. Схема работы всегда одна: выписать позиции от финиша, разметить выигрышные и проигрышные, ответить на вопрос задания по разметке.

Практикум: возьми цель N = 12 и построй таблицу позиций от 1 до 11 — проигрышными окажутся 3, 6 и 9, и это проверяется вручную за пять минут. Потом сыграй с другом в «до 12» и попробуй удерживать кратность трём после каждого своего хода: ощущение «я управляю партией» и есть практический смысл всей темы. Теория игр — последний крупный блок дискретной математики в курсе информатики: дальше стоит повторить алгебру логики и рекурсию, потому что дерево игры — это, по сути, рекурсивный обход дерева. В программе тема соседствует с моделированием: игра — это модель конфликта, а дерево — её компьютерная форма, та же идея, на которой строятся шахматные движки и боты в стратегиях.

Подсказка: клавиши J — следующая тема, K — предыдущая, на телефоне: свайп влево/вправо — соседняя тема