Автор статьи: Андрей Рогов
Введение
Эта статья — третья в серии, посвящённой теории игр. Её следует читать после изучения методов аналитического решения и решения с помощью электронных таблиц. Программированием мы будем пользоваться только для вычислений.
Решая задачу аналитически, мы определяем для каждой позиции, какая она:
- конечная позиция — игра заканчивается, потому что достигнуто окончательное число камней
- В1 — выигрышная позиция за один ход: существует хотя бы один ход в конечную позицию
- П1 — проигрышная позиция за один ход: все ходы ведут в В1
- В2 — выигрышная позиция за два хода: существует хотя бы один ход в П1
- П2 — проигрышная позиция за один (не гарантированно) или два хода; все ходы ведут в В1 или В2
С помощью динамического подхода мы определим каждую позицию в пределах двух ходов. Для хранения позиций можно использовать как списки, так и словари. Мы продемонстрируем решение с помощью списков, а вы в качестве упражнения можете реализовать аналогичное решение с использованием словарей.
Будем перебирать все позиции в указанном порядке: сначала определим конечные, затем В1, П1, В2 и П2. По-другому не получится, поскольку найти В1 можно, только определив конечные позиции, найти П1 можно, только зная В1, и т. д. Для конечных позиций не требуется никаких вычислений, они известны заранее.
Все остальные определяем с помощью цикла: для каждой неопределённой позиции проверяем подходящее по виду условие (например, для В1 — что существует ход в конечную позицию). Если позиция удовлетворяет условию, помечаем её.
Рассмотрим решение на примере нескольких заданий.
Задача 1. Одна куча камней, два разных хода
Для хранения позиций заведём список, содержащий нули. Количество нулей определим как позицию для победы, к которой применили «сильный» ход, в нашем случае 301 × 5 = 1500. Впрочем, точное количество можно не определять, а размер списка определить с запасом.
Удобно ввести две переменные под общее количество позиций и количество камней для победы.
n = 2000 # размер списка
win = 301 # количество камней для победы
s = [0] * n
Введём следующие обозначения:
| Обозначение | Позиция |
|---|---|
| 5 | Конечная |
| 1 | В1 — победа первым ходом |
| −1 | П1 — поражение первым ходом |
| 2 | В2 — победа вторым ходом |
| −2 | П2 — поражение первым (не гарантированно) или вторым ходом |
Конечные позиции — все начиная от 301 и больше.
Внесём в соответствующие позиции списка число 5.
# Конечные позиции. Обозначим 5
for i in range(win, n):
s[i] = 5
Для определения позиций В1 необходимо рассмотреть все позиции с 1 до 300 и проверить, есть ли из них ход в конечную. Строго говоря, здесь можно проверять только «сильный» ход. Однако в решении остальных заданий мы будем использовать очень похожий фрагмент кода, который удобно копировать и подстраивать под конкретный вопрос.
# В1 — победа первым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если один из ходов ведёт в конечную
if s[i + 3] == 5 or s[i * 5] == 5:
s[i] = 1 # помечаем позицию как выигрышную
Скопируем этот фрагмент и изменим его. Для поражения все ходы должны вести в В1. Поэтому вместо логического ИЛИ напишем И.
# П1 — поражение первым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если все ходы ведут в В1
if s[i + 3] == 1 and s[i * 5] == 1:
s[i] = -1 # помечаем позицию как проигрышную
Позиции В2 похожи на В1, но хотя бы один ход должен вести не в конечную позицию, а в П1.
# В2 — победа вторым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если один из ходов ведёт в проигрышную за 1 ход
if s[i + 3] == -1 or s[i * 5] == -1:
s[i] = 2 # помечаем позицию как выигрышную
И, наконец, проигрышные за один или два хода ведут либо в 1, либо в 2. Для упрощения проверки условия его можно сформулировать как «больше нуля».
# П2 — поражение первым или вторым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если все ходы ведут в В1 или В2
if s[i + 3] >0 and s[i * 5] > 0:
s[i] = -2 # помечаем позицию как проигрышную
Таким образом, мы просчитали все позиции. Осталось вывести их на экран.
Вывод удобно фильтровать, оставляя только те позиции, которые необходимы для конкретного задания, чтобы не пропустить значения. Для задания № 19 нужны позиции −1, для задания № 20 нужны позиции 2, а для задания № 21 — позиции −2. Приведём полную программу с выводом ответа для 19-го задания.
n = 2000 # размер списка
win = 301 # количество камней для победы
s = [0] * n
# Конечные позиции. Обозначим 5
for i in range(win, n):
s[i] = 5
# В1 — победа первым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если один из ходов ведёт в конечную
if s[i + 3] == 5 or s[i * 5] == 5:
s[i] = 1 # помечаем позицию как выигрышную
# П1 — поражение первым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если все ходы ведут в В1
if s[i + 3] == 1 and s[i * 5] == 1:
s[i] = -1 # помечаем позицию как проигрышную
# В2 — победа вторым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если один из ходов ведёт в проигрышную за 1 ход
if s[i + 3] == -1 or s[i * 5] == -1:
s[i] = 2 # помечаем позицию как выигрышную
# П2 — поражение первым или вторым ходом
for i in range(1, win):
if s[i] == 0: # позиция ещё не определена
# если все ходы ведут в В1 или В2
if s[i + 3] >0 and s[i * 5] > 0:
s[i] = -2 # помечаем позицию как проигрышную
# Для задания № 19 нужны позиции −1
# Для задания № 20 нужны позиции 2
# Для задания № 21 нужны позиции −2
for i in range(win):
if s[i] == -1:
print(i, s[i])
Вывод программы.
Задание № 19
58 −1
59 −1
60 −1
Задание № 20
12 2
55 2
56 2
57 2
Задание № 21
52 −2
53 −2
54 −2
Задача 2. Убирание камней
Поскольку ходы уменьшают количество камней, необходимо развернуть все циклы на возрастание. Определим максимальное S, которое мы будем рассматривать. При определении позиций дважды используется «сильный» ход (для В1 и В2) и дважды — «слабый». Будем брать верхнюю границу S с запасом: 30 × 42 × 2 = 960. Округлим до 1000.
Для определения конечных позиций присвоим всем элементам списка с индексами от 1 до 30 значение 5. В оставшейся части кода заменим все команды действий на соответствующие условию задачи. Приведём полный код.
n = 1000 # размер списка
win = 30 # количество камней для победы
s = [0] * n
# Конечные позиции. Обозначим 5
for i in range(1, win + 1):
s[i] = 5
# В1 — победа первым ходом
for i in range(win, n):
if s[i] == 0: # позиция ещё не определена
# если один из ходов ведёт в конечную
if s[i - 3] == 5 or s[i - 5] == 5 or s[i // 4] == 5:
s[i] = 1 # помечаем позицию как выигрышную
# П1 — поражение первым ходом
for i in range(win, n):
if s[i] == 0: # позиция ещё не определена
# если все ходы ведут в В1
if s[i - 3] == 1 and s[i - 5] == 1 and s[i // 4] == 1:
s[i] = -1 # помечаем позицию как проигрышную
# В2 — победа вторым ходом
for i in range(win, n):
if s[i] == 0: # позиция ещё не определена
# если один из ходов ведёт в проигрышную за 1 ход
if s[i - 3] == -1 or s[i - 5] == -1 or s[i // 4] == -1:
s[i] = 2 # помечаем позицию как выигрышную
# П2 — поражение первым или вторым ходом
for i in range(win, n):
if s[i] == 0: # позиция ещё не определена
# если все ходы ведут в В1 или В2
if s[i - 3] > 0 and s[i - 5] > 0 and s[i // 4] > 0:
s[i] = -2 # помечаем позицию как проигрышную
# Для задания № 19 нужны позиции −1
# Для задания № 20 нужны позиции 2
# Для задания № 21 нужны позиции −2
for i in range(n):
if s[i] == -1:
print(i, s[i])
Вывод программы.
Задание № 19
124 −1
125 −1
126 −1
Задание № 20
127 2
128 2
129 2
130 2
131 2
496 2
497 2
498 2
499 2
500 2
501 2
502 2
503 2
504 2
505 2
506 2
507 2
Задание № 21
132 −2
133 −2
134 −2
508 −2
509 −2
510 −2
Ответом на задание № 19 будет 124, на задание № 20 — 127 и 128, на задание № 21 — 132.
Задача 3. Две кучи камней
Подход к решению остаётся прежний, но, поскольку в задании присутствует две кучи камней, код необходимо адаптировать.
Для хранения игровой позиции используем вложенные списки. В этом случае у каждой позиции будет две «координаты»: 1) количество камней в первой и во второй куче, 2) индекс элемента внутри списка и индекс вложенного списка. Вот пример организации такого списка, содержащего три вложенных, в каждом по три числа.
s = [
[-2, 2, -1],
[-1, 1, 1],
[2, 1, 5]
]
Поскольку каждая позиция характеризуется двумя координатами, для перебора всех позиций необходимо использовать два цикла, один из которых вложен в другой. Вот так необходимо заполнять конечные позиции с учётом того, что условие победы — сумма камней в двух кучах.
n = 200 # размер списка
win = 65 # количество камней для победы
s = [[0] * n for _ in range(n)]
# Конечные позиции. Обозначим 5
for i in range(win + 1):
for j in range(win + 1):
if i + j >= win:
s[i][j] = 5
Поскольку задание № 19 содержит вопрос, который отличается от игровой стратегии заданий № 20 и 21, сначала отдельно найдём ответ на 19-е задание, потом изменим код для заданий № 20 и 21.
Для определения позиции необходимо рассматривать все четыре варианта хода: два для первой кучи камней и два для второй. Поскольку нас интересует неудачный ход, при определении позиций П1 рассмотрим позиции, из которых хотя бы один ход ведёт в В1. Выводить на экран будем только случаи, когда в первой куче 6 камней.
# В1 — победа первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если один из ходов ведёт в конечную
if s[i][j + 1] == 5 or s[i][j * 3] == 5 or s[i + 1][j] == 5 or s[i * 3][j] == 5:
s[i][j] = 1 # помечаем позицию как выигрышную
# Минимальная позиция для неудачного хода Пети
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если один из ходов ведёт в В1
if s[i][j + 1] == 1 or s[i][j * 3] == 1 or s[i + 1][j] == 1 or s[i * 3][j] == 1:
s[i][j] = -1 # помечаем позицию как проигрышную
# Вывод позиций, если в первой куче 6 камней
for i in range(win + 1):
if s[6][i] == -1:
print(i, s[6][i])
Программа выводит достаточно много чисел. Нас интересует минимальное из них: это 7.
7 −1
11 −1
12 −1
13 −1
…
44 −1
45 −1
46 −1
Для решения остальных заданий необходимо изменить поиск позиций П1, поскольку речь уже не идёт про неудачный ход.
n = 200 # размер списка
win = 65 # количество камней для победы
s = [[0] * n for _ in range(n)]
# Конечные позиции. Обозначим 5
for i in range(win + 1):
for j in range(win + 1):
if i + j >= win:
s[i][j] = 5
# В1 — выигрыш первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если один из ходов ведёт в конечную
if s[i][j + 1] == 5 or s[i][j * 3] == 5 or s[i + 1][j] == 5 or s[i * 3][j] == 5:
s[i][j] = 1 # помечаем позицию как выигрышную
# П1 — поражение первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если все ходы ведёт в В1
if s[i][j + 1] == 1 and s[i][j * 3] == 1 and s[i + 1][j] == 1 and s[i * 3][j] == 1:
s[i][j] = -1 # помечаем позицию как проигрышную
# В2 — выигрыш первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если один из ходов ведёт в П1
if s[i][j + 1] == -1 or s[i][j * 3] == -1 or s[i + 1][j] == -1 or s[i * 3][j] == -1:
s[i][j] = 2 # помечаем позицию как выигрышную
# П2 — поражение первым или вторым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если все ходы ведут в В1 или В2
if s[i][j + 1] > 0 and s[i][j * 3] > 0 and s[i + 1][j] > 0 and s[i * 3][j] > 0:
s[i][j] = -2 # помечаем позицию как проигрышную
# Вывод позиций, если в первой куче 6 камней
for i in range(win + 1):
if s[6][i] == -2:
print(i, s[6][i])
Вывод программы.
10 2
19 2
18 −2
Ответы на задания: 19 — 7, 20 — 10 и 19, 21 — 18.
Сокращение кода
Внутри циклов используются довольно громоздкие условия. Их задача — проверить, что выполняется хотя бы одно из условий или все. В Python есть языковые конструкции, позволяющие упростить код.
Функция any() принимает на вход набор логических значений (или сводимых к ним объектам) и возвращает True, если хотя бы один из аргументов функции равен True. В функцию удобно передавать генератор, создающий логические значения.
Функция all() работает схожим образом, но возвращает True, когда все аргументы функции равны True.
Для вычисления ходов заведём отдельную функцию, принимающую текущую позицию и возвращающую набор возможных ходов из неё.
Используя эти конструкции, решение последней задачи можно переписать так:
def move(x, y):
return (x + 1, y), (x * 3, y), (x, y + 1), (x, y * 3)
n = 200 # размер списка
win = 65 # количество камней для победы
s = [[0] * n for _ in range(n)]
# Конечные позиции. Обозначим 5
for i in range(win + 1):
for j in range(win + 1):
if i + j >= win:
s[i][j] = 5
# В1 — выигрыш первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если один из ходов ведёт в конечную
if any(s[x][y] == 5 for x, y in move(i, j)):
s[i][j] = 1 # помечаем позицию как выигрышную
# П1 — поражение первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если все ходы ведёт в В1
if all(s[x][y] == 1 for x, y in move(i, j)):
s[i][j] = -1 # помечаем позицию как проигрышную
# В2 — выигрыш первым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если один из ходов ведёт в П1
if any(s[x][y] == -1 for x, y in move(i, j)):
s[i][j] = 2 # помечаем позицию как выигрышную
# П2 — поражение первым или вторым ходом
for i in range(win + 1):
for j in range(win + 1):
if s[i][j] == 0: # позиция ещё не определена
# если все ходы ведут в В1 или В2
if all(s[x][y] > 0 for x, y in move(i, j)):
s[i][j] = -2 # помечаем позицию как проигрышную
# Вывод позиций, если в первой куче 6 камней
for i in range(win + 1):
if s[6][i] == -2:
print(i, s[6][i])
Заключение
В статье был рассмотрен динамический метод решения заданий № 19–21 ЕГЭ по информатике. Несомненный плюс такого решения заключается в его ориентации на аналитический подход. Мы не организуем совершенно другую логику решения, а просто просчитываем позиции. Повторяемость фрагментов кода позволяет не набирать его с нуля, а получать путём копирования и изменения фрагментов кода.
Этот метод не будет зависеть от объёма вычислений и не потребует кеширования значений, как, например, рекурсивный подход.
Рекомендуем решить подборки задач для практики: