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

искусственный интеллект Программа перевода самородков алгоритм

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

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

Теория минимакса (minimax), предложенная фон Нейманом в 1928 году, проложила путь для состязательных методов поиска по дереву, которые стали основой теории принятия решений на заре информатики и искусственного интеллекта. Методы Монте-Карло решают задачи путем случайной выборки, а впоследствии, в 1940-х годах, как способ решения нечетко определенных задач, непригодных для прямого поиска по дереву. Реми Кулон объединил эти два метода в 2006 году, чтобы предоставить новый метод планирования ходов в Go, известный сегодня как поиск по дереву Монте-Карло (MCTS).

В последнее время, благодаря достижениям в компьютерном Go и его потенциалу для решения некоторых сложных проблем, интерес к MCTS в области научных исследований быстро возрос. Область его применения не ограничивается играми, и теоретически MCTS можно применить к любому{состояние, действие}Формально опишите область прогнозирования результатов с помощью моделирования.

Базовый алгоритм

Самый простой алгоритм MCTS сам по себе прост: построить дерево поиска с узлами, связанными в соответствии с результатами моделирования. Весь процесс можно разбить на следующие этапы:

1. Выберите

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

2. Расширение

Если L не является конечным узлом (то есть игра еще не закончена), то создайте один или несколько дочерних узлов и выберите один из C.

3. Моделирование

Выполните имитацию развертывания из C, пока не получите результат.

4. Обратное распространение

Обновите текущую последовательность движений с помощью смоделированных результатов.

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

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

Выбор узла

Игровой автомат и алгоритм UCB

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

вviэто оценка узла,niэто количество посещений узла иNэто общее количество посещений его родительского узла.Cявляется регулируемым параметром смещения.

Эксплуатационный против Исследовательского

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

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

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

UCT = MCTS + UCB

преимущество

MCTS имеет несколько приятных преимуществ перед традиционными методами поиска по дереву.

без контекста

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

Асимметричный рост дерева

MCTS демонстрирует асимметричный рост дерева для адаптации к топологии пространства поиска. Алгоритм посещает более «интересные» узлы и концентрирует пространство поиска на наиболее релевантных частях.

Это делает MCTS хорошо подходящим для игр с большим количеством влияющих факторов, таких как Go размером 19x19. Такие большие пространственные комбинации, как правило, делают проблематичными стандартные методы поиска в глубину или ширину, но адаптивный характер MCTS означает, что он (в конечном итоге) найдет эти лучшие движения (действия) и сосредоточит поиск на них.

выйти изящно

Алгоритм может прерваться в любой момент и вернуть текущую наилучшую политику оценки. Установленное дерево поиска можно отбросить или сохранить для повторного использования в будущем.

Простота использования

Алгоритм очень прост в реализации, см. туториал. (Примечание переводчика:pythonиjavaИсходный код и связанные с ним знания можно найти здесь)

недостаток

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

Сила игры

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

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

Метод подъема

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

конкретная область (знания)

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

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

Независимость от домена (метод подъема)

Метод улучшения, не зависящий от предметной области, имеет широкий спектр применений, это святой Грааль в исследованиях алгоритмов MCTS, а также направление, на которое сегодня нацелены многие исследования. Было предложено множество таких усовершенствований, которые соответствовали разным уровням успеха: от простых (игра и выигрышные ходы/избегание потенциально проигрышных ходов при развертывании) до сложных методов инициализации и выбора узлов и метастратегий.
можно просматриватьсписок повышенияДополнительные сведения об улучшениях MCTS см.

установленные темы исследований

MCTS по-прежнему является новой частью области исследований, и существует множество текущих тем для исследований.

Улучшение алгоритма

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

Автоматическая настройка параметров

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

Расширение узла

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

Надежность узла

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

анализ формы дерева

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

Программа перевода самородковэто сообщество, которое переводит высококачественные технические статьи из Интернета сНаггетсДелитесь статьями на английском языке на . Охват контентаAndroid,iOS,React,внешний интерфейс,задняя часть,продукт,дизайнЕсли вы хотите видеть более качественные переводы, пожалуйста, продолжайте обращать вниманиеПрограмма перевода самородков,официальный Вейбо,Знай колонку.

Категории