Теория игр: выигрышная стратегия

На экзамене

Задания 19, 20 и 21. Нужно классифицировать позиции и доказать стратегию при любых допустимых ответах соперника.

Формулы и факты

• Позиция: полное состояние игры, например S или пара (a, b).
• Терминальная позиция: условие окончания уже выполнено.
• Выигрышная позиция: существует ход в проигрышную позицию соперника.
• Проигрышная позиция: все ходы ведут в выигрышные позиции соперника.

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

Алгоритм

1. Запиши позицию, терминальное условие и все функции перехода.
2. Для двух куч примени каждую разрешенную команду к каждой куче.
3. Отметь W1: позиции с немедленным выигрышным ходом.
4. Отметь L1: позиции, из которых каждый ход ведет в W1.
5. Продолжай разметку слоями до нужного числа ходов.
6. Учти точные слова: "именно", "не позднее", "после любого хода", "при неудачной игре".
7. Выбери требуемый минимум, максимум или набор значений и проверь стратегию по всем ответам соперника.

Ловушки

• Путают: выигрышную стратегию и путь с ошибкой соперника. Сверь: проверь все ответы соперника.
• Путают: терминальную позицию и позицию для продолжения игры. Сверь: цель проверяется до новых ходов.
• Путают: "именно вторым" и "не позднее второго". Сверь: для "именно" исключи W1.
• Путают: строгое и нестрогое условие цели. Сверь: отдельно проверь граничное значение.