Какова концепция "Последний хороший ответ" и "Оценка стоимости быстрого действия" в симуляции Монте-Карло?
Я разработал простой шестнадцатеричный игрок на основе поиска дерева Монте-Карло для игры в Hex. Теперь я хочу расширить гекс-плеер, используя RAVE (Rapid Action Value Assessment) и LGP (последний хороший ответ). Статьи здесь и здесь.
Мне было интересно, если кто-нибудь здесь использовал какой-либо из этих методов для улучшения производительности поиска по дереву и может помочь мне понять это?
Я также хочу знать, почему эти алгоритмы называются эвристикой AMAF (All Moves As First)?
1 ответ
В области поиска дерева Монте-Карло в играх, в которых используется обучение с подкреплением, существует два типа обратного распространения: AMAF и UCT.
Метод UCT возвращает обратно путь, который во время фазы выбора он прошел. только узлы, которые во время отбора встречаются, распространяются назад точно в своих состояниях. Но в AMAF все узлы, которые встречаются во время фазы отката, сохраняются, а в фазе обратного распространения, наряду с узлами в пути выбора, распространяются назад без учета состояний.
UCT дает очень точное и локальное значение пары (состояние, действие), но оно слишком медленно, чтобы сходиться. с другой стороны, эвристика AMAF сходится очень быстро, но значение пары (состояние, действие) слишком общее и не может быть надежным.
Мы можем получить преимущества обеих стратегий, используя уменьшающийся коэффициент для таких значений:
a * UCT + (1 - a) * AMAF
Это эвристический RAVE(быстрое действие Value Stimation).
Last-Good-Reply основан на AMAF, но может выиграть от RAVE. его общая идея заключается в том, что в фазе воспроизведения, когда мы используем ходы против ходов противника, если эти ходы были успешными против действий противника, мы могли бы сохранить эти ходы и использовать их в следующих играх.