Деревья. Дискретные игры двух игроков с полной информацией
Цели и задачи
- Цель по SMART: к концу урока научиться строить дерево игры для дискретной игры двух игроков с полной информацией, определять выигрышную стратегию первого или второго игрока и обосновывать её анализом позиций.
- Сформировать представление о дереве игры как модели последовательности ходов, состояний и возможных исходов.
- Научиться различать выигрышные и проигрышные позиции и применять правило анализа с конца игры.
- Развивать умение строить рассуждение по алгоритму, проверять стратегию на всех возможных ответах соперника и аргументировать вывод в паре.
- Показать связь алгоритмов решения игр с рекурсивными процедурами, перебором состояний и задачами повышенной сложности ЕГЭ по информатике.
Планируемые результаты
Личностные
- Осознавать ценность строгого доказательства стратегии по всем возможным ходам, а не только по одному удачному примеру.
- Проявлять познавательный интерес к алгоритмам, математическим моделям и задачам теории игр.
- Оценивать собственный способ рассуждения и принимать необходимость исправления стратегии после обнаружения контрпримера.
- Понимать связь изучаемой темы с будущей профессиональной деятельностью в области программирования, анализа данных и разработки алгоритмов.
Метапредметные
- Строить информационную модель игры в виде дерева состояний и переходов между ними.
- Выделять существенные условия задачи: начальную позицию, допустимые ходы, условие выигрыша и порядок ходов.
- Планировать решение от конечных позиций к начальной, фиксируя результаты анализа в таблице или на схеме.
- Работать в паре, задавать уточняющие вопросы, приводить контрпример и аргументированно защищать вывод.
- Осуществлять самопроверку по критериям: полнота дерева, корректность конечных позиций, доказанность стратегии.
Предметные
- Знать понятия «вершина», «ребро», «лист», «корень», «позиция», «ход», «выигрышная позиция» и «проигрышная позиция».
- Уметь представлять последовательность ходов двух игроков в виде дерева игры.
- Уметь определять тип позиции по результатам возможных ходов: позиция выигрышная, если существует ход в проигрышную позицию; позиция проигрышная, если все ходы ведут в выигрышные позиции.
- Уметь находить выигрышную стратегию одного из игроков и объяснять, почему соперник не может ей помешать.
- Владеть алгоритмом анализа небольшой дискретной игры с полной информацией от листьев дерева к корню.
Универсальные учебные действия (УУД)
Личностные УУД
- Определяют личный уровень понимания темы и формулируют затруднение после диагностического задания.
- Соотносят результат решения с требованием доказать стратегию для всех ответов соперника.
- Проявляют ответственность за собственный вклад в парную исследовательскую работу.
- Формулируют учебную мотивацию через связь деревьев игр с алгоритмическим мышлением.
Регулятивные УУД
- Принимают и уточняют цель анализа игры.
- Планируют построение дерева от начальной позиции к конечным состояниям.
- Осуществляют пошаговый самоконтроль по таблице выигрышных и проигрышных позиций.
- Обнаруживают ошибку в неполном дереве или необоснованном выводе и корректируют решение.
- Оценивают результат по заранее объявленным критериям.
Познавательные УУД
- Выделяют состояние игры и возможные переходы из него.
- Классифицируют позиции по результату при оптимальной игре.
- Устанавливают причинно-следственную связь между конечными позициями и стратегией.
- Моделируют игру с помощью дерева, таблицы и рекурсивного описания.
- Проверяют гипотезу построением полного набора ответов соперника.
Коммуникативные УУД
- Распределяют роли в паре: один строит дерево, другой проверяет полноту ходов.
- Формулируют вопросы к условию и уточняют смысл выигрышной позиции.
- Объясняют партнёру каждый переход в дереве и приводят доказательство стратегии.
- Сравнивают два решения и корректно указывают на контрпример или пропущенный ход.
- Представляют итоговое решение классу в сжатой логической форме.
Подготовка учителя к уроку
- Подготовить презентацию или интерактивную доску с обозначениями вершины, ребра, листа и корня дерева.
- Распечатать карточки для парной работы: по одной карточке базового уровня и одной карточке повышенного уровня на каждую пару.
- Подготовить индивидуальный лист самопроверки с алгоритмом: построить дерево, отметить листья, определить позиции снизу вверх, записать стратегию.
- Вывести на доску условие стартовой игры: на столе лежит одна куча из 7 фишек; за ход игрок добавляет 1 или 2 фишки; выигрывает тот, кто первым получает ровно 10 фишек.
- Подготовить отдельную схему с правилами: «есть ход в проигрышную позицию — позиция выигрышная» и «все ходы ведут в выигрышные позиции — позиция проигрышная».
- Распечатать по одному листу с критериями оценивания на ученика и по одному листу-эталону на пару.
- Подготовить маркеры двух цветов или виртуальные инструменты доски для обозначения выигрышных и проигрышных позиций.
- Организовать таймер на 2–4 минуты для диагностических и парных заданий.
- Подготовить домашнее задание трёх уровней в виде таблицы на экране или в раздаточном материале.
- Оборудование: компьютер учителя, проектор или интерактивная доска, доска, маркеры, карточки, листы самопроверки.
Ход урока
Этап 1. Организационный момент и мотивация (3 мин)
Цель этапа: включить учащихся в исследовательскую деятельность и показать практическую ценность анализа игры.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель приветствует класс и обращается к ученикам: "Сегодня мы будем не просто решать игру, а доказывать, что выбранная стратегия работает при любом ответе соперника. Это важное отличие алгоритмического решения от догадки. Проверьте, что у вас есть тетрадь, ручка и лист для схемы." | Проверяют готовность, записывают дату и тему урока: «Деревья. Дискретные игры двух игроков с полной информацией». Формулируют ожидание: «Нужно научиться находить гарантированный выигрыш». |
2 мин | Учитель показывает на доске позицию: "На столе 7 фишек. Игрок за ход добавляет 1 или 2 фишки. Побеждает тот, кто первым получит ровно 10. Как вы думаете, может ли первый игрок гарантировать победу? Не называйте пока только ответ — объясните, что должен учитывать игрок." Учитель принимает несколько гипотез и фиксирует их без оценки. | Индивидуально формулируют гипотезу, затем обсуждают её с соседом 30 секунд. Предполагают: «Нужно учитывать оба возможных хода соперника», «Первый игрок может заранее оставить сопернику неудобное количество фишек». |
Завершение этапа: учитель подводит итог: "Мы увидели, что одного удачного продолжения недостаточно: соперник может выбрать другой ход. Чтобы проверить стратегию полностью, нам понадобится специальная модель — дерево игры."
Этап 2. Актуализация знаний и выявление затруднения (6 мин)
Цель этапа: актуализировать понятия дерева и алгоритма перебора вариантов, зафиксировать трудность полного доказательства стратегии.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает схему небольшого дерева: "Посмотрите на доску. Как называются точка, соединяющая два состояния, конечная вершина и самая верхняя вершина схемы? Вспомните, где деревья встречаются в информатике." | Указывают на элементы схемы и отвечают: «Вершина», «ребро», «лист», «корень». Называют применения: «файловая система», «дерево решений», «перебор вариантов». |
2 мин | Учитель возвращается к игре: "Перечислите возможные состояния после первого хода и возможные ответы соперника. Почему нельзя рассмотреть только одну последовательность?" Учитель записывает на доске слово «полнота». | В тетради перечисляют состояния и ответы. Объясняют: «У соперника есть несколько вариантов, поэтому нужно проверить каждую ветвь». |
2 мин | Учитель предлагает приём «Подумай — обсуди в паре — поделись»: "Сформулируйте, что должно быть в каждой вершине дерева игры. Подумайте самостоятельно, обсудите с партнёром и назовите общий вариант." | Сначала записывают собственную формулировку, затем обсуждают её в паре и предлагают классу: «Текущее состояние, игрок, которому принадлежит ход, и допустимые переходы». |
Завершение этапа: учитель подводит итог: "Мы вспомнили структуру дерева и поняли, что дерево игры должно содержать все допустимые продолжения. Теперь определим, как по этому дереву отличать позицию, из которой можно гарантировать победу, от позиции, где победа невозможна."
Этап 3. Постановка проблемы и целеполагание (4 мин)
Цель этапа: вывести правило классификации игровых позиций и совместно сформулировать план решения.
Посмотрите план целиком
Зарегистрируйтесь — и откройте план урока по этой теме полностью: цели, ход урока и рефлексия по ФГОС.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель показывает два конечных состояния: "Если ход приводит к тому, что соперник уже проиграл и не может сделать разрешённый ход, как назовём исходную позицию? А если из позиции любой ход отдаёт сопернику возможность выиграть?" Учитель подводит к различию «существует» и «для всех». | Формулируют: «Первая позиция выигрышная, потому что существует удачный ход», «Вторая проигрышная, потому что любой ход ведёт к выигрышной позиции соперника». |
2 мин | Учитель записывает на доске план: "1. Построить все ходы. 2. Отметить конечные позиции. 3. Двигаться от листьев к корню. 4. Найти первый ход и доказать ответы на каждый ход соперника. Согласны ли вы с таким планом? Что добавим?" | Соглашаются или предлагают дополнение: «Нужно проверить, что не пропущены допустимые ходы». Записывают план решения в тетрадь. |
Завершение этапа: учитель подводит итог: "Цель урока сформулирована: научиться строить дерево и доказывать выигрышную стратегию. Переходим к открытию правила анализа позиций снизу вверх."
Этап 4. Открытие нового знания: дерево игры и правило анализа (10 мин)
Цель этапа: сформировать алгоритм анализа дискретной игры двух игроков с полной информацией на конкретном примере.
Время | Действие учителя | Действие учеников |
|---|---|---|
3 мин | Учитель строит на доске дерево для игры с 7 фишками и целью получить ровно 10. Обращается к классу: "Обозначим состояние числом фишек. Из состояния 7 возможны переходы в 8 и 9. Из каждой следующей позиции снова выписываем все разрешённые ходы, пока не получим 10. Лист 10 означает окончание игры. Следите, чтобы каждая ветвь была продолжена до конца." | Перерисовывают в тетрадь часть дерева, подписывают состояния 7, 8, 9 и 10. Проверяют, что из каждой позиции добавляется 1 или 2 фишки. |
3 мин | Учитель выделяет конечные позиции: "Рассмотрим позицию, в которой игрок должен ходить, а после любого его хода соперник получает 10. Такая позиция проигрышная. Если же существует ход, после которого соперник оказывается в проигрышной позиции, исходная позиция выигрышная. Запишем это как правило." | Записывают правило: «Позиция выигрышная, если есть ход в проигрышную позицию. Позиция проигрышная, если все ходы ведут в выигрышные позиции». Объясняют разницу между «есть хотя бы один» и «для каждого». |
2 мин | Учитель задаёт сократительный вопрос: "Почему анализ начинаем с конца, а не с начальной позиции? Представьте, что мы уже знаем статус всех ближайших состояний. Как определить статус текущего?" | Отвечают: «На конечных позициях результат очевиден; затем статус текущей позиции определяется по статусам её потомков». Формулируют связь с рекурсивным алгоритмом. |
2 мин | Учитель предлагает мини-проверку: "Если из позиции есть два хода: один ведёт в проигрышную позицию соперника, другой — в выигрышную, какой статус у текущей позиции? А если оба хода ведут в выигрышные позиции?" | Отвечают: «В первом случае позиция выигрышная, потому что можно выбрать первый ход; во втором — проигрышная». |
Запись в тетрадях
Дерево игры — ориентированное дерево, в котором вершины соответствуют игровым позициям, а рёбра — допустимым ходам. Проигрышная позиция: все допустимые ходы ведут в выигрышные позиции соперника. Выигрышная позиция: существует ход в проигрышную позицию соперника. Анализ выполняется от конечных позиций к начальной.
Завершение этапа: учитель подводит итог: "Теперь у нас есть не только схема, но и правило классификации каждой позиции. Проверим его на полном дереве и убедимся, что стратегия должна учитывать любой ответ соперника."
Этап 5. Первичное закрепление в парах (8 мин)
Цель этапа: применить правило анализа к небольшой игре и проговорить доказательство стратегии в паре.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель раздаёт парам карточки: "Работаем в парах. В игре на столе 5 фишек. За ход можно добавить 1 или 2 фишки. Побеждает тот, кто первым получает ровно 8 фишек. Постройте дерево от 5 до 8. Один участник строит ветви, второй проверяет, что каждый допустимый ход учтён." | Распределяют роли в паре, читают условие и начинают строить дерево состояний 5, 6, 7, 8. |
4 мин | Учитель напоминает алгоритм: "Сначала отметьте конечные позиции, затем двигайтесь к корню. Используйте два цвета: одним отметьте выигрышные позиции, другим — проигрышные. После этого запишите первый ход и ответ на каждый возможный ход соперника." Учитель проходит между парами и задаёт вопросы: "Почему эта позиция проигрышная? Все ли ходы вы проверили?" | В парах строят полное дерево, отмечают позиции цветами, объясняют партнёру каждую отметку. Формулируют стратегию и находят возможный первый ход. |
3 мин | Учитель организует краткую проверку: "Пара, готовая объяснить решение, представьте его у доски. Не называйте только ответ: покажите ветви и используйте слова «существует» и «для всех». Остальные пары ищут возможный контрпример." | Одна пара представляет дерево. Остальные сверяют схемы, задают вопросы и проверяют, не существует ли ответа соперника, нарушающего стратегию. |
Эталон решения
Для игры с 5 фишками и целью получить 8 конечная позиция 8 является выигрышной для игрока, который сделал последний ход. Перед ней позиции 6 и 7 позволяют завершить игру ходом до 8, поэтому они выигрышные для игрока, которому предстоит ход. Из позиции 5 можно перейти в 6 или 7, то есть в каждом случае соперник получает выигрышную позицию. Следовательно, позиция 5 проигрышная для игрока, который начинает с неё. Вывод: гарантированной победы у первого игрока нет; при правильной игре второй игрок использует ответ, дополняющий ход первого до достижения 8.
Завершение этапа: учитель подводит итог: "Вы применили правило к дереву и увидели, что проигрышная позиция определяется не интуицией, а проверкой всех ходов. Теперь каждый самостоятельно решит новую игру и покажет полный ход рассуждений."
Этап 6. Самостоятельная работа с самопроверкой (9 мин)
Цель этапа: проверить индивидуальное умение строить дерево и находить выигрышную стратегию.
Время | Действие учителя | Действие учеников |
|---|---|---|
1 мин | Учитель раздаёт индивидуальные карточки: "Решите задачу самостоятельно. В начале на столе 4 фишки. За ход можно добавить 1 или 2 фишки. Побеждает тот, кто первым получает ровно 7 фишек. Запишите дерево, отметьте типы позиций и укажите, кто выигрывает при правильной игре." | Записывают условие и строят дерево состояний от 4 до 7. |
5 мин | Учитель напоминает критерии: "В решении должны быть все допустимые ходы, обозначения конечных позиций и объяснение стратегии. Если вы считаете, что выигрывает второй игрок, объясните, какой ответ он выбирает после каждого хода первого." | Индивидуально анализируют дерево, отмечают выигрышные и проигрышные позиции, записывают стратегию и проверяют её по всем ветвям. |
3 мин | Учитель выводит эталон на доску: "Сверьте не только итог, но и логику переходов. Поставьте себе отметку по трём вопросам: дерево полное? позиции определены снизу вверх? стратегия доказана для любого ответа соперника?" | Сравнивают решение с эталоном, отмечают совпадения и ошибки, исправляют пропущенные ветви или неверные обозначения. |
Эталон решения
Конечная позиция 7 означает завершение игры. Из позиций 5 и 6 можно сделать ход в 7, поэтому они выигрышные для игрока, которому предстоит ход. Из позиции 4 возможны переходы в 5 и 6, обе позиции выигрышные для следующего игрока. Следовательно, позиция 4 проигрышная для начинающего. При правильной игре выигрывает второй игрок: после хода первого из 4 в 5 второй добавляет 2, а после хода из 4 в 6 второй добавляет 1 и получает 7.
Завершение этапа: учитель подводит итог: "Самостоятельная работа показала, умеете ли вы переходить от схемы к доказательству. Важно не перепутать победу в одной ветви с гарантированной стратегией. Завершим урок проверкой понимания и планом дальнейшей работы."
Этап 7. Рефлексия, оценивание и домашнее задание (5 мин)
Цель этапа: осмыслить способ решения, выявить затруднения и зафиксировать домашнюю исследовательскую задачу.
Время | Действие учителя | Действие учеников |
|---|---|---|
2 мин | Учитель проводит приём «Светофор»: "Покажите цветом уровень понимания: зелёный — могу построить и проанализировать дерево; жёлтый — понимаю правило, но ошибаюсь в ветвях; красный — нужна помощь с различием выигрышной и проигрышной позиции. Одним предложением объясните свой выбор." | Поднимают карточку выбранного цвета и формулируют самооценку: «Мне нужно потренироваться проверять все ходы соперника» или «Я могу доказать стратегию от листьев к корню». |
1 мин | Учитель предлагает «Билет на выход»: "Запишите два коротких ответа: что означает выигрышная позиция и почему при доказательстве нужно рассматривать все ходы соперника?" | Записывают ответы на листе и сдают учителю при выходе. |
2 мин | Учитель показывает таблицу домашнего задания: "Выберите уровень по своей готовности. Обязательная часть предназначена для всех, повышающая требует полного дерева, дополнительная предлагает описать алгоритм. Перед уходом проверьте, что записали условие и критерии проверки." | Записывают выбранный уровень и контрольные вопросы, уточняют непонятные требования. |
Критерии оценивания практической работы
- «5» — полностью построено дерево игры, учтены все допустимые ходы, корректно определены выигрышные и проигрышные позиции, стратегия доказана для каждого ответа соперника.
- «4» — дерево и основной вывод верны, но допущена одна неточность в обозначении позиции или недостаточно подробно объяснён один переход; стратегия в целом подтверждена.
- «3» — построена только часть дерева, верно определены отдельные конечные позиции, но доказательство стратегии неполное или присутствует одна существенная ошибка.
- «2» — дерево не отражает условие игры, типы позиций определены случайно, стратегия не обоснована.
Рефлексия
Вопрос для ученика | Цель вопроса |
|---|---|
Что такое выигрышная позиция и чем она отличается от проигрышной? | Проверка осознания ключевого правила классификации позиций. |
Почему дерево игры нужно анализировать от конечных позиций к начальной? | Выявление понимания логики обратного анализа и рекурсивной зависимости. |
Какой ход или переход оказался самым трудным при построении дерева? | Выявление точек затруднения в моделировании и учёте всех вариантов. |
Можете ли вы доказать стратегию, если соперник выбирает любой допустимый ход? | Проверка перехода от догадки к строгому доказательству полной стратегии. |
Завершающее слово учителя
"Сегодня мы представили дискретную игру как дерево состояний и научились анализировать её от конечных позиций к начальной. Главное — отличать существование удачного хода от гарантированной стратегии против любого ответа соперника. Типичная ошибка — рассмотреть только одну ветвь и объявить победу, не проверив остальные. На следующем уроке мы продолжим работу с играми и обсудим, как подобные рассуждения записываются в виде алгоритмов и программ."
Домашнее задание
Уровень | Что задать | Зачем |
|---|---|---|
Базовый (обязательный) | Решить 2 игры по схеме урока: в начальной позиции 3 фишки за ход можно добавить 1 или 2, цель — получить 6; в начальной позиции 6 фишек за ход можно добавить 1 или 2, цель — получить 9. Для каждой игры построить дерево или его полную часть, определить выигрышную позицию и указать стратегию. | Закрепляет построение дерева и применение правила «существует ход» / «все ходы». При проверке смотреть на полноту переходов и объяснение стратегии. |
Средний (повышающий) | Решить 3 игры с другими начальными значениями и целью, где за ход разрешено прибавлять 1, 2 или 3. Для каждой игры определить, кто выигрывает при правильной игре, и доказать ответ анализом позиций. | Развивает перенос алгоритма на изменённое множество ходов. При проверке смотреть, учтены ли все три варианта хода и не подменено ли доказательство примером одной партии. |
Продвинутый (дополнительный) | Описать псевдокод рекурсивного алгоритма, который получает текущее количество фишек, целевое количество и список разрешённых ходов, а затем определяет, является ли позиция выигрышной. Привести небольшой пример работы алгоритма. | Формирует связь дерева игры с рекурсией, перебором состояний и программной реализацией. При проверке смотреть на базовый случай, перебор ходов и корректное различие условий «существует» и «для всех». |
Контрольные вопросы перед выходом из класса: «Что записывают вершины дерева игры?», «Как определить проигрышную позицию по её потомкам?», «Почему стратегия должна учитывать каждый возможный ход соперника?», «Какой этап анализа выполняется первым — начальная позиция или конечные позиции?»