Решение игр перебором на Python

1. 1.

   from functools import lru_cache
   T = 30                    # игра кончается, когда камней не больше T
   def moves(s):
       return [s - 3, s - 6, s // 3]
   @lru_cache(None)
   def win(s):
       # ходящий выигрывает, если есть ход, заканчивающий игру
       # или отдающий сопернику проигрышную позицию
       return any(m <= T or not win(m) for m in moves(s))
   print(win(93))

Ответ: win(93) = False: из 93 ходящий (Петя) проигрывает — на этом и строятся ответы заданий 19–21

1. 1.

   from functools import lru_cache

   KONEC = 30 # игра кончается при куче не больше 30

   def hody(s):
       return [x for x in (s - 3, s - 6, s // 3) if x >= 1]

   def konech(s):
       return s <= KONEC

   @lru_cache(None)
   def win1(s):

   """Ходящий выигрывает первым же ходом.""" return any(konech(h) for h in hody(s))

   @lru_cache(None)
   def win2(s):

   """Ходящий выигрывает вторым ходом при любой игре соперника."""

       for h in hody(s):
           if konech(h):
               continue                # это уже победа первым ходом
           if all((not konech(g)) and win1(g) for g in hody(h)):
               return True
       return False

2. 2. Шаг 1. Как читать win1. Ходящий выигрывает сразу, если существует ход, после которого куча стала не больше тридцати. Это прямой перевод определения «победитель — сделавший последний ход».
3. 3. Шаг 2. Как читать win2. Перебираем наш первый ход h. Он не должен сам заканчивать игру (иначе это победа первым ходом). Дальше ходит соперник: из h он может пойти в любое g, и при каждом g должно выполняться два условия — соперник не выиграл (not konech(g)) и мы выигрываем следующим ходом (win1(g)). Квантор здесь именно «при любом g», отсюда all.
4. 4.

   Шаг 3. Теперь три вопроса банка выражаются короткими условиями.

   Линия 19: «Петя не может выиграть за один ход, но при любом ходе Пети Ваня выигрывает своим первым» — это not win1(S) и одновременно все ходы ведут в позиции, где win1 истинно.

   Линия 20: «у Пети есть выигрышная стратегия: он не выигрывает первым ходом, но выигрывает вторым» — это not win1(S) and win2(S).

   Линия 21: «у Вани есть выигрышная стратегия, он выигрывает первым или вторым ходом, но не всегда первым» — проверяем, что при каждом ходе Пети Ваня выигрывает, и что хотя бы в одной ветви ему нужен второй ход.

5. 5.

   Шаг 4. Код для линии 19:

   for S in range(31, 400):
       if win1(S):
           continue
       if all((not konech(h)) and win1(h) for h in hody(S)):
           print(S)
           break

6. 6. Шаг 5. Программа печатает 93 — совпадает с ручным разбором дерева.
7. 7.

   Шаг 6. Код для линии 20 — одна строка условия:

   otvet = [S for S in range(31, 400) if not win1(S) and win2(S)]
   print(otvet[:2])

8. 8. Шаг 7. Печатается [96, 97]. Задание просит два наименьших значения, и ответ записывают подряд: 9697.
9. 9. Шаг 8. Проверим 96 руками. Ходы из 96: 93, 90 и 32 — ни один не кончает игру, значит Петя первым ходом не выигрывает ✔ Петя выбирает ход в 93. Оттуда Ваня может пойти в 90, 87 или 31 — ни один ход не заканчивает игру, а из каждой этой позиции Петя выигрывает первым ходом (90 → 30, 87 → 29, 31 → 28) ✔ Значит, Петя выигрывает вторым ходом при любой игре Вани.
10. 10. Шаг 9. Для линии 21 проверяем S = 102. Ходы Пети: 99, 96 и 34. Ни один не кончает игру. Из 34 Ваня выигрывает сразу (34 − 6 = 28). А из 99 и 96 Ваня первым ходом не выигрывает, зато ходит в 93 — и дальше, как в шаге 8, добивает вторым ходом. Значит, Ваня выигрывает всегда, но не всегда первым ходом — ровно то, что требует условие. Ответ 102 ✔
11. 11. Шаг 10. Все три ответа программы совпали с эталонными ответами банка. Под свой вариант меняются три вещи: значение KONEC, список ходов в функции hody и условие отбора. Тело win1 и win2 остаётся прежним.

Ответ: 93; 96 и 97; 102

1. 1. Шаг 1. Классическая разметка отвечает на вопрос «кто выигрывает при правильной игре». Она двоичная: позиция либо выигрышная, либо проигрышная, и никаких оттенков.
2. 2. Шаг 2. А вопросы линий 19–21 спрашивают за сколько ходов. «Выигрывает своим первым ходом», «выигрывает вторым ходом», «первым или вторым» — это уже не «кто», а «когда».
3. 3.

   Шаг 3. Разница видна на примере. Позиция S = 93 проигрышная для Пети — это верно, но недостаточно: линия 19 требует, чтобы Ваня выигрывал именно первым своим ходом, а не когда-нибудь. Позиция, где Ваня выигрывает третьим ходом, тоже проигрышная для Пети, но условию не удовлетворяет.

   Именно поэтому в программе заведены две разные функции, win1 и win2, а не одна win.

4. 4.

   Шаг 4. Как устроена классическая функция для сравнения:

   @lru_cache(None)
   def vyigrysh(s):

   """Выигрывает ли тот, чей ход."""

       if konech(s):
           return False          # игра кончена, ходивший до нас победил
       return any(konech(h) or not vyigrysh(h) for h in hody(s))

5. 5. Шаг 5. Она отвечает «да» или «нет» и годится для вопросов вида «у кого есть выигрышная стратегия». Для S = 93 она вернёт False — Петя проигрывает. Но какой это будет ход Вани, первый или пятый, она не скажет.
6. 6. Шаг 6. Практический вывод: читайте, что именно спрашивает вопрос. Если про «выигрышную стратегию» без указания числа ходов — хватит одной функции vyigrysh. Если про первый или второй ход — нужны win1 и win2, и они пишутся по определению, а не выводятся из vyigrysh.
7. 7. Шаг 7. И совет про отладку: печатайте таблицу. for S in range(31, 110): print(S, int(win1(S)), int(win2(S))) показывает сразу всю картину, и видно, где начинаются и кончаются интересные диапазоны. По такой таблице проверяются все три ответа одновременно, и ошибку в условии отбора видно мгновенно.

Ответ: Нужны отдельные функции для «выигрывает первым ходом» и «выигрывает вторым ходом»

1. 1.

   print(' S  сразу  вторым')
   for S in range(90, 106):
       print(f'{S:3d}  {int(win1(S)):5d}  {int(win2(S)):6d}')

2. 2. Шаг 1. Что печатается. Первый столбец — размер кучи, второй — выигрывает ли ходящий первым же ходом, третий — выигрывает ли он вторым ходом при любой игре соперника.
3. 3. Шаг 2. Строки 90, 91, 92: в столбце «сразу» стоят единицы. Из этих позиций ходящий заканчивает игру делением на три: ⌊90/3⌋ = 30, ⌊91/3⌋ = 30, ⌊92/3⌋ = 30.
4. 4. Шаг 3. Строки 93, 94, 95: в обоих столбцах нули. Ходящий не выигрывает ни первым, ни вторым ходом — это проигрышные позиции. Отсюда ответ линии 19: минимальное такое S равно 93.
5. 5. Шаг 4. Строки 96, 97, 98, 99: в столбце «сразу» ноль, в столбце «вторым» единица. Ходящий (то есть Петя) выигрывает вторым ходом. Два наименьших значения — 96 и 97, это ответ линии 20.
6. 6. Шаг 5. Строки 100 и 101: в столбце «сразу» ноль, в «вторым» единица — значит, выигрывает снова Петя, а не Ваня. Для линии 21 они не подходят.
7. 7. Шаг 6. Строка 102: оба нуля, то есть позиция проигрышная для Пети. Но, в отличие от 93–95, Ваня выигрывает здесь не всегда первым ходом — это видно, если построить дерево, и это ответ линии 21.
8. 8. Шаг 7. Вот почему таблица удобнее трёх отдельных запусков: все три ответа читаются из одной картинки, и видно, как позиции группируются блоками. Блок 93–95 проигрышный, блок 96–99 выигрышный вторым ходом, 100–101 тоже, а со 102 начинается следующий проигрышный блок.
9. 9. Шаг 8. Практический совет: печатайте таблицу шире, чем нужно, скажем от 85 до 115. Лишние строки ничего не стоят, зато видны границы блоков, и ошибка в условии отбора сразу бросается в глаза — например, если «выигрышные» позиции идут вперемешку без всякой структуры.
10. 10. Шаг 9. И про диапазон перебора. Начинать с 31 обязательно (условие говорит S ≥ 31), а верхнюю границу берут с запасом — 400 или 1000. Позиции повторяются блоками, поэтому ответ находится в первой же сотне, но узнать это заранее нельзя.

Ответ: 93; 96 и 97; 102 — все три ответа видны в одной таблице