Как Монте-Карло Tree Search реализован на практике

Question

В определенной степени я понимаю, как работает алгоритм. То, что я не полностью понимаю, - то, как алгоритм фактически осуществлен на практике.

Мне интересно понять, какие оптимальные подходы были бы для довольно сложной игры (возможно, шахматы). т.е. рекурсивный подход? асинхронный? одновременно? параллельно? распределены? структуры данных и / или базы данных?

- Какой тип ограничений мы ожидаем увидеть на одной машине? (Можем ли мы работать одновременно на многих ядрах... может быть, GPU?)

- Если каждая ветвь приводит к совершенно новой игре, в которую играют (это может достигать миллионов), как мы сохраняем стабильность всей системы? И как мы можем повторно использовать уже сыгранные ветки?

Answer 1

рекурсивный подход? асинхронный? одновременно? параллельно? распределены? структуры данных и / или базы данных

• В MCTS нет особого смысла в рекурсивной реализации (что часто встречается в других алгоритмах поиска по дереву, например, в минимаксных), потому что вы всегда проходите игру последовательно в последовательности от текущего игрового состояния (корневого узла) до игровые состояния, которые вы выбираете для оценки (конечные игровые состояния, если только вы не решите использовать нестандартную реализацию, использующую ограничение глубины на этапе воспроизведения и эвристическую функцию оценки). Гораздо более очевидная реализация с использованием while петли просто отлично.
• Если вы впервые реализуете алгоритм, я бы рекомендовал сначала перейти на однопоточную реализацию. Это сравнительно простой алгоритм для распараллеливания, хотя есть несколько статей по этому вопросу. Вы можете просто запустить несколько симуляций (где симуляция = выделение + расширение + воспроизведение + обратное распространение) параллельно. Вы можете попытаться убедиться, что все обновляется корректно во время обратного распространения, но вы также можете просто решить вообще не использовать никаких блокировок / блокировок и т. Д., Во всяком случае, во всех симуляциях уже достаточно случайности, так что если вы потеряете информацию из пары симуляций кое-где из-за наивно реализованного распараллеливания это действительно не слишком больно.
• Что касается структур данных, в отличие от таких алгоритмов, как minimaxвам действительно нужно явно построить дерево и сохранить его в памяти (оно создается постепенно по мере выполнения алгоритма). Итак, вам понадобится общая древовидная структура данных с Nodes которые имеют список преемника / ребенка Nodes, а также указатель на родителя Node (требуется для обратного распространения результатов моделирования).

Какой тип ограничений мы ожидаем увидеть на одной машине? (Можем ли мы работать одновременно на многих ядрах... может быть, GPU?)

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

Если каждая ветвь приводит к совершенно новой игре, в которую играют (это может достигать миллионов), как мы можем поддерживать стабильность всей системы? И как мы можем повторно использовать уже сыгранные ветки?

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