Monte Carlo Tree Search

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

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

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

Сыграйте несколько ходов и ищите число камней, после которого любой ваш выбор оставляет сопернику выигрышный ответ. Сформулируйте правило для таких позиций и проверьте его на другой стадии партии.

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

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

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

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

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

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

Сначала выполните несколько раундов по одному и перед каждым назовите автомат с наибольшей оценкой UCB. Затем увеличьте число раундов. Может ли алгоритм выбрать автомат с меньшим средним выигрышем и чем он это компенсирует?

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

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

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

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

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

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

Пройдите один цикл поиска по фазам. Перед каждой следующей фазой укажите, что должно измениться: путь выбора, состав дерева или статистика вершин. Затем выполните ещё один цикл и объясните, какую информацию он использует от первого.

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

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

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

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

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

Сначала выберите небольшой бюджет поиска и сыграйте партию, затем сравните решения при большем бюджете. Отделяйте число исследованных продолжений от исхода одной партии: почему отдельная победа или ошибка ещё не измеряет качество поиска?