MCTS является краеугольным камнем AlphaGo и многих приложений искусственного интеллекта. Мы стремимся развить интуицию и попутно пачкаем руки.

Поиск по дереву Монте-Карло (MCTS) - важный алгоритм, лежащий в основе многих крупных успехов недавних приложений искусственного интеллекта, таких как поразительное противостояние AlphaGo в 2016 году.

В этом блоге мы сначала начнем с неинформированного поиска, в котором мы просто просматриваем все пространство поиска, чтобы найти оптимумы. Он включает поиск в глубину и поиск в ширину.

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

Неинформированный поиск

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

Дерево с коэффициентом ветвления b и глубиной d будет иметь b ^ d (читается как b в степени d ) количество листовых узлов.

В играх мы используем так называемое игровое дерево, где каждый узел представляет состояние игры, а его дочерние узлы представляют возможные следующие состояния для всех возможных действий, которые может предпринять игрок.

Чтобы дать некоторые идеи, Go имеет средний коэффициент ветвления 250 согласно Википедии. Некоторая обратная сторона вычислений быстро покажет, насколько запретительно использовать неинформированный поиск в Go:

  • На шаге 1: 250
  • На шаге 2: 250² = 62500
  • На шаге 3: 250³ = 15 625 000
  • На шаге 4: 250⁴ = 3 906 250 000
  • На шаге 5: 250⁵ = 976 562 500 000
  • …
  • На шаге 10: 250¹⁰ = 953 674 316 406 250 000 000 000

После 10 шагов мы уже видим косметическое количество возможных состояний игры. Это также дает некоторое представление о том, почему победа над AlphaGo стала такой важной вехой для человечества.

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

Теперь мы понимаем, что нам нужно что-то умнее, чем неинформированный поиск, чтобы перемещаться по гигантскому пространству состояний, как в игре Go. MCTS - один из таких умных алгоритмов, который дает нам выход.

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

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

Выбор

На этом этапе мы используем политику дерева для построения пути от корня к наиболее многообещающему конечному узлу.

Листовой узел - это узел, у которого есть неисследованные дочерние узлы.

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

В алгоритме AlphaGo используется политика на основе UCB. Более конкретно, каждый узел имеет связанное значение UCB, и во время выбора мы всегда выбираем дочерний узел с наивысшим значением UCB.

Как мы видим, чем больше посещается узел i, тем ниже становится второй член в UCB, что снижает вероятность его повторного выбора. Следовательно, алгоритм UCB изначально имеет встроенное исследование и использование. Шикарно и аккуратно!

Для более подробного, но все же легкого для понимания отчета об исследовании и эксплуатации (включая UCB), пожалуйста, прочтите Блог Лилиан Венга по этой теме.

Наконец, на этапе выбора мы можем пройти по снежному покрову или исследуемой части дерева, пока не будет достигнут листовой узел.

Расширение

Помните, что в конце выбора мы достигаем листового узла?

На этапе раскрытия мы просто случайным образом выбираем неисследованный узел листового узла.

Моделирование (или развертывание)

На этом этапе мы запускаем одну или несколько симуляций с накоплением вознаграждения за каждую симуляцию. Политика развертывания обычно проста или даже случайна, поэтому ее можно быстро выполнить. Например, выигрыш может вызвать награду +1, ничья - 0, а проигрыш - -1.

Кто-то может спросить, а зачем?

В игре Го этот шаг подобен алгоритму, который мастер Го мог бы сделать в своей голове, играя много раз в игре, пока не закончится. Истинный гений видит не только будущее, но и множество его версий.

Резервное копирование

Мы провели много симуляций, что мы можем с ними сделать, чтобы определить лучший следующий ход?

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

Примечание. Мы не обновляем значения узлов на этапе развертывания! Это сделано потому, что нам нужно сосредоточиться на окрестности корневого узла (снежного покрова), на основе которого нам нужно принимать решения о следующем (ых) движении (ах). Принимая во внимание, что значения за пределами снежного покрова не имеют отношения к такому решению и не являются вычислительно эффективными для хранения и расчета.

Сложите это вместе

Псевдокод может выглядеть так:

def run(node, num_rollout):
    "one iteration of select->expand->simulation-> backup"
    path = select(node)
    leaf = path[-1]
    expand(leaf)
    reward = 0
    for i in range(num_rollout):
        reward += simulate(leaf)
    backup(path, reward)

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

Простой, но не более простой пример

(Код доступен по адресу: git repo)

Предположим, у нас есть двоичное дерево глубины 7, все его листовые узлы несут определенное вознаграждение от 0 до 100, полученное из равномерного распределения. Наша задача - найти наивысшее вознаграждение среди 2⁷ листовых узлов (небольшое примечание: используемые здесь листовые узлы имеют рудиментарное значение, то есть узлы в дереве без дочерних узлов, в отличие от MCTS, мы используем листовые узлы для обозначения узлов с неизученными. ребенок).

Читатель может проверить мое git repo и запустить find_max_leaf_binary_tree.py. Код удобно включает в себя несколько параметров:

  • numb_iter для изменения количества итераций MCTS
  • num_rollout для изменения количества развертываний во время моделирования
  • exploration_weight для контроля баланса между разведкой и эксплуатацией

Хватит играть!

Результаты по умолчанию показаны ниже:

Expected (max) leaf node: node@7_53, value: 99.16984625936269
Expected (min) leaf node: node@7_121, value: 1.2521064278136151
Found optimal (max) leaf node: node@7_104, value: 95.8546572417074

Не так уж и плохо, найденный оптимальный узел довольно близок к своему ожидаемому значению (обратите внимание, что вы можете не получить точный результат из-за его вероятностного характера).

Заключение

Многие проблемы искусственного интеллекта уходят корнями в проблемы поиска. В конце концов, жизнь - это поиск. Надеюсь, вы все найдете свой оптимальный путь :).