Улучшения поиска по дереву Монте-Карло
Я пытаюсь реализовать алгоритм MCTS в игре. Я могу использовать только около 0,33 секунды за ход. За это время я могу сгенерировать одну или две игры для каждого ребенка из начального состояния, которое содержит около 500 дочерних узлов. Мои симуляции не случайны, но, конечно, я не могу сделать правильный выбор, основываясь на 1 или 2 симуляциях. Дальше в игре дерево становится меньше, и я могу сделать выбор, основываясь на большем количестве симуляций.
Так что моя проблема в первых нескольких ходах. Есть ли способ улучшить алгоритм MCTS, чтобы он мог имитировать больше игр, или я должен использовать другой алгоритм?
1 ответ
Можно ли придумать некоторую эвристическую функцию оценки для состояний? Я понимаю, что одним из основных преимуществ MCTS является то, что теоретически это вам не понадобится, НО: если вы все равно сможете создать несколько разумную функцию оценки, это позволит вам остановить симуляции на ранних стадиях до того, как они достигнут состояния конечной игры., Затем вы можете поддержать оценку такого нетерминального игрового состояния, а не просто выиграть или проиграть. Если вы остановите свои симуляции как можно раньше, вы сможете запустить больше симуляций (потому что каждая отдельная симуляция занимает меньше времени).
Кроме того, вы захотите найти способы "обобщить". Если вы запустите одно моделирование, вы должны попытаться выяснить, можете ли вы извлечь из этого моделирования некоторую полезную информацию для других узлов дерева, через которые вы не прошли. Примерами улучшений, которые вы можете рассмотреть в этом духе, являются AMAF, RAVE, Progressive History, техника выбора N-Gram.
Вы случайно не знаете, где узкое место для вашей работы? Вы можете исследовать это с помощью профилировщика. Если большая часть вашего времени обработки затрачивается на функции, связанные с игрой (генерация хода, переход из одного состояния в другое и т. Д.), Вы точно знаете, что вы будете ограничены в количестве симуляций, которые вы можете выполнять., Затем вы должны попытаться реализовать улучшения, которые делают каждое отдельное моделирование максимально информативным. Это может означать, например, использование действительно хороших, вычислительно дорогих функций оценки. Если сам код игры уже очень хорошо оптимизирован и быстр, перемещение дополнительного времени вычислений в такие вещи, как функции оценки, будет более вредным для вашего счета моделирования и, вероятно, окупится меньше.
Более подробно об этой последней идее может быть интересно взглянуть на некоторые вещи, которые я написал для своего агента на базе MCTS в General Video Game AI, который также представляет собой среду реального времени с очень дорогой в вычислительном отношении игрой, то есть симуляции количество жестко ограничено (но фактор ветвления намного меньше, чем кажется в вашем случае). PDF-файлы моих публикаций по этому вопросу также доступны в Интернете.