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