Как работает «поиск Монте-Карло»?

16

Я слышал об этой концепции в посте Reddit об Alpha Go. Я попытался просмотреть статью и статью, но не смог понять смысл алгоритма.

Итак, может ли кто-нибудь дать понятное объяснение того, как работает алгоритм поиска Монте-Карло и как он используется при создании игровых ИИ-ботов?

Dawny33
источник
Хорошее описание алгоритма MCTS можно найти по адресу: https://towardsdatascience.com/monte-carlo-tree-search-in-reinforcement-learning-b97d3e743d0f .
nbro

Ответы:

13

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

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

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

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

Если вы хотите получить больше информации или взглянуть на некоторые иллюстрации, я нашел интересную статью на эту тему: C. Browne и др., Обзор методов поиска по дереву Монте-Карло ( открытый репозиторий / постоянная ссылка (paywalled) )

Расстроенный скрытник
источник
Таким образом, в основном то, что Монте-Карло делает в альфа, состоит в том, чтобы создавать долгосрочные стратегии, рассматривая различные комбинации ходов, а не наоборот (выберите стратегию и затем шаги для ее достижения)?
Диего Антонио Росарио Паломино
Там нет упоминания о ключевом элементе подхода Монте-Карло, который является стохастическим элементом, интегрированным в выбор доступных ходов для исследования. Не был упомянут и компромисс между точностью и точностью обработки. Это два наиболее важных аспекта, которые отсутствуют в ответе. Вместо этого было упомянуто «большое количество случайных значений или симуляций», когда меньшее число симуляций из псевдослучайных факторов (менее исчерпывающий поиск) характерно для сходимости Монте-Карло.
FauChristian