Monte Carlo Tree Search (MCTS)
Поиск по дереву методом Монте-Карло (MCTS) выбирает действия, разрастая дерево поиска на основе симулированных партий и уделяя внимание перспективным ходам. Этот метод применяют в AlphaGo и робототехнике.
Поиск по дереву методом Монте-Карло (MCTS) — алгоритм планирования, который выбирает следующее действие, разрастая дерево возможных будущих состояний на основе множества симуляций и выделяя больше вычислительного бюджета ходам, которые кажутся наиболее перспективными. Ему достаточно способа генерировать допустимые ходы и их результаты, например правил игры или симулятора; написанная вручную функция оценки не нужна. Это также алгоритм с результатом на любом этапе: если остановить его в любой момент, он вернет лучший найденный ход, а дополнительное время улучшит ответ. Rémi Coulom ввел название метода в 2006 году — в том же году Levente Kocsis и Csaba Szepesvári опубликовали UCT, правило выбора, ставшее стандартной формой метода. За несколько лет MCTS преобразовал компьютерную игру го, позднее стал основой AlphaGo и AlphaZero, а теперь применяется для планирования поведения роботов и транспортных средств, а также для поиска по шагам рассуждения в больших языковых моделях (LLM).
Как работает MCTS#
Поиск строит дерево, корень которого соответствует текущей позиции, а в узлах хранится число посещений и количество посещений, завершившихся победой. Каждая итерация состоит из четырех этапов:
- Выбор: Начиная с корня, алгоритм проходит по полностью исследованным узлам, выбирая дочерний узел с наивысшим показателем UCT. Этот показатель учитывает и высокий процент побед, и редко опробованные ходы.
- Расширение: В первом узле, где есть неопробованный ход, этот ход добавляется как новый дочерний узел.
- Симуляция: Из нового дочернего узла игра доводится до конца, обычно случайными ходами, чтобы получить результат.
- Обратное распространение: Алгоритм возвращается по пройденному пути и обновляет счетчик посещений и число побед каждого узла с учетом результата.
Когда бюджет исчерпан, алгоритм выбирает наиболее посещаемый дочерний узел корня. Это надежнее, чем выбирать ход с самым высоким средним показателем.
Баланс исследования и использования#
UCT рассматривает выбор в каждом узле как задачу многорукого бандита и применяет формулу UCB1: оценка дочернего узла равна доле побед w/n плюс c·√(ln N / n), где n — число посещений дочернего узла, N — число посещений его родителя, а c — константа исследования, теоретически равная √2 и на практике подбираемая. Второе слагаемое уменьшается по мере того, как ход пробуют чаще, поэтому несколько случайных побед не дают одному ходу вытеснить остальные, а к заброшенному ходу со временем возвращаются.
В этом примере на Python MCTS применяется к небольшой игре: игроки по очереди берут от одного до трех камней из кучи в 10 камней, а победа достается тому, кто заберет последний камень.
import math
import random
# Game: players take 1-3 stones in turn, and whoever takes the last stone wins
random.seed(0)
N, W = {(10,): 0}, {} # visits and wins per node; a node is the sequence of pile sizes from the root
def rollout(stones):
"""Play random moves to the end and return 1 if the player to move wins."""
turn = 0
while stones:
stones -= random.randint(1, min(3, stones))
turn ^= 1
return turn
def search(node):
"""Run one MCTS iteration below a node and return 1 if the player to move there wins."""
if node[-1] == 0:
return 0 # the opponent took the last stone
children = [(*node, node[-1] - k) for k in (1, 2, 3) if k <= node[-1]]
unvisited = [c for c in children if c not in N]
if unvisited: # expansion, then simulation
child = random.choice(unvisited)
N[child], W[child] = 0, 0
result = 1 - rollout(child[-1])
else: # selection by UCT, balancing win rate against how rarely a child was tried
child = max(children, key=lambda c: W[c] / N[c] + 1.4 * math.sqrt(math.log(N[node]) / N[c]))
result = 1 - search(child)
N[child] += 1 # backpropagation, with wins counted for the player who moved into the child
W[child] += result
return result
for _ in range(2000):
search((10,))
N[(10,)] += 1
for take in (1, 2, 3):
child = (10, 10 - take)
print(f"Take {take}: {N[child]} visits, win rate {W[child] / N[child]:.2f}")Ход, при котором берут два камня, получает 1 889 из 2 000 посещений и приводит к победе в 91% симуляций; для хода с одним камнем зафиксировано 68 посещений, а с тремя — 43. Это выигрышный ход: если оставить 8 камней, то есть число, кратное 4, первый игрок может отвечать на каждый ход соперника так, чтобы снова оставить число, кратное 4, пока куча не опустеет. Поиск нашел этот ход только благодаря случайным симуляциям и статистике посещений, без заданной стратегии.
От AlphaGo до AlphaZero и MuZero#
Средний коэффициент ветвления в го составляет около 250 допустимых ходов против примерно 35 в шахматах, что делало полный перебор невозможным. С конца 2000-х MCTS стал основой заметного роста силы компьютерной игры в го. AlphaGo от DeepMind направляла MCTS с помощью сети политики, предлагавшей вероятные ходы, и оценивала позиции с помощью сети ценности и быстрых симуляций. В марте 2016 года она победила Lee Sedol со счетом 4:1. AlphaZero и MuZero пошли дальше. AlphaZero полностью отказалась от симуляций, оценивая конечные позиции сетью ценности и обучая ее на партиях против самой себя. Число посещений каждого узла в ходе поиска использовалось как целевое значение для сети политики, поэтому MCTS стал этапом улучшения политики в рамках обучения с подкреплением. MuZero выполняла тот же поиск внутри выученной модели среды, благодаря чему играла в го, шахматы, сёги и игры Atari, не получая их правила.
MCTS для планирования и рассуждений#
Роботы и автономные транспортные средства используют MCTS для планирования действий в неопределенных ситуациях, например при выезде в поток машин. Такие варианты, как POMCP, расширяют метод на частично наблюдаемые марковские процессы принятия решений, отслеживая распределение вероятностей по скрытым состояниям. Для поиска, который планирует действия по изображению с камеры, нужно определить состояние корневого узла: например, роботизированная рука, играющая в шахматы, может использовать модель Ultralytics YOLO26, обученную на изображениях доски, чтобы найти все фигуры, после чего восстановленная позиция станет корнем поиска.
В рассуждениях LLM каждый узел представляет собой частичное решение, а каждое ребро — шаг рассуждения; ветви оценивает модель вознаграждения за ход решения или проверка ответа. rStar-Math от Microsoft использовала MCTS с моделью предпочтений по ходу решения и повысила результат Qwen2.5-Math-7B на бенчмарке MATH с 58,8% до 90,0%. Дерево мыслей вместо этого перебирает шаги рассуждения с поиском в ширину или глубину. Использовать MCTS при обучении оказалось сложнее: DeepSeek назвала этот метод среди неудачных попыток для DeepSeek-R1, поскольку пространство последовательностей токенов намного больше пространства ходов в настольной игре, а обучить модель оценки, направляющую поиск, трудно. Вместо этого R1 обучили с помощью обучения с подкреплением и проверяемыми вознаграждениями.










