Дидактические цели
Как машина может научиться играть, если никто не учит её стратегии? Этот лаб для средней школы и бахильерато отвечает на вопрос самой красивой и конкретной идеей искусственного интеллекта — обучением с подкреплением. Шаг за шагом мы воссоздаём машину из спичечных коробков Дональда Мичи (MENACE) и робота Гексапона Мартина Гарднера: ящики с фишками, которые, поощряя ходы, ведущие к победе, и наказывая ходы, ведущие к поражению, сами находят безупречный ход. В конце мы делаем скачок: игра, в которой нет фиксированного оптимального хода, потому что лучший выбор зависит от того, что сделает другой.
Чему учимся
Интуиции о том, что машина может учиться на опыте, подстраивая вероятности, и ей не нужно программировать стратегию: достаточно многократных поощрений и наказаний.
- Блок A — Игра в камни (залы 1-9): сначала ученик играет против случайного соперника (выиграть легко), затем против ИИ с безупречной игрой и обнаруживает, что существует выигрышная стратегия (оставлять сопернику число, кратное 4: 4 и 8). Затем механизм разбирается по шагам: как ИИ выбирает ящик (сумма фишек → случайное число → подсчёт ящик за ящиком) в одной позиции и во всех шести; опасность вычитания 1 (наказание хороших ходов за последующие ошибки опустошает ящики), которая приводит к идее умножать на коэффициент; ученик играет против обучающегося ИИ; наконец, ИИ играет сам с собой — с анимацией во времени сходимости, скоростью обучения и обучением по учебному плану (curriculum).
- Блок B — Гексапон (залы 10-14): тот же принцип на игре Гарднера 3×3, но с добавлением другой стороны медали: полного дерева игры и алгоритма минимакса (максимина). Главный вывод: ящики сами учатся тому же ходу, который минимакс вычисляет напрямую, — обучение и поиск приходят к одному и тому же.
- Блок C — Работа в команде (залы 15-18): кооперативная игра двух игроков с тремя стратегиями (стараться, делать мало, ничего не делать), в которой зачёт получают, если совместное усилие достигает порога N. Здесь нет единственного оптимального хода: два ИИ, обучающихся одновременно, могут прийти к справедливому сотрудничеству, к несправедливому распределению работы (безбилетничеству) или к краху — в зависимости от порога. Это живая теория игр: от дилеммы добровольца (N=2) до охоты на оленя (N=4).
Ключевые математические идеи
- Обучение с подкреплением: поощрение и наказание действий для максимизации ожидаемой награды без заранее заданной модели игры.
- Выбор по вероятности (рулетка): вероятность каждого хода пропорциональна числу фишек в его ящике; исследование против использования найденного.
- Мультипликативное подкрепление и скорость обучения: умножение содержимого ящика на коэффициент (>1 поощряет, <1 наказывает) никогда не опустошает его полностью; коэффициент и есть скорость обучения, а его неудачный выбор нарушает сходимость.
- Игра в камни и стратегия кратных 4: проигрышные позиции игры из 10 камней (берут 1-3, выигрывает взявший последний) — числа, кратные 4.
- Дерево игры и минимакс: каждый игрок максимизирует свой результат, предполагая, что соперник минимизирует его; значение передаётся от листьев вверх, чтобы узнать исход при безупречной игре.
- Кооперативные игры с порогом: дилемма добровольца и охота на оленя, множественные равновесия (справедливое и несправедливое, сотрудничество и крах) и проблема безбилетника (free-rider).
- Самоигра нескольких агентов (self-play): несколько обучающихся, тренирующихся друг против друга; поведение (чистое или смешанное) возникает само и его можно визуализировать как эволюцию вероятностей во времени.
Содержание по залам
Зал 1 · Игра в 10 камней
Объясняются правила: есть 10 камней, игроки по очереди берут 1, 2 или 3; выигрывает тот, кто возьмёт последний. Ученик играет против соперника, который ходит наугад, и убеждается, что выиграть очень легко.
Задания для ученика
- Сыграть несколько партий против случайного соперника.
- Заметить, что выиграть у игрока, ходящего наугад, почти всегда легко.
Зал 2 · Есть ли выигрышная стратегия?
Теперь соперник — ИИ, играющий безупречно; иногда он начинает первым, иногда ученик. После 4 партий появляется сообщение «Уже не так легко обыграть ИИ, правда?», и нужно определить, сколько камней надо оставить сопернику, чтобы выиграть (кнопки от 1 до 10).
Задания для ученика
- Сыграть 4 партии против безупречного ИИ и присмотреться к его ходам.
- Отметить проигрышные позиции: 4 и 8 (оставлять сопернику число, кратное 4).
Зал 3 · Как ИИ выбирает ящик?
Шаг, который ученики обычно не видят: как ИИ выбирает ящик. В одной позиции с 3 ящиками фишек медленная анимация складывает все фишки (+700 мс), выбирает случайное число от 1 до суммы (+700 мс), пересчитывает фишки ящик за ящиком (по 200 мс на каждую) и подсвечивает ящик, на который пришлось число. Затем ученик решает 3 задачи: по раскладу фишек и числу выбрать нужный ящик.
Задания для ученика
- Посмотреть по шагам анимацию выбора методом рулетки.
- Правильно выбрать ящик во всех 3 задачах.
Зал 4 · Играйте с ИИ, шаг за шагом
Ученик играет кнопками «Взять 1/2/3» против ИИ на коробках (фишки целые, по 3 в ящике, чтобы эффект был заметнее). Ход ИИ комментируется очень медленно — сумма фишек, случайное число, пересчёт ящик за ящиком и подсветка ящика — и записывается в протокол (6 → ИИ берёт 2 → 4 → вы берёте 3 → …). Когда кто-то выигрывает, ящики, которыми пользовался ИИ, пересчитываются на ±1 фишку, ход за ходом, и остаются подсвеченными. После первой партии задаётся вопрос, что произошло с вероятностью каждой стратегии. В следующих партиях пересчёт ускоряется, чтобы не утомлять.
Задания для ученика
- Сыграть полную партию, следя за комментируемым ходом ИИ.
- Посмотреть пересчёт ±1 и ответить, что произошло с вероятностями.
Зал 5 · Опасность вычитания 1
Первая идея обучения с целыми фишками: после поражения убирать по 1 фишке из каждого использованного ящика. Демонстрация показывает её недостаток: верный ход (взять 2 в позиции 6) наказывается из-за более поздней ошибки. После 5 повторений ящик верного хода пустеет, и ИИ больше никогда его не делает. Отсюда идея умножать на коэффициент вместо вычитания.
Задания для ученика
- Посмотреть, как после 5 поражений пустеет ящик верного хода в позиции 6.
- Понять, почему лучше умножать, а не вычитать.
Зал 6 · Играйте с обучающимся ИИ
Теперь ученик играет против ИИ на коробках, и ИИ всегда начинает первым. После каждой партии вместо вычитания ящики умножаются на коэффициент: ходы победителя — на число больше 1, ходы проигравшего — на число меньше 1 (до 0 они никогда не доходят). ИИ учится и на ходах соперника: если выиграл ученик, усиливаются сделанные им ходы. После 6 партий ученик предсказывает, как сыграет ИИ в начале (6 камней) и при 3 камнях, и сравнивает это с реально выученной стратегией. Продолжить можно только после того, как сыграно не меньше 7 партий.
Задания для ученика
- Сыграть не менее 7 партий против ИИ (он начинает).
- Предсказать наиболее вероятный ход ИИ при 6 и при 3 камнях и сравнить с тем, чему он научился.
Зал 7 · ИИ играет сам с собой
При том же виде коробок есть кнопки «сыграть 1 раз», «сыграть 5 раз» (с паузой 1 с между партиями) и «сыграть 20 раз». Анимация во времени показывает, как от партии к партии меняется вероятность каждой стратегии в каждой позиции, пока она не сойдётся к верному ходу (оставлять число, кратное 4).
Задания для ученика
- Запускать серии самоигры разной длины.
- Проследить по графику, как каждая позиция сходится (или не сходится) к стратегии.
Зал 8 · Скорость обучения
Объясняется, почему лучше умножать на коэффициент, чем вычитать фишки: так ящик никогда не доходит до 0 и не становится «мёртвым». Этот коэффициент и есть скорость обучения. С помощью ползунка пробуют крайние значения и смотрят, к чему они приводят: при слишком большом ИИ застревает на поспешно выбранной стратегии, при слишком малом не сходится.
Задания для ученика
- Попробовать большие и малые коэффициенты и проследить сходимость.
- Найти разумный диапазон скорости обучения.
Зал 9 · Обучение по программе
Два ИИ обучаются самоигрой с 30 камнями, и обоим даётся ОДИНАКОВОЕ общее число ходов (так сравнение честное, потому что партии по программе, с небольшим числом камней, короче). Один всегда тренируется с 30 камней, другой — по программе, от нескольких камней до 30. Полоса из 30 клеток для каждого ИИ показывает, какие позиции он выучил (зелёные), а какие нет (серые). При тех же усилиях обучение по программе осваивает заметно больше позиций (~90 % против ~75 %), потому что при игре всегда с 30 камней многие позиции остаются недотренированными. Обучение по программе играет ключевую роль в огромных играх (шахматы, го).
Задания для ученика
- Обучить оба ИИ и сравнить их полосы выученных позиций.
- Объяснить, почему при том же числе ходов обучение по программе даёт больше.
Зал 10 · Гексапешка Гарднера
Знакомство с гексапешкой: доска 3×3, у каждой стороны по 3 пешки, которые ходят как в шахматах (идут прямо, бьют по диагонали). Выигрывает тот, кто проведёт пешку на противоположный ряд или оставит соперника без ходов. Ученик играет против случайного соперника.
Задания для ученика
- Разобраться, как пешки ходят и бьют.
- Сыграть несколько партий против случайного соперника.
Зал 11 · Дерево игры
Подробно объясняется, что такое дерево игры: все возможные партии, нарисованные вместе, где каждая стрелка — ход, а каждая ветвь сверху вниз — полная партия. Начальная доска мигает, и ученик раскрывает узлы касанием. Каждый лист показывает, кто выигрывает («У красных нет ходов: выигрывают белые»). Задание: найти самую короткую и самую длинную партию (3 и 7 ходов).
Задания для ученика
- Раскрыть дерево и пройти полные ветви.
- Найти самую короткую (3) и самую длинную (7) партию и записать, сколько в каждой ходов.
Зал 12 · Минимакс
Простыми словами объясняется стратегия минимакса: каждый игрок выбирает лучшее для себя, предполагая, что соперник тоже играет безупречно. Показана ветвь безупречной игры (доски в ряд, зелёный цвет — выигрывает тот, кто ходит, красный — проигрывает), звёздочкой отмечен ключевой ход, который должны найти красные. Два задания с выбором ответа: кто делает ключевой ход и кто выигрывает при безупречной игре (красные, второй игрок).
Задания для ученика
- Определить по ветви, кто делает ключевой ход, отмеченный звёздочкой.
- По цвету начальной доски определить, кто выигрывает в гексапешку при безупречной игре.
Зал 13 · Коробки учатся гексапешке
ИИ на коробках играет красными (второй игрок) против белых, ходящих наугад, и учится с мультипликативным подкреплением (×1,3 за победу, ×0,75 за поражение). Обучение идёт сериями; ВСЕ возможные ходы красных в ключевой позиции НАРИСОВАНЫ вместе с их ВЕСОМ, который меняется по ходу обучения, а график показывает рост доли побед. Под спойлером «Для любознательных» — полная математика подкрепления (E[Δln w]: вес растёт, если ход выигрывает чаще чем примерно в 52 % случаев).
Задания для ученика
- Обучать сериями и следить, как меняются веса ходов в ключевой позиции.
- Убедиться, что оптимальный ход в итоге преобладает и доля побед растёт.
Зал 14 · Сможете обыграть обученный ИИ?
Ученик играет белыми против ИИ, который научился играть (он ходит красными безупречно, по минимаксу). Поскольку при безупречной игре выигрывают красные (второй игрок), обыграть его невозможно: зал даёт попробовать, а после поражения объясняет почему. Кнопка новой партии позволяет попытаться ещё раз.
Задания для ученика
- Сыграть против безупречного ИИ и попытаться выиграть белыми.
- Понять, что при безупречной игре второй игрок (красные) всегда выигрывает.
Зал 15 · Обучение — это поиск (завершение блока)
Завершение блока о гексапешке. Сначала тест из 3 вопросов с подвохом (что изменилось ВНУТРИ ИИ, когда он учился; почему обученный ИИ и минимакс играют одинаково; что происходит с хорошим ходом, который в этот раз проиграл). После ответов открывается раздел «Чему мы научились» и ключевая связь: ВСЕ нейронные сети учатся, настраивая веса; есть ссылка на лаб «Нейронные сети».
Задания для ученика
- Ответить на 3 вопроса вступительного теста.
- Прочитать итоги и при желании перейти к лабу о нейронных сетях.
Зал 16 · Игра в команде
Два игрока одновременно выбирают, сколько усилий приложить: стараться (2), сделать немного (1) или ничего не делать (0). Зачёт они получают, если сумма усилий достигает порога N. Каждый получает 3 за зачёт (или теряет 1 за незачёт) минус собственные усилия. При N=2 исследуется платёжная матрица 3×3, и появляется соблазн проехаться за чужой счёт.
Задания для ученика
- Изучить платёжную матрицу и найти комбинации, при которых ставится зачёт.
- Понять, почему каждый игрок предпочёл бы, чтобы работу сделал другой.
Зал 17 · Два ИИ учатся (N=2)
У каждого игрока свой ящик с 3 стратегиями, и выбор делается по вероятности; два ИИ играют друг с другом и подкрепляют ходы умножением. Диаграмма из сложенных полос (один пиксель на раунд) показывает, как меняются вероятности каждого игрока. Кнопки позволяют сыграть один раз или непрерывно (очень быстро). После достаточного числа раундов появляется вывод с диагнозом результата: справедливое сотрудничество, несправедливое распределение (безбилетничество) или крах.
Задания для ученика
- Запустить самоигру (один раз или непрерывно) и понаблюдать за полосами.
- Прочитать вывод: к какому равновесию приходит команда?
Зал 18 · Поднимаем планку (N=3, N=4)
Обучение повторяется с более высокими порогами, и продолжить нельзя, пока не опробованы N=3 И N=4. При N=3 распределение обычно становится несправедливым: один ИИ видит, что другой всегда старается, и пользуется этим (безбилетничество). При N=4 (преподаватель, требующий совершенства) зачёт ставится, только если оба выбирают (2,2); совпасть так трудно, что ИИ опускают руки — их усилия слишком часто пропадают впустую, и команда разваливается. Возникающее поведение сравнивается при разных порогах.
Задания для ученика
- Обучить ИИ при N=3 и при N=4 (обязательно оба) и прочитать вывод для каждого случая.
- Сравнить, что возникает в зависимости от N: сотрудничество, несправедливое распределение (безбилетничество) или отчаяние и крах.
Зал 19 · Смешанные стратегии (театр или футбол?)
Игра на координацию («семейный спор») от первого лица. Ученик выбирает любимое занятие (ИИ предпочитает другое) и вероятность, с которой пойдёт на своё. 1) «Играть против ИИ»: ИИ КОПИРУЕТ уровень настойчивости ученика, поэтому распределение всегда справедливое (упрямство не приносит победы; крайние значения дают 0). 2) Анимированная самоигра: два ИИ подстраивают стратегии так, чтобы ими нельзя было воспользоваться, и устойчиво сходятся к ≈2/3 (равновесие Нэша). 3) Ученик угадывает оптимальную смешанную стратегию с подсказкой Нэша (партнёру должно быть всё равно, менять ли выбор) и получает очки: 15 за 66-67, 10 за 60-72, 5 за 50-80.
Задания для ученика
- Выбрать любимое занятие и вероятность и сыграть против ИИ (убедиться, что распределение справедливое).
- Посмотреть самоигру и угадать оптимальную вероятность (≈67 %).
Зал 20 · Учиться — настраивать веса
Завершение лаба: научиться самостоятельно — не волшебство, а настройка весов стратегий с помощью поощрений и наказаний. Показаны только выводы (одна стратегия: преобладает один вес, как в игре в камни или в гексапешке; смешанная стратегия: веса распределены; или всё зависит от другого игрока), заключительная фраза, связывающая это с нейронными сетями, и ссылка на лаб «Нейронные сети». Вопроса нет.
Задания для ученика
- Прочитать выводы лаба.
- При желании перейти к лабу «Нейронные сети».
Залы для показа
Самые наглядные для показа и обсуждения в классе.