1
$\begingroup$

The basic Monte-Carlo Tree Search algorithm uses the tree policy:

while v is nonterminal:
  if v is not fully expanded:
    expand v
  else:
    v = v.best_child

By always expanding a node as long as it is expandable a lot of time is consumed to explore the direct next move. When there are a large number of possible moves it can be time (and space) consuming to create nodes for all move candidates and if many of them may have similar outcome it would be preferable to descend in existing subtrees even when the node is not fully expanded yet.

The closest related method that I found is first-play urgency, but as far as I see it also creates the nodes for the actions and also only modifies the algorithm which children are selected to use more exploitation than exploration, but doesn't reduce the amount of move candidates that are created when inserting a node.

I thought about removing the check if the node is expandable and treating it like its children, but I think the UCT of a parent node doesn't get larger than the UCT of its best child because the values of the children are propagated to the parent and the visit count of the parent is always larger than the visit counts of the children, so the parent node would not be selected again later.

Should I try to find a modification for the UCT or are there other methods to allow for exploring subtrees of not fully expanded nodes while still allowing to further expand the parent node from time to time?

Another alternative would be to stochastically only generate a subset of all possible moves at the risk of missing out on a good move, so I would prefer to find a modification of UCT or the descend / expansion algorithms to revisit inner nodes that are still expandable.

Improve this question
$\endgroup$
3
  • $\begingroup$ When you need to expand a node, you just need to add all its children (with 0 visits). Then you select one of the children for rollout. Is this already a problem (to add all the children as nodes)? $\endgroup$
    – Oren
    Commented Jun 28, 2023 at 14:01
  • $\begingroup$ You can't do it with the standard UCT formula because $n_i$ is in the denominator. I also think it is there for a reason and the standard approach basically says that evaluating if an unexplored node leads to a good solution has infinite priority. The equivalent to what you're thinking of would probably be not adding a node and then you again need to make sure that the algorithm doesn't always descend in the tree to add the missing node. $\endgroup$
    – allo
    Commented Jun 30, 2023 at 9:27
  • $\begingroup$ I would add all children (with 0 visits) altogether. Then before testing for UCT I would check if any has 0 visits and choose from those. None with 0 visits? Then fall back to UCT. $\endgroup$
    – Oren
    Commented Jun 30, 2023 at 14:36

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .