Количество симуляций на узел в поиске дерева Монте-Карло

Question

В алгоритме mcts, описанном в Википедии, он выполняет ровно одно воспроизведение (симуляцию) при каждом выборе узла. Сейчас я экспериментирую с этим алгоритмом в простой игре connect-k. Интересно, на практике, мы проводим больше игр, чтобы уменьшить дисперсию?

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

Затем я добавил эвристику AMAF (в частности, с переходом RAVE) к базовой MCTS. Я не замечаю слишком большой разницы с 500 играми, возможно, потому что дисперсия уже низкая. Я еще не проанализировал результат с 1 раздачей.

Кто-нибудь может дать мне какие-либо идеи?

Answer 1

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

Рассмотрим, например, случай, когда в корневом узле доступно только два хода. Если затем запустить, скажем, 10000 полных итераций MCTS (где одна итерация = Выбор + Расширение + Воспроизведение + Обратное распространение), каждый из двух узлов ниже корневого узла будет выбран примерно 5000 раз (или, возможно, один выбран 9000 раз, а остальные 1000 раз, если первый вариант явно лучше, чем seocnd, но, тем не менее, оба выбираются более одного раза).

Соответствует ли это тому, что вы в настоящее время делаете в своей реализации? Если нет, попробуйте предоставить какой-нибудь код, который у вас есть в данный момент, чтобы мы могли увидеть, где он идет не так. Но если вы реализовали это именно так (как и должно быть), тогда не должно быть проблем с выполнением только одного воспроизведения на шаг выбора.