Monte Carlo Tree Search (MCTS)

Поиск по дереву Монте-Карло (MCTS) — это алгоритм эвристического поиска, применяемый для решения сложных задач принятия решений, прежде всего в машинном обучении и искусственном интеллекте. Согласно определению в Википедии, MCTS сочетает точность алгоритмов поиска по дереву с преимуществами случайной выборки (симуляций Монте-Карло) для оценки наиболее перспективных ходов в заданном пространстве состояний. Сначала алгоритм получил известность благодаря успеху в сложных настольных играх, а теперь он стал важным компонентом современных ИИ-агентов и продвинутых систем рассуждения, в том числе новейших больших языковых моделей (LLM).

Как работает поиск по дереву Монте-Карло#

MCTS постепенно строит дерево поиска, исследуя наиболее перспективные действия. Работая в рамках марковского процесса принятия решений, алгоритм последовательно повторяет четыре этапа, пока не исчерпает вычислительный бюджет или не достигнет временного ограничения:

1. Выбор: начиная с корневого узла, алгоритм проходит по дереву, выбирая дочерние узлы, в которых сбалансированы исследование (проверка новых путей) и использование уже известных результатов (предпочтение путей с высокой наградой в прошлом). Для управления этим компромиссом обычно используют формулу верхней доверительной границы для деревьев (UCT).

2. Расширение: если выбранный узел не завершает симуляцию, к нему добавляют один или несколько дочерних узлов, расширяя дерево поиска за счёт ранее не исследованных состояний.

3. Симуляция (розыгрыш): из вновь добавленного узла запускается быстрая, часто случайная симуляция до конца сценария, чтобы предсказать результат.

4. Обратное распространение: результат симуляции распространяется вверх по дереву, обновляя статистику успехов и значения всех пройденных узлов, чтобы учесть их при дальнейшем выборе.

Применение ИИ в реальных задачах#

В подробном обзоре методов поиска по дереву Монте-Карло показано, насколько эффективно этот подход решает задачи с обширными, вычислительно неразрешимыми пространствами поиска.

• Игры: MCTS получил мировую известность, когда Google DeepMind использовала его в AlphaGo, создав первый ИИ, победивший чемпиона мира по игре го. Сочетание MCTS с нейронными сетями позволило системе эффективно оценивать позиции на доске, слишком сложные для обычного полного перебора.
• Рассуждения LLM и агентный ИИ: в 2024 и 2025 годах исследователи всё чаще объединяли MCTS с LLM, чтобы улучшить мышление и логические способности «Системы 2». Например, недавнее исследование автоматизированного проектирования эвристик показывает, как MCTS помогает LLM решать сложные задачи оптимизации. Аналогично, сочетание MCTS с LLM значительно повышает качество ответов на вопросы по базам знаний и математических рассуждений, оценивая несколько возможных логических путей до выбора ответа. Такие организации, как OpenAI, используют механизмы инференса на основе поиска в своих продвинутых моделях, например OpenAI o1, чтобы значительно повысить точность решения задач.
• Робототехника и автономное планирование: MCTS используется для оптимизации логистики и маршрутов, автономных транспортных средств и разбиения действий в робототехнике, позволяя моделировать будущие состояния и безопасно перемещаться в сложных физических средах.

MCTS и связанные с ним понятия#

Чтобы полностью понять MCTS, полезно отличать его от родственных методов ИИ:

• Обучение с подкреплением (RL): при обучении с подкреплением модель со временем учится глобальной стратегии, тогда как MCTS обычно служит алгоритмом планирования, который во время инференса в реальном времени выбирает лучшее немедленное действие для конкретного состояния. Однако эти методы часто объединяют: модели RL могут задавать эвристическую оценку узлов MCTS.
• Дерево мыслей (ToT): ToT — это структура промптов, специально разработанная для LLM. Она во многом основана на MCTS и представляет генерацию языка в виде дерева, где каждый узел соответствует «мысли». MCTS — более общий алгоритмический фундамент, на котором строятся ToT и похожие фреймворки.

Интеграция ИИ для компьютерного зрения в MCTS#

В воплощённом ИИ и автономных системах визуальное восприятие часто используется для оценки состояния узла MCTS. Используя Ultralytics YOLO26, агент может быстро оценить окружение и вычислить эвристическую оценку на этапе симуляции.

Вот концептуальный пример использования модели Ultralytics YOLO для расчёта простой награды узла во время розыгрыша MCTS.

from ultralytics import YOLO

# Load an Ultralytics YOLO26 model for state evaluation
model = YOLO("yolo26n.pt")


def evaluate_mcts_state(image_state):
    # Run inference to evaluate the visual environment
    results = model(image_state, verbose=False)

    # Example heuristic: Reward the MCTS path if an 'obstacle' is successfully avoided
    # Assume class 0 is 'obstacle'. Reward is 1 if path is clear, 0 if blocked.
    obstacle_detected = any(box.cls == 0 for box in results[0].boxes)
    return 0 if obstacle_detected else 1


# Simulate a rollout step
reward = evaluate_mcts_state("path_simulation_view.jpg")
print(f"MCTS Rollout Reward: {reward}")

Для разработчиков, которые хотят масштабировать такие интеллектуальные агенты, платформа Ultralytics предлагает надёжные инструменты для обучения и развёртывания базовых моделей компьютерного зрения. Это значительно упрощает интеграцию быстрого и надёжного восприятия в сложные архитектуры поиска, созданные с помощью стандартных математических библиотек или фреймворков машинного обучения, таких как PyTorch и TensorFlow.