Выигрышные и проигрышные состояния в играх
Рассуждайте о победителе при оптимальной игре
«Выигрышные и проигрышные состояния в играх» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Два игрока, идеальная игра
В комбинаторной игре два игрока ходят по очереди, оба играют идеально, а проигрывает тот, кто не может сделать ход. Ваша задача — определить победителя. 🎯
У каждой позиции есть метка
Каждая игровая позиция — это состояние. Ваша задача — пометить каждое состояние как выигрышное или проигрышное для игрока, которому предстоит ходить.
Что означает выигрышное состояние
Состояние является выигрышным состоянием, если у игрока, которому предстоит ходить, есть хотя бы один ход в проигрышное состояние соперника.
Что означает проигрышное состояние
Состояние является проигрышным состоянием, если любой сделанный Вами ход передаёт сопернику выигрышное состояние. Вы проигрываете при любом выборе.
Базовый случай
Позиция, в которой невозможно сделать ни одного хода, — это базовый случай. Игрок, оказавшийся в ней, уже проиграл, поэтому пометьте её как проигрышную.
Строим решение снизу вверх
Начните с базовых случаев и двигайтесь наружу. Метка каждого нового состояния зависит только от состояний, в которые ведут его ходы.
Достаточно одного хорошего хода
Чтобы выиграть, Вам нужен всего один ход в проигрышное состояние соперника. Достаточно найти любой путь к спасению.
Небольшой пример
Из кучки можно брать 1 или 2 камня, последний взявший выигрывает. При наличии 0 камней игрок, которому предстоит ходить, проигрывает, поэтому это проигрышное состояние.
Программируем проверку выигрыша
Эта рекурсия помечает состояние, перебирая все ходы и рекурсивно обрабатывая результат. ⚙️
def win(n):
if n == 0:
return False
return any(not win(n - k) for k in (1, 2))Мемоизация сохраняет скорость
Состояния повторяются в разных ветвях, поэтому сохраняйте каждый результат. Простая мемоизация превращает экспоненциальный объём работы в линейный.
from functools import lru_cache
@lru_cache(None)
def win(n):
return n != 0 and any(not win(n - k) for k in (1, 2))Симметрия как сокращённый путь
Если позиция идеально симметрична, второй игрок часто может зеркально повторять ходы и победить. Следите за этим приёмом.
Быстрая проверка
Вы оказались в некотором состоянии. Когда оно является для Вас проигрышным?
Итоги
Теперь Вы умеете помечать состояния: win означает наличие хода в проигрышное состояние соперника, а в проигрышном состоянии такого хода нет. Стройте решение от базовых случаев и используйте мемоизацию. 🧠
Изучай Coding Interview Prep с ИИ-репетитором — бесплатно
Пиши и запускай код прямо в браузере, получай мгновенную помощь от ИИ-репетитора 24/7 и продолжи учиться на сайте или в приложении.
- Курсы
- 90
- Уроки
- 360
Часто задаваемые вопросы
Урок «Выигрышные и проигрышные состояния в играх» бесплатный?
Да — полный текст урока «Выигрышные и проигрышные состояния в играх» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Выигрышные и проигрышные состояния в играх»?
Рассуждайте о победителе при оптимальной игре Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Выигрышные и проигрышные состояния в играх»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Выигрышные и проигрышные состояния в играх
- Ним и число Гранди
- Встреча посередине
- Быстрая отладка: стресс-тесты и сортировка ошибок