Общие сведения о выборе узла MCTS

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

Я имею в виду, что если мы используем, скажем, UCB для поиска лучшего узла для расширения, он всегда будет выбирать узел, который мы выбрали первым (учитывая, что он привел к выигрышу), полностью игнорируя все остальные, поскольку он будет единственным. ненулевое значение. Что мне здесь не хватает, поскольку это явно не так?


algorithm montecarlo
person Straightfw    schedule 24.01.2014    source источник

Ответы (1)


arrow_upward
8
arrow_downward

Каждый раз, когда вы находитесь в узле, вы расширяете узел в соответствии со следующими правилами:

  • если дочерний узел никогда ранее не расширялся, то расширяем один из неисследованных дочерних узлов случайным образом (и можно сразу отмотать от этого дочернего узла)
  • в противном случае каждый дочерний узел был посещен хотя бы один раз. Вычислите для всех них значение «исследование/эксплуатация» и разверните дочерний узел с наибольшим значением.

Идея MCTS заключается в максимизации разведки/эксплуатации. Если дочерний узел никогда ранее не исследовался, значение «исследования», связанное с ним, бесконечно, вам придется исследовать его. Однако, как только вы расширите все дочерние узлы, вы будете чаще расширять дочерние узлы с более высоким значением (это часть «эксплуатации»).

person B. Decoster    schedule 24.01.2014