Поиск по дереву Монте-Карло (MCTS)

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

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

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

1. Выбор: Начиная с корневого узла, алгоритм проходит по дереву вниз, выбирая дочерние узлы, которые обеспечивают баланс между исследованием (пробованием новых путей) и использованием (предпочтением путей с высокими прошлыми вознаграждениями). Формула «Верхней границы доверия, примененной к деревьям» (UCT) является стандартным методом, используемым для управления этим компромиссом.
2. Расширение: если выбранный узел не завершает симуляцию, добавляется один или несколько дочерних узлов, чтобы расширить дерево поиска за счёт неисследованных состояний.
3. Моделирование (прогон): выполняется быстрое, зачастую рандомизированное моделирование от недавно развернутого узла до конца сценария с целью прогнозирования результата.
4. Обратное распространение: Результат моделирования распространяется вверх по дереву, обновляя статистику успешности и значения всех прошедших узлов для использования при последующем выборе.

Приложения реального мира в искусственном интеллекте

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

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

MCTS и связанные концепции

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

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

Интеграция системы искусственного интеллекта для обработки изображений в MCTS

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

Ниже приведен наглядный пример, демонстрирующий, как можно использоватьYOLO 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.