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

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

Один цикл MCTS

1. Выбор: начать с исходной позиции и идти по существующим ветвям, уравновешивая ходы, уже выглядящие сильными, и варианты, которые остаются неопределёнными.
2. Расширение: добавить позицию или ход, которые дерево ещё не развивало.
3. Оценка: оценить результат из новой позиции. Классические методы могут завершать моделируемые партии, а современные системы способны использовать нейронную сеть, обученную модель распознавания шаблонов, для оценки позиции.
4. Обратное распространение: вернуть результат по пройденному пути и обновить число посещений и оценки.

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

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