Деревья решений и выигрышная стратегия
Дерево имеет иерархию без циклов; у каждого узла, кроме корня, один родитель.
В этом занятии
- Самостоятельно решить задачу по теме «Деревья решений и выигрышная стратегия» и объяснить проверку результата.
- Нарисуй дерево игры для 4 камней. Выдели первый ход, который оставляет сопернику проигрышную позицию; объясни обе его возможные реакции.
Пригодится: informatics11-path-counting
Разберёмся перед практикой+
Деревья решений и выигрышная стратегия
Дерево имеет иерархию без циклов; у каждого узла, кроме корня, один родитель. В бинарном дереве у вершины не более двух дочерних узлов. Дерево решений показывает варианты, а дерево игры — последовательности ходов игроков.
В игре с полной информацией состояние и допустимые ходы известны обоим. Выигрышная стратегия обеспечивает победу при любых допустимых ответах соперника, а не только в одной удачной партии. Позиции удобно анализировать от конца: есть ход в проигрышную позицию соперника или все ходы передают ему выигрыш.
Из кучки берут 1 или 2 камня; взявший последний побеждает. При 1 и 2 камнях текущий игрок выигрывает сразу, при 3 любой ход отдаёт сопернику 1 или 2, поэтому 3 — проигрышная позиция.
- Зафиксируй ходы, очередность и условие победы.
- Проверь все ответы соперника, начиная с конечных позиций.
Открываем цифровую мастерскую…
Попробуй самостоятельно
Запиши рассуждения в черновик или сделай построение на бумаге. Эти задания для самостоятельной работы: автоматической проверки и XP за них пока нет.
- Нарисуй дерево игры для 4 камней. Выдели первый ход, который оставляет сопернику проигрышную позицию; объясни обе его возможные реакции.
- Сначала предположи результат, затем проверь и объясни, что изменилось.
Источники и дальнейшее чтение
Материал изложен своими словами. Здесь можно проверить научные основания и подробнее изучить тему; часть источников — на английском.
Читай и разбирай пример в своём темпе. К практике можно перейти, когда будешь готов.