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

Я пытаюсь реализовать алгоритм MCTS в игре. Я могу использовать только около 0,33 секунды на ход. За это время я могу сгенерировать одну или две игры для каждого дочернего элемента из начального состояния, которое содержит около 500 дочерних узлов. Мои симуляции не случайны, но, конечно, я не могу сделать правильный выбор на основе 1 или 2 симуляций. Дальше в игре дерево становится меньше, и я могу выбирать, исходя из большего количества симуляций.

Так что моя проблема в первых нескольких ходах. Есть ли способ улучшить алгоритм MCTS, чтобы он мог моделировать больше игр, или мне следует использовать другой алгоритм?


artificial-intelligence monte-carlo-tree-search
person Joaquin van Loon    schedule 01.09.2017    source источник
comment
что это за игра? около 500 дочерних узлов? разве вы не перестраиваете дерево с нуля после каждого хода? 1 или 2 выбора в дочерних узлах может быть достаточно, если узлы верхнего уровня, непосредственно следующие за корнем, имеют достаточно дочерних элементов и симуляций, таким образом. Должен ли я использовать другой алгоритм? очень сильно зависит от игры. MCTS плохо подходит для шахмат, но отлично подходит, например, для GO.   -  person Shihab Shahriar Khan    schedule 29.09.2017

Ответы (1)


arrow_upward
3
arrow_downward

Можно ли придумать какую-нибудь эвристическую функцию оценки состояний? Я понимаю, что одно из основных преимуществ MCTS заключается в том, что теоретически вам это не понадобится, НО: если вы все равно сможете создать несколько разумную функцию оценки, это позволит вам остановить симуляции раньше, прежде чем они достигнут конечного игрового состояния. . Затем вы можете создать резервную копию оценки такого нетерминального игрового состояния, а не просто выигрыша или проигрыша. Если вы остановите свои симуляции раньше, вы сможете запустить больше симуляций (поскольку каждая отдельная симуляция занимает меньше времени).

Кроме того, вы захотите попытаться найти способы «обобщения». Если вы запускаете одну симуляцию, вы должны попытаться посмотреть, сможете ли вы также извлечь некоторую полезную информацию из этой симуляции для других узлов дерева, через которые вы не прошли. Примерами усовершенствований, которые вы можете рассмотреть в этом духе, являются AMAF, RAVE, прогрессивная история, метод выбора N-грамм.

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

Чтобы узнать больше об этой последней идее, может быть интересно просмотреть некоторые материалы, которые я написал на моем агент на основе MCTS в General Video Game AI, который также является средой реального времени с очень ресурсоемкой игрой, что означает, что симуляции количество строго ограничено (но коэффициент ветвления намного меньше, чем кажется в вашем случае). Pdf-файлы моих публикаций по этому вопросу также доступны в Интернете.

person Dennis Soemers    schedule 22.11.2017