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

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

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

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

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

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

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

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