Поиск дерева Монте-Карло: политика дерева для игр двух игроков
Я немного запутался в том, как реализована "древовидная политика" MCTS. Каждая статья или статья, которую я читаю, говорит о том, как спуститься по дереву из текущего игрового состояния (в терминологии MCTS: корень для игрока, готового сделать ход). Мой вопрос заключается в том, как я выбираю лучшего ребенка, даже когда я нахожусь на уровне MIN (если я игрок MAX). Даже если я выберу какое-то конкретное действие, которое может предпринять MIN, и мое дерево поиска будет проходить глубже через этот узел, игрок MIN во время своего хода может также выбрать другой узел (если мин-игрок - человек-любитель, он может хорошо выбрать какой-то узел, который не обязательно является лучшим). Этот вид делает всю работу MAX по распространению через этот узел бесполезной, поскольку MIN выбрал другой узел. Для шагов, которые я имею в виду: https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/ где политика дерева: https://jeffbradberry.com/images/mcts_selection.png заставляет меня поверить, что они исполняют это с точки зрения одного игрока.
1 ответ
Чтобы реализовать MCTS для игры для двух игроков, вы можете просто перевернуть знак на каждом этапе обратного распространения, изменив код на одну строку.
Это означает, что мы пытаемся максимизировать награду на каждом уровне, но когда мы распространяем награду вверх по дереву, положительная награда для вашего оппонента становится отрицательной для вас, когда вы добираетесь до своего уровня.
Для MCTS вам нужен какой-то способ получения разумной оценки распределения вероятностей возможных ходов. Для AlphaGo [1] это вероятность быстрого развертывания, $p_\pi$ в статье, которая принимает состояние и выдает грубое распределение вероятностей по всем возможным ходам. Команда AlphaGo реализовала это в виде мелкой нейронной сети, которая сначала обучалась экспертным играм, а затем совершенствовалась, играя против себя.
[1] http://www.nature.com/nature/journal/v529/n7587/full/nature16961.html