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

Опубликовано: 25 Июля, 2021

Поиск по дереву Монте-Карло (MCTS) - это метод поиска в области искусственного интеллекта (AI). Это вероятностный и эвристический алгоритм поиска, который сочетает в себе реализации классического поиска по дереву с принципами машинного обучения обучения с подкреплением.

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

Исследование помогает исследовать и обнаруживать неисследованные части дерева, что может привести к поиску более оптимального пути. Другими словами, мы можем сказать, что исследование расширяет ширину дерева больше, чем его глубину. Исследование может быть полезным, чтобы убедиться, что MCTS не упускает из виду потенциально лучшие пути. Но быстро становится неэффективным в ситуациях с большим количеством шагов или повторений. Чтобы этого избежать, она уравновешивается эксплуатацией. Эксплуатация придерживается единственного пути, имеющего наибольшую оценочную ценность. Это жадный подход, и он увеличит глубину дерева больше, чем его ширину. Проще говоря, формула UCB, применяемая к деревьям, помогает сбалансировать компромисс между исследованием и эксплуатацией, периодически исследуя относительно неисследованные узлы дерева и обнаруживая потенциально более оптимальные пути, чем тот, который он использует в настоящее время.
Благодаря этой характеристике MCTS становится особенно полезным при принятии оптимальных решений в задачах искусственного интеллекта (AI).

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

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

где;
S _i = значение узла i
x _i = эмпирическое среднее значение узла i
C = постоянная
t = общее количество симуляций

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

Вышеупомянутые шаги можно визуально понять по схеме, представленной ниже:

Эти типы алгоритмов особенно полезны в пошаговых играх, где нет элемента случайности в игровой механике, таких как крестики-нолики, соединение 4, шашки, шахматы, го и т. Д. Это недавно использовалось программами искусственного интеллекта, такими как AlphaGo, чтобы играть против лучших мировых игроков в го. Но его применение не ограничивается только играми. Его можно использовать в любой ситуации, которая описывается парами состояние-действие и моделированием, используемым для прогнозирования результатов.

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

 # main function for the Monte Carlo Tree Search
 def monte_carlo_tree_search(root):
     
    while resources_left(time, computational power):
        leaf = traverse(root)
        simulation_result = rollout(leaf)
        backpropagate(leaf, simulation_result)
         
    return best_child(root)
 
# function for node traversal
 def traverse(node):
    while fully_expanded(node):
        node = best_uct(node)
         
    # in case no children are present / node is terminal
    return pick_univisted(node.children) or node
 
# function for the result of the simulation
 def rollout(node):
    while non_terminal(node):
        node = rollout_policy(node)
    return result(node)
 
# function for randomly selecting a child node
 def rollout_policy(node):
    return pick_random(node.children)
 
# function for backpropagation
 def backpropagate(node, result):
    if is_root(node) return
    node.stats = update_stats(node, result)
    backpropagate(node.parent)
 
# function for selecting the best child
 # node with highest number of visits
 def best_child(node):
    pick child with highest number of visits

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

Преимущества поиска по дереву Монте-Карло:

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

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

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

Машинное обучение Technical Scripter Продвинутая компьютерная тематика

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

РЕКОМЕНДУЕМЫЕ СТАТЬИ