Обучение с подкреплением · часть 1

Как программа учится играть, ничего не зная про игру заранее — просто разыгрывая тысячи случайных партий и постепенно понимая, куда стоит смотреть внимательнее.

Начать с игры → Сразу к алгоритму
Раздел 1 · Правила

Игра с камнями

Перед двумя игроками лежит куча камней. Игроки ходят по очереди. За один ход можно забрать 1, 2 или 3 камня. Кто забирает последний камень — побеждает.

Сыграйте сами против простого соперника, чтобы почувствовать игру. Начинаете вы.

Раздел 2 · Выбор

Дилемма: исследовать или использовать?

Прежде чем строить дерево, решим маленькую, но ключевую задачу. Представьте три игровых автомата. У каждого свой скрытый шанс выплаты, но вы его не знаете — узнать можно только дёргая ручку и глядя на результат. У вас ограниченное число попыток. Куда их тратить?

Возникает противоречие. Можно использовать (exploitation) — дёргать тот автомат, что пока приносит больше всего выигрышей. А можно исследовать (exploration) — пробовать редкие автоматы: вдруг один из них на самом деле лучше, просто ему не повезло на первых попытках. Всё время делать только одно — проигрышная стратегия.

Решение — оценка UCB1 (Upper Confidence Bound). Для варианта i, который выбирали N_i раз и который дал W_i выигрышей, при общем числе попыток N:

\mathrm{UCB1}(i) \;=\; \underbrace{\frac{W_i}{N_i}}_{\text{использование}} \;+\; c \,\underbrace{\sqrt{\frac{\ln N}{N_i}}}_{\text{исследование}}

Каждый раунд выбирается вариант с наибольшим \mathrm{UCB1}.

Левое слагаемое W_i/N_i — это средний выигрыш, оно тянет к проверенным вариантам. Правое — бонус за новизну: он велик, когда N_i мало́ (вариант редко пробовали), и тает по мере проб. Константа c (часто c=\sqrt{2}) задаёт, насколько алгоритм «любопытен».

Понаблюдайте: первые раунды UCB1 раздаёт по очереди всем автоматам (у нетронутых бонус бесконечный), потом всё чаще возвращается к лучшему — но никогда не бросает остальные совсем. Ровно этот механизм MCTS применяет на шаге Selection, спускаясь по дереву. Посмотрим, как из четырёх таких шагов складывается весь алгоритм.

Раздел 3 · Идея

Четыре шага, повторённые тысячи раз

MCTS не строит дерево целиком. Вместо этого он выращивает его по чуть-чуть, повторяя один и тот же цикл из четырёх шагов. Каждый цикл — это одна «прикидка» того, насколько хорош тот или иной ход.

1

Selection
Выбор

Спускаемся по дереву, выбирая многообещающие узлы, пока не дойдём до края изученного.

2

Expansion
Расширение

Добавляем в дерево новый, ещё не исследованный узел-ребёнка.

3

Simulation
Симуляция

Доигрываем партию до конца случайными ходами и смотрим, кто победил.

4

Backprop
Обратный ход

Несём результат вверх по дереву, обновляя статистику всех пройденных узлов.

Каждый узел дерева хранит всего два числа: N — сколько раз через него прошли, и W — сколько из этих раз привели к победе. Отношение W/N — это оценка «насколько хорош этот ход». Чем больше циклов, тем точнее оценка.

Раздел 4 · Алгоритм вживую

Один цикл MCTS, шаг за шагом

Ниже — настоящий MCTS, работающий на нашей игре с камнями. Жмите «Шаг», чтобы пройти фазы по очереди, или «×100», чтобы прогнать сотню циклов и увидеть, как дерево умнеет.

Обратите внимание: со временем алгоритм почти перестаёт спускаться в плохие ветки — рёбра к ним становятся тонкими, а N почти не растёт. Зато выигрышный ход исследуется всё глубже. Это и есть асимметричный рост дерева — фирменная черта MCTS.

Раздел 5 · Решение

А какой ход в итоге сделать?

Когда «время на размышление» вышло, бонус за исследование больше не нужен — рисковать незачем. Поэтому финальный ход выбирают не по UCB1, а просто по числу посещений N: самый «обкатанный» ребёнок корня и есть самый надёжный ход.

\text{ход}^{\star} \;=\; \arg\max_{i \,\in\, \text{дети корня}} N_i

Robust child: чаще всего посещали — значит, симуляции стабильно его одобряли.

Полный игрок просто оборачивает всё это в цикл: «подумал K циклов → сходил → соперник сходил → снова подумал». Попробуйте сыграть против настоящего MCTS, который вы только что построили:

Итог

Что мы узнали

MCTS — это четыре строчки идеи, повторённые много раз:

  1. Selection — спускаемся по \mathrm{UCB1}, балансируя исследование и использование
  2. Expansion — добавляем новый узел на границе знания
  3. Simulation — доигрываем случайно до результата
  4. Backpropagation — обновляем N и W вверх по пути

Эта же схема, усиленная нейросетями для оценки позиций и приоритезации ходов, лежит в основе AlphaGo и AlphaZero. Разница — в масштабе и в том, что случайные доигровки заменяет обученная сеть. Но скелет — ровно тот, что вы только что собрали на куче камней.

\begin{aligned} \pi(s) &= \arg\max_{a}\, N(s,a),\\[4pt] a_{\text{sel}} &= \arg\max_{a}\left[ Q(s,a) + c\sqrt{\tfrac{\ln N(s)}{N(s,a)}}\,\right] \end{aligned}

Слева — итоговое решение, справа — правило спуска. Весь MCTS в двух формулах.