Monte Carlo Tree Search (MCTS)

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

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

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

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

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

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

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

Link to this sectionРеальные применения в ИИ#

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

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

Link to this sectionMCTS в сравнении с похожими концепциями#

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

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

Link to this sectionИнтеграция визуального ИИ в 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.