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

Question

Кто-нибудь может объяснить, как (поскольку я нигде не нашел четкого примера) алгоритм MCTS повторяется для второго игрока.

Все, что мне кажется, похоже на то, что оно играет, например, движение P1 каждый раз. Я понимаю шаги для одного агента, но я никогда не нахожу ничего, показывающего код, в котором P2 размещает свой счетчик, что обязательно должно произойти при выращивании дерева.

По сути я бы ожидал:

для каждого итератора:

выбрать узел Player1 развернуть Player1

выберите узел Player2 разверните player 2

развертывание backpropogate

следующий итер

Это правильно?? Кто-нибудь может, пожалуйста, объяснить какой-нибудь psuedocode, показывающий это? Либо итеративно, либо рекурсия, я не против.

Спасибо за любую помощь.

Answer 1

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

Код для MCTS

Обратите внимание на функцию UCT, особенно комментарии:

 #Backpropagate
    while node != None: # backpropagate from the expanded node and work back to the root node
        node.Update(state.GetResult(node.playerJustMoved)) # state is terminal. Update node with result from POV of node.playerJustMoved
        node = node.parentNode

Если вы будете следовать вызову функции, вы поймете, visit переменная всегда обновляется; wins однако нет.