Теория игр
В заданиях 19–21 два игрока по очереди добавляют камни в кучу, и выигрывает тот, кто первым доведёт кучу до порога. Каждую позицию размечают с конца: П1 — ходящий выигрывает одним ходом, В1 — любой его ход отдаёт победу сопернику, затем П2 и В2. Небольшую игру разбирают вручную, а для любой игры подходит рекурсивная программа с lru_cache, которая ставит метку каждой позиции.
Как найти выигрышную стратегию
Позиции размечают с конца игры. Метка говорит, что будет, если в этой позиции ходит Петя.
- П1: есть ход, который заканчивает игру. Ходящий выигрывает первым ходом.
- В1: позиция не П1, и каждый ход ведёт в П1. Соперник выигрывает своим первым ходом.
- П2: позиция не П1, и есть ход в В1. Ходящий выигрывает вторым ходом.
- В2: позиция не П1 и не В1, и каждый ход ведёт в П1 или П2. Соперник выигрывает первым или вторым ходом.
- Задание 19 ищет В1 или позицию с ходом в П1, задание 20 — П2, задание 21 — В2.
- Программа: функция
movesперечисляет ходы, функцияgameс@lru_cache(None)проверяет эти четыре условия по порядку.
Позиция, ход и выигрышная стратегия
Позиция — число камней в куче, а для двух куч — пара чисел . Ход переводит позицию в одну из соседних: из при ходах «добавить камень» и «удвоить кучу» получаются , , и . Игра кончается, когда число камней достигает порога: «не менее 29» значит 29 или больше. Побеждает игрок, который сделал последний ход.
Выигрышная стратегия — правило, по которому игрок выбирает ход и побеждает при любых ходах соперника. Выигрышная позиция — позиция, в которой у ходящего есть выигрышная стратегия. Проигрышная позиция — позиция, в которой любой ход ходящего даёт сопернику выигрышную стратегию. После хода игроки меняются ролями: позиция, которую Петя оставил Ване, оценивается уже для Вани.
Пример
Две кучи, позиция . За ход можно добавить в одну из куч один камень или удвоить одну из куч. Игра кончается, когда в двух кучах вместе не менее 25 камней. Какой ход заканчивает игру?
- 1.: 16 камней. : 16 камней.
- 2.: 25 камней, это не меньше 25.
- 3.: 20 камней.
Ответ: удвоить первую кучу
П1: победа одним ходом
Позиция — П1, если из неё есть ход, после которого число камней не меньше порога. Достаточно проверить самый сильный ход: тот, после которого камней больше всего. Какой ход сильнее, зависит от — числа камней в куче. Удвоение не слабее прибавки 1 при любом : . Утроение сильнее прибавки 4 только при : . Значит, при ходах «» и «» и пороге позиция — П1 при .
В двух кучах с порогом на сумму самый сильный ход — удвоить большую кучу: — П1 при . Если порог задан на произведение, удвоение любой кучи удваивает произведение: — П1 при .
Пример
Одна куча. За ход можно добавить 1 камень, добавить 3 камня или удвоить кучу. Игра кончается, когда в куче не менее 50 камней. При каких Петя выигрывает первым ходом?
- 1.При удвоение даёт не меньше, чем прибавка 3: .
- 2. при .
- 3.При удвоение даёт не больше 48 камней, а прибавка 3 — не больше 27: этого мало.
Ответ:
В1: любой ход Пети проигрывает
Позиция — В1, если сам Петя выиграть одним ходом не может, а каждый его ход ведёт в П1: там ходит Ваня и выигрывает своим первым ходом. Это вопрос задания 19 «Петя не может выиграть за один ход, но при любом ходе Пети Ваня может выиграть своим первым ходом».
Найдите границу П1, затем возьмите позиции чуть ниже неё. Проверьте каждый ход Пети, и самый слабый тоже: все они должны попасть в П1.
Пример
Одна куча. За ход можно добавить 1 камень или удвоить кучу. Игра кончается, когда в куче не менее 41 камня. Найдите , при котором Петя не может выиграть за один ход, но при любом ходе Пети Ваня выигрывает своим первым ходом.
- 1.П1: , то есть .
- 2.Петя не выигрывает сразу, значит .
- 3.Слабый ход должен вести в П1: , то есть .
- 4.Проверка : ходы дают 21 и 40, обе позиции — П1.
Ответ:
Неудачный ход Пети
Другая форма задания 19: «Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное ». Здесь нужен один ход Пети, а не все: из позиции есть хотя бы один ход в П1, и сам Петя одним ходом не выигрывает. Чтобы найти наименьшее , возьмите два самых сильных хода подряд: Петя делает самый сильный ход, Ваня отвечает самым сильным ходом. Для двух куч с порогом на сумму это удвоение большей кучи два раза: из получается .
Пример задания
Открытый банк ФИПИ
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 59. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах оказывается 59 или больше камней.
В начальный момент в первой куче было пять камней, во второй куче – S камней; 1 ≤ S ≤ 53.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, при котором такая ситуация возможна.
П2: победа вторым ходом
Позиция — П2, если Петя не выигрывает одним ходом, но может пойти в В1. Тогда любой ответ Вани ведёт в П1, и Петя заканчивает игру своим вторым ходом. Это вопрос задания 20: «Петя не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Ваня». Найдите все позиции В1 и все позиции, из которых в них ведёт хотя бы один ход. Два значения записывают в порядке возрастания.
Стратегию удобно показать деревом игры: в корне — начальная позиция, под каждой позицией — позиции после ходов. Для Пети в дерево входит только его выигрышный ход, для Вани — все его ходы.
Пример
Та же игра: ходы и , порог 41. Найдите два значения , при которых Петя выигрывает своим вторым ходом при любой игре Вани.
- 1.Из примера про В1: единственная позиция В1 — 20.
- 2.В 20 ведут ход из 19 и ход из 10.
- 3.Из 19 и из 10 Петя одним ходом не выигрывает: 38 и 20 меньше 41.
Ответ: и
В2: Ваня выигрывает первым или вторым ходом
Позиция — В2, если она не П1 и не В1, а каждый ход Пети ведёт в П1 или П2. Тогда Ваня выигрывает первым ходом, если Петя пошёл в П1, и вторым ходом, если Петя пошёл в П2. Это вопрос задания 21: «у Вани есть стратегия выиграть первым или вторым ходом, но нет стратегии гарантированно выиграть первым ходом». Позиция В1 условию не подходит: из неё Ваня гарантированно выигрывает первым ходом.
Проверяйте позиции ниже П2 по одной. Ход, который ведёт в позицию без метки П1 или П2, сразу исключает позицию.
Пример
Та же игра: ходы и , порог 41. Найдите , при котором Ваня выигрывает первым или вторым ходом, но не может гарантированно выиграть первым ходом.
- 1.Метки уже известны: П1 — от 21 до 40, В1 — 20, П2 — 10 и 19.
- 2.: ходы дают 19 (П2) и 36 (П1). Позиция не П1 и не В1, значит, В2.
- 3.Ниже 18 таких позиций нет. При ход даёт позицию без метки П1 или П2, а из 9 ход даёт 18, то есть В2.
Ответ:
Программа: метка каждой позиции
Программа повторяет разметку с конца. Функция moves возвращает позиции после всех ходов. Функция game возвращает 'END', если игра уже окончена, иначе получает метки соседних позиций и проверяет условия в порядке П1, В1, П2, В2. Метки в коде латинские: 'P1' — это П1, 'V1' — это В1. Позиции, которые требуют больше двух ходов, получают '?'.
Функция вызывает себя для каждого хода, и одни позиции встречаются много раз. Строка @lru_cache(None) запоминает найденные метки, и программа работает мгновенно: мемоизация в рекурсивных функциях. Для неудачного хода из задания 19 нужна позиция, где game(s) != 'P1' и any(game(m) == 'P1' for m in moves(s)).
Пример
Та же игра: ходы и , порог 41, . Найдите программой позиции В1, П2 и В2.
- 1.В
movesдва хода:h + 1иh * 2. - 2.В
gameпервая проверка — порог:h >= 41. - 3.Цикл перебирает все от 1 до 40 и печатает позиции с нужной меткой.
- 4.Программа печатает
V1 [20],P2 [10, 19],V2 [18]: ответы совпадают с ручным разбором.
Ответ: В1: 20; П2: 10 и 19; В2: 18
Программа для двух куч
Для двух куч позиция — пара (x, y). Функция moves возвращает четыре пары: ход в первую кучу и ход во вторую кучу для каждого правила. Проверка конца игры берёт сумму x + y или произведение x * y — как сказано в условии. Начальную позицию строят из условия: если в первой куче 2 камня, вызов — game((2, s)). Остальной код не меняется.
Пример задания
Открытый банк ФИПИ
Условие игры
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень либо увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (20, 7), (10, 8), (10, 14). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда произведение количеств камней в кучах становится не менее 144. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, что произведение количеств камней в кучах будет 144 или больше.
В начальный момент в первой куче было два камня, во второй куче — S камней;
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от дальнейшей игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Для игры, описанной выше, найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.