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