Дискретные игры двух игроков

Содержание и основные понятия

← Вернуться к оглавлению
Alterna · глава 18 · страница 18.1
Дискретные игры двух игроков
Элементы игры, анализ с конца, симулятор с ИИ.
На ЕГЭ №19, 20, 21 — игра двух игроков с камешками/числами. Секрет:
анализ с конца
. Помечаем проигрышные позиции (L) — это кратные K+1. Остальные — выигрышные (W). ИИ в симуляторе играет оптимально.
ФГОС
ФОП
ЕГЭ №19,20,21
01
Элементы игры
Игроки
— два (Петя и Вася, или Первый и Второй).
Позиция
— текущее состояние (например, число камней S).
Ход
— преобразование позиции по правилам.
Правила
— допустимые ходы (например, +1 или *2).
Цель
— достичь выигрышного условия (≥N, последний ход).
Стратегия
— план на все ходы, гарантирующий выигрыш.
02
Анализ с конца
Алгоритм
Отметить
выигрышную конечную позицию
(S ≥ N) как W.
Пометить позицию как
L (проигрышная)
, если ВСЕ её ходы ведут в W.
Пометить позицию как
W (выигрышная)
, если хотя бы один ход ведёт в L.
Повторять, пока не разметим все позиции.
Ключевой паттерн
Для игры «1..N, за ход +1 или *2, достигнуть ≥N» проигрышные позиции — это кратные
(K+1)
, где K=2 (умножение). Например, для N=20: 3, 6, 9, 12, 15, 18 — проигрышные (если ходишь первым и цель ≥20).
03
Игра с ИИ: «Камешки +1 или ×2»
Ты играешь против оптимального ИИ. Цель: достигнуть ≥N.
🎮
Игра с ИИ: достигни N
Цель N
Стартовое S
Сделай ход!