MCTS / UCT - это метод поиска по дереву игр, который использует алгоритм бандита для выбора перспективных узлов для исследования. Игры разыгрываются до их завершения случайным образом, и узлы, ведущие к большему количеству побед, исследуются более интенсивно. Алгоритм бандита поддерживает баланс между исследованием узлов с высокими показателями выигрыша и исследованием неизвестных узлов (и в чистом виде не обязательно использует эвристическую функцию оценки). Программы, основанные на этой общей технике, достигли довольно удивительных результатов в компьютерном Go .
Применялись ли бандитские поиски Монте-Карло к другим поисковым задачам? Например, будет ли это полезным подходом для аппроксимации решений MAX-SAT, BKP или других задач комбинаторной оптимизации? Существуют ли какие-либо конкретные характеристики проблемы (структурные / статистические / и т. Д.), Которые позволяют предположить, будет ли эффективен подход в стиле бандитов?
Существуют ли какие-либо известные детерминированные проблемы, которые были бы абсолютно устойчивыми к бандитским методам из-за природы пространства решений?