Могу ли я использовать эвристику для получения результата на этапе воспроизведения в дереве поиска Монте-Карло?

Насколько я понимаю, цель этапа воспроизведения или моделирования в MCTS — получить результат и наградить или наказать узлы на пути от корня во время обратного распространения. (Пожалуйста, поправьте меня, если я ошибаюсь)

Мой вопрос заключается в том, могу ли я использовать эвристику знания предметной области, чтобы получить этот результат, вместо того, чтобы фактически моделировать игру до конца.

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


person Zhongjun 'Mark' Jin    schedule 26.07.2016    source источник


Ответы (2)


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

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

person Dennis Soemers    schedule 22.08.2016

Я на самом деле нашел этот документ "Планирование Монте-Карло для поиска пути в стратегии в реальном времени Игры". В качестве вознаграждения он использует обратное евклидову расстояние.

person Zhongjun 'Mark' Jin    schedule 30.09.2016