Задание 19-20-21 КЕГЭ: как организовать перебор позиций игры, чтобы найти выигрышную стратегию?
Знаю, что задания 19–21 про теорию игр решаются перебором, и видел общую идею выигрышной стратегии. Но конкретно не понимаю, как написать саму функцию, которая определяет, выигрышная позиция или проигрышная. Можете показать каркас для типовой игры с кучей камней?
2 ответа
Каркас на рекурсии с двумя функциями: "может ли игрок выиграть из позиции s". Допустим, ходы: добавить 1 камень или умножить на 2; победа — когда камней >= 30.
def hod(s):
return [s + 1, s * 2] # все возможные ходы из позиции s
def win(s):
# позиция выигрышная, если есть ход, ведущий в проигрышную для соперника
if s >= 30:
return False # уже конец — тот, кто получил такую, проиграл по условию
return any(not win(h) for h in hod(s) if h < 30 or True)
Идея ключевая:
- Проигрышная позиция — все ходы ведут в выигрышные для соперника.
- Выигрышная позиция — есть хотя бы один ход в проигрышную для соперника.
Задание 19 (Петя/первый игрок выигрывает первым ходом), 20, 21 различаются формулировкой "за сколько ходов". Удобнее писать функции win1, win2, lose1 под конкретный вопрос задания — но в основе всегда эта рекурсия "выигрышная = есть ход в проигрышную соперника".
Аккуратно перепиши условие победы и ходы ровно из задания — остальное каркас сделает.
Совет по структуре под три задания сразу. Заведи функции:
lose(s)— позиция проигрышная для того, кто ходит;win(s)— выигрышная;- и при необходимости
win2(s)— выигрыш не более чем за 2 хода.
Задание 19 обычно про значение S, при котором первый игрок выигрывает СВОИМ первым ходом. 20–21 — про "за сколько ходов" и кто именно (Петя/Ваня). Перебираешь нужные S и проверяешь соответствующую функцию. Главное — base case: "камней достаточно для победы" должен совпадать с условием задачи дословно, иначе вся рекурсия посыпется.